| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > реализация алгоритма |
| Автор: boostcoder 9.11.2011, 09:56 |
| всем бодрого утра. итак. имеется протокол ввода-вывода. пакет состоит из заголовка фиксированного размера в котором содержится всякая инфа, размер тела данных, и, собственно, тело. в данный момент, чтение пакета происходит следующим образом: 1)читается заголовок, 2)из заголовка узнается объем тела, 3)читается тело. тут, мне не нравится то, что для чтения одного пакета приходится выполнять две операции чтения. а это довольно длинная цепь вызовов, в придачу, завершающаяся системным вызовом. пришла такая идея: сторона, которая запрашивает данные, не должна читать их напрямую из сокета. алгоритм: для каждого сокета выделяется буфер. для каждого буфера нужны два итератора: 1)итератор записи, 2)итератор чтения. сокет и буфер должны находится на одном уровне. условно, назовем этот уровень нижним. так же, у нас есть уровень, обращающийся к нижнему за данными. назовем его верхним уровнем. начальное состояние: сокет открыт. буфер пуст. чтения не происходит. итак. верхний уровень делает запрос к нижнему чтоб получить порцию данных. нижний уровень проверяет, имеется ли в буфере достаточно данных, и если да - верхнему уровню передается массив(пока не решил как, тупо копированием из буфера нижнего уровня в буфер верхнего, или путем передачи итератора(ов)). если это первое обращение за данными - выполняем запрос в сокет, и таким образом запускаем цикл пополнения буфера. тут, нужен контроль следующих условий: 1. итератор чтения не должен перегнать итератор записи. 2. итератор записи не должен перегнать итератор чтения. при такой реализации мы получаем следующую информацию основанную на позициях итераторов: 1. позиция итератора чтения нам говорит о том, сколько данных было прочтено. 2. дистанция от итератора чтения до итератора записи = объем доступных в буфере данных. 3. дистанция от итератора записи до итератора чтения = пространство доступное для записи. при создании операции асинхронного чтения, в качестве буфера передаем итератор записи, а объем определяем согласно пункту 3 предыдущего параграфа. операция асинхронного чтения читает из сокета все доступные данные, но не более чем было запрошено. в общем, это изложение мысли как есть, без проработки и связи. наверняка что-то не учел, не додумал.. собственно тема создана для того, чтоб выслушать мнение форумчан, и, возможно, выявить "узкие" места и недочеты. всем спасибо. |
| Автор: bsa 9.11.2011, 10:33 |
| Ты уверен, что именно на чтение сокета убивается большая часть ресурсов процессора? Что-то мне подсказывает, что это не так... Скажи, а как именно данные оправляются? Есть подозрение, что отправляются они так же, как принимаются - сначала заголовок, а затем тело. Таким образом, есть у меня подозрение, что сначала выполнится операция чтения, возвращающая только заголовок, а уже затем чтение тела, так как придут в разных пакетах... Или я не прав (в сетях я не большой гуру)? |
| Автор: boostcoder 9.11.2011, 10:48 | ||||
я бы не сказал что бОльшая..но порядочно. около 12 процентов.
не-не-не. отправка данных происходит за раз. с этим все нормально. |
| Автор: mabrarov 9.11.2011, 11:15 |
| Утра бодрого и Вам, boostcoder. http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/buffered_read_stream.html и http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/buffered_write_stream.html и, наконец, http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/buffered_stream.html. Это позволит сэкономить на обращениях к сокету. В принципе, Вы этого и хотели. Но я предпочитаю иной вариант, потому что каждый async-запрос к buffered_stream все равно выливается в копии handler и пр. мелочевку. Для примера возьму чтение (алгоритм для записи выводим как-то по аналогии). Итак, берем кольцевой буфер (ma::cyclic_buffer), размер которого >= максимальный размер сообщения (в идеале >>>). В каждой итерации пытаемся читать из сокета - (async_)read_some - столько, сколько есть/осталось свободного места в буфере. Отдельным объектом (class message_parser) парсим то, что считалось в буфер. При этом, на выходе message_parser::parse_some м/б [0..n] сообщений. message_parser есть КА и хранит текущее состояние парсинга с тем, чтобы при каждом последующем вызове не парсить всю последовательность с начала. Вообще в message_parser::parse_some каждый раз передаются только новые (вновь поступившие) данные (buffer_sequence или, точнее, ma::cyclic_buffer::const_buffers_type). Если message_parser::parse_some (худший случай) длительный, то его можно проводить параллельно, но это уже больше похоже на извращение. Чтение (async_read_some) всегда выполняется в фоне. Т.е. сначала начинаем следующую итерацию чтения (start_async_read_some), а уже потом вызываем message_parser::parse_some. Поэтому, если уж message_parser::parse_some длительный, то эффективнее будет async_read_some + http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/null_buffers.html + неблокирующий режим. Такой режим, между прочим, считается последним спасением при высоких нагрузках и IOCP - видел англоязычную запись в каком-то блоге, посвященном IOCP и высоким нагрузкам (до сих пор найти не могу - может кто подскажет?). Еще такой момент - все, что прошло через message_parser::parse_some, может 1. считаться "свободным", т.е. освобождается в кольцевом буфере под запись новых данных (ma::cyclic_buffer::commit) или 2. message_parser::parse_some может дополнительно сообщать, сколько байт от начала переданной ему buffer_sequence можно считать "проглоченными парсером", т.е. "свободными". Если не устраивает кольцевой буфер, то можно взять обычный. Но тогда в случае [2] (см. выше) нужно предусмотреть shift - сдвиг распарсенных, но не извлеченных из буфера данных в начало буфера с тем, чтобы обеспечить ненулевой свободный остаток в конце буфера. Можно делать сдвиг не всегда, а только в тех случаях, когда "свободный остаток в конце буфера" < threshold (я так и делал когда-то). Все вышеописанное есть тот же самый buffered_stream, но с выделением логики парсинга из логики чтения. "100-пудов" это всем было известно и без меня. Но захотелось заодно и обсудить. P.S. http://asio-samples.svn.sourceforge.net/viewvc/asio-samples/trunk/include/ma/cyclic_buffer.hpp?revision=467&view=markup. |
| Автор: newbee 9.11.2011, 11:20 |
| ОП прочла по диагонали, по-моему ты слишком усложняешь. Скорее всего цпу забивает процесс разбора пакета, а не чтения из сокета. Но даже если так, можно сделать много проще, ведь скорость обмена данными у тебя очень велика. Читаешь из сокета большой (в идеале заведомо больший, чем возможная максимальная длина пакета*) кусок данных, натравливаешь на него парсер. Опять читаешь буфер, продолжаешь парсить, и т.д. Процесс можно пустить в два потока: один парсит имеющийся буфер, другой читает следующий буфер. Если парсер будет сильно не успевать за читалкой, можно сделать пул парсеров. *под пакетом я имею в виду твой фрейм поверх IP/UDP/TCP/etc. |
| Автор: mabrarov 9.11.2011, 11:27 | ||
"Если что" (если я непонятно выразился), я имел в виду то же самое. У Вас получилось описать это проще  |
| Автор: newbee 9.11.2011, 11:29 |
| mabrarov, когда я начинала писать, твоего сообщения еще не было. Так что это не плагиат |
| Автор: mabrarov 9.11.2011, 11:30 | ||
Да какой уж тут плагиат. Не "алгоритм Дейкстры" же. Просто у меня получилось запутанно. Вдруг кого смутит. |
| Автор: baldina 9.11.2011, 11:40 | ||
те 12 процентов видимо из-за системного вызова, а не разбора заголовка. тем не менее буферизация и параллельная работа с буфером мне кажется более удачной идеей чем прыжки с сокетами и итераторами |
| Автор: mabrarov 9.11.2011, 11:51 | ||
То, что описал boostcoder, и еcть буферизация. Тот же самый asio::buffered_stream. |
| Автор: boostcoder 9.11.2011, 12:07 | ||||||
нельзя читать больше, чем доступно для чтения без блокировки. иначе есть риск того, что я не смогу обработать первый пришедший пакет из-за того, что мы попросили прочитать 200 пакетов.
это тоже есть. и от этого не избавится. я же хочу избавится от одного асинхронного чтения, что, по предсказанию профайлера, подарит мне более 12 процентов освободившихся ресурсов.
угу. и из-за всего предшествующего. т.е. байндеры, io_service, new/delete, и т.д. про asio::buffered_stream никогда не читал. почему-то... в общем, сейчас "переварю" мысли/идеи.... |
| Автор: mabrarov 9.11.2011, 12:24 | ||
У Вас async_read_some или async_read? async ли вообще? Потому что async-операции вполне позволяют Вам разбирать то, что уже пришло, параллельно чтению. |
| Автор: boostcoder 9.11.2011, 12:59 | ||
async_read() дело в том, что разбирать я начинаю в хендлере. а хендлер вызовется только тогда, когда будет прочитано указанное кол-во байт. т.е. к примеру мы указываем прочитать 200 байт, а в сокете есть только 100. так вот эти 100 я не могу обработать, потому что не вызывается хендлер. тут наверное правильней использовать async_read_some()... значит нужно менять архитектуру. Добавлено @ 13:04 почитал я http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/buffered_stream.html(если можно это назвать чтением)... в доке, вообще нет никакого описания поведения или принципа работы. ни каким образом получает данные, ни кто такой http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/buffered_stream/buffered_stream.html  полез в исходники. |
| Автор: bsa 9.11.2011, 13:23 | ||
Я давно заметил, что Asio отличается особой полнотой и глубиной описания... Не то что всякие Qt... |
| Автор: mabrarov 9.11.2011, 13:46 | ||||||
Вот именно эта часть вообще недокументированна. Вроде бы раньше это были служебные (внутренние для Asio) классы. Сам все хочу почитать их исходники, но никак не сделаю это последовательно и целиком. Arg - это параметр для конструктора lower_layer. В случае, если lower_layer есть asio::ip::tcp::socket, то Arg - это asio::io_service&. Тут все аналогично http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/ssl__stream.html. Это вообще общая техника для оберток в Asio. Добавлено @ 13:55
Естественно. У Qt есть коммерческая версия + Trolltech/Nokia. Там есть кому писать и что платить "писателям". Ну напишете наконец Chris-у совместную "петицию" с указанием, что непонятно и где дописать/уточнить/поправить. В рассылке по Asio пока не было такого письма. В одной "российской" компании на Y мне (asio samples) сказали: "А чего там писать? И так все понятно - проще некуда". И в Qt встречаются плохо документированные места. Попадалось использование !QObject raw pointer без объяснения, кто будет владеть ресурсом и кто будет его удалять/освобождать. Добавлено @ 13:58
Можно попробовать asio::async_read + http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/transfer_at_least.html. В той же компании Y не используют asio::async_xxx (мне так сказали - сам не проверял ) - только async_xxx_some. Видимо, они работают с таймаутами так же, как echo_server из asio samples - когда идет таймаут не на передачу n-го кол-ва данных, а таймаут на "активность". Т.е. если принят всего один байт, но он уложился в таймаут, то все ok - продолжаем держать соединение. |
| Автор: boostcoder 9.11.2011, 14:07 | ||||
да, уже разобрался. все просто.
тут нужно начать с написания теста по предыдущей реализации, и задуманной. этим и займусь. и да, если с докой что-то не так, всегда можно исходники почитать. ну, на крайняк, самому написать доку и отослать автору патч. не думаю что он сильно расстроится. |
| Автор: mabrarov 9.11.2011, 14:20 | ||
Я бы на его месте поленился тащить такую ношу (+ несколько платформ) в одиночку да еще и бесплатно. Видимо, он что-то имеет с консультаций. Вроде что-то проскакивало про Австралию и custom-solution для гос/научного учреждения... Вот посмотрите на ACE. Сколько гос-бабла туда вбухали США? И как Вам документация (я уж молчу про код и что про него мне сказали в Y). |
| Автор: boostcoder 9.11.2011, 14:26 | ||
дока ужасная, какой всегда и была, сколько я ее помню. |
| Автор: boostcoder 16.4.2012, 07:16 |
| вот только на один момент никто(?) не обратил внимания: используя asio::buffered_stream мы избавляемся от длиной цепочки вызовов и одного сискола, но взамен добавляем операцию копирования из asio::buffered_stream в передаваемый буфер. а это не малое копирование. это копирование всего трафика. как считаете, будет ли такая оптимизация оправданна? |
| Автор: mabrarov 16.4.2012, 11:25 | ||||
А разве могло быть иначе?
Я думал, что на http://forum.vingrad.ru/index.php?showtopic=341403&view=findpost&p=2423719 и последующих ответах тема себя исчерпала. Это почти стандартный подход:
|
| Автор: boostcoder 16.4.2012, 13:03 | ||
я тоже так думал. но как дошел до реализации, одумался |
| Автор: mabrarov 16.4.2012, 13:25 | ||
Почему? Реализация описанного выше (буфер, чтение, парсер на КА, логика на КА) получается слишком запутанной? Или Вы написали это про asio::buffered_stream? IMHO: asio::buffered_stream не стоит тянуть в свои проекты. "Чтение с запасом + парсер-КА" универсальнее. |
| Автор: boostcoder 16.4.2012, 18:56 | ||||||
и это тоже. но основное - копирование всего трафа. но, как я понимаю, по другому быть не может. это я, хочу странного =) КА мне тоже по идее не нужны. по сети будут передаваться массивы бинарного сериализатора. т.е. при прочтении, массив передается десериализатору.
по Вашему мнению, почему?
объясните плиз более развернуто, для чего тут КА и кем является "парсер"? |
| Автор: mabrarov 16.4.2012, 20:16 | ||||||||
Это возможно, когда десериализация не требует ничего кроме копирования. Тогда по заголовку сообщения можно сразу выделять буфер нужного размера и тогда же не удастся сэкономить на обращениях к сокету.
У нас наметилось явное недопонимание: парсер == десериализатор.
Потому что это лишнее, если Ваш десериализатор умеет парсить данные из буфера приема и может продолжать парсить частично полученные сообщения. Обработка того же протокола заголовок-с-размером-тела+тело - есть простейший парсер/десериализатор.. в книжках по ACE эту часть называют... эээ... frame protocol, что ли. |
| Автор: boostcoder 17.4.2012, 02:40 | ||||
что-то я совсем запутался %) сначала я запрашиваю у сокета прочитать заголовок. из него я узнаю размер тела. и делаю еще один запрос на чтение тела. это сейчас так. и тут у нас проблема с двумя цепочками вызовов для получения одного пакета. если решать эту проблему с помощью буферизированного сокета - логика остается та же. но разница в том, что для прочтения тела не всегда будет производится сискол аж на уровень сокета, ибо тело может быть уже в буфере. таким образом, мы сэкономим на сисколе, но вся цепь вызовов до него все равно будет выполняться. к тому же, то, что я описал в топике, не предполагало копирование всего трафа, ибо там я предполагал передавать итераторы. как-то так:
|
| Автор: boostcoder 17.4.2012, 03:11 |
| я думаю скопипастить реализацию asio::buffered_read_stream и переделать ее для работы с итераторами... Добавлено через 3 минуты и 34 секунды проблему неизвестного максимального размера буфера, я думаю, можно решить дополнительным буфером, который будет создаваться если запрошен размер превышающий максимальный размер дефолтного буфера. большинство пакетов имеют размер до 20ти байт. |
