Парсер многогигабитных потоков данных

[Губанов Сергей Юрьевич]

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

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

Как это сделать наиболее оптимально?

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

[albobin]

Сразу вспомнилась так называемая SWITCH технология в автоматном программировании, которую продвигает Шалыто А.А. в Питерском УНИВЕРСИТЕТе ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ. Там события(приход символа к примеру) передаются автомату для обработки, а сам автомат события не запрашивает.

[albobin]

Всплыло ещё в памяти презентация или доклад Р.Пайка по Go и сопрограммам , на примера как раз парсинга или чего-то подобного.  Там  парсер в точках, где  запрашивает новый символ, получает его через канал из другой сопрограммы.  Тут уже в отличии от SWITCH-техн. парсер "постоянно" активен.

[Peter Almazov]

Да, сопрограммы.
Когда-то очень давно пришлось писать BIOS на ассемблере.
Вывод на экран (посимвольный) должен был отрабатывать ESC-последовательности. Автоматная реализация крайне не наглядна.
Реализовано было с помощью сопрограммы, очень эффективно и очень наглядно. Текст программы - практически описание протокола.

[albobin]

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

[Kemet]

символы в него будут впихивать

ээээ, извиняюсь, кто куда и как будет впихивать?

[Губанов Сергей Юрьевич]

ээээ, извиняюсь, кто куда и как будет впихивать?

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

[Geniepro]

Что-то типа ленивого парсера получается. Комбинаторы парсеров в помощь (Haskell'ная библиотека Parsec)...

[Romiras]

ээээ, извиняюсь, кто куда и как будет впихивать?

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

Какая-то странная архитектура. Почему HTML декодер не может "спрашивать" у сборщика TCP необходимое количество через заданного размера буфер?
Надеюсь, эта ссылка поможет: buffering in standard streams

[Губанов Сергей Юрьевич]

Какая-то странная архитектура. Почему HTML декодер не может "спрашивать" у сборщика TCP необходимое количество через заданного размера буфер?

Я пояснил это в первом сообщении. Запрашивать новые символы не может потому что их ещё нет. Они ещё не приехали. Да и буфера (в обычном смысле) тоже не может быть из-за строжайшего запрета на лишнее перекопирование (контроллер памяти не справится). Вместо буфера возможен небольшой список IP пакетов.

---

Да, кстати, я немного не то написал в прошлый раз, не HTML, а конечно же HTTP.

---

Сейчас обдумываю "классический" парсер у которого пространство символов дополнено одним специальным символом под названием СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН. Работает такой парсер как обычно сам запрашивая следующий символ. В один прекрасный момент он в ответ на свой запрос получает от сканера символ под названием СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН. Тогда парсер должен запомнить своё текущее состояние и вернуть управление. Когда будет получен очередной IP пакет управление вновь будет передано парсеру и т.д.

[albobin]

Не придётся ли всё равно перейти к варианту парсера-автомата который будет обрабатывать одно событие (один символ) за один вызов, ведь символ "СЛЕДУЮЩИЙ_СИМВОЛ_ЕЩЁ_НЕ_ПОЛУЧЕН" может быть обнаружен в произвольном месте "классического " парсера ?

[Губанов Сергей Юрьевич]

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

[Peter Almazov]

А какие язык/ОС?

[Губанов Сергей Юрьевич]

Linux, C++

[albobin]

Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.