Pull to refresh

Comments 25

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

В STL-контейнерах кое-где move операции заменяются копирующими в зависимости от их noexcept'ness. Есть даже std::move_if_noexcept. Можно и тут сделать по аналогии.
switch(prime_index)
{
case 0:
    return 0llu;
case 1:
    return hash % 2llu;
case 2:
    return hash % 3llu;
// ... 
case 185:
    return hash % 14480561146010017169llu;
case 186:
    return hash % 18446744073709551557llu;
}

Это жесть. А массив вместо этого использовать нельзя?

Вряд ли оптимизатор поймёт, что развернуть hash % arr[prime_index] в switch быстрее, но проверить стоит. Я бы только сократил это до одной строки на case и, возможно, использовал макрос вида P(i, prime) case i: return hash % prime;: тогда можно несколько значений в одной строке писать.

А не подскажете почему switch быстрее? Интуитивно вроде бы должно быть наоборот… Если есть пример генерируемого кода — вообще было бы отлично, но как руки дойдут попробую сам проверить.
Интуитивно — не всегда точно. Switch может развернуться в последовательность direct mov и один jmp (если компилятор достаточно умный), что даст пару промахов конвеера в худшем случае. Чтение же из таблицы (которая скорее всего упадёт в read-only data section) даст один mov, но из memory, что подороже регистрового.
Потому и написал, что проверю как смогу. В общем проблема только в стоимости обращения к памяти/потенциальном промаха кэша… Спасибо.

Проверил, не разворачивает: для такого кода получается такой листинг, скомпилировано gcc-5.4.0 -O3 -std=c++11 primes.cpp -c -S: заинлайнил вариант с массивом, в нём виден divq и обращение к массиву. Весь вопрос в том, сколько тактов займёт divq, а сколько — jmp+оптимизации компилятора. Пока switch влезает в кэш, а выигрыш по тактам перекрывает то, что предсказатель переходов почти наверняка провалится — всё должно быть хорошо. Вот почему конкретно divq медленная я не знаю, но сделать даже целочисленное деление в микропроцессорах всегда было сложно.

Да, по факту, в профайлере, всё дело в делении, один сброс конвейера + деление на константу дешевле честного деления.
Да уж что может быть быстрее, чем взятие элемента массива? Компилятор себе наверняка составит массив меток и будет по ним переходить, в результате будет две операции вместо одной.
Каждый из вариантов — целое число по модулю на основе статической константы. Чем это хорошо? Если использовать константу, то компилятор применит кучу оптимизаций для ускорения вычисления. Для каждого из вариантов вы получаете кастомный ассемблерный код, который будет работать гораздо быстрее, чем целое число по модулю. Выглядит несколько безумно, но даёт огромный прирост скорости.

Я так понимаю, тут утверждается, что операция получения остатка от деления долгая, и в случае с константой компилятор сможет заменить деление на что-нибудь более быстрое.

Я ради интереса скомпилировал тот кусок кода с gcc и посмотрел, что получилось.


Код
unsigned long long getHash(unsigned long long hash, int prime_index){
    switch(prime_index){
    case 0:
        return 0llu;
    case 1:
        return hash % 2llu;
    case 2:
        return hash % 3llu;
    case 3:
        return hash % 5llu;
    case 4:
        return hash % 7llu;
    case 5:
        return hash % 11llu;
    case 6:
        return hash % 13llu;
    case 7:
        return hash % 17llu;
    case 8:
        return hash % 23llu;
    case 9:
        return hash % 29llu;
    case 10:
        return hash % 37llu;
    case 11:
        return hash % 47llu;
    case 12:
        return hash % 59llu;
    case 13:
        return hash % 14480561146010017169llu;
    case 14:
        return hash % 18446744073709551557llu;
    }
    return 0;
}

собрать можно командой типа: gcc -O2 -o o2.o -c code.c
посмотреть objdump -d o2.o
Скомпилированный код с любой опцией, кроме -Os, вместо каждого взятия остатка содержит кучку инструкций:


objdump для o3
o3.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <getHash>:
   0:   83 fe 0e                cmp    $0xe,%esi
   3:   77 0b                   ja     10 <getHash+0x10>
   5:   89 f6                   mov    %esi,%esi
   7:   ff 24 f5 00 00 00 00    jmpq   *0x0(,%rsi,8)
   e:   66 90                   xchg   %ax,%ax
  10:   31 c0                   xor    %eax,%eax
  12:   c3                      retq   
  13:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  18:   48 89 f8                mov    %rdi,%rax
  1b:   83 e0 01                and    $0x1,%eax
  1e:   c3                      retq   
  1f:   90                      nop
  20:   48 89 f8                mov    %rdi,%rax
  23:   48 ba ab aa aa aa aa    movabs $0xaaaaaaaaaaaaaaab,%rdx
  2a:   aa aa aa 
  2d:   48 f7 e2                mul    %rdx
  30:   48 89 d0                mov    %rdx,%rax
  33:   48 d1 e8                shr    %rax
  36:   48 8d 04 40             lea    (%rax,%rax,2),%rax
  3a:   48 29 c7                sub    %rax,%rdi
  3d:   48 89 f8                mov    %rdi,%rax
  40:   c3                      retq   
  41:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  48:   48 89 f8                mov    %rdi,%rax
  4b:   48 ba cd cc cc cc cc    movabs $0xcccccccccccccccd,%rdx
  52:   cc cc cc 
  55:   48 f7 e2                mul    %rdx
  58:   48 89 d0                mov    %rdx,%rax
  5b:   48 c1 e8 02             shr    $0x2,%rax
  5f:   48 8d 04 80             lea    (%rax,%rax,4),%rax
  63:   48 29 c7                sub    %rax,%rdi
  66:   48 89 f8                mov    %rdi,%rax
  69:   c3                      retq   
  6a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  70:   48 89 f8                mov    %rdi,%rax
  73:   48 ba 93 24 49 92 24    movabs $0x2492492492492493,%rdx
  7a:   49 92 24 
  7d:   48 f7 e2                mul    %rdx
  80:   48 89 f8                mov    %rdi,%rax
  83:   48 29 d0                sub    %rdx,%rax
  86:   48 d1 e8                shr    %rax
  89:   48 01 c2                add    %rax,%rdx
  8c:   48 89 d0                mov    %rdx,%rax
  8f:   48 c1 e8 02             shr    $0x2,%rax
  93:   48 8d 14 c5 00 00 00    lea    0x0(,%rax,8),%rdx
  9a:   00 
  9b:   48 29 c2                sub    %rax,%rdx
  9e:   48 29 d7                sub    %rdx,%rdi
  a1:   48 89 f8                mov    %rdi,%rax
  a4:   c3                      retq   
  a5:   0f 1f 00                nopl   (%rax)
  a8:   48 89 f8                mov    %rdi,%rax
  ab:   48 ba a3 8b 2e ba e8    movabs $0x2e8ba2e8ba2e8ba3,%rdx
  b2:   a2 8b 2e 
  b5:   48 f7 e2                mul    %rdx
  b8:   48 89 d0                mov    %rdx,%rax
  bb:   48 d1 e8                shr    %rax
  be:   48 8d 14 80             lea    (%rax,%rax,4),%rdx
  c2:   48 8d 04 50             lea    (%rax,%rdx,2),%rax
  c6:   48 29 c7                sub    %rax,%rdi
  c9:   48 89 f8                mov    %rdi,%rax
  cc:   c3                      retq   
  cd:   0f 1f 00                nopl   (%rax)
  d0:   48 89 f8                mov    %rdi,%rax
  d3:   48 ba c5 4e ec c4 4e    movabs $0x4ec4ec4ec4ec4ec5,%rdx
  da:   ec c4 4e 
  dd:   48 f7 e2                mul    %rdx
  e0:   48 89 d0                mov    %rdx,%rax
  e3:   48 c1 e8 02             shr    $0x2,%rax
  e7:   48 8d 14 40             lea    (%rax,%rax,2),%rdx
  eb:   48 8d 04 90             lea    (%rax,%rdx,4),%rax
  ef:   48 29 c7                sub    %rax,%rdi
  f2:   48 89 f8                mov    %rdi,%rax
  f5:   c3                      retq   
  f6:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  fd:   00 00 00 
 100:   48 89 f8                mov    %rdi,%rax
 103:   48 ba f1 f0 f0 f0 f0    movabs $0xf0f0f0f0f0f0f0f1,%rdx
 10a:   f0 f0 f0 
 10d:   48 f7 e2                mul    %rdx
 110:   48 89 d0                mov    %rdx,%rax
 113:   48 c1 e8 04             shr    $0x4,%rax
 117:   48 89 c2                mov    %rax,%rdx
 11a:   48 c1 e2 04             shl    $0x4,%rdx
 11e:   48 01 c2                add    %rax,%rdx
 121:   48 89 f8                mov    %rdi,%rax
 124:   48 29 d0                sub    %rdx,%rax
 127:   c3                      retq   
 128:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
 12f:   00 
 130:   48 89 f8                mov    %rdi,%rax
 133:   48 ba c9 42 16 b2 90    movabs $0x642c8590b21642c9,%rdx
 13a:   85 2c 64 
 13d:   48 f7 e2                mul    %rdx
 140:   48 89 f8                mov    %rdi,%rax
 143:   48 29 d0                sub    %rdx,%rax
 146:   48 d1 e8                shr    %rax
 149:   48 01 c2                add    %rax,%rdx
 14c:   48 89 d0                mov    %rdx,%rax
 14f:   48 c1 e8 04             shr    $0x4,%rax
 153:   48 8d 14 40             lea    (%rax,%rax,2),%rdx
 157:   48 c1 e2 03             shl    $0x3,%rdx
 15b:   48 29 c2                sub    %rax,%rdx
 15e:   48 29 d7                sub    %rdx,%rdi
 161:   48 89 f8                mov    %rdi,%rax
 164:   c3                      retq   
 165:   0f 1f 00                nopl   (%rax)
 168:   48 89 f8                mov    %rdi,%rax
 16b:   48 ba 1b 61 b9 a7 11    movabs $0x1a7b9611a7b9611b,%rdx
 172:   96 7b 1a 
 175:   48 f7 e2                mul    %rdx
 178:   48 89 f8                mov    %rdi,%rax
 17b:   48 29 d0                sub    %rdx,%rax
 17e:   48 d1 e8                shr    %rax
 181:   48 01 c2                add    %rax,%rdx
 184:   48 89 d0                mov    %rdx,%rax
 187:   48 c1 e8 04             shr    $0x4,%rax
 18b:   48 8d 14 c5 00 00 00    lea    0x0(,%rax,8),%rdx
 192:   00 
 193:   48 29 c2                sub    %rax,%rdx
 196:   48 8d 04 90             lea    (%rax,%rdx,4),%rax
 19a:   48 29 c7                sub    %rax,%rdi
 19d:   48 89 f8                mov    %rdi,%rax
 1a0:   c3                      retq   
 1a1:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
 1a8:   48 89 f8                mov    %rdi,%rax
 1ab:   48 ba 8b 7c d6 0d a6    movabs $0xdd67c8a60dd67c8b,%rdx
 1b2:   c8 67 dd 
 1b5:   48 f7 e2                mul    %rdx
 1b8:   48 89 d0                mov    %rdx,%rax
 1bb:   48 c1 e8 05             shr    $0x5,%rax
 1bf:   48 8d 14 c0             lea    (%rax,%rax,8),%rdx
 1c3:   48 8d 04 90             lea    (%rax,%rdx,4),%rax
 1c7:   48 29 c7                sub    %rax,%rdi
 1ca:   48 89 f8                mov    %rdi,%rax
 1cd:   c3                      retq   
 1ce:   66 90                   xchg   %ax,%ax
 1d0:   48 89 f8                mov    %rdi,%rax
 1d3:   48 ba 63 72 05 31 b9    movabs $0x5c9882b931057263,%rdx
 1da:   82 98 5c 
 1dd:   48 f7 e2                mul    %rdx
 1e0:   48 89 f8                mov    %rdi,%rax
 1e3:   48 29 d0                sub    %rdx,%rax
 1e6:   48 d1 e8                shr    %rax
 1e9:   48 01 c2                add    %rax,%rdx
 1ec:   48 89 d0                mov    %rdx,%rax
 1ef:   48 c1 e8 05             shr    $0x5,%rax
 1f3:   48 8d 14 40             lea    (%rax,%rax,2),%rdx
 1f7:   48 c1 e2 04             shl    $0x4,%rdx
 1fb:   48 29 c2                sub    %rax,%rdx
 1fe:   48 29 d7                sub    %rdx,%rdi
 201:   48 89 f8                mov    %rdi,%rax
 204:   c3                      retq   
 205:   0f 1f 00                nopl   (%rax)
 208:   48 89 f8                mov    %rdi,%rax
 20b:   48 ba 23 68 38 a9 fb    movabs $0x8ad8f2fba9386823,%rdx
 212:   f2 d8 8a 
 215:   48 f7 e2                mul    %rdx
 218:   48 89 d0                mov    %rdx,%rax
 21b:   48 c1 e8 05             shr    $0x5,%rax
 21f:   48 8d 0c 85 00 00 00    lea    0x0(,%rax,4),%rcx
 226:   00 
 227:   48 89 c2                mov    %rax,%rdx
 22a:   48 c1 e2 06             shl    $0x6,%rdx
 22e:   48 29 ca                sub    %rcx,%rdx
 231:   48 29 c2                sub    %rax,%rdx
 234:   48 29 d7                sub    %rdx,%rdi
 237:   48 89 f8                mov    %rdi,%rax
 23a:   c3                      retq   
 23b:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
 240:   48 ba 91 1d 40 18 a4    movabs $0xc8f549a418401d91,%rdx
 247:   49 f5 c8 
 24a:   31 c0                   xor    %eax,%eax
 24c:   48 39 d7                cmp    %rdx,%rdi
 24f:   0f 93 c0                setae  %al
 252:   48 0f af d0             imul   %rax,%rdx
 256:   48 89 f8                mov    %rdi,%rax
 259:   48 29 d0                sub    %rdx,%rax
 25c:   c3                      retq   
 25d:   0f 1f 00                nopl   (%rax)
 260:   31 c0                   xor    %eax,%eax
 262:   48 83 ff c5             cmp    $0xffffffffffffffc5,%rdi
 266:   0f 93 c0                setae  %al
 269:   48 6b d0 c5             imul   $0xffffffffffffffc5,%rax,%rdx
 26d:   48 89 f8                mov    %rdi,%rax
 270:   48 29 d0                sub    %rdx,%rax
 273:   c3                      retq   
Не стоит считать производительность по количеству инструкций. Одна инструкция div (divq) требует десятки тактов, тогда как большинство битовых — 1 такт.
Есть даже такое чудо как https://github.com/ridiculousfish/libdivide

Это библиотека, которая реализует… целочисленное деление на константу… как умножение со сдвигом.

Ну почему "даже" :) Что деление через умножение выгоднее, если деление на выбранный делитель делается хотя бы 2-3 раза, известно достаточно давно (с тех пор, как появилось O(1) умножение). Выбирая делитель (размер таблицы у ТС), можно вычислить необходимые параметры (в простейшем случае — множитель, величину финального сдвига и направление округления) и запомнить их до следующей смены размера.
Библиотека по ссылке значительно более продвинута, и может оказаться оверкиллом. Но по крайней мере сильно быстрее divl/divq каждый раз :)

Для реализаций хэш-таблиц — самое то, пожалуй!
Обычное деление выполняется со скоростью 1 бит за такт. Поскольку ALU сейчас работает на удвоенной частоте, в итоге имеем 2 бита за такт. Но в 32-битном режиме делимое имеет размер 64 бита (edx:eax), а в 64-битном вообще 128 бит, поэтому операция деления может длиться весьма долго (из Intel AORM: For dividend value greater than 64-bits, the latency can range from 70-90 cycles). Если же деление происходит на константу, то обычно компилятор может заменить его на умножение (п. 9.2.4 Intel AORM), которое выполняется в разы быстрее (единицы тактов). Поэтому получается, что ошибка в переходе + десяток инструкций (которые могут выполняться по несколько за такт) в итоге могут оказаться быстрее одной операции деления. Хотя вот этот момент было бы интересно увидеть на практике — насколько быстрее, стоит ли это того.
Так что если вы вставляете целочисленные значения, то 1 байт получит ещё 3 байта паддинга, в результате выйдет 4 байта накладных расходов на каждый элемент. Если вы вставляете указатели, то паддинг будет уже 7 байтов, получаем 8 байтов накладных расходов.

Пожалуйста, можете пояснить? Почему с указателями будет паддинг 7байтов? Размер указателя на сколько помню 4байта для 32х и 8байтов для 64х
Именно. Получаем 8 байт на элемент, 1 байт «системный», и ещё 7 байт смещения т.к. следующий элемент должен быть выравнен на 8 байт.
Товарищу конечно надо было брать не список простых чисел, а просто перехешировать хэш полиномом на простом числе. Сейчас он делает h mod p, что блин дорого. Надо вместо этого использовать ну например (h * 137) mod 2^n на таблице размером 2^n, что очень дёшево. Умножение на 137 это два сдвига и два сложения, остаток от деления на 2^n это один AND. При этом они взаимно простые (размазывание по таблице будет равномерным), и очень сложно представить данные с периодом 137. При росте таблицы можно брать более длинные простые числа в качестве полиномов.
По сути таблица растёт пока максимальный список коллизий не будет размещён практически линейно. Конечно это будет быстро… если хватит памяти. Робин Гуд помогает, но незначительно. Ну т.е. вот есть какое-то распределение, получаем коллизию, локальное уплотнение занятых слотов превышает максимальный lookup range, таблица растёт. При росте получаем совершенно новое распределение и никто не гарантирует что в нём не получится нового плотного места которое в свою очередь приведёт к новому росту и т.д. Слишком всё случайно. Даже коллизий много не надо, потому что рост таблицы происходит не просто из-за коллизии а из-за неукладывания в lookup range. Т.е. на небольших объёмах оно конечно дорастает до состояния perfect hash, но вот на 20 миллионах данных с достаточно хорошим распределением я протестировать таблицу так и не смог, вероятность локальных уплотнений растёт, что приводит к постоянному росту таблицы, просто памяти не хватило.
Таблица имеет тенденцию к росту если в ней есть хоть один непрерывно занятый диапазон, длина которого превышает lookup range. Вероятность того, что слот будет иметь тенденцию к росту всегда ненулевая если число занятых слотов превышает диапазон поиска. Можно её даже посчитать, — если рассматривать свободные слоты как случайную выборку на диапазоне, это вероятность того, что максимальное расстояние между соседними элементами в ней будет больше чем lookup range. Т.е. вероятность того, что при выборке K из N элементов ни один из них не попадет в произвольно выбранный диапазон длины R. Комбинаторика, берем число сочетаний из N по K, вычитаем число сочетаний из (N-R) по K, соотносим. В общем там куча восклицательных знаков, ну да это и неважно. Интуитивно понятно что она инвариант при масштабировании. Т.е. даже чтобы сохранить эту вероятность, таблица и диапазон должны расти пропорционально. Но диапазон рассчитывается как логарифм от размера таблицы, т.е. имеет арифметическую прогрессию при геометрической прогрессии роста таблицы. Поэтому с ростом таблицы вероятность попасть на слот с тенденцией к росту растет.
Кстати, в этой таблице rehash рекурсивный.
> Итак, max_load_factor у всех равен 0,5, и я хотел измерить скорость работы
Здесь лукавство, соотносить скорость надо не при равном max_load_factor, т.к. данная таблица растёт не только в зависимости от него. Сравнивать можно только при равном bucket_count.
Может я что-то не так делаю, но статистика соотношения load_factоr при вставке одинакового количества элементов по сравнению с unordered_map (MS, по степени двойки) у меня получается такая:
1000000 — 0.48 против 0.95
2000000 — 0.24 против 0.95
4000000 — 0.12 против 0.95
8000000 — 0.06 против 0.95 — (!!! 16 кратный запас, сравнивать можно если делать reserve(16X))

> Но если вас не смущает возможность неожиданного перераспределения
Если не смущает, что при некотором «везении» этот контейнер может съесть всю доступную память.

а если добавить критерий «перераспределять, если процент заполнения не менее N»? В таком случае будет медленнее работать на тех данных, которые потенциально сожрут всю оперативку, и (примерно) так же для более-менее равномерно распределенных величин
Перераспределение связано с увеличением lookup range, это ограничение поиска. Ну и вставка не произойдет пока перераспределение не приведёт к тому что место вставки не окажется в пределах lookup range от начального слота. А данные и так хорошо распределены, большая часть без коллизий вообще ну и допустим меньше процента с глубиной списка коллизий до 6. Но вот этот самый один процент при большом количестве данных всегда ведёт к росту.
Sign up to leave a comment.