Szybszy test podzielności niż operator%?

23

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;
}
DaBler
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Samuel Liew
Chciałbym również zobaczyć test, w którym faktycznie stwierdzacie, że te dwa robliczane przez was wartości są rzeczywiście sobie równe.
Mike Nakis
@MikeNakis Właśnie to dodałem.
DaBler
2
Większość rzeczywistych zastosowań a % bma bznacznie mniej niż a. Większość iteracji w twoim przypadku testowym ma podobny rozmiar lub bjest większa, a Twoja wersja może być szybsza na wielu procesorach w takich sytuacjach.
Matt Timmermans

Odpowiedzi:

11

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).

Davislor
źródło
historycznie nie był testowany w kilku popularnych testach porównawczych - również dlatego, że podział jest z natury iteracyjny i trudny do szybkiego! x86 przynajmniej pozostała jako część div/ idivktóre zyskały trochę miłości w Intel Penryn, Broadwell i IceLake (dzielniki sprzętowe o wyższej radix)
Peter Cordes
1
Rozumiem, że „redukcja siły” polega na tym, że ciężką operację w pętli zastępujesz jedną lżejszą operacją, np. Zamiast x = i * constkażdej iteracji robisz x += constkażdą iterację. Nie sądzę, aby zastąpienie pojedynczego mnożenia pętlą shift / add nazywało się redukcją siły. en.wikipedia.org/wiki/… mówi, że termin ten może być używany w ten sposób, ale z dopiskiem „Ten materiał jest kwestionowany. Lepiej jest opisany jako optymalizacja wizjera i przydzielanie instrukcji”.
Peter Cordes
9

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 |
DaBler
źródło