Parabix: SIMD инструкции при разборе XML

Хороший пример для других.

Нас ждут специально заточеные под парсинг xml процы?

Хотя с другой стороны, подозреваю, существует не так много приложений, скорость которых упирается в скорость парсера XML.

А какже gconf?

Ну не упирается конечно, но парсить приходится много.

> Хотя с другой стороны, подозреваю, существует не так много приложений, скорость которых упирается в скорость парсера XML.

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

Но прецедент открытия кода всё равно позитивный.

http://en.wikipedia.org/wiki/SIMD

судя по этому не все платформы имеют этот SIMD. Поэтому либа будет не кросплатформенная. Следовательно толку от него мало. Гномеры ее использовать явно не будут.

Или я wiki как-то по диогонали прочитал и чета не понял?

О боже мой. Профессор не зря прожил свою жизнь.

>судя по этому не все платформы имеют этот SIMD Открою страшную тайну большинство процессоров имеют набор SIMD инструкций. А если брать платформу х86, х86_64 так просто все.

ждем реконфигурируемые процы на плисках, прошивка в которые компилится вместе с прогой.

> Согласен, обычно это либо разовый разбор конфига при старте приложения, либо разбор чего-то, полученного по сети - и в этом случае сеть тормозит на порядки сильнее, чем разбор.

Спецы с многолетним опытом написания высоконагруженных сетевых приложений не дают потеряться в современном мире программирования. :)

Представляете что такое разбирать 100мегабит XML в риалтайме ?

http://en.wikipedia.org/wiki/SIMD#Hardware

глянь, тут далеко не все архитектуры написаны. Да и если бы все поддерживали, то ясное дело дело, врядли бы перечисляли, что поддерживает.

> судя по этому не все платформы имеют этот SIMD. Поэтому либа будет не кросплатформенная.

Не обязательно использовать конкретно SIMD. Некоторые инструкции из набора SIMD перекликаются с инструкциями MIPS-процессоров (или это только мне так кажется?) и про Altivec (PowerPC) написано в статье.

Читаем первую строчку Small-scale (64 or 128 bits) SIMD has become popular on general-purpose CPUs, starting in 1989. Вывод в массовых процессорах для пользователя они есть.

Вообще, это похоже на шутку, что "Специаллисты интел очень лестно отзываются о технологии XML, потому что как только начинается её интенсивное использование, так сразу производительность падает в разы... и очень кстати приходятся их новые процессоры"

Ну хотя наличие стандарта типа XML лучше, чем его отсутствие.

> Хотя с другой стороны, подозреваю, существует не так много приложений, скорость которых упирается в скорость парсера XML.

Ну в общем да, но все равно приятно что в современном мире bloatware занимаются оптимизацией того что и так вроде бы работает. Кроме того на ум сразу приходит Firefox и прочие браузеры, а также базы данных на XML.

ODF = XML + ZIP

Что вы прицепились к трем буквам? Методы, которые исследует Prof. Cameron, могут найти применение в задачах разбора и совершенно других данных. Зюмель - только начало.

>Хотя с другой стороны, подозреваю, существует не так много приложений, скорость которых упирается в скорость парсера XML.

Вебсервисы, в основном. Здесь скорость обработки XML очень важна.

>А если брать платформу х86, х86_64 так просто все.

Ну покажите мне эти инструкции в i386 или p54 :)

есть ещё такая вещь, как XHTML, например. а разбор страниц - это то, чем часто занимается браузер.

Давно пора оптимизировать рутинную операцию разбора XML, которая используется все чаще и чаще, решение с привлечением инструкций аппаратного уровня считаю верным. +1

>есть ещё такая вещь, как XHTML, например. а разбор страниц - это то, чем часто занимается браузер. >anonymous (*) (29.02.2008 10:16:46)

У вас такой быстрый инорнет, что бровзер не успевает бровзировать язык разметки?

У этого есть только один недостаток: это не кроссплатформенно

оно хоть с подсветкой?

До сих пор работаешь на 386? На пеньММХ не накопил? Бе-е-едненький...

> ODF = XML + ZIP

Таки да. Осталось только уговорить SUN купить у профессора его либу... :D

1. Зачем уговаривать SUN?
2. Зачем покупать?
3. Кабы это было актуально, почему ни Intel ни AMD, не выпустили такие парсеры сами с заточкой под свои камни?
4. Кабы это было актуально, почему сообщество опенсорс до сих пор не родило чего-нибудь подобного?

Список можно продолжить.

P.S.
Несмотря на вышеперечисленное, проф.Камерону респект.

читаю и фигею. разговор поистине умных людей.

лучше бы научились этот самый SIMD использовать. а то ява млять, хаскиль наши фсио.

Есть много очень актуальных потребностей, не перекрытых никакими решениями. Как мне кажется, основная причина -- высокая трудоемкость решения, запредельная для возможностей разработчиков opensource. Сам пытался приспособить SIMD для аналогичных задач, не осилил. Нужны новые методы обработки данных, новые алгоритмы, исследования.

Наконец то он открыл свои труды! Давно было пора! А парсер нужен всем. Типо как на http://ya.ru нет?

В идеале этим долны заниматься компиляторы.

>этом случае сеть тормозит на порядки сильнее, чем разбор

ну-ну. а ничего, что данные со скоростью 1Гбит приходят?

Незнаю у меня только так обрабатывается голос с помощью этих инструкций очень удобно, особенно делать конференции и обратно его в TDM юзверям рассовывать. Конечно реализация на Асемблере под конкретный проц. Универсальность здесь будет в ущерб производительности, а для таких задачь это не приемлемо.

> парсера XML, использующего SIMD инструкции современных процессоров

А разве не компилятор должен заниматься подобным??? Или он на asm-е написан?

Сходил по ссылке, заглянул в исходники и увидел такой комментарий:

Copyright (c) 2007, Robert D. Cameron

Licensed to the public under the Open Software License 3.0.

Licensed to International Characters, Inc., under the Academic

Free License 3.0.

Вопрос: что это за лицензия такая?

Компиляторы пока с этим плохо справляются. Более-менее интеловский что-то пытается.

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

Это не затрудняет применение SIMD, а снижает его эффективность. В этом то и проблема, чтобы получить существенный прирост в скорости, а не падение. Блоковая обработка в данном случае приводит к избыточности вычислений, так как в рамках блока несколько ветвей вычислений могут обрабатываться параллельно и отбрасываться позднее. Кроме того имеются скрытые накладные расходы на упаковку/распаковку данных и выравнивание их в памяти.

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

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

> Представляете что такое разбирать 100мегабит XML в риалтайме ?

+1. сабж интересен и полезен.

> 1. Зачем уговаривать SUN?

Иначе надо форкать ОО

> 2. Зачем покупать?

У профессора не GPL - это раз. SUN в свои разработки (даже свободные) берёт только код с полной передачей прав.

> 3. Кабы это было актуально, почему ни Intel ни AMD, не выпустили такие парсеры сами с заточкой под свои камни?

ИМ это не актуально.

> 4. Кабы это было актуально, почему сообщество опенсорс до сих пор не родило чего-нибудь подобного?

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

> При разборе символьных потоков требуется принимать решение после обработки каждого символа.

> Это не затрудняет применение SIMD, а снижает его эффективность.

Вы ведь это не серьёзно, правда? Для примера рассмотрите простейшую задачу - узнать номер слова в списке:

1 - call

2 - can

3 - cat

Посимольное сравнение грубо даст 3N операций, а сравнение восьмерок символов N операций

> Хотя с другой стороны, подозреваю, существует не так много приложений, скорость которых упирается в скорость парсера XML.

хорошо оптимизированная библиотека всегда пригодится, т.к. программы имеют свойство расти

В вашем примере строка - это массив. Обработка массивов -- традиционно удобная для SIMD область. Я имел в виду LL или LR - парсинг на уровне всего алгоритма, а не некоторой его части.

>Нас ждут специально заточеные под парсинг xml процы?

Дебил, это парсер заточен под i686.

Алсо, капча gracher

> Вы ведь это не серьёзно, правда? Для примера рассмотрите простейшую задачу - узнать номер слова в списке: 1 - call 2 - can 3 - cat

> Посимольное сравнение грубо даст 3N операций, а сравнение восьмерок символов N операций

вообще-то такая задача решается по другому -- тут regexp-ы рулят. Т.е. я бы сначала посоветовал заглянуть в код перла по разбору слов, там оч.быстрые алгоритмы

Извиняюсь за вторжение, но регэкспы тоже могли бы выиграть от SIMD.

Если мне не изменяет склероз, то регэксп-выражения компилируются в конечный детерминированный автомат. Переход к недетерминированным автоматам тоже может быть полезен, так как последние намного более проще (экспоненциально меньше состояний и условий перехода), чем их детерминированные аналоги. Работают они, конечно же, экспоненциально дольше, так как форкаются экспоненциальное количество раз. Однако на некоторых входных данных экспоненциального роста копий автомата не происходит, так как все нити быстро "отмирают". Похожая идея реализована в GLR-парсере. http://en.wikipedia.org/wiki/GLR_parser

Мне кажется SIMD может дать хорошие результаты для ускорения недетерминированных автоматов. Надо взять на заметочку :)

окромя викиПЕДии, видимо, других источников не существует, знатоки мля. 8)

процессор не нужен! >0_0<

Кто-то может сказать, гном теперь перестанет тормозить?