Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
High-performance single-producer/single-consumer FIFO 10.06.08 06:06
Автор: void <Grebnev Valery> Статус: Elderman
|
Задача:
Данные синхронно принимаются producer-ом, модифицируются, и передаются для асинхронной обработки consumer. Средняя частота потока данных относительно невелика, 5000-10000 элементов в секунду. Из-за неравномерности, число данных в единицу времени может быть значительно больше для меньших интервалов, ~30-60 элементов в 1 ms. Допускается “оverrun” consumer – когда producer перезаписывает данные новыми значениями, если consumer не успевает их обрабатывать. Consumer latency (~100-500 ms) не имеет большого значения. Нужен FIFO для регистрации и мониторинга “spikes” данных producer (~30-100 данных в 1 ms и выше).
Что посоветуете для Windows XP/Vista/W2008?
Спасибо.
|
|
BerkeleyDB ? 10.06.08 12:40
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 10.06.08 12:41 Количество правок: 2
|
Это очень мощная встраиваемая БД.
Её не так давно купил Oracle, и ИМХО там только поддержка платная,
а использовать можно без ограничений. С исходниками. Официально
поддерживается для различных С компиляторов, для VS есть тоже.
Можно закомпилить в DLL, а можно статически как в твоего продюсера,
так и в консамера.
Создаётся на диске объект DB, при создании указывается,
что метод доступа к ней будет DB_QUEUE. Эта очередь может держать максимум
до 2^32 записей, так что поводов для беспокойства вроде нет. Далее,
продюсер толкает записи (BerkeleyDB хранит двоичные данные практически любого размера, но как по "полям" их разберёт софта это проблема софта, а для BDB по барабану) при помощи метода DB->put с флагом DB_APPEND.
Консумер открывает эту же DB, и использует метод DB->get с флагом
DB_CONSUME_WAIT. The DB_CONSUME_WAIT flag is the same as the DB_CONSUME flag, except that if the Queue database is empty, the thread of control will wait until there is data in the queue before returning.
В общем, очень мощная штуковина.
BerkeleyDB
|
| |
Поразительно! Класс! 16.06.08 04:56
Автор: void <Grebnev Valery> Статус: Elderman
|
Поразительно! Класс!
Результаты тестирования BerkeleyDB DB_QUEUE оказываются лучше на ~7% (по скорости) по сравнению с обычной FIFO с использованием std::queue на однопроцессорной машине. И это при том!, что данные на диске! Видимо там "вылизано" всё...
Немного хуже оказываются другие параметры:
- число переключений потоков producer/comsumer ~180/180 против 75/105 для FIFO<std::queue>
- загрузка kernel mode CPU ~15% против %5 для FIFO<std::queue>
Для многопроцессорной машины не тестировал. Надеюсь, что в BerkeleyDB нет яных багов относительно синхронизации потоков для нескольких CPU. Так что должно работать отлично.
В целом, впечатление приятное. Producer может легко обрабатывать ~5 запрсов в 1 ms. И это классно для большого круга задач! На большей скорости не пробовал. Думаю, что поведение будет аналогичным queue - не будет работать для 30-60 запросов в 1 ms.
Также есть небольшие баги (например, deadlock-и в случае, если get выполнить из того же потока producer), но это мелочи.
|
| | |
Да, супер! 18.06.08 08:43
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 18.06.08 09:36 Количество правок: 3
|
> Результаты тестирования BerkeleyDB DB_QUEUE оказываются
> лучше на ~7% (по скорости) по сравнению с обычной FIFO с
> использованием std::queue на однопроцессорной машине. И это
> при том!, что данные на диске! Видимо там "вылизано"
> всё...
Да, и не нужно забывать, что вылизано не только для разных потоков, но и в принципе, не важно, если продюсер и консумер будут в разных процессах. А «данные на диске» — я уже говорил, что оно там всё меммапится, и винда асинхронно скидывает страницы, доколе BDB конкретно не скажет ей сделать flash. Ну и поскольку мем-маппед, то и все процессы видят всё синхронно.
> Для многопроцессорной машины не тестировал. Надеюсь, что в
> BerkeleyDB нет яных багов относительно синхронизации
> потоков для нескольких CPU. Так что должно работать
> отлично.
Использует объекты синхронизации там, где это надо. Причём, те, которые доступны и максимально эффективны для данной платформы. Короче, долго и печально её оттачивали в основном на nix'ах, там (раньше было, по крайней мере) с объектами синхронизации множество подводных камней и гимора для разных платформ, и они в конце концов пришли к пуленепробиваемости ;-)
> Также есть небольшие баги (например, deadlock-и в случае,
> если get выполнить из того же потока producer), но это
> мелочи.
У BDB есть прекрасный механизм блокировок и их резольвинга, читай доки. Т.е. минимально BDB сама может резольвить их, а максимально — твой отдельный поток может получать информацию о взаимных блокировках и их резольвить как тебе надо.
И ещё — BDB не реентерабельна, это тоже нужно аккуратно учитывать ;-) Т.е. нельзя вызывать функции BDB из колбяк, поведение становится непредсказуемым, или вызывай, пожалуйста, только через другие free-freaded handles.
Ну и, кроме скорости, ещё есть журналирование и транзакции, for sophisticated robust applications, как ты любишь выражаться по-ангельскому ;-)
|
| | |
На счет std::queue 16.06.08 12:31
Автор: PS <PS> Статус: Elderman
|
std::queue проигрывает std::vector (в реализации microsoft, 2003) чуть ли не в полтора раза. Во всяком случае у меня получился именно такой результат.
Поэтому выигрыш 7% Bdb, по сравнению с std::queue скорей всего будет нивелирован заменой queue на vector.
> Поразительно! Класс!
>
> Результаты тестирования BerkeleyDB DB_QUEUE оказываются
> лучше на ~7% (по скорости) по сравнению с обычной FIFO с
> использованием std::queue на однопроцессорной машине. И это
> при том!, что данные на диске! Видимо там "вылизано"
> всё...
>
> Немного хуже оказываются другие параметры:
> - число переключений потоков producer/comsumer ~180/180
> против 75/105 для FIFO<std::queue>
> - загрузка kernel mode CPU ~15% против %5 для
> FIFO<std::queue>
> Для многопроцессорной машины не тестировал. Надеюсь, что в
> BerkeleyDB нет яных багов относительно синхронизации
> потоков для нескольких CPU. Так что должно работать
> отлично.
>
> В целом, впечатление приятное. Producer может легко
> обрабатывать ~5 запрсов в 1 ms. И это классно для большого
> круга задач! На большей скорости не пробовал. Думаю, что
> поведение будет аналогичным queue - не будет работать для
> 30-60 запросов в 1 ms.
>
> Также есть небольшие баги (например, deadlock-и в случае,
> если get выполнить из того же потока producer), но это
> мелочи.
|
| | | |
Маленькое замечание 17.06.08 11:52
Автор: amirul <Serge> Статус: The Elderman
|
> std::queue проигрывает std::vector (в реализации microsoft,
> 2003) чуть ли не в полтора раза. Во всяком случае у меня
> получился именно такой результат.
> Поэтому выигрыш 7% Bdb, по сравнению с std::queue скорей
> всего будет нивелирован заменой queue на vector.
В случае FIFO, лучше использовать std::deque. Хранение в памяти практически такое же как у вектора (и все преимущества и недостатки в производительности будут для вектора и дека идентичными), но при этом O(const+) доступ с обоих концов, а не только с "заднего" (back) - а это именно то, что нужно для FIFO
|
| | | |
You didn’t get a point. We are not talking about performance... 16.06.08 18:15
Автор: void <Grebnev Valery> Статус: Elderman
|
> std::queue проигрывает std::vector (в реализации microsoft,
> 2003) чуть ли не в полтора раза. Во всяком случае у меня
> получился именно такой результат.
> Поэтому выигрыш 7% Bdb, по сравнению с std::queue скорей
> всего будет нивелирован заменой queue на vector.
You didn’t get a point. We are not talking about performance of std::queue or std::vector in general what might be senseless by definition, but performance of a FIFO storage for the single-producer/single-consumer pattern which may be designed and implemented using <queue>, or <vector>, or stack/queue of cyclic buffers /queues and so on. Also, we are talking about quite simple and transparent solutions.
|
| | | | |
Да, видимо я действительно didn't get a point 16.06.08 18:57
Автор: PS <PS> Статус: Elderman
|
>Результаты тестирования BerkeleyDB DB_QUEUE оказываются лучше на ~7% (по скорости) по >сравнению с обычной FIFO с использованием std::queue на однопроцессорной машине.
Видимо я отстал от жизни и приведенная мной выше твоя фраза - это никак не talking about performance of std::queue.
Кстати, любой перформанс зависит в большей части от имплиментейшен, чем от дизайне.
Паттерт, же, напритив - понятие исключительно дизайна. Поэтому твоя фраза "performance of a FIFO
storage for the single-producer/single-consumer pattern which may be designed and implemented using <queue> or <vector>, or stack/queue of cyclic buffers /queues and so on." - мне абсолютно не компрендре.
"Also, we are talking about quite simple and transparent solutions." - обычно это прямая противоположность перформансу :)
Быстро, качественно и дешево - можно выбрать только два критерия.
Мой ответ тебе, на счет вектора, что бы теперь ты гет а поинт, должен был быть понят тобой так:
Попробовать заметить одну имлементацию FIFO, постороенную на queue, на другую имплементацию, построенную на vector. И сравнить последний результат с имплементацией на Bdb.
Возможно (!) перформанс окажется лучше.
А что тебе дальше делать с твоим треугольником - решать только тебе.
> > std::queue проигрывает std::vector (в реализации
> microsoft,
> > 2003) чуть ли не в полтора раза. Во всяком случае у
> меня
> > получился именно такой результат.
> > Поэтому выигрыш 7% Bdb, по сравнению с std::queue
> скорей
> > всего будет нивелирован заменой queue на vector.
> You didn’t get a point. We are not talking about
> performance of std::queue or std::vector in general what
> might be senseless by definition, but performance of a FIFO
> storage for the single-producer/single-consumer pattern
> which may be designed and implemented using <queue>,
> or <vector>, or stack/queue of cyclic buffers /queues
> and so on. Also, we are talking about quite simple and
> transparent solutions.
|
| | | | | |
didn't get a point 16.06.08 19:37
Автор: void <Grebnev Valery> Статус: Elderman
|
|
It is obvious that the performance will be the same. Stack/queue of buffers (based on <vector>, <queue>, array) will give the better results. Even the double buffer (in the FIFO storage) will be better. Should I explain to you why?
|
| | | | | | |
Извини, но ты нарушаешь семантику языка. 17.06.08 10:39
Автор: PS <PS> Статус: Elderman
Отредактировано 17.06.08 10:41 Количество правок: 1
|
Что в русском, что в английском языке слово "лучше" подразумевает указание на что-то. У тебя в предложениях этого нет. "will give the better results" - than что ?
Если ты собираешся объяснять свои утверждения с теми же нарушениями правил языка, то можешь не утруждаться.
> It is obvious that the performance will be the same.
> Stack/queue of buffers (based on <vector>,
> <queue>, array) will give the better results. Even
> the double buffer (in the FIFO storage) will be better.
> Should I explain to you why?
|
| |
Спасибо за совет. 11.06.08 03:44
Автор: void <Grebnev Valery> Статус: Elderman
|
Спасибо за совет.
Скачал. Разбираюсь. Интересно протестировать производительность.
|
| | |
Не за что, на здоровье -) Кстати, она может не только очереди делать, но и BTree, и Hash словари, так что если надо ещё и сортировать — попробуй, может и с сортировкой справится… 12.06.08 07:16
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 12.06.08 07:17 Количество правок: 1
|
|
|
| |
Нет. Там после BDB2.0 лицензия позволяет бесплатно... 10.06.08 15:15
Автор: amirul <Serge> Статус: The Elderman
|
> Это очень мощная встраиваемая БД.
>
> Её не так давно купил Oracle, и ИМХО там только поддержка
> платная,
> а использовать можно без ограничений. С исходниками.
Нет. Там после BDB2.0 лицензия позволяет бесплатно использовать только в open source продуктах. Для иных способов использования нужно отдельно договариваться с ораклом.
http://www.oracle.com/technology/software/products/berkeley-db/htdocs/licensing.html
> Создаётся на диске объект DB, при создании указывается,
> что метод доступа к ней будет DB_QUEUE. Эта очередь может
> держать максимум
> до 2^32 записей, так что поводов для беспокойства вроде
> нет. Далее,
10к элементов. А стоит ли вообще заморачиваться с диском?
> В общем, очень мощная штуковина.
Ага. Сейчас еще и BDB XML с XQilla-ой. И все опенсорс - красота.
|
| | |
Консумер делает достаточно простую работу: 11.06.08 03:31
Автор: void <Grebnev Valery> Статус: Elderman
|
> 10к элементов. А стоит ли вообще заморачиваться с диском?
Консумер делает достаточно простую работу:
если число елементов (или их суммарные характеристики) за 1ms превышают лимиты, то косумер складывает эту саммари вместе со списком элементов в "бин". Бин добавляется в буфер. Когда буфер заполнен, IO-тред так или иначе должен записать это в файл. Может BDB - это как раз то, что надо. Надо пробовать.
В принципе, ты прав про "... > 10к элементов. А стоит ли вообще заморачиваться с диском?". Вопрос был в том, чтобы FIFO работала быстро при нагрузке > 100 елементов в 1 ms.
|
| | | |
BDB могёт in-memory, в доках всё написано. Да и с файлом работая, он его mem-mapид, так что попробуй. 12.06.08 07:10
Автор: HandleX <Александр М.> Статус: The Elderman
|
|
|
| | | | |
Попробовал (тестировал db_hash/db_btree). для небольших (по... 05.08.08 07:08
Автор: void <Grebnev Valery> Статус: Elderman
|
|
Попробовал (тестировал DB_HASH/DB_BTREE). Для небольших (по кол-ву записей) контейнеров - in-memory не даёт каких либо преимуществ. Всё и так кэшировано в памяти. Гораздо больший вклад в ботелнек - политика блокировок (по-странично/по-записи/всю базу целиком), которая разная для queue и hash/btree и для курсоров (если курсоры используются, что я бы теперь не рекомендовал).
|
|
Думаю, лучшее решение тебе подскажет здесь: http://rsdn.ru... 10.06.08 09:34
Автор: IgorR <Igor Razin> Статус: Member
|
> Что посоветуете для Windows XP/Vista/W2008?
Думаю, лучшее решение тебе подскажет здесь: http://rsdn.ru товарищ remark, большой специалист по данным вопросам.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
