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

[alexis031182]

...
Так что QMutex в Linux и так быстрый.

Всё же интересно посмотреть в сравнении. К тому же мой комп с интеловским процессором, и, возможно, решение Intel использует аппаратную часть по полной. Впрочем, я не сильно разбираюсь в этом, чтобы судить. Так или иначе, потестить можно. Тестировать конечно буду только Linux-субъективно.

[Igors]

То есть использовать не QList для хранения нодов, а массив, индексами которого будут являться порядковые номера букв?

Ну да. Конечно если for перебирает 2-3 элемента, то выигрыш незначителен. А вот если хотя бы 10 - уже ощутимо.

Всё же интересно посмотреть в сравнении. К тому же мой комп с интеловским процессором, и, возможно, решение Intel использует аппаратную часть по полной. Впрочем, я не сильно разбираюсь в этом, чтобы судить. Так или иначе, потестить можно. Тестировать конечно буду только Linux-субъективно.

Intel tbb поддерживает не только процессор Intel. Однако сразу тащить библиотеку совсем необязательно, атомарный лок несложно реализовать хотя бы средствами Qt. Важно что "честный" QMutex (на базе pthread_..) может оказаться капитальным "узким местом" как это случилось для одного моего проекта.

[alexis031182]

Ну да. Конечно если for перебирает 2-3 элемента, то выигрыш незначителен. А вот если хотя бы 10 - уже ощутимо.

Согласен с Вами, спасибо за очень дельный совет. Так и сделаю.

Intel tbb поддерживает не только процессор Intel.

А-а... тогда хорошо.

Однако сразу тащить библиотеку совсем необязательно, атомарный лок несложно реализовать хотя бы средствами Qt.

Я пока даже близко не подходил к этой теме.

Важно что "честный" QMutex (на базе pthread_..) может оказаться капитальным "узким местом" как это случилось для одного моего проекта.

Хм... тогда без вариантов. Буду знакомиться с этой темой.

[alexis031182]

Ну вот, ещё 5 мс отбил на тесте. Спасибо, Игорь

[DmitryM]

Важно что "честный" QMutex (на базе pthread_..) может оказаться капитальным "узким местом" как это случилось для одного моего проекта.

Не все так однозначно
Тот же pthread_mutex может не использовать системных вызовов ОС.

[alexis031182]

Пришёл к выводу, что Trie не подходит мне. Ключей не слишком много, и некоторые из них значительно отличаются друг от друга. В общем, стал разбираться с хэшем.

Как и прежде, задача заключается в максимально быстром поиске элементов контейнера по ключам.

Нарисовал следующее:

Код

C++ (Qt)
//! Функция возврата элемента.
const ValueType &value(const char *key) const {
   size_t   key_len  = strlen(key);
   uint32_t key_hash = calcHash(key, key_len);
 
   if(!_p_units.isEmpty()) {
      int val = (key_hash & 0x000000ff);
      int index = val - _lvl_min[0];
 
      //if(index >= 0/* && index < _p_units.size()*/) {
         const QVector<QVector<QVector<Unit*> > > &p_units1 = _p_units.at(index);
         val = (key_hash & 0x0000ff00) >> 8;
         index = val - _lvl_min[1];
 
         //if(index >= 0/* && index < p_units1.size()*/) {
            const QVector<QVector<Unit*> > &p_units2 = p_units1.at(index);
            val = (key_hash & 0x0000ff00) >> 16;
            index = val - _lvl_min[2];
 
            //if(index >= 0/* && index < p_units2.size()*/) {
               const QVector<Unit*> &p_units3 = p_units2.at(index);
               val = (key_hash & 0x0000ff00) >> 24;
               index = val - _lvl_min[3];
 
               //if(index >= 0/* && index < p_units3.size()*/) {
                  return p_units3.at(index)->value();
               //}
            //}
         //}
      //}
   }
 
   return ValueType();
}
 

В приведённом листинге закомментированы условия, позволяющие определить, входит ли вычисленный индекс запрашиваемого элемента в каждый из контейнеров, формирующих иерархию хэшей ключей. Если я выполняю код в таком виде, подставляя в функцию заведомо корректные ключи, то на 100000*41 (41 - кол-во элементов в контейнере) вызовов я получаю время 5 мс. Но стоит только открыть условия проверки хотя бы просто на "index >= 0", то время выполнения теста с теми же параметрами увеличивается до 96 мс. Если же полностью раскомментировать код, то вплоть до 160 мс.

Вопрос: как бы тут хитро извратиться, чтобы, сохранив скорость, обеспечить проверку вхождения индекса в диапазон?

[alexis031182]

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

Разница в 65 мс - это просто мечта!

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

[Igors]

Во все детвли не вникал, но идею понял. Имеет смысл сделать первые 4 таблицы по 256 элементов и проверяться на uint index < 256

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

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

[alexis031182]

Ёлки! Только собрался ответ написать, как объявили эвакуацию всего дома (панельная 9-ти этажка) из-за возможно заложенного взрывного устройства. Какие-то школьники развлеклись, как оказалось

Во все детвли не вникал, но идею понял. Имеет смысл сделать первые 4 таблицы по 256 элементов и проверяться на uint index < 256

Да тут получается, что как только я абсолютно любое условие вставляю - сразу значительное снижение производительности.

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

Хорошее замечание. Несомненно что-то тут запоминается машиной. Но провёл проверку - вывод перенаправил в QDebug. Результат:

QHash - 36586 мс
Мой хэш - 35472 мс
Разница - 1114 мс

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

К этому я вернусь. Раз уж затеял "разборки" с контейнерами, так и решил довести до конца.

[Igors]

Несомненно что-то тут запоминается машиной. Но провёл проверку - вывод перенаправил в QDebug. Результат:

QHash - 36586 мс
Мой хэш - 35472 мс
Разница - 1114 мс

Ну QDebug - то жирно. Поставьте нагрузку соразмеримую, напр qRand и/или acos, atan2 а еще лучше - что-нибудь из своей задачи

[alexis031182]

Ну QDebug - то жирно. Поставьте нагрузку соразмеримую, напр qRand и/или acos, atan2 а еще лучше - что-нибудь из своей задачи

Разница с qrand составила 50 мс, проверял на int'ах: QHash 150-160 мс, мой - 90-100 мс.

Мне для фабрики этот контейнер понадобится. По сути, по ключу-строке я буду вызывать функтор (рассматривали его в другой теме), который создаст экземпляр нужного класса.

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

К сожалению, пока не могу придумать как. Да и вообще непонятно, почему если я добавляю хотя бы самый простой "if", то тут же многократно падает скорость, причём хуже чем у QHash. Совсем это непонятно. Вроде ведь и не compile-time. Как это можно объяснить?

В аттаче - моя машина.

[Igors]

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

Поставить обработчики-заглушки во все остальные/пустые элементы таблицы. Заглушка переводит на др байт (если они еще есть) или возвращает "нету"

Да и вообще непонятно, почему если я добавляю хотя бы самый простой "if", то тут же многократно падает скорость, причём хуже чем у QHash. Совсем это непонятно. Вроде ведь и не compile-time. Как это можно объяснить?

Где-то удачно "легло на конвейер".

[alexis031182]

Поставить обработчики-заглушки во все остальные/пустые элементы таблицы. Заглушка переводит на др байт (если они еще есть) или возвращает "нету"

Запрашиваемый индекс может не только попадать в диапазоне на пустой указатель в таблице, но и выходить за пределы диапазона. Тут сразу приложение упадёт.

Я сделал по Вашей рекомендации для trie: вычисляю индекс в таблице указателей через минимальный символ, вместо перебора (for). Этот "символ" у меня - хэш. Точнее сказать, часть хэша. Весь хэш индексом массива не сделать, поэтому я поделил его на четыре части - байта. И вот для каждой из частей храню минимальный байт. Этот минимальный байт вычисляется при каждой вставке нового элемента в контейнер. Соответственно полностью обновляется и вся таблица указателей на элементы. Это всё делает вставку элементов довольно медленной, но мне это не принципиально.

Где-то удачно "легло на конвейер".

Надо проверить на другой машине. Можете помочь с этим? Я подготовлю код и запостю сюда.

[Igors]

Запрашиваемый индекс может не только попадать в диапазоне на пустой указатель в таблице, но и выходить за пределы диапазона.

Каким образом если байт-значения в диапазоне [0..255]?

Надо проверить на другой машине. Можете помочь с этим? Я подготовлю код и запостю сюда.

Не вопрос, но только я в роли "болванчика" Т.е. получил файлы, сделал проект из .pro, откомпилил и запустил. Что-то не идет - проблемы Ваши

[alexis031182]

Каким образом если байт-значения в диапазоне [0..255]?

Я для экономии (хотя это можно было и не делать) соорудил изменяемый минимальный символ. То есть минимальным может быть и 100, и 111, и 121, и т.п. Таким образом, таблица указателей получается меньше размером. Это конечно заставляет делать перерасчёт таблицы указателей при каждом изменении контейнера, но длительность вставки элементов в контейнер не существенна, если исходить из условий моей задачи.

Не вопрос, но только я в роли "болванчика" Т.е. получил файлы, сделал проект из .pro, откомпилил и запустил. Что-то не идет - проблемы Ваши

Спасибо. Я подготовлю полностью .pro . Единственное, я использую функцию для подсчёта длительности затраченного времени gettimeofday(). Я не знаю, есть ли она на виндовсе. Может быть тогда придётся подставить свою.