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 a
i m > 0
. Można go jednak łatwo uogólnić na wszystkich a
i 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 -DNDEBUG
na 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ą a
i 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;
}
r
obliczane przez was wartości są rzeczywiście sobie równe.a % b
mab
znacznie mniej niża
. Większość iteracji w twoim przypadku testowym ma podobny rozmiar lubb
jest większa, a Twoja wersja może być szybsza na wielu procesorach w takich sytuacjach.Odpowiedzi:
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).
źródło
div
/idiv
które zyskały trochę miłości w Intel Penryn, Broadwell i IceLake (dzielniki sprzętowe o wyższej radix)x = i * const
każdej iteracji robiszx += const
każ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”.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ę
i tablice
które są / nie są tasowane za pomocą funkcji odtwarzania losowego .
Bez tasowania wyniki są nadal
Jednak po przetasowaniu tych tablic wyniki są inne
źródło