Реализации strspn

Когда разбирался в коде реализации разбора и преобразования html - в gtkhtml - заметил что при разборе любого текстового файла очень часто используется функции strspn. Конечно это обычная практика - сам так делал, но не анализировал эту ситуацию.

Правда в gtkhtml - при разборе его не используют разбирают по символам с последующим анализом к какому классу относиться символ с последующим выделением токенов из исходных данных. В принципе не плохое надежное решение - с одним минусом иногда автоматический пропуск незначащих символов сработает гораздо быстрее посимвольного разбора.

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

В glibc 2.7 существует 2 вида реализаций:

• Медленная реализация вида - проход исходной строке в цикле с последующим проходом для каждого символа по строке - шаблону. Довольно таки простой надежный алгоритм, но не более количество проходов если не ошибаюсь сложность O это O(n*m) - где m*n это соответственно количество символов в исходном тексте и количество символов в шаблоне. Используется только для тестирования реализации. Расположена в файле string/test-strspn.c.
• Основная реализация расположена в sysdeps/архитектура/strspn.S и реализует на ассемблере эту функцию для каждой поддерживаемой архитектуры. Алгоритм немного изменился - вначале создается буфер под 256 байт для реализации множества на масcиве флагов(массив создается в стеке). Затем для для каждого символа присутствующего в шаблоне устанавливается флаг. Затем осуществляется проход по исходной строке и осуществляется обычная проверка установлен ли флаг(значение байта != 0). В результате сложность алгоритма не зависит от количества символов в шаблоне(O(n*m)).

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

Возможные пути улучшения:

Заменить массив из 256 байт на массив из 32 байт(256 бит) и проверять установлен ли бит в байте. Имеет основным достоинством что использует меньше памяти и возможно на архитектурах с такой разрядностью и/или аппаратно реализованной проверкой установлен ли бит - получить реализацию с минимальной зависимостью от скорости обращения к памяти при проверке присутствия элемента во множестве. Для архитектур x86 это большого выграша дать не может так как не полностью все множество влазит в размерность регистров и получение данных из кеша достаточно быстрое и получение данных из исходной строки идет с учетом особенностей архитектуры и получение данных идет с размерностью равной 32 бита с последующим получением частей. Так используется получение именно по 4 байта есть подозрение, что на части процессоров оно работает значительно быстрее получения 64 битных значений.

Для реализации получения значения бита в множестве на массиве из 32 байт пришлось бы использовать 5 инструкции:

• получение байта в котором установлен бит через сдвиг(>>5 или >>4),
• получение этого байта из памяти(скорее получение 4-8 байт в котором расположен нужный байт)
• получение позиции в которой должен быть бит через и(i&(1<<5-1))
• сдвиг полученного из памяти значения на полученное выше количество бит
• проверка установлен ли этот бит через &

В алгоритмах вместо этого используется косвенная операция проверки установлен ли элемент в массиве testb, которая в теории проработает быстрее чем 5 ранее указанных .

И еще одно возможное ускорение рассчитанное на обычное наиболее частое употребление: пропустить пробелы - при этом снизив количество обращений к памяти - объединить все элементы в шаблоне по или и для каждого элемента в исходном тексте проверять через или входит ли он в подозрительное множество. Также можно проверять группу символов выравненных по границе машинного слова и передвигаться на размер этого слова.

Особого ускорения это не даст - может пара процентов. Нужно бы это проверить на досуге....