Зачем нужен остаток от деления
Операция взятия по модулю применяется для ограничения значения хэш-функции размером массива. Это делает её полезной в хэш-таблицах для выбора соответствующего бакета или в циклических структурах данных, таких как ring-buffer. Так же в некоторых алгоритмах генерации псевдослучайных чисел операция взятия по модулю используется для ограничения диапазона значений.
index = hash(key) % array_size
Но проблема в то, что операция деления на x86(и многих других архитектурах) является одной из самых медленных арифметических операций.
Деление — это сложная операция, которая требует выполнения множества шагов. Она плохо поддается конвейеризации из-за своей сложности. Процессор не может начать выполнение следующей инструкции, пока не завершит текущую операцию деления.
В итоге имеем высокую задержку(latency) и низкую пропускную способность(throughput).
На примере Intel Skylake
Целочисленное деление (DIV):
- Задержка(latency): 20-80 тактов.
- Пропускная способность(throughput): 1 операция каждые 20-80 тактов.
Умножение (MUL):
- Задержка: 3-4 такта.
- Пропускная способность: 1 операция каждые 1-2 такта.
Сложение (ADD):
- Задержка: 1 такт.
- Пропускная способность: 2 операции за такт.
Обычно вместо деления применяется битовый сдвиг
a / N == a >> N
Однако нам необходимо, чтобы размер(capacity) массива был степенью двойки. При каждом увеличении нам нужно удваивать его.
Есть альтернативный способ!
func reduce(x uint32, N uint32) uint32 {
return uint32((uint64(x) * uint64(N)) >> 32)
}
Функция отображает все значения [0,2^32] на диапазон [0,N].
При N = 8
0 [0 536_870_911]
1 [536870912 1073741823]
2 [1073741824 1610612735]
3 [1610612736 2147483647]
4 [2147483648 2684354559]
5 [2684354560 3221225471]
6 [3221225472 3758096383]
7 [3758096384 4294967295]
При N = 25
0 [0 171_798_691]
1 [171798692 343597383]
2 [343597384 515396075]
3 [515396076 687194767]
4 [687194768 858993459]
5 [858993460 1030792151]
6 [1030792152 1202590842]
7 [1202590843 1374389534]
8 [1374389535 1546188226]
9 [1546188227 1717986918]
10 [1717986919 1889785610]
11 [1889785611 2061584302]
12 [2061584303 2233382993]
13 [2233382994 2405181685]
14 [2405181686 2576980377]
15 [2576980378 2748779069]
16 [2748779070 2920577761]
17 [2920577762 3092376453]
18 [3092376454 3264175144]
19 [3264175145 3435973836]
20 [3435973837 3607772528]
21 [3607772529 3779571220]
22 [3779571221 3951369912]
23 [3951369913 4123168604]
24 [4123168605 4294967295]
Сравнение деления и умножения со сдвигом
- на Apple M3 Pro разница ~20%
- на Intel Xeon Processor (Cascadelake) разница ~260%
goos: linux
goarch: amd64
pkg: github.com/germangorelkin/sandbox/golang/fastrange
cpu: Intel Xeon Processor (Cascadelake)
Benchmark_fastsum/N=32_nmbr=500-2 2807746 424.9 ns/op
Benchmark_fastsum/N=4096_nmbr=500-2 2839779 424.1 ns/op
Benchmark_fastsum/N=65536_nmbr=500-2 2638436 461.0 ns/op
Benchmark_fastsum/N=31_nmbr=500-2 2822629 422.8 ns/op
Benchmark_fastsum/N=1500_nmbr=500-2 2824612 424.2 ns/op
Benchmark_fastsum/N=150000_nmbr=500-2 2746162 438.9 ns/op
Benchmark_modsum/N=32_nmbr=500-2 775676 1533 ns/op
Benchmark_modsum/N=4096_nmbr=500-2 761546 1534 ns/op
Benchmark_modsum/N=65536_nmbr=500-2 777290 1537 ns/op
Benchmark_modsum/N=31_nmbr=500-2 778815 1536 ns/op
Benchmark_modsum/N=1500_nmbr=500-2 775467 1524 ns/op
Benchmark_modsum/N=15000_nmbr=500-2 771380 1539 ns/op
goos: darwin
goarch: arm64
pkg: github.com/germangorelkin/sandbox/golang/fastrange
cpu: Apple M3 Pro
Benchmark_fastsum/N=32_nmbr=500-12 4877011 226.1 ns/op
Benchmark_fastsum/N=4096_nmbr=500-12 5358771 223.3 ns/op
Benchmark_fastsum/N=65536_nmbr=500-12 5364735 222.2 ns/op
Benchmark_fastsum/N=31_nmbr=500-12 5565835 223.1 ns/op
Benchmark_fastsum/N=1500_nmbr=500-12 5376478 220.0 ns/op
Benchmark_fastsum/N=150000_nmbr=500-12 5199354 221.3 ns/op
Benchmark_modsum/N=32_nmbr=500-12 4473048 268.6 ns/op
Benchmark_modsum/N=4096_nmbr=500-12 4359279 267.8 ns/op
Benchmark_modsum/N=65536_nmbr=500-12 4440230 274.6 ns/op
Benchmark_modsum/N=31_nmbr=500-12 4520017 270.9 ns/op
Benchmark_modsum/N=1500_nmbr=500-12 4502005 265.3 ns/op
Benchmark_modsum/N=15000_nmbr=500-12 4487454 276.3 ns/op
PASS
ok github.com/germangorelkin/sandbox/golang/fastrange 17.521s
Быстрый альтернативный способ выполнения операции взятия по модулю
Перевод/заметки A fast alternative to the modulo reduction
Допустим, вы хотите выбрать случайное целое число из набора из N элементов. Ваш компьютер способен генерировать случайные 32-битные целые числа, но как преобразовать их в индексы, не превышающие N?
Ещё один пример — использование хэш-таблицы с размером N. В этом случае вам также нужно преобразовать хэш-значения, которые обычно представляют собой 32- или 64-битные целые числа, в индексы, не превышающие N.
Разработчики часто решают эту проблему, гарантируя, что N является степенью двойки. Однако это не всегда идеально.
Мы стремимся создать максимально справедливое отображение для любого целого числа N. В идеале, каждому значению в диапазоне от 0 до N-1 должно соответствовать ровно 2^32/N возможных значений, если рассматривать все 2^32 32-битных целых чисел.
К сожалению, мы не можем добиться абсолютно справедливого отображения, если 2^32 не делится на N. Однако мы можем предложить следующий подход: каждому значению в диапазоне должно соответствовать либо floor(2^32/N), либо ceil(2^32/N).
Если N мало по сравнению с 2^32, то такое представление можно считать не хуже идеального.
Стандартным способом решения является операция взятия по модулю: x mod N.
uint32_t reduce(uint32_t x, uint32_t N) {
return x % N;
}
Как можно убедиться, что это работает правильно? Давайте просто пробежимся по значениям x, начиная с 0. Вы должны увидеть, что взятия по модулю принимает значения 0, 1, ..., N - 1, 0, 1, ... по мере увеличения x.
Это работает, но взятия по модулю требует деления, а деление обходится дорого. Намного дороже, чем умножение. Например, на современном процессоре x64 одно 32-битное деление выполняется по одной инструкции каждые шесть циклов с задержкой в 26 циклов. Для сравнения, умножение происходит быстрее — по одной инструкции за цикл, а задержка составляет всего три цикла.
Существуют трюки для “precompute” взятия по модулю, чтобы его можно было преобразовать в пару умножений и несколько других операций при условии, что N известно заранее. Ваш компилятор будет использовать их, если N известно на момент компиляции.
Однако оказалось, что можно сделать ещё лучше! Существует простой в реализации подход, который обеспечивает столь же качественное отображение без проблем с производительностью.
Предположим, что x и N - 32-битные целые числа, рассмотрим 64-битное произведение x * N. Получается, что (x * N) div 2^32 находится в диапазоне, и это справедливое отображение.
uint32_t reduce(uint32_t x, uint32_t N) {
return ((uint64_t) x * (uint64_t) N) >> 32 ;
}
Вычисление (x * N) div 2^32 происходит очень быстро на 64-битном процессоре. Это операция умножения с последующим сдвигом. На современном процессоре Intel я ожидаю, что её задержка составит около четырёх циклов, а пропускная способность — не менее одного вызова каждые два цикла.
Чтобы проверить это, я написал бенчмарк, в котором вы многократно обращаетесь к случайным индексам в массиве размером N. Индексы вычисляются либо с помощью операции взятия по модулю, либо с использованием нашего метода. На последнем процессоре Intel (Skylake) я получил следующие результаты: количество циклов процессора на один проход:
Как обычно, мой код находится в свободном доступе..
Если вы использовали в своих массивах и хэш-таблицах capacity, равную степени двойки, чтобы избежать дорогостоящих делений, вы можете применить быстрое отображение диапазона для поддержки произвольной ёмкости без значительного снижения производительности.
Это также позволит вам быстрее генерировать случайные числа в заданном диапазоне, что особенно важно, если у вас имеется очень быстрый генератор случайных чисел.
Как же понять, что отображение верное?
Умножая на N, мы берём целые числа из диапазона [0, 2^32) и преобразуем их в кратные N в интервале [0, N * 2^32).
Деля на 2^32, мы получаем все кратные N в диапазоне [0, 2^32) как 0, все кратные N в интервале [2^32, 2 * 2^32) — как 1, и так далее.
Чтобы проверить, правильно ли это работает, нужно просто подсчитать количество кратных N в интервалах длиной 2^32. Это количество должно быть либо ceil(2^32/N), либо floor(2^32/N).
Предположим, что первое значение в рассматриваемом интервале является кратным N. Очевидно, что такой сценарий обеспечит максимальное количество кратных в этом интервале.
Сколько кратных мы сможем обнаружить? Ответ: ровно ceil(2^32/N). Это можно понять, если разбить интервал на подынтервалы длины N. Каждый полный подынтервал будет начинаться с кратного N, а если останется остаток, то в этом подынтервале будет еще одно кратное N.
В худшем случае первое кратное N может оказаться на позиции N-1 в интервале. В этом случае мы получим floor(2^32/N) кратных. Чтобы понять, почему так происходит, снова рассмотрите подынтервалы длиной N. Каждый полный подынтервал будет заканчиваться кратным N.
Из интереса мы можем быть немного более точными. Мы уже говорили, что количество кратных максимально, когда кратное N появляется в самом начале интервала длиной 2^32. В конце этого интервала мы имеем неполный подынтервал длиной 2^32 mod N.
Если бы первое кратное N появилось не в самом начале интервала, а с индексом 2^32 mod N, то в конце не осталось бы места для неполного подынтервала. Это означает, что всякий раз, когда кратное N встречается до 2^32 mod N, мы будем иметь кратное ceil(2^32/N), а в противном случае — кратное floor(2^32/N).
Можем ли мы определить, какие результаты встречаются с частотой floor(2^32/N), а какие — с частотой ceil(2^32/N)? Да, это возможно.
Представим, что у нас есть выходное значение k. Наша цель — найти первое кратное N, которое не меньше, чем k 2^32. Это местоположение можно определить как ceil(k 2^32 / N) N – k 2^32. Затем нам нужно сравнить полученное число с 2^32 mod N. Если результат меньше, то мы имеем значение ceil(2^32/N), в противном случае — floor(2^32/N).
Комментарии в Telegram-группе!