[РЕШЕНО] Ассоциативный контейнер для быстрого lookup'а

[alexis031182]

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

Ещё раз спасибо. Буду ожидать результата тестирования. Если возможно, то также укажите характеристики своей машины.

[Igors]

Никаких проблем не возникло. Машина Intel Dual Xeon 2.6 (2х2 = 4 ядоа). Mac OSX (posix). Все компиляции в release,

493 (ms) - исходный на gcc 4.2
434  - icc 12.1

Доп тесты (icc)

161 - без qRand
517 - переставил qRand

//        qrand() % c.value(keys.at(i));
       c.value(keys.at(qrand() % keys.size()));

Разница между прогонами (для каждого варианта) незначительна (2-3 ms максимум) 

[alexis031182]

Что интересно: QHash выполняется в этом тесте за 70 мс. Для получения элемента использовал его функцию at(), которая предполагает отсутствие проверки на корректность ключа (это из Ассистента, да и практикой подтверждено).

Перегрелся вчера. У QHash нет функции at(). Используется value(). Значит, в 70 мс у QHash входит и проверка на корректность ключа.

[alexis031182]

...
Разница между прогонами (для каждого варианта) незначительна (2-3 ms максимум) 

Значит дело в машине. Только что попробовал Ваш вариант теста, разница 80-100 мс. Честно говоря, мне это непонятно.

[Igors]

Значит дело в машине. Только что попробовал Ваш вариант теста, разница 80-100 мс. Честно говоря, мне это непонятно.

По-другому ложится в процессорный кеш.

Попробовал незатейливый QHash (переделать на него оказалось очень легко). Получил

31 - sum += c.value(keys.at(i));
300 - qrand() % c.value(keys.at(i));
382 - c.value(keys.at(qrand() % keys.size()));
266 - sum += qrand() % keys.size()
 

[alexis031182]

Попробовал незатейливый QHash (переделать на него оказалось очень легко). Получил

31 - sum += c.value(keys.at(i));
300 - qrand() % c.value(keys.at(i));
382 - c.value(keys.at(qrand() % keys.size()));
266 - sum += qrand() % keys.size()

QHash:
44 - "sum += c.value(keys.at(i));"
165 - "qrand() % c.value(keys.at(i));"
186 - "c.value(keys.at(qrand() % keys.size()));"
114 - "sum += qrand() % keys.size();"

Мой хэш:
0 - "sum += c.value(keys.at(i));"
101 - "qrand() % c.value(keys.at(i));"
105 - "c.value(keys.at(qrand() % keys.size()));"
91 - "sum += qrand() % keys.size();"

[alexis031182]

...
Мой хэш:
0 - "sum += c.value(keys.at(i));"
...

И стоило только эту сумму вывести в qDebug(), то результат тут же стал 93 мс

[alexis031182]

Сконструировал ещё один хэш, почитав соответствующую литературу. Но по прежнему не могу добиться превышения скорости над QHash. Самое интересное, что вроде и логика работы контейнера такая же, и алгоритм вычисления хэша строки беру быстрее (или такой же), а результат плачевный.

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

[Igors]

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

Но совсем др дело если бы учитывалась специфика задачи, пусть небольшая загогулина но все же вне общего случая. Вот тогда возможно далеко перегнать общие/стандартные решения. Пока я такой специфики не вижу.

[alexis031182]

Непонятно на чем Вы хотите "сыграть". Др словами Вы берете общую задачу ассоциативного поиска и хотите ее ускорить. Так, на мой взгляд, шансов немного - общие вещи хорошо изучены и придумать что-то новое трудно.

Я хочу разобраться, что является ускоряющим фактором у QHash. У меня нет лишних циклов (всё как у QHash), доступ к элементам в массивах по индексу (не QList, просто массив). Логика работы контейнера, вроде бы, одинаковая.

Если беру код вычисления хэша строки из QHash, то мой контейнер работает в 3 раза медленнее. Если беру более быстрый хэш, то в 2 раза медленнее. Значит дело не в хэше. Надо найти причину, из-за которой QHash выигрывает по скорости.

Ладно уж, общую критику велосипедизма опускаем 

У меня изначально проект - велосипед

Но совсем др дело если бы учитывалась специфика задачи, пусть небольшая загогулина но все же вне общего случая. Вот тогда возможно далеко перегнать общие/стандартные решения. Пока я такой специфики не вижу.

Специфики особой нет. Известно лишь то, что ключей строго определённое кол-во, они не меняются в процессе работы приложения, и само собой изначально известны их значения. Этакий read-only контейнер.

Я пробовал соорудить Hash-контейнер для compile-time. У меня получилось. Я добился такой же скорости, как у QHash. Но там алгоритм вычисления хэша навороченный не вставить, т.к. принцип построения кода совсем другой (впрочем я уверен, что это возможно, просто недостаточно разбираюсь в этой теме). Из-за этого модернизацию compile-time хэша оставил пока до лучших времён.

Пока же задачу поставил разобраться с тонкостями QHash. Что делает его быстрее в сравнении с прямым указанием индексов в массиве?

[alexis031182]

Может ли скорость lookup'а в QHash быть выше из-за того, что ноды (Node) содержатся выравнено в памяти?

[Igors]

В какой стандартный хеш у Вас? Напр если QHash <const char *, int>, то это может оказаться совсем не то (сравниваются адреса а не содержимое)

[alexis031182]

В какой стандартный хеш у Вас? Напр если QHash <const char *, int>, то это может оказаться совсем не то (сравниваются адреса а не содержимое)

Я просто изучаю исходники QHash и вижу, что там при одном условии может использоваться выравнивание в памяти для Node, где Node - это структура, являющаяся элементом контейнера и содержащая ключ, хэш ключа и значение элемента.

Однако функция выравнивания qMallocAligned() вызывается только если __alignof__(Node) возвратит число, большее 8 байт. Глянув на свой класс Node (он аналогичен), я получил размер в 4 байта. Другими словами, выравнивание в памяти - это не то, что я ищу. Вот ведь вешалка...

[alexis031182]

В аттач проект хэша присоединил. Алгоритм вычисления хэша ключа взят у QHash. Поиск по ключу выполняется в 3 раза медленнее, нежели чем у QHash.

[Igors]

Вот я и спрашиваю с каким стандартным QHash Вы сравниваете. Если QHash <const char *, ...>, то он сравнивает адрес строки, что быстрее хотя и не то что нужно. Вычисление ключа я бы сделал так

Код

C++ (Qt)
uint32 hash( const char * str )
{
 if (!str) return 0;
 uint32 val = 0;
 char * dst = (char *) &val;
 size_t i = 0;
 while (*str) {
  dst[i] ^= *str;
  ++str;
  i = (i + 1) % sizeof(val); 
 }
 return val;
}