LINUX.ORG.RU

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

 parabix, , ,


0

0

Профессор Роб Камерон отдал миру плод своих трудов, а именно открыл исходные коды Парабикса, парсера XML, использующего SIMD инструкции современных процессоров для ускорения процесса разбора XML. Тесты показывают увеличение скорости разбора в несколько раз.

>>> Подробности

anonymous

Проверено: anonymous_incognito ()

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

timur_dav ☆☆☆☆☆
()
Ответ на: комментарий от lvv

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

timur_dav ☆☆☆☆☆
()
Ответ на: комментарий от Hagalaz

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

Hagalaz
()
Ответ на: комментарий от timur_dav

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

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

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

anonymous
()

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

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

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

mrdeath ★★★★★
()

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

ikm ★★
()
Ответ на: комментарий от mrdeath

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

Mikler
()
Ответ на: комментарий от lvv

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

vasaka ★★★
()
Ответ на: комментарий от anonymous

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

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

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

anonymous
()
Ответ на: комментарий от mrdeath

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

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

anonymous
()
Ответ на: комментарий от mrdeath

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

Mikler
()

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

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

ierton ★★
()
Ответ на: комментарий от anonymous

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

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

anonymous
()

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

grob ★★★★★
()
Ответ на: комментарий от timur_dav

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

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

aist1 ★★★
()

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

anonymous
()

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

anonymous
()

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

KUser
()
Ответ на: комментарий от yyk

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

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

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

wwarlock
()
Ответ на: комментарий от frost_ii

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

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

scaldov ★★
()
Ответ на: комментарий от wwarlock

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

aist1 ★★★
()

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

anonymous
()
Ответ на: комментарий от scaldov

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

madcore ★★★★★
()
Ответ на: комментарий от anonymous

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

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

Pi ★★★★★
()
Ответ на: комментарий от aist1

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

Mikler
()

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

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

anonymous
()

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

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.

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

Demon37 ★★★★
()
Ответ на: комментарий от anonymous

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

madcore ★★★★★
()
Ответ на: комментарий от Mikler

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

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

aist1 ★★★
()
Ответ на: комментарий от aist1

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

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

aist1 ★★★
()
Ответ на: комментарий от anonymous

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

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

isden ★★★★★
()
Ответ на: комментарий от wwarlock

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

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

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

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

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

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

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

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

yyk ★★★★★
()
Ответ на: комментарий от aist1

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

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

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

1 - call

2 - can

3 - cat

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

anonymous
()
Ответ на: комментарий от timur_dav

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

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

vadiml ★★★★★
()
Ответ на: комментарий от anonymous

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

aist1 ★★★
()
Ответ на: комментарий от lvv

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

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

Алсо, капча gracher

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

vadiml ★★★★★
()
Ответ на: комментарий от vadiml

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

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

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

aist1 ★★★
()

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

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.