Алгоритмы общего назначения

Простые хэш-функции высокой производительности

Часть вторая

Множество лун тому назад было проведено общеизвестное тестирование качества простых хеш-функций общего назначения, в котором мы выявили слабые стороны ряда популярных алгоритмов. Как выяснилось, алгоритм может показывать себя довольно хорошо на определенных наборах тестового материала, а некоторых будет "сыпаться". Алгоритмы, основанные на понятной математической модели, ведут себя довольно стабильно, хотя и звезд с неба не хватают. К числу таких конструкций можно отнести алгоритмы семейства FNV. Такие функции, как правило, обладают сравнительно хорошей производительностью, качественным распределенением, соответственно и покажут примерно одинаковые результаты на различных наборах данных, включая сложные. К примеру, набор из практически идентичных строк, как-то список ip-адресов с различающимися двумя последними байтами, или даже слова одниковой длины - все это может оказаться сложным случаем для функций и некими контруктивными недостатками, но не составит труда хорошо для проработанной функции. Все тот же FNV, он родимый, довольно-таки умело справляется с вышеуказанным материалом. Примером стабильной функции в плане коллизионной чистоты можно назвать и разработку автора - функцию MaPrime2c. Этот нехитрый набор кода хотя и не отличается ошеломляющей производительностью, но имеет свои плюсы, среди которых: крайняя простота реализации, возможность использования в программно-технических (аппаратных) комплексах. Сравнительно с FNV, конечно же, этот алгорим будет медленнее. почему?

MaPrime2c

Оную функцию мы рассмотрели еще в первом выпуске. Что отличает ее от большинства существующих? В качестве подсисемы рассеивания здесь используется таблица замены (подстановки), которая инициирует массивное обращение к памяти. На аппаратных решениях это может быть выполнено весьма быстро, но программные реализации могут "проседать". Конструктивной причиной различия в производительности является еще и побайтовое сжатие, в отличие от 32-разрядного во многих из наиболее распространенных. Собственно этот момент и имеет две стороны - хорошее распределение и пропорциональное снижение производительности.

static const unsigned char sTable[256] =
{
  0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
  0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
  0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
  0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
  0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
  0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
  0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
  0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
  0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
  0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
  0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
  0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
  0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
};


#define PRIME_MULT 1717


unsigned int
maPrime2cHash (unsigned char *str, unsigned int len)
{
  unsigned int hash = len, i;


  for (i = 0; i != len; i++, str++)
    {

      hash ^= sTable[( *str + i) & 255];
      hash = hash * PRIME_MULT;
    }

  return hash;
}

MaFastPrime1

Что можно сказать о прошлой функции? Наш алгоритм вполне себе неплох, но существующая ныне система оценки в первую очередь смотрит на производительности. Если брать на вскидку актуальный список простых хеш функций общего назначения, где обычно присутствует и MaPrime2c, то мы увидим последнюю как-раз таких ближе к концу списка. По качеству распределения она будет одной из первых, по скорости - из последних. Почему так? Всё потому, что сейчас акцент ставится именно на скорости, соответственно и оптимизация смотрит именно в этом направлении. Указанный далее алгоритм сочетает в себе элементы конструкции MaPrime2c и новомодный базис некриптографических хешей - обработку блоками в 4 байта. Как видно, подход остался прежним, за исключением табличной замены, которая теперь отсутствует. Хвост, тоесть не кратные 4 байтам данные, сжимаются отдельно. В этом случае применяется классический подход. Что мы имеем в результате? Кто пан, а кто пропал - покажут тесты, но пока можно сказать одно. Алгоритм конструктивно быстрее, особенно на блоках кратных 32-м битам. На остальных наборах данных замедление не будет принципиально ощутимо, поскольку блоки будут невелики - не более трех байт.

unsigned int
maFastPrime1Hash(char *str, unsigned int len) {
	unsigned int hash = len, i = 0, k;
	long rem = len;
	unsigned char trail;

	const unsigned char * data = (const unsigned char *)str;

	while (rem >= 4) {
		k = *(unsigned int*)data;
		k += i++;
		hash ^= k;
		hash *= 171717;
		data += 4;
		rem -= 4;
	}

	while (rem >= 0) {
		trail = *(unsigned char*)data;
		trail += i++;
		hash ^= trail;
		hash *= 171717;
		data++;
		rem--;
	}

	return hash;
}

MaRushPrime1

Прошлый раз нам была представлена 32-х разрядная модификация классического алгоритма MaPrime2c. Как нам стало известно, она сочитает значительно увеличенную производительность (ввиду перехода на 4-х байтные блоки) и традиционную прозрачную структуру, основанную на простых математических операциях. Сам алгоритм не только не усложнился, но и даже "похудел" ввиду отсутствия таблицы подстановок. Безусловно, переход на 32-х разрядную обработку не мог сказаться на числе коллизий в итоге, за низкое количество которых мы так любим MaPrime2c. Будем считать это маленьким, необходимым злом. Но можно ли еще его ускорить саму функцию? Попробуем. Рассмотренный ранее FastPrime1c имеет одно особенность - там применяется побайтовый просмотр для некратных данных в конце строки. Что если мы будем использовать все тот же блок, забитый пустыми значениям до кратного? Скажется ли это на результате? Безусловно. В плане качества распределения FastPrime1 будет лучше, но, вероятно, масштаб новоприобретенных коллизий не будет столь велик?

unsigned int maRushPrime1Hash(char *str, unsigned int len) {
	unsigned int hash = len, i = 0, k;
	long rem = len;

	const unsigned char * data = (const unsigned char *)str;

	while (rem >= 4) {
		k = *(unsigned int*)data;
		k += i++;
		hash ^= k;
		hash *= 171717;
		data += 4;
		rem -= 4;
	}

	switch (rem) {
	case 3:
		k = (unsigned int)(data[0]) | (unsigned int)(data[1] << 8) |
			(unsigned int)(data[2] << 16);
		k += i++;
		hash ^= k;
		hash *= 171717;
		break;

	case 2:
		k = (unsigned int)(data[0]) | (unsigned int)(data[1] << 8);
		k += i++;
		hash ^= k;
		hash *= 171717;

		break;

	case 1:
		k = (unsigned int)(data[0]);
		k += i++;
		hash ^= k;
		hash *= 171717;
		break;

	}

	return hash;
}

От слов - к делу

Теория хороша, но посмотрим, все же, что покажет практика. Постараемся провести ряд независимых, но открытых тестов, характеризующих как качество функции, так и ее производительность. Объем материала в области разработки и оценки некриптографических функций общего назначения в настоящее время совсем не велик. Преобладает обилие "скоростных" тестов, но можно ли оценивать только скорость? Вероятно, для ряда назначений она первична, но опредяляющим для выбора того или иного алгоритма будет что? Простота в реализации на требуемой платформе, возможно - портируемость, понятная разработчику структура, оптимальное соотношение качества расределения (числа коллизий) и скорости на применяемом материале. Следует подчеркнуть последнее. Существуют алгоритмы, оптимальные, скажем, только для небольших или напротив - для больших объемов хешируемого материала. Некоторые алгоримы могут быть разработаны и оптимизированы, к примеру, для определенного пространства символов, некоторые могут "сыпаться" на сложном наборе схожего матерала. А тут даже при условии высокой производительности число ложных совпадений сведет всю фору на нет.

Приступим!

Проведем исключительно синтетический тест скорости. В данном испытании наши функции будут хешировать миллион случайных строк длиной 1024, 512, 256, 128 и 64 байта. Набор материала для всех функций един, перед выполнением батареи тестов приоритет процесса устанавливается на realtime (реального времени), а сам процесс выполняется лишь на одном из ядер ЦП для исключения возможных искажений информации. Результатом замера будет разница значений функции QueryPerfomanceTimer. Сам код скомпилирован С++ Builder 16.0 с оптимизацией "fastest possible code". Следует отметить, что исходный текст алгоримтов не был никоем образом оптимизирован, поэтому вся работа в этом направлении ведется лишь компилятором. Результаты отсортированы по сренему показателю процессорного времени. Соответственно, чем оно меньше, тем быстрее показал себя испытуемый.

Попробуем выявить некую зависимость результатов от выбранного компилятора. В данном конкуретном случае будем использовать GNU GCC 4.4 с опцией "optimize even more" под процессор класса Intel Core 2 DUO

А теперь протестируем код, скомпилированный на MSVC 10 с опциями "максимальная скорость" и "поддержка SIMD2"

Стоит для чистоты тестов провести их и на ином оборудовании. В данном случае использован вариант с C++ Builder 16 на AMD Athlon II X4 640

Теперь проведем общий "забег" алгоритмов, скомпилированных GCC с опцией "Athlon64 tuning" на AMD Athlon II X4 640

Посмотрим, как покажет себя код, генерированный компилятором MSVC на AMD Athlon II X4 640

А теперь отойдем от чисто синтетических исследований и совместим наше испытанием с вычислением качества функции, проще говоря, замерим число коллизий (случайных совпадений) на большом массиве информации. В качестве тестового материала выбран все тот же, содержащий слова, отсортированные в алфавитном порядке. В основе оного - заголовки из Русской Википедии, Большой советской энциклопедии, Большого англо-русского словаря и других словарных источников в общем колличестве 2726299 уникальных слова. Важно отменить, что все тексты - в кодировке cp866, минимальная длина - 3 символа, регистр - верхний. Исходный код скомпилирован на C++ Builder, как и в синтетическом тесте. Замер выполняется на AMD Athlon II X4 640. Отличие от синтетического теста здесь подсчет временных характеристик выполняется суммированием времени вычисления отдельных строк, что более приближено к реальным условия работы типового приложения. Набор тестов от A до H идентичен методике прошлого теста. В данной таблице результаты отсортированы по числу коллизиций, т.е. по качеству функции в рамках исследования.

Отсортируем результаты по времени выполнения. Выше расположены функции, лучшие по данному показателю на все том же наборе данных. Результаты в виде электронной таблицы расположены здесь.

Теперь усложним тест. Вместо слов различной длины у нас будет фиксированный список слов, различающихся незначительно. В качестве материала выбран список IP адресов, имеющих массу случайных совпадений. В данной таблице рассмотрим число выявленных коллизий в порядке возрастания. Результаты можно скачать в виде электронной таблицы не иначе как здесь.

Посмотрим теперь время вычисления хешей в предыдущем тесте. Простые математические функции были исключительно хороши, показав полное отсутствие случайных совпадений. Какова их производительность? Результаты можно скачать в виде электронной таблицы не иначе как здесь.

Усложним еще нашу задачу. Что если мы в качестве тестового набора возьмем пакет схожих, ограниченных небольшим пространством, символов? Проведем тестирование на группе IP адресов, записаных без свободных нулей. В данном случае сгрупируем по числу коллизий. Результаты тут.

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

Один из самых сложных тестов - он и самый простой. Более двух с половиной миллионов чисел, от 0 до 2726298, могут поставить в тупик любой из самых сложных алгоритмов. Проведем испытание скомпилированного на BCC кода, тестовым стендом будет машина на базе Intel Core i3. Результаты отсортируем по колличеству коллизий. Скачать их можно будет вот здесь.

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