Просмотр сообщений

В этом разделе можно просмотреть все сообщения, сделанные этим пользователем.


Сообщения - Губанов Сергей Юрьевич

Страницы: [1] 2 3 ... 40
2
Выделяется довольно большой кольцевой буфер. Единым куском памяти. Туда с начала и почти до конца (как придётся) пишутся данные из сети.
Мне так нельзя по двум причинам:

1) Мне нельзя копировать данные (трафик запредельно огромный). То есть нет никаких собственных буферов для данных. Я работаю с указателями на области памяти куда сетевые пакеты кладутся чисто аппаратно самим сетевым контроллером.

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

3
Для таких случаев я запускаю разборщик в параллельном потоке. Он продвигается по рекурсивному спуску по мере поступления данных из главного потока. Для обмена данными я использую POSIX pipe(fd):  в основном потоке - write(fd[1]), в параллельном - read(fd[0]).
Очень красивое решение. Жаль не подходит для моего случая (потребуется одновременно более ста миллионов потоков).

4
Пока сделал следующим способом. Те 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) Если ключевое слово интересно, то парсер переводится в состояние чтения значения после ключевого слова.

То есть состояний у парсера получилось совсем немного...



5
Ну как же не находит, всё находит. Сначала надо проверить что размер буфера достаточно большой, уж точно больше 7 букв. Заменить седьмую букву сзади на '\n' запомнив её настоящее значение. Применить указанный цикл. Вернуть седьмой букве сзади прежнее значение. Применить обычный одношаговый поиск с проверкой на переполнение буфера, чтоб проверить оставшиеся 7 букв. Вуаля.

Рассказал об этом на работе. Меня попросили сравнить скорость моего семимильного изврата с обычной стандартной memchr. Получилась история как в анекдоте про чукчу-не-читателя. Предопределённая memchr оказалась примерно в три раза быстрее моего поделья. Я был потрясён. Как такое возможно ??? ??? ???

6
Вот этот код на моём процессоре (Tilera)

            while ((*c != '\n') & (*(c+1) != '\n') & (*(c+2) != '\n') & (*(c+3) != '\n') & (*(c+4) != '\n') & (*(c+5) != '\n') & (*(c+6) != '\n'))
            {
                c += 7;
            }

на больших массивах ищет конец строки по меньшей мере в 2.44 раза быстрее чем

            while (*c != '\n')
            {
                c++;
            }

Подходящих SIMD инструкций аналогичных Интеловским SSE в Тилере нету, так что сделать линейный поиск конца строки ещё более быстрым видимо не получится.

А с SSE прикольно было бы, можно было бы скакать сразу на 16 букв вперёд.

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

Спасибо.

Посмотрел его код: https://github.com/h2o/picohttpparser/blob/master/picohttpparser.c

Он сначала копирует данные в накопительный буфер, потом парсит обычным stateless парсером.

Мне копировать данные нельзя - не хватит пропускной способности контроллера памяти. Да и сильно накапливать данные мне тоже нельзя - не хватит объёма памяти.

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

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

---

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

---

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

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

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

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

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

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

13
Урочище Флуда / Re: Ополченцам капец
« : Декабрь 08, 2014, 02:53:21 pm »
Похоже на "Геном" Лукьяненко. Там люди-"спец" имели генетические модификации для выполнения соответствующей работы. Не ты не "спец", то на работу где нужен "спец" тебя не возьмут, просто по объективным показателям - не осилишь.

14
Общий раздел / Re: Юмор
« : Декабрь 04, 2014, 07:36:46 am »
http://professionali.ru/Vacancy/54326/
Цитировать
Описание:
 Команда разработчиков краудфандингового сервиса «Дай пять» ищет себе по-настоящему несносного босса.
 Обязанности

 Разрешение конфликтных ситуаций
Сообщение об увольнении некомпетентным сотрудникам
Выбор поставщика готовой еды
Право решающего голоса на еженедельных собраниях
Разработка системы мотивации и демотивации
Быть беспощадным по отношению к конкурентам
Быть беспощадным по отношению к подчиненным
 Требования к кандидату

 1. Умение командовать
2. Строгость
3. Безжалостность к соблюдению сроков
4. Умение вызывать страх своим присутствием
5. Страсть к дорогим канцтоварам
6. Желание быть очень богатым
 Условия работы

3 дня в неделю в офисе
Ненормированный рабочий день (доступность в скайпе 24 часа)
Оплата мобильного интернета и новый iPhone
Подарочная карта Starbucks

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

 Краудфандиговая платформа «Дай пять» основана в 2013 году. Объем частных инвестиций — $500 000
В данный момент имеется полностью готовый продукт с финансированием на срок от 1,5 лет или до момента самоокупаемости. Старт проекта 27 ноября

15
Вот - ЧТО ЧИТАТЬ и СМОТРЕТЬ? ??? ?? Хочется ХОРОШЕЙ фантастики, а её - НЕТ.
Рекомендую прочитать - Вернор Виндж "Глубина в небе".

Страницы: [1] 2 3 ... 40