Szybszy test podzielności niż operator%?

Zauważyłem ciekawą rzecz na moim komputerze. ^* Odręczny test podzielności jest znacznie szybszy niż %operator. Rozważ minimalny przykład:

^{* _{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);
}

Przykład jest ograniczony przez nieparzyste ai m > 0. Można go jednak łatwo uogólnić na wszystkich ai m. Kod po prostu przekształca podział na serię dodatków.

Teraz rozważ program testowy skompilowany z -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
        }
    }

... i wyniki na moim komputerze:

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.52user |
| builtin % operator |   17.61user |

Dlatego ponad 2 razy szybciej.

Pytanie: Czy możesz mi powiedzieć, jak kod zachowuje się na twoim komputerze? Czy przegapiono okazję do optymalizacji w GCC? Czy możesz zrobić ten test jeszcze szybciej?

AKTUALIZACJA: Zgodnie z życzeniem, oto minimalny odtwarzalny przykład:

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

skompilowany z gcc -std=c99 -march=native -O3 -DNDEBUGna AMD Ryzen Threadripper 2990WX z

gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0

AKTUALIZACJA 2: Zgodnie z żądaniem, wersja, która może obsłużyć dowolną ai m(jeśli chcesz również uniknąć przepełnienia liczb całkowitych, test należy zaimplementować z typem całkowitym dwa razy dłuższym niż liczby całkowite wejściowe):

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

To, co robisz, nazywa się redukcją siły: zastępując kosztowną operację serią tanich.

Instrukcja mod na wielu procesorach jest powolna, ponieważ historycznie nie była testowana w kilku popularnych testach porównawczych, dlatego projektanci zoptymalizowali inne instrukcje. Algorytm ten będzie działał gorzej, jeśli będzie musiał wykonać wiele iteracji, i %będzie działał lepiej na procesorze, w którym potrzebuje tylko dwóch cykli zegara.

Na koniec należy pamiętać, że istnieje wiele skrótów, które pozwalają wykorzystać pozostałą część podziału według określonych stałych. (Chociaż kompilatory zazwyczaj zajmą się tym za Ciebie).

Sam odpowiem na moje pytanie. Wygląda na to, że padłem ofiarą przewidywania gałęzi. Wzajemna wielkość operandów nie wydaje się mieć znaczenia, tylko ich kolejność.

Rozważ następującą implementację

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

i tablice

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

które są / nie są tasowane za pomocą funkcji odtwarzania losowego .

Bez tasowania wyniki są nadal

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

Jednak po przetasowaniu tych tablic wyniki są inne

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