Я заметил любопытную вещь на моем компьютере. * Рукописный тест делимости значительно быстрее, чем %
оператор. Рассмотрим минимальный пример:
* AMD Ryzen Threadripper 2990WX, GCC 9.2.0
static int divisible_ui_p(unsigned int m, unsigned int a)
{
if (m <= a) {
if (m == a) {
return 1;
}
return 0;
}
m += a;
m >>= __builtin_ctz(m);
return divisible_ui_p(m, a);
}
Пример ограничен нечетным a
и m > 0
. Впрочем, это можно легко обобщить на все a
и m
. Код просто преобразует разделение в серию дополнений.
Теперь рассмотрим тестовую программу, скомпилированную с -std=c99 -march=native -O3
:
for (unsigned int a = 1; a < 100000; a += 2) {
for (unsigned int m = 1; m < 100000; m += 1) {
#if 1
volatile int r = divisible_ui_p(m, a);
#else
volatile int r = (m % a == 0);
#endif
}
}
... и результаты на моем компьютере:
| implementation | time [secs] |
|--------------------|-------------|
| divisible_ui_p | 8.52user |
| builtin % operator | 17.61user |
Поэтому более чем в 2 раза быстрее.
Вопрос: Можете ли вы сказать мне, как код ведет себя на вашей машине? Это упущенная возможность оптимизации в GCC? Можете ли вы сделать этот тест еще быстрее?
ОБНОВЛЕНИЕ: Как и требовалось, вот минимальный воспроизводимый пример:
#include <assert.h>
static int divisible_ui_p(unsigned int m, unsigned int a)
{
if (m <= a) {
if (m == a) {
return 1;
}
return 0;
}
m += a;
m >>= __builtin_ctz(m);
return divisible_ui_p(m, a);
}
int main()
{
for (unsigned int a = 1; a < 100000; a += 2) {
for (unsigned int m = 1; m < 100000; m += 1) {
assert(divisible_ui_p(m, a) == (m % a == 0));
#if 1
volatile int r = divisible_ui_p(m, a);
#else
volatile int r = (m % a == 0);
#endif
}
}
return 0;
}
скомпилирован gcc -std=c99 -march=native -O3 -DNDEBUG
на AMD Ryzen Threadripper 2990WX с
gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0
UPDATE2: по запросу, версия, которая может обрабатывать любые a
и m
(если вы также хотите избежать переполнения целых чисел, тест должен быть реализован с целочисленным типом, вдвое длиннее входных целых):
int divisible_ui_p(unsigned int m, unsigned int a)
{
#if 1
/* handles even a */
int alpha = __builtin_ctz(a);
if (alpha) {
if (__builtin_ctz(m) < alpha) {
return 0;
}
a >>= alpha;
}
#endif
while (m > a) {
m += a;
m >>= __builtin_ctz(m);
}
if (m == a) {
return 1;
}
#if 1
/* ensures that 0 is divisible by anything */
if (m == 0) {
return 1;
}
#endif
return 0;
}
r
которые вы вычислили, действительно равны друг другу.a % b
имеютb
гораздо меньше, чемa
. На протяжении большинства итераций в вашем тестовом примере они имеют одинаковый размер илиb
больше, и в этих ситуациях ваша версия может работать быстрее на многих процессорах.Ответы:
То, что вы делаете, называется снижением прочности: замена дорогой операции на серию дешевых.
Инструкция мода на многих процессорах медленная, потому что исторически она не тестировалась в нескольких общих тестах, и поэтому разработчики оптимизировали другие инструкции. Этот алгоритм будет работать хуже, если он будет выполнять много итераций, и
%
будет работать лучше на процессоре, где ему нужно всего два такта.Наконец, имейте в виду, что есть много горячих клавиш, чтобы взять остаток от деления на определенные константы. (Хотя компиляторы обычно позаботятся об этом за вас.)
источник
div
/idiv
которая получила некоторую любовь в Intel Penryn, Broadwell и IceLake (аппаратные делители с более высоким основанием)x = i * const
каждой итерации вы делаетеx += const
каждую итерацию. Я не думаю, что замена одного умножения на цикл сдвига / добавления будет называться снижением силы. en.wikipedia.org/wiki/… говорит, что этот термин можно использовать таким образом, но с пометкой «Этот материал оспаривается. Его лучше описать как оптимизацию глазка и назначение инструкции».Я отвечу на мой вопрос сам. Кажется, я стал жертвой отраслевого прогноза. Взаимный размер операндов, кажется, не имеет значения, только их порядок.
Рассмотрим следующую реализацию
и массивы
которые не перетасовываются с использованием функции перемешивания .
Без тасования результаты по-прежнему
Однако, как только я перетасую эти массивы, результаты будут другими
источник