Russian Qt Forum
Ноябрь 23, 2024, 05:04 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Задачка на производительность
Страниц: 1 2 [3]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Задачка на производительность  (Прочитано 22729 раз)
ssoft
Гость
« Ответ #30 : Февраль 27, 2012, 13:44 »
Цитата: once_again_abc от Февраль 27, 2012,  10:06
схема с разными буферами подразумевает лишнее копирование, что при больших объемах данных однозначно дает бОльшую потерю производительности чем использование одного - общего буфера.
в зависимости от того, как должны вести себя данные при заполнении буфера, возможно сделать полностью асинхронное lock-free чтение/запись на аппаратно-атомарных счетчиках.
один из примеров легко находится в википедии http://en.wikipedia.org/wiki/Producer-consumer_problem, секция Without semaphores or monitors
Быстрее такого подхода ничего нет. Я в это фанатично верю  Смеющийся

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

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

Реализация через атомарные операции "подвешивает" компьютер даже при отсутствии данных, разве это гуд ? Остальные то процессы не жалуются ?
Записан
once_again_abc
Гость
« Ответ #31 : Февраль 27, 2012, 13:53 »
Цитата: Igors от Февраль 27, 2012,  11:58
Цитата: once_again_abc от Февраль 27, 2012,  03:47
достаточно определить что данные однородные и пишуться/читаются одинаковыми кусками. для указания на хвост и голову буфера использовать атомарные указатели, если при записи обнаруживается, что голова должна перекрыть хвост, то занятый под чтение блок перепрыгивается и для записи используется следующий. в свою очередь хвост никогда сам не выйдет вперед головы =) никаких блокировок и простое считывание N блоков в любой точке. что касается самых свежих точек, то, зная что данные однородны и имея указатель на голову, можно одним простым движением скопировать самый свежий блок данных.
Мне кажется можно сделать проще, без прыжков и столь же lock-free

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

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

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

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

это мягко говоря не самый оптимальный способ быстрого асинхронного чтения/записи данных.
и не понятно зачем молотить нули на диск если это не нужно =)
Записан
once_again_abc
Гость
« Ответ #32 : Февраль 27, 2012, 13:59 »
Цитата: ssoft от Февраль 27, 2012,  13:44

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

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


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

Сообщений: 11445


Просмотр профиля
« Ответ #33 : Февраль 27, 2012, 14:20 »
Цитата: once_again_abc от Февраль 27, 2012,  13:53
это мягко говоря не самый оптимальный способ быстрого асинхронного чтения/записи данных.
и не понятно зачем молотить нули на диск если это не нужно =)
Что же в нем не оптимального? Улыбающийся Данные в 1 экземпляре, потребители могут копировать в свой локальный буфер или использовать напрямую - как хотят. Блокировок - можно и ни одной. А у Вас?

Цитата: once_again_abc от Февраль 27, 2012,  13:53
..если при записи обнаруживается, что голова должна перекрыть хвост, то занятый под чтение блок перепрыгивается и для записи используется следующий.
Если "занятый под чтение" то выплывает (неприятный) лок. Напр (псевдокод)
Код
C++ (Qt)
if (BlockInUse(blockNomer))   // блок занят читателем?
 blockNomer = (blockNomer + 1) % blockCount;  
// пишем в блок blockNomer 
 
Так не годится

Цитата: ssoft от Февраль 27, 2012,  07:53
Один поток читает данные и отправляет через очередь сообщений потребителям.
Каждый потребитель находится в своем потоке, собирает данные, формирует свой буфер и следит за ним, обрабатывает данные - отображает или записывает.
"через очередь сообщений" - жить проще, но производительности не выжать. Если буфера потребителей shared - то приходим к той же схеме
Записан
ssoft
Гость
« Ответ #34 : Февраль 28, 2012, 10:14 »
"через очередь сообщений" - жить проще, но производительности не выжать. Если буфера потребителей shared - то приходим к той же схеме
[/quote]

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

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

Конкретно в этом случае я бы выбрал более простой вариант реализации.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #35 : Февраль 28, 2012, 10:34 »
Цитата: ssoft от Февраль 28, 2012,  10:14
Нужно ли выжимать максимально возможную производительность программы, за счет ее усложнения и потери производительности ОС?
Откуда возникла легенда о потери производительности ОС на атомарных операциях - теряюсь в догадках  Улыбающийся

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

Кстати автор темы (увлеченный lock-free) пока не упомянул - а что же с синхронизацией? Если нет новых данных, что должны делать рабочие нитки (пишущая в файл и рисующая)? Каким образом их усыплять и будить если данные появились? 
Записан
once_again_abc
Гость
« Ответ #36 : Февраль 29, 2012, 07:14 »
Цитата: Igors от Февраль 28, 2012,  10:34
Кстати автор темы (увлеченный lock-free) пока не упомянул - а что же с синхронизацией? Если нет новых данных, что должны делать рабочие нитки (пишущая в файл и рисующая)? Каким образом их усыплять и будить если данные появились?  

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


ПС. использование LIFO/FIFO в виде списков очень популярно для решения задач типа lock-free и wait-free. а мне больше нравится почему-то цельный кольцевой буфер =)
« Последнее редактирование: Февраль 29, 2012, 07:33 от once_again_abc » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #37 : Февраль 29, 2012, 11:00 »
Цитата: once_again_abc от Февраль 29, 2012,  07:14
наличие или отсутствие нговых данных проблемой не было. нет данных - нечего писать/отрисовывать - можно поспать.
В смысле sleep? Чего ж тогда делать изысканный lock-free если потом "грязные ноги на стол"?  Улыбающийся

Цитата: once_again_abc от Февраль 29, 2012,  07:14
ПС. использование LIFO/FIFO в виде списков очень популярно для решения задач типа lock-free и wait-free. а мне больше нравится почему-то цельный кольцевой буфер =)
Та можно и кольцевой, только надо отрабатывать ситуацию когда писатель затирает данные чтения. В любом случае сценарий примерно одинаков

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

Важно что для обоих очень небольшая часть кода выполняется под локом. Напр читателю достаточно просто узнать "с какого блока по какой" новые данные, использовать их он может и без лока
« Последнее редактирование: Февраль 29, 2012, 11:09 от Igors » Записан
once_again_abc
Гость
« Ответ #38 : Февраль 29, 2012, 11:04 »
Цитата: Igors от Февраль 29, 2012,  11:00
Цитата: once_again_abc от Февраль 29, 2012,  07:14
наличие или отсутствие нговых данных проблемой не было. нет данных - нечего писать/отрисовывать - можно поспать.
В смысле sleep? Чего ж тогда делать изысканный lock-free если потом "грязные ноги на стол"?  Улыбающийся



у меня слип не использовался. отрисовка и сохранения в файл были медленнее чем прием данных (непрерывный). слип воткнул на всякий случай =) вообще же слип это конечно категорически неправильно...
Записан
ssoft
Гость
« Ответ #39 : Март 01, 2012, 17:22 »
Цитировать
Откуда возникла легенда о потери производительности ОС на атомарных операциях - теряюсь в догадках  Улыбающийся
Если мы для реализации буфера обмена используем только атомарные операции, без дополнительных примочек аля semaphor, mutex, sleep, то это приводит к загрузке ЦП даже при отсутствии данных.
Так что имеется в виду не потеря производительности ОС как таковой, а постоянная загрузка ЦП. Подмигивающий
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #40 : Март 01, 2012, 18:09 »
Цитата: ssoft от Март 01, 2012,  17:22
Если мы для реализации буфера обмена используем только атомарные операции, без дополнительных примочек аля semaphor, mutex, sleep, то это приводит к загрузке ЦП даже при отсутствии данных.
Так что имеется в виду не потеря производительности ОС как таковой, а постоянная загрузка ЦП. Подмигивающий
Если имеется ввиду напр while пока атомарная переменная не изменится - то это также лок, только атомарный (unfair). Да, это может загрузить проц по самые помидоры. Но здесь об этом речи нет. Если Вы о чем-то другом - поясните
Записан
Страниц: 1 2 [3]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.079 секунд. Запросов: 22.