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

Удобным подходом к формированию ответа на этот вопрос является создание таблицы из логических флагов, в которой поставленное в соответствие каждому символу логическое значение 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; }

Даже без перехода к использованию платформо-специфичных наборов инструкций иногда можно перейти к использованию данных в векторной форме при выполнении операций с символами. Например, ниже приведен один способ проверки того, представляют ли четыре последовательных байта из потока строковых данных в кодировке UTF-8 символы из таблицы ASCII7:

(*(const uint32_t*)data & 0x80808080) == 0