Рейтинг@Mail.ru

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com




Библиотека сайта rus-linux.net

Разбор документов XML со скоростью света

Глава 4 из книги "Производительность приложений с открытым исходным кодом".

Оригинал: Parsing XML at the Speed of Light
Автор: Arseny Kapoulkine
Перевод: А.Панин

Оптимизация символьных операций

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

Наиболее важной операцией является операция определения принадлежности символа к определенному множеству: принадлежит ли символ из входного потока данных к определенному набору символов?

Удобным подходом к формированию ответа на этот вопрос является создание таблицы из логических флагов, в которой поставленное в соответствие каждому символу логическое значение true/false устанавливается в зависимости от того, принадлежит ли символ к данному набору символов или нет. В зависимости от кодировки, имеет смысл использовать таблицы с различными структурами и размерами:
  • При работе с кодировками, в которых каждый символ занимает не более 8 бит, таблица из 256 значений вполне достаточна.
  • При работе с кодировкой UTF-8 мы предпочтем использовать таблицу с байтовыми индексами для предотвращения декодирования с использованием кодов; такой подход работает только тогда, когда все символы с кодами (т.е., все числовые значения) больше 127 принадлежат к набору или никакие из символов с кодами больше 127 не принадлежат к набору. Если какое-либо из этих условий выполняется, таблицы из 256 значений будет достаточно. Первые 128 элементов таблицы заполняются логическими значениями true или false (в зависимости от того, находится ли символ в целевом наборе), а остальные 128 элементов таблицы содержат одно и то же значение. В соответствии с методом кодирования данных в UTF-8, все символы со значениями больше 127 будут представлены в виде последовательностей байт со значениями больше 127. Более того, первый символ последовательности будет также больше 127.
  • При работе с кодировкой UTF-16 или UTF-32 использование таблиц больших размеров обычно не является практичным. Зная о том же ограничении, что используется и при оптимизации работы с кодировкой UTF-8, мы можем оставить таблицу из 128 или 256 элементов, а дополнительные сравнения проводить только в случае работы с символами вне задаваемого таблицей диапазона.
Следует учесть, что нам требуется только один бит для хранения значения true/false, поэтому может иметь смысл использование битовых масок для хранения восьми различных наборов символов в рамках одной таблицы из 256 байт. Библиотека pugixml использует такой подход для экономии пространства кэша: на архитектуре x86 проверка логического значения обычно эквивалентна по затратам ресурсов проверке значения бита в байте в том случае, если позиция бита является константой, заданной во время компиляции. Данный код на языке C демонстрирует описанный подход:
enum chartype_t {
  ct_parse_pcdata  = 1, // \0, &, \\r, \<
  ct_parse_attr    = 2, // \0, &, \\r, ', "
  ct_parse_attr_ws = 4, // \0, &, \\r, ', ", \\n, tab
  // ...
};
static const unsigned char table[256] = {
  55, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 0, 0, 63, 0, 0, // 0-15
  // ...
};
bool ischartype_utf8(char c, chartype_t ct) {
  // примечание: преобразование к беззнаковому типу данных важно,
  // так как гарантирует то, что значение будет находиться в диапазоне 0..255
  return ct & table[(unsigned char)c];
}

bool ischartype_utf16_32(wchar_t c, chartype_t ct) {
  // примечание: преобразование к беззнаковому типу данных важно,
  // так как гарантирует то, что значение не будет отрицательным
  return ct & ((unsigned)c < 128 ? table[(unsigned)c] : table[128]);
}
В том случае, если исследуемый диапазон значений включает в себя все символы в определенном интервале, может иметь смысл использование операторов сравнения вместо поиска значений в таблице. При осторожном использовании арифметических операций над беззаконными целочисленными переменными требуется всего лишь один оператор сравнения. Например, проверка того, что символ соответствует числу:
bool isdigit(char ch) { return (ch >= '0' && ch <= '9'); }
может быть преобразована для использования единственного оператора сравнения:
bool isdigit(char ch) { return (unsigned)(ch - '0') < 10; }

При последовательной обработке символов использование описанных выше приемов для улучшения производительности обычно становится невозможным. Однако, иногда возможна обработка групп символов и использование проверок с данными в векторной форме. Если целевая система имеет поддержку какого-либо типа SIMD-инструкций, вы обычно можете использовать эти инструкции для быстрой обработки групп из 16 и более символов.

Даже без перехода к использованию платформо-специфичных наборов инструкций иногда можно перейти к использованию данных в векторной форме при выполнении операций с символами. Например, ниже приведен один способ проверки того, представляют ли четыре последовательных байта из потока строковых данных в кодировке UTF-8 символы из таблицы ASCII7:
(*(const uint32_t*)data & 0x80808080) == 0

Наконец, что бы вы не делали, избегайте функций is.*() из стандартной библиотеки (таких, как isalpha()) в коде, от которого требуется повышенная производительность. Даже лучшие реализации этих функций производят проверку соответствия значения текущей локализации значению "C", причем эта операция более ресурсоемка, чем сам поиск значения в таблице, а неудачные реализации могут быть в два раза медленнее этой операции поиска.8


Продолжение статьи: Оптимизация строковых преобразований.

Если вам понравилась статья, поделитесь ею с друзьями: