Более быстрый тест делимости, чем оператор%? - PullRequest
Новая
       68

Более быстрый тест делимости, чем оператор%?

23 голосов
/ 18 марта 2020

Я заметил странную вещь на моем компьютере. * Рукописный тест делимости значительно быстрее, чем оператор %. Рассмотрим минимальный пример:

* AMD Ryzen Threadripper 2990WX, G CC 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 раза быстрее.

Вопрос: Можете ли вы сказать мне, как код ведет себя на вашей машине? Это упущенная возможность оптимизации в G CC? Можете ли вы сделать этот тест еще быстрее?

ОБНОВЛЕНИЕ: По запросу приведен минимальный воспроизводимый пример: 

#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;
}

Ответы [ 2 ]

11 голосов
/ 19 марта 2020

То, что вы делаете, называется снижением прочности: замена дорогой операции на серию дешевых.

Инструкция по моду на многих процессорах медленная, потому что она исторически не тестировалась в нескольких общих тестах и ​​тестах. поэтому разработчики оптимизировали другие инструкции. Этот алгоритм будет работать хуже, если он будет выполнять много итераций, и % будет работать лучше на процессоре, где ему нужно всего два такта. деления на заданные c константы. (Хотя компиляторы обычно позаботятся об этом за вас.)

9 голосов
/ 21 марта 2020

Я сам отвечу на мой вопрос. Кажется, я стал жертвой отраслевого прогноза. Взаимный размер операндов, кажется, не имеет значения, только их порядок.

Рассмотрим следующую реализацию 

int divisible_ui_p(unsigned int m, unsigned int a)
{
    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

    return 0;
}

и массивы 

unsigned int A[100000/2];
unsigned int M[100000-1];

for (unsigned int a = 1; a < 100000; a += 2) {
    A[a/2] = a;
}
for (unsigned int m = 1; m < 100000; m += 1) {
    M[m-1] = m;
}

, которые являются / не перетасовываются с использованием функции shuffle .

Без перетасовки результаты все равно 

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.56user |
| builtin % operator |   17.59user |

Однако, как только я перетасовываю эти массивы, результаты будут другими 

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |   31.34user |
| builtin % operator |   17.53user |
...