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

[Akon]

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

[once_again_abc]

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

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

[Igors]

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

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

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

[once_again_abc]

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

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

Лучше рассматривать "с точки зрения взаимодействия" - ну или "возможных локов". Здесь четко виден один общий буфер

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

[Igors]

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

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

[once_again_abc]

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

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

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

[Igors]

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

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

[Akon]

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

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

[once_again_abc]

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

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

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

[once_again_abc]

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

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

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

[once_again_abc]

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

[once_again_abc]

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

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

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

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

[ssoft]

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

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

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

[once_again_abc]

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

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

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

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

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

[Igors]

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

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

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

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

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

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