Russian Qt Forum

есть некий генератор массивного потока данных (примерно 8МБ/сек.).
программа считывает эти данные из сети. необходимо сделать следующее:

1. записать _все_ полученные данные (с несложной предварительной обработкой) на диск;
2. обработать актуальные данные несколькими разными способами для разного графического представления в реальном времени (т.е. пришли данные - фильтры - отображение актуальной информации и т.д.).

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

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

Вопрос многопоточности стоит? Или у вас всё будет однопоточно?

По идее задачка интересная, только нет моментов - какие фильтры, какие данные, какая обработка. (я и при 115200 скорости могу на пять минут обработку сделать ;) )

По-моему здесь простейшая схема: одна нитка читает и помещает новые задачи в контейнер. N др ниток извлекают задачи из контейнера. Помещение/извлечение защищены локом - вся любовь

ничего особенного. спектральный анализ на FFT, усреднение, простые алгебраические операции над массивом float. т.е. не на 5 минут =) ну может быть миллисекунд 50 на 4х ядерном в несколько потоков. вообще я думаю это неважно для данной задачи... 50 мс. или 5 минут.

что имеется ввиду под задачами и контейнером?

Что приём новых данных идёт в буфер (контейнер). Если контейнер переполняется, она его чистит. Это первая нитка.
Вторая нитка берёт из буфера даные и обрабатывает. Результат скидывает куда - то ;)

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

Эммм... Чистить - это и есть сброс в файл/поток обработки/память/другой контейнер.
И потребитель данных - один. Это поток обработки.

Можно вообще пойти по пути упрощения - обновлять информацию на графике раз в 200-300 мс. Человеческий глаз не заметит разницы, зато в разы уменьшается время на обработку и прочая.

данные идут неприрывно со скоростью 8 МБ/сек. что делать с данными, которые пришли во время сброса заполненного буфера в файл? копировать в другой буфер? тогда это и есть кусочный кольцевой буфер...

оффтоп: 200-300 мс. на графике очень хорошо заметно по дерганьям картинки =) идеально для меня 20 мс. есть к чему стремиться =)

Сбрасывать можно спокойно и в отдельном потоке ;) А то, что пришло в тот момент опять таки будет попадать в буфер.
Долго можно филосовствовать. С таким подходом вам нужно 3-4 буфера.
1 - приём
2 - данные на обработку
3 - данные для сброса в файл
4 - ?

4. Профит!!!!111

 ;D

буду експерементировать.

Единый кольцевой буфер на всех потребителей. Голова для всех потребителей одна, хвост у каждого свой. Ячейка в буфере помечается свободной, когда обработана всеми потребителями. Размер буфера выбирается исходя из того, чтобы не допустить потерю записи в файл. Отрисовка данных может быть реальным тормозом, поскольку выполняется из GUI потока, поэтому необходимая порция самых свежих данных копируется из буфера.

FFT (да и практически любая обработка) требует фиксированного кол-ва точек сигнала. Поэтому возникает единица (chunk) данных. Читающий должен прочитать N измерений в буфер. Когда все N прочитаны этот буфер помещается в контейнер буферов. А с контейнером уже как хотите так и крутите - сливаете в файл, рисуете, пропускаете куски и.т.п.

У разных потребителей разные чанки.

Входные - одни и те же. А как потребитель их использует (или во что конвертирует) = его личное дело

Я и имел ввиду, именно, входные. Например, файл пишется чанками по 10 МБ, а FFT обрабатывает 100 КБ.

изначально я это и реализовал. к сожалению через несколько часов (примерно через 5-10 в зависимости от фазы луны и гравитационных аномалий) накапливающаяся задержка приводик к buffer overrun. поэтому сейчас я переделываю так, чтобы у файлового манагера был свой буфер, у графического движка свой. тогда каждый будет обрабатываться по своему и проблема исчезнет.

Лучше рассматривать "с точки зрения взаимодействия" - ну или "возможных локов". Здесь четко виден один общий буфер (фрагментов). А с точки зрения каждого потребителя может быть всяко-разно. Напр он может скопировать данные в свой локальный буфер и установить для каких-то фрагментов флажок "принято". Или он может работать напрямую - в любом случае это дело потребителя, схема взаимодействие остается той же

у меня lock-free кольцевой буфер на атомарных счетчиках, блокировки занимают слишком много времени по сранению с ними.

Для простоты допустим емкость кольцевого буфера всего 10 точек, как Вы возьмете для отрисовки напр 5 последних?

последние относительно чего?

последних пришедших/считанных

А из-за чего задержка?

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

десктоп ОС не ОС реального времени. особенно такая как виндовс.

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

и это очень просто реализовать. пара строчек простого кода. надо лишь придерживаться двух правил: 1. писатель гарантирует, что никогда ни при каких условиях не будет использовать блок занятый читателем и 2. читатель гарантирует, что никогда не при каких условиях не будет впереди писателя.

Что-то похожее я давненько реализовывал.  :-\
Все выкрутасы с общим буфером у блокировками между писателями и читателями оказались для меня тормозными.
В конце концов пришел к схеме с разными буферами.

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

Так у меня работает быстрее.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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