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;
: тогда можно несколько значений в одной строке писать.
Проверил, не разворачивает: для такого кода получается такой листинг, скомпилировано 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, вместо каждого взятия остатка содержит кучку инструкций:
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
Это библиотека, которая реализует… целочисленное деление на константу… как умножение со сдвигом.
Ну почему "даже" :) Что деление через умножение выгоднее, если деление на выбранный делитель делается хотя бы 2-3 раза, известно достаточно давно (с тех пор, как появилось O(1) умножение). Выбирая делитель (размер таблицы у ТС), можно вычислить необходимые параметры (в простейшем случае — множитель, величину финального сдвига и направление округления) и запомнить их до следующей смены размера.
Библиотека по ссылке значительно более продвинута, и может оказаться оверкиллом. Но по крайней мере сильно быстрее divl/divq каждый раз :)
Так что если вы вставляете целочисленные значения, то 1 байт получит ещё 3 байта паддинга, в результате выйдет 4 байта накладных расходов на каждый элемент. Если вы вставляете указатели, то паддинг будет уже 7 байтов, получаем 8 байтов накладных расходов.
Пожалуйста, можете пояснить? Почему с указателями будет паддинг 7байтов? Размер указателя на сколько помню 4байта для 32х и 8байтов для 64х
Кстати, в этой таблице rehash рекурсивный.
Здесь лукавство, соотносить скорость надо не при равном 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))
> Но если вас не смущает возможность неожиданного перераспределения
Если не смущает, что при некотором «везении» этот контейнер может съесть всю доступную память.
Я написал самую быструю хеш-таблицу