Задачка на производительность

[ssoft]

схема с разными буферами подразумевает лишнее копирование, что при больших объемах данных однозначно дает бОльшую потерю производительности чем использование одного - общего буфера.
в зависимости от того, как должны вести себя данные при заполнении буфера, возможно сделать полностью асинхронное lock-free чтение/запись на аппаратно-атомарных счетчиках.
один из примеров легко находится в википедии http://en.wikipedia.org/wiki/Producer-consumer_problem, секция Without semaphores or monitors
Быстрее такого подхода ничего нет. Я в это фанатично верю  

ПС. поскольку у меня писатель дожен писать всегда и безусловно, то я вообще реализовал все на основе всего лишь одной атомарной переменной.

Никакого копирования данных, в качестве порции данных я использовал QByteArray, в котором реализован умный подсчет ссылок и данные без лишней надобности не копировались.
Для простой записи на диск копирования не происходит, а для обработки FFT или другой все равно нужно собирать данные в некоторую кучу.

Реализация через атомарные операции "подвешивает" компьютер даже при отсутствии данных, разве это гуд ? Остальные то процессы не жалуются ?

[once_again_abc]

достаточно определить что данные однородные и пишуться/читаются одинаковыми кусками. для указания на хвост и голову буфера использовать атомарные указатели, если при записи обнаруживается, что голова должна перекрыть хвост, то занятый под чтение блок перепрыгивается и для записи используется следующий. в свою очередь хвост никогда сам не выйдет вперед головы =) никаких блокировок и простое считывание N блоков в любой точке. что касается самых свежих точек, то, зная что данные однородны и имея указатель на голову, можно одним простым движением скопировать самый свежий блок данных.

Мне кажется можно сделать проще, без прыжков и столь же lock-free

- список блокоа, писатель линкует новые блоки в голову. Единственное ограничение для писателя - число блоков (или их общий размер в байтах) превысило заданный порог

- потребитель знает "свой" блок данных и маркирует его готовым если данные больше не нужны, затем берет новый блок продвигаясь от хвоста к голове. Если прибыло много новых блоков, потребитель может маркировать 2 и более и взять последний. Хвост подсекается когда маркирован всеми потребителями

В принципе это можно делать с любым контейнером, при нормальном размере блока блокировки не страшны. Если хочется lock-free то просто свой двухсвязный список + атомарный счетчик блоков (хотя вероятно и QLinkedList подойдет).

При таком подходе размер блока может меняться динамически. Напр пропал входной сигнал - можно спокойно пропустить это время, а не молотить нули на диск.

это мягко говоря не самый оптимальный способ быстрого асинхронного чтения/записи данных.
и не понятно зачем молотить нули на диск если это не нужно =)

[once_again_abc]

Никакого копирования данных, в качестве порции данных я использовал QByteArray, в котором реализован умный подсчет ссылок и данные без лишней надобности не копировались.
Для простой записи на диск копирования не происходит, а для обработки FFT или другой все равно нужно собирать данные в некоторую кучу.

Реализация через атомарные операции "подвешивает" компьютер даже при отсутствии данных, разве это гуд ? Остальные то процессы не жалуются ?

или я что-то не так понял или одно из двух =)
если сравнить затраты на QByteArray и две-три аппаратно-атомарные инструкции типа cmpxchg то я думаю никто не станет спорить с тем, что второе _значительно_ быстрее и _значительно_ менее накладно для железа и системы =)

[Igors]

это мягко говоря не самый оптимальный способ быстрого асинхронного чтения/записи данных.
и не понятно зачем молотить нули на диск если это не нужно =)

Что же в нем не оптимального? Данные в 1 экземпляре, потребители могут копировать в свой локальный буфер или использовать напрямую - как хотят. Блокировок - можно и ни одной. А у Вас?

..если при записи обнаруживается, что голова должна перекрыть хвост, то занятый под чтение блок перепрыгивается и для записи используется следующий.

Если "занятый под чтение" то выплывает (неприятный) лок. Напр (псевдокод)

Код

C++ (Qt)
if (BlockInUse(blockNomer))   // блок занят читателем?
 blockNomer = (blockNomer + 1) % blockCount;  
// пишем в блок blockNomer 
 

Так не годится

Один поток читает данные и отправляет через очередь сообщений потребителям.
Каждый потребитель находится в своем потоке, собирает данные, формирует свой буфер и следит за ним, обрабатывает данные - отображает или записывает.

"через очередь сообщений" - жить проще, но производительности не выжать. Если буфера потребителей shared - то приходим к той же схеме

[ssoft]

"через очередь сообщений" - жить проще, но производительности не выжать. Если буфера потребителей shared - то приходим к той же схеме
[/quote]

Нужно ли выжимать максимально возможную производительность программы, за счет ее усложнения и потери производительности ОС?

[/quote]
есть некий генератор массивного потока данных (примерно 8МБ/сек.).
[/quote]

Конкретно в этом случае я бы выбрал более простой вариант реализации.

[Igors]

Нужно ли выжимать максимально возможную производительность программы, за счет ее усложнения и потери производительности ОС?

Откуда возникла легенда о потери производительности ОС на атомарных операциях - теряюсь в догадках 

Конкретно в этом случае я бы выбрал более простой вариант реализации.

Я однозначно за простоту - но чем Ваш вариант "проще"? Используя событийную схему Вы упрощаете чтение данных но получаете возню с shared указателями. Логика "я сделал и оно РАБОТАЕТ!!!" всем понятна, но рассмотреть др возможности тоже интересно.

Кстати автор темы (увлеченный lock-free) пока не упомянул - а что же с синхронизацией? Если нет новых данных, что должны делать рабочие нитки (пишущая в файл и рисующая)? Каким образом их усыплять и будить если данные появились? 

[once_again_abc]

Кстати автор темы (увлеченный lock-free) пока не упомянул - а что же с синхронизацией? Если нет новых данных, что должны делать рабочие нитки (пишущая в файл и рисующая)? Каким образом их усыплять и будить если данные появились?  

первоначально я пошел по самому простому и очевидному пути и реализовал кольцевой буфер на атомарных операциях без блокировок. что-то подобное http://en.wikipedia.org/wiki/Producer-consumer_problem. проблем с синхронизацией не было т.к. потребители сами решали когда и что делать, а наличие или отсутствие нговых данных проблемой не было. нет данных - нечего писать/отрисовывать - можно поспать. в качестве быстрого и более-менее рабочего варианта достаточно.
от lock-free я сейчас отказался. нет времени сделать правильный алгоритм для нужного функционала. так что буду делать лишь бы работало с удовлетворительной скоростью и надежно. использую критическую секцию на пару producer-consumer + семафор для спячки если нет данных для потребителя.


ПС. использование LIFO/FIFO в виде списков очень популярно для решения задач типа lock-free и wait-free. а мне больше нравится почему-то цельный кольцевой буфер =)

[Igors]

наличие или отсутствие нговых данных проблемой не было. нет данных - нечего писать/отрисовывать - можно поспать.

В смысле sleep? Чего ж тогда делать изысканный lock-free если потом "грязные ноги на стол"?  

ПС. использование LIFO/FIFO в виде списков очень популярно для решения задач типа lock-free и wait-free. а мне больше нравится почему-то цельный кольцевой буфер =)

Та можно и кольцевой, только надо отрабатывать ситуацию когда писатель затирает данные чтения. В любом случае сценарий примерно одинаков

- писатель: захватил лок, добавил в буфер новый кусок, освободил лок, отсигналил  семафор(ы) читателей
- читатель(и): проснулся по семафору, захватил лок, посмотрел новые блоки, освободил лок, занялся своими делами

Важно что для обоих очень небольшая часть кода выполняется под локом. Напр читателю достаточно просто узнать "с какого блока по какой" новые данные, использовать их он может и без лока

[once_again_abc]

наличие или отсутствие нговых данных проблемой не было. нет данных - нечего писать/отрисовывать - можно поспать.

В смысле sleep? Чего ж тогда делать изысканный lock-free если потом "грязные ноги на стол"? 

у меня слип не использовался. отрисовка и сохранения в файл были медленнее чем прием данных (непрерывный). слип воткнул на всякий случай =) вообще же слип это конечно категорически неправильно...

[ssoft]

Откуда возникла легенда о потери производительности ОС на атомарных операциях - теряюсь в догадках 

Если мы для реализации буфера обмена используем только атомарные операции, без дополнительных примочек аля semaphor, mutex, sleep, то это приводит к загрузке ЦП даже при отсутствии данных.
Так что имеется в виду не потеря производительности ОС как таковой, а постоянная загрузка ЦП.

[Igors]

Если мы для реализации буфера обмена используем только атомарные операции, без дополнительных примочек аля semaphor, mutex, sleep, то это приводит к загрузке ЦП даже при отсутствии данных.
Так что имеется в виду не потеря производительности ОС как таковой, а постоянная загрузка ЦП.

Если имеется ввиду напр while пока атомарная переменная не изменится - то это также лок, только атомарный (unfair). Да, это может загрузить проц по самые помидоры. Но здесь об этом речи нет. Если Вы о чем-то другом - поясните