?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
fast utf-8 validation
nyaload
_winnie
Наткнулся на простую и быструю библиотеку декодирования UTF-8, кроссплатформенную, с валидацией всех возможных ошибок в utf-8 (overlong, surrogate pairs) - http://bjoern.hoehrmann.de/utf-8/decoder/dfa , без бранчинга ( «?:» заменяется на стандатный битхак mask=((int)x-1)>>31), легко векторизуется до чтения dword/qword. Декодирование рассматривается как конечный автомат, конечный автомат загонятся в таблицу [char x state] →state

Протестировал брутфорсом, работает эквивалентно iconv (в плюс iconv - он умеет детектить суррогатные пары, но что с ними делать - оставляет решать пользователю).

Не законом Мура единым ускоряем софт
Tags:


  • 1
Гениально; непонятно другое, а почему раньше никто ничего такого не написал? Непонятно. На том же юникоде, куча народу такого типа грамотного, бывшие айбиэмовцы. Ну, правда, в их программистских способностях...

А я вот не понимаю, что именно тут гениального. Даже более того, не удивлюсь, если, к примеру, реализация здесь: https://github.com/behdad/harfbuzz/blob/master/src/hb-utf-private.hh (функция hb_utf_next), окажется быстрее.

Ну да, да, видел кучу такого кода. В котором /* TODO check for overlong sequences? */ и капуста из if -

#define HB_UTF8_COMPUTE(Char, Mask, Len) \
if (Char < 128) { Len = 1; Mask = 0x7f; } \
else if ((Char & 0xe0) == 0xc0) { Len = 2; Mask = 0x1f; } \
else if ((Char & 0xf0) == 0xe0) { Len = 3; Mask = 0x0f; } \
else if ((Char & 0xf8) == 0xf0) { Len = 4; Mask = 0x07; } \
else Len = 0;
( можно на табличку по (Char >> 4) заменить )

Вот этот цикл - for (i = 1; i < len; i++) - он на русском тексте срабатывает рандомноо 1 или 2 раза, у процессора нет возможности предсказать ветвление на начало цикла.

В первом примере компилятор вообще не знает, какой длины будет цикл (счётчик задаётся из внешнего массива), а здесь - компилятору доступна вся информация о зависимости между Char и количеством итераций (плюс компилятор точно знает, что Len - мало, имеет смысл сразу цикл разворачивать). Вот из этих соображений.

А как оно на самом деле на Intel'е будет - надо мерять.

опять в спам попал, будь оно всё неладно!

да писал конечно, я думаю таких библиотек сотни (я сам что-то подобное писал). но вот собраться, оформить и выложить смог только один.

В смысле автор блога предлагает избавиться от бранчей с помощью:
mask = (x-1) >> 31
И что дальше делать с этой маской?

Адресовать таблицу?

Это не убирает бранч. Ну и потом, как минимум, есть бранч в цикле прохода по массиву. Чтобы его минимизировать нужно циклы разворачивать.

Бранч в цикле прохода по массиву предсказывается в разы лучше чем бранч, зависящий от структуры utf8 потока.

В коде по ссылке a ? b : c, предлагается заменить это на mask = (a - 1) >> 31; result = (b & mask) | (c & ~mask) с точностью до перемены b/c местами, внутри цикла *state не проверять вообще, и получить безбранчевый код на detect, если в цикле только смотреть, закончился ли стрим (и не делать early reject) - получается почти безбранчевый код проверки utf8.

Спасибо за объяснение! Дело в том, что я подробно не смотрел текст, а, просмотрев по диагонали не нашел объяснения. Даже при повторном просмотре сейчас. :-) Ну да ладно. А зачем >> 31 делать-то? 1-0 = 0, 0-1=0x11111.... То бишь маска получается без сдвига.


Сделать проверку state и окончания цикла почти без бранчей действительно не очень сложно.

Edited at 2013-03-22 05:47 am (UTC)

Ниже _winnie ответил, >> 31 это общий трюк, если a - 0 или 1 строго то да, не надо.

((x>=0) ? a : b) , где x - 32-битный signed заменяется на

mask = (x>>31);
(~mask & b) | (mask & a)


Стоит ли так делать - зависит от компилятора и процессора, я ещё не измерял. Если b - это array[index], то компилятору сложнее самому выкинуть бранч.


Edited at 2013-03-22 10:39 am (UTC)

Теперь верю. Это симуляция predication. Единственное, что в теории сдвиг знаковых в Си++ стандарте не определен. На практике: в gcc, vc (Intel) мы знаем как оно будет работать.

тестировать это все надо на производительность, так как ?: это cmov

В gcc да, в msvc нет. Но тестировать все равно надо, да :)

  • 1