Ich bemerkte eine merkwürdige Sache auf meinem Computer. * Der handschriftliche Teilbarkeitstest ist deutlich schneller als der %
Bediener. Betrachten Sie das minimale Beispiel:
* 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);
}
Das Beispiel ist durch ungerade a
und begrenzt m > 0
. Es kann jedoch leicht auf alle a
und verallgemeinert werden m
. Der Code konvertiert nur die Unterteilung in eine Reihe von Ergänzungen.
Betrachten Sie nun das Testprogramm, das kompiliert wurde mit -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
}
}
... und die Ergebnisse auf meinem Computer:
| implementation | time [secs] |
|--------------------|-------------|
| divisible_ui_p | 8.52user |
| builtin % operator | 17.61user |
Daher mehr als 2 mal schneller.
Die Frage: Können Sie mir sagen, wie sich der Code auf Ihrem Computer verhält? Wird die Optimierungsmöglichkeit in GCC verpasst? Können Sie diesen Test noch schneller durchführen?
UPDATE: Wie angefordert, ist hier ein minimal reproduzierbares Beispiel:
#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;
}
kompiliert mit gcc -std=c99 -march=native -O3 -DNDEBUG
auf AMD Ryzen Threadripper 2990WX mit
gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0
UPDATE2: Wie angefordert, die Version, die alle verarbeiten kann a
und m
(wenn Sie auch einen Ganzzahlüberlauf vermeiden möchten, muss der Test mit einem ganzzahligen Typ implementiert werden, der doppelt so lang ist wie die eingegebenen Ganzzahlen):
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
Ihnen berechneten s tatsächlich gleich sind.a % b
habenb
viel kleiner alsa
. Bei den meisten Iterationen in Ihrem Testfall sind sie ähnlich groß oderb
größer, und Ihre Version kann in diesen Situationen auf vielen CPUs schneller sein.Antworten:
Was Sie tun, heißt Festigkeitsreduzierung: Ersetzen einer teuren Operation durch eine Reihe billiger.
Die Mod-Anweisung auf vielen CPUs ist langsam, da sie in der Vergangenheit nicht in mehreren gängigen Benchmarks getestet wurde und die Entwickler daher stattdessen andere Anweisungen optimiert haben. Dieser Algorithmus ist schlechter, wenn er viele Iterationen
%
ausführen muss , und besser auf einer CPU, auf der nur zwei Taktzyklen benötigt werden.Beachten Sie schließlich, dass es viele Verknüpfungen gibt, um den Rest der Division durch bestimmte Konstanten zu übernehmen. (Obwohl Compiler dies in der Regel für Sie erledigen.)
quelle
div
/,idiv
die in Intel Penryn, Broadwell und IceLake (Hardware-Teiler mit höherem Radix) etwas Liebe gefunden habenx = i * const
jeder Iteration, die Sie beix += const
jeder Iteration durchführen. Ich denke nicht, dass das Ersetzen einer einzelnen Multiplikation durch eine Shift / Add-Schleife als Kraftreduzierung bezeichnet wird. en.wikipedia.org/wiki/… sagt, dass der Begriff möglicherweise auf diese Weise verwendet werden kann, aber mit dem Hinweis "Dieses Material ist umstritten. Es wird besser als Gucklochoptimierung und Anweisungszuweisung beschrieben."Ich werde meine Frage selbst beantworten. Es scheint, dass ich ein Opfer der Branchenvorhersage geworden bin. Die gegenseitige Größe der Operanden scheint keine Rolle zu spielen, nur ihre Reihenfolge.
Betrachten Sie die folgende Implementierung
und die Arrays
die mit der Shuffle- Funktion gemischt werden / werden .
Ohne zu mischen sind die Ergebnisse immer noch
Sobald ich diese Arrays mische, sind die Ergebnisse jedoch unterschiedlich
quelle