Schnellerer Teilbarkeitstest als% Operator?

23

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 aund begrenzt m > 0. Es kann jedoch leicht auf alle aund 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 -DNDEBUGauf 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 aund 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;
}
DaBler
quelle
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Samuel Liew
Ich würde auch gerne einen Test sehen, bei dem Sie tatsächlich behaupten, dass die beiden von rIhnen berechneten s tatsächlich gleich sind.
Mike Nakis
@ MikeNakis Das habe ich gerade hinzugefügt.
DaBler
2
Die meisten realen Anwendungen von a % bhaben bviel kleiner als a. Bei den meisten Iterationen in Ihrem Testfall sind sie ähnlich groß oder bgrößer, und Ihre Version kann in diesen Situationen auf vielen CPUs schneller sein.
Matt Timmermans

Antworten:

11

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

Davislor
quelle
wurde historisch nicht in mehreren gängigen Benchmarks getestet - auch weil die Teilung von Natur aus iterativ und schwer schnell durchzuführen ist! x86 macht zumindest den Rest als Teil von div/, idivdie in Intel Penryn, Broadwell und IceLake (Hardware-Teiler mit höherem Radix) etwas Liebe gefunden haben
Peter Cordes
1
Mein Verständnis von "Kraftreduzierung" ist, dass Sie eine schwere Operation in einer Schleife durch eine einzelne leichtere Operation ersetzen, z. B. anstelle x = i * constjeder Iteration, die Sie bei x += constjeder 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."
Peter Cordes
9

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

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

und die Arrays

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

die mit der Shuffle- Funktion gemischt werden / werden .

Ohne zu mischen sind die Ergebnisse immer noch

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

Sobald ich diese Arrays mische, sind die Ergebnisse jedoch unterschiedlich

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