Анализ простейших хэш-функций и методы их оптимизации на ассемблере.

Рассматриваемые функции:

unsigned int stupid_hash(char* string)
{
    return 1;
}

unsigned int strlen_hash(char* string)
{
    return strlen(string);
}

unsigned int mid_ascii_hash(char* string)
{
    unsigned int hash_sum = 0;
    unsigned int str_len = 0;
    while (*string != 0)
    {
        hash_sum += *(string++);
        str_len++;
    }
    return hash_sum / str_len;
}

unsigned int ascii_sum_hash(char* string)
{
    unsigned int hash_sum = 0;
    while (*string != 0)
        hash_sum += *(string++);
    return hash_sum;
}

unsigned int ded_hash(char* string)
{
    unsigned int hash_sum = 0;
    while (*string != 0)
    {
        hash_sum ^= *string;
        hash_sum = (hash_sum << 1) | (hash_sum >> 31);
        ++string;
    }
    return hash_sum;
}

Проанализируем распределение слов в хэш-таблице.

Выборка: ~60000 существующих английских слов

Размер хэш-таблицы: 2017

stupid_hash:

strlen_hash:

mid_ascii_hash:

ascii_sum_hash:

ded_hash:

Лучшее распределение показывает ded_hash, будем оптимизировать его.

#define _OPTIMIZATION

Профилируем:

Выборка: ~370000 английских слов, над которыми проводятся операции вставки и удаления (см. words.txt)

Размер хэш-таблицы: 59999

Работаем следующим образом:

for (int j = 0; j < 100; ++j)
    for (int i = 0; i < size; ++i)
        if((i + j) % 2)
            hash_map.insert(words_array[i]);
        else
            hash_map.remove(words_array[i]);

Результаты профилирования:

Без оптимизации. Время работы: 24,7 с.

-O1. Время работы: 23 с.

-O2. Время работы: 18,8 с.

Или, более наглядно:

Делаем вставку на языке ассемблера:

#define _ASM

unsigned int ded_hash(char* string)
{
    _asm
    {
        mov ebx, string
        xor eax, eax
        xor edx, edx
        _loop :
        mov dl, [ebx]
        xor eax, edx
        rol eax, 1
        inc ebx
        cmp[ebx], 0
        jne _loop
    }
}

Снова проводим замеры:

Время работы: 19,6 с.

Момент истины: сравним с предыдущими результатами.

Относительное время:

Время работы программы:

Время, потраченное на работу данной хэш-функции:

Полученные коэффициенты ускорения(абсолютное время до оптимизации / абсолютное время после оптимизации)

Оптимизация	Od	-O1	-O2
Коэффициент	1,79	1,39	0,93