Oberon space
General Category => Общий раздел => Тема начата: Губанов Сергей Юрьевич от Декабрь 25, 2014, 12:44:28 pm
-
Приятно писать парсер который сам запрашивает следующий символ когда ему это становится нужно...
У меня сейчас задача "обратная", неприятная. Мой парсер сам запрашивать следующий символ не может, а, наоборот, символы в него будут впихивать, а парсер должен как "автомат" помнить своё состояние.
Как это сделать наиболее оптимально?
Самому парсеру запрашивать следующий символ нельзя так как следующего символа ещё может не быть. Символы прилетают из сети толстым многогигабитным потоком. Символы немножко буферировать можно, но без перекопирований. А именно, можно задержать ненадолго немного IP пакетов. Данные из IP пакетов читать можно, но перекопировать их в отдельный буфер нельзя - поток очень многогигабитный и на лишнее перекопирование не хватит скорости контроллера памяти.
-
Сразу вспомнилась так называемая SWITCH технология в автоматном программировании, которую продвигает Шалыто А.А. в Питерском УНИВЕРСИТЕТе ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ. Там события(приход символа к примеру) передаются автомату для обработки, а сам автомат события не запрашивает.
-
Всплыло ещё в памяти презентация или доклад Р.Пайка по Go и сопрограммам , на примера как раз парсинга или чего-то подобного. Там парсер в точках, где запрашивает новый символ, получает его через канал из другой сопрограммы. Тут уже в отличии от SWITCH-техн. парсер "постоянно" активен.
-
Да, сопрограммы.
Когда-то очень давно пришлось писать BIOS на ассемблере.
Вывод на экран (посимвольный) должен был отрабатывать ESC-последовательности. Автоматная реализация крайне не наглядна.
Реализовано было с помощью сопрограммы, очень эффективно и очень наглядно. Текст программы - практически описание протокола.
-
если продолжать про сопрограммы, то справедливее, конечно, вспомнить не Пайка, а Мелвина Конвея и его статью, где он помимо прочего привел пример практического опыта создания компилятора с кобола с применением сопрограмм.
-
символы в него будут впихивать
ээээ, извиняюсь, кто куда и как будет впихивать?
-
ээээ, извиняюсь, кто куда и как будет впихивать?
Например, сборщик TCP отдаёт данные в HTML декодер, то есть данные толкаются из нижнего уровня в верхний. А в "обычном" парсере было бы наоборот, верхним уровнем данные запрашивались бы у нижнего уровня.
-
Что-то типа ленивого парсера получается. Комбинаторы парсеров в помощь (Haskell'ная библиотека Parsec)...
-
ээээ, извиняюсь, кто куда и как будет впихивать?
Например, сборщик TCP отдаёт данные в HTML декодер, то есть данные толкаются из нижнего уровня в верхний. А в "обычном" парсере было бы наоборот, верхним уровнем данные запрашивались бы у нижнего уровня.
Какая-то странная архитектура. Почему HTML декодер не может "спрашивать" у сборщика TCP необходимое количество через заданного размера буфер?
Надеюсь, эта ссылка поможет: buffering in standard streams (http://www.pixelbeat.org/programming/stdio_buffering/)
-
Какая-то странная архитектура. Почему HTML декодер не может "спрашивать" у сборщика TCP необходимое количество через заданного размера буфер?
Я пояснил это в первом сообщении. Запрашивать новые символы не может потому что их ещё нет. Они ещё не приехали. Да и буфера (в обычном смысле) тоже не может быть из-за строжайшего запрета на лишнее перекопирование (контроллер памяти не справится). Вместо буфера возможен небольшой список IP пакетов.
---
Да, кстати, я немного не то написал в прошлый раз, не HTML, а конечно же HTTP.
---
Сейчас обдумываю "классический" парсер у которого пространство символов дополнено одним специальным символом под названием СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН. Работает такой парсер как обычно сам запрашивая следующий символ. В один прекрасный момент он в ответ на свой запрос получает от сканера символ под названием СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН. Тогда парсер должен запомнить своё текущее состояние и вернуть управление. Когда будет получен очередной IP пакет управление вновь будет передано парсеру и т.д.
-
Не придётся ли всё равно перейти к варианту парсера-автомата который будет обрабатывать одно событие (один символ) за один вызов, ведь символ "СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН" может быть обнаружен в произвольном месте "классического " парсера ?
-
Ну, вероятно, будет некая комбинация того и другого. Пока следующий символ доступен должен бы работать метод рекурсивного спуска. Надо только придумать как запоминать состояние. Хотя, конечно, гибрид ужа с ежом пугает.
-
А какие язык/ОС?
-
Linux, C++
-
Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.
-
Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.
Там конкретно может представлять интерес PicoHTTPParser.
PicoHTTPParser now has a chunked-encoding decoder (http://blog.kazuhooku.com/2014/12/picohttpparser-now-has-chunked-encoding.html)
Ну и со слайдов (http://www.slideshare.net/kazuho/h2o-20141103pptx?ref=http://blog.kazuhooku.com/search/label/in%20English) можно узнать много полезного, чтобы не наступить на те же грабли. К примеру, на 32-й странице написано с примером кода:
never write a character-level state machine if performance matters
-
Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O (http://blog.kazuhooku.com/search/label/H2O) , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.
Спасибо.
Посмотрел его код: https://github.com/h2o/picohttpparser/blob/master/picohttpparser.c
Он сначала копирует данные в накопительный буфер, потом парсит обычным stateless парсером.
Мне копировать данные нельзя - не хватит пропускной способности контроллера памяти. Да и сильно накапливать данные мне тоже нельзя - не хватит объёма памяти.
-
Пока сделал следующим способом. Те L7 протоколы которые мне сейчас надо парсить объединяет то, что они текстово-построчные: каждый параметр в новой строке.
Чтобы их парсить "со скоростью света" удобно было бы
1) уметь видеть начало строки (10-20 букв) в виде непрерывного массива (для того чтобы распознать ключевое слово);
2) уметь быстро пропустить текущую строку (если параметр не интересует);
3) уметь считывать значение интересующего параметра.
Данные лежат в списке IP пакетов (в списке буферов). Распознавание организовано как следующий цикл:
1) В начале цикла запрашивается указатель char* на первые несколько букв новой строки (для определённости пусть будет 20 букв). Если до конца текущего IP пакета ещё много места (больше 20 букв), то просто возвращается указатель на текущую позицию (это быстро, за счёт этого peek работает со скоростью света). Если до конца текущего пакета осталось совсем немного (меньше 20 букв), но есть ещё один IP пакет, то несколько оставшихся букв из первого IP пакета и несколько первых букв из второго IP пакета копируются в отдельный 20-буквенный буфер и возвращается указатель на него. Это тоже довольно быстро, ведь надо скопировать всего 20 байт да и то, только на границе IP пакетов. Если пакеты большие, то это случается редко. На всякий случай предусмотрел возможно мёржить в такой буфер до 4 IP пакетов (вдруг будут пакеты по пять байтов :) ). Если до конца текущего IP пакета осталось меньше 20 букв, а следующего IP пакета ещё нет (и, возможно, не будет), то пытаемся отыскать символ конца строки '\n' в оставшемся хвосте. Это тоже довольно быстро делается. Если нашли '\n' значит возвращаем указатель на строку и говорим что размер у неё такой-то (меньший 20 байт). На всякий случай предусмотрел возможность искать конец строки в нескольких IP пакетах (до 4 штук).
2) Получив указатель char* на первые 20 букв (или меньше если найден конец строки) определяю что там за ключевое слово написано, если оно мне не интересно, то парсер переводится в состояние "пропустить текущую строку".
3) Если ключевое слово интересно, то парсер переводится в состояние чтения значения после ключевого слова.
То есть состояний у парсера получилось совсем немного...
-
На ДРАКОН-схеме алгоритм было бы проще понять.
Ещё надо учесть и IPv6.
-
Для таких случаев я запускаю разборщик в параллельном потоке. Он продвигается по рекурсивному спуску по мере поступления данных из главного потока. Для обмена данными я использую POSIX pipe(fd): в основном потоке - write(fd[1]), в параллельном - read(fd[0]).
-
Для таких случаев я запускаю разборщик в параллельном потоке. Он продвигается по рекурсивному спуску по мере поступления данных из главного потока. Для обмена данными я использую POSIX pipe(fd): в основном потоке - write(fd[1]), в параллельном - read(fd[0]).
Очень красивое решение. Жаль не подходит для моего случая (потребуется одновременно более ста миллионов потоков).
-
А такой вариант пробовали?
Выделяется довольно большой кольцевой буфер. Единым куском памяти.
Туда с начала и почти до конца (как придётся) пишутся данные из сети. В TCP/IP размер пакета может меняться, поэтому заранее предугадать или задать его нельзя. Или не желательно. Поэтому, очередной пакет пишется туда, где окончился предыдущий пакет. Когда в буфере заканчивается место или размер остатка будет делать работу сети не эффективной, то переходить к началу буфера.
Для обработки буфера будет использоваться два курсора. Первый отмечает позицию, следующую сразу за последней распознанной лексемой, а второй указывает на текущий обрабатываемый символ. У первого курсора два назначения: с одной стороны он не даёт перезаписать ещё не обработанные данные, а с другой - указывает, откуда следует начать повторный разбор лексемы, если потребуется.
-
Выделяется довольно большой кольцевой буфер. Единым куском памяти. Туда с начала и почти до конца (как придётся) пишутся данные из сети.
Мне так нельзя по двум причинам:
1) Мне нельзя копировать данные (трафик запредельно огромный). То есть нет никаких собственных буферов для данных. Я работаю с указателями на области памяти куда сетевые пакеты кладутся чисто аппаратно самим сетевым контроллером.
2) Даже если бы в природе существовал гипер контроллер памяти, который мог бы копировать данные со сверхсветовой скоростью, то таких больших кольцевых буферов мне пришлось бы завести более ста миллионов штук одновременно (столько одновременных потоков данных).
-
это же классическая задача поставщика-потребителя!
И вот как она решается на Активном Обероне:
MODULE BoundedBuffers;
TYPE
Item* = OBJECT;
Buffer* = OBJECT
VAR
h, n: INTEGER;
B: ARRAY * OF Item;
PROCEDURE Get*(): Item;
VAR x: Item;
BEGIN {EXCLUSIVE}
AWAIT(n # 0); (* буфер не пуст *)
x := B[h]; h := (h+1) MOD LEN(B); DEC(n);
RETURN x
END Get;
PROCEDURE Put*(x: Item);
BEGIN {EXCLUSIVE}
AWAIT(n # LEN(B)); (* буфер не полон *)
B[(h+n) MOD LEN(B)] := x; INC(n)
END Put;
PROCEDURE &Init(max: INTEGER);
BEGIN (* инициализатор *)
NEW(B, max); h := 0; n := 0
END Init;
END Buffer;
END BoundedBuffers.
-
Это решение аналогично моему. И у него та же проблема: Put - аппаратный. Его осуществляет сетевая карта. И поэтому, на операцию записи в буфер налагаются аппаратные и, возможно, ОС-ные ограничения. Операция записи не достаточно гибка, чтобы последовательно записывать данные в один и тот же буфер по кругу. Возможно, частично это можно решить, вмешавшись в работу ОС (управление памятью и драйвер сетевой карты), но я сомневаюсь, что сама сетевая карта будет способна писать данные по любому смещению в памяти. Поэтому, для того, чтобы воспользоваться такой очередью, потребуется копировать данные из исходного буфера в дополнительный, а Сергей хочет этого избежать.
-
...
Пример не об очереди, а о многопоточности и синхронизации
-
это же классическая задача поставщика-потребителя!
"Никто ни хрена не понимает за пределами своих собственных работ." (http://vteninn.livejournal.com/15528.html)
-
Приматический интеллект = комбинаторный интеллект
http://vteninn.livejournal.com/8263.html
Любопытно. Это у info21 утащили или он утащил. Или это такая всеобщая догадка? Типа тренд...?
Я вообще уже долгое время над этим размышляю. И все больше убеждаюсь, что человеки практически ничего не делают окромя этого самого "доставания бананов".
То, что там info21 задвигал про второй умотип интересно, но мутно.
Гораздо убедительнее идея, что все человеки тупые как бревна. Даже эти ваши эйнштейны с фенманами.
Вот читал у кого-то мол мозг это тупо популяция клеток, которые могут эволюционировать (скорее приспосабливаться) более эффективно (без нужды дохнуть мильёнами) чем обычные. Ну т.е. там где раньше мульон годов требовался, тепереча достаточно часа... и т.д. и т.п. в том же духе. Кажется довольно правдоподобным. И получается типа бошка - это такой эволюционный котелок, в котором путем комбинирования и отбора выращиваются конкретные мемы, которые посредством социума вовлекаются в другие комбинаторные процессы и т.д.
И как бы нет никакой умности в итоге. Этот ваш эйнштейн нихера бы не добился родившись в окружении других мемов.
Индивидуальные физиологические различия конечно влияют на способность к конкретной умственной деятельности, но это лишь случайное стечение обстоятельств... (мемы + способности)
И вот думается, что мозг - это просто эффективная платформа для эволюции мемов. Основной механизм тот же, что и в дарвиновской эволюции. Просто скорость процесса выше на несколько порядков.
-
Во я тупой. Тык это он и есть. (судя по другим текстам)
-
Во я тупой. Тык это он и есть. (судя по другим текстам)
Так профиль вот куда ведёт: http://www.inr.ac.ru/~ftkachov/vteninn/