Ist es besser, den Mod-Operator möglichst zu vermeiden?

Ich nehme an, dass die Berechnung des Moduls einer Zahl eine ziemlich teure Operation ist, zumindest im Vergleich zu einfachen arithmetischen Tests (wie zum Beispiel zu sehen, ob eine Zahl die Länge eines Arrays überschreitet). Wenn dies tatsächlich der Fall ist, ist es effizienter, beispielsweise den folgenden Code zu ersetzen:

res = array[(i + 1) % len];

mit den folgenden? :

res = array[(i + 1 == len) ? 0 : i + 1];

Der erste ist angenehmer für die Augen, aber ich frage mich, ob der zweite effizienter sein könnte. Wenn ja, kann ich erwarten, dass ein optimierender Compiler das erste Snippet durch das zweite ersetzt, wenn eine kompilierte Sprache verwendet wird?

Natürlich funktioniert diese “Optimierung” (sofern es sich tatsächlich um eine Optimierung handelt) nicht in allen Fällen (in diesem Fall funktioniert sie nur, wenn i+1 ist nie mehr als len).

Mein allgemeiner Rat lautet wie folgt. Verwenden Sie die Version, die Ihrer Meinung nach für das Auge angenehmer ist, und profilieren Sie dann Ihr gesamtes System. Optimieren Sie nur die Teile des Codes, die der Profiler als Engpässe kennzeichnet. Ich wette meinen letzten Dollar, dass der Modulo-Operator nicht darunter sein wird.

Was das spezifische Beispiel angeht, kann nur Benchmarking sagen, was auf Ihrer spezifischen Architektur mit Ihrem spezifischen Compiler schneller ist. Sie ersetzen möglicherweise Modulo durch Verzweigungund es ist alles andere als offensichtlich, was schneller wäre.

Einige einfache Messungen:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int test = atoi(argv[1]);
    int divisor = atoi(argv[2]);
    int iterations = atoi(argv[3]);

    int a = 0;

    if (test == 0) {
        for (int i = 0; i < iterations; i++)
            a = (a + 1) % divisor;
    } else if (test == 1) {
        for (int i = 0; i < iterations; i++)
            a = a + 1 == divisor ? 0 : a + 1;
    }

    printf("%d\n", a);
}

Kompilieren entweder mit gcc oder clang with -O3und läuft time ./a.out 0 42 1000000000 (Modulo-Version) bzw time ./a.out 1 42 1000000000 (Vergleichsversion) ergibt

• 6,25 Sekunden Benutzerlaufzeit für die Modulo-Version,
• 1,03 Sekunden für die Vergleichsversion.

(unter Verwendung von gcc 5.2.1 oder clang 3.6.2; Intel Core i5-4690K @ 3,50 GHz; 64-Bit-Linux)

Das bedeutet, dass es wahrscheinlich eine gute Idee ist, die Vergleichsversion zu verwenden.

Schauen Sie sich 2 Möglichkeiten an, um den nächsten Wert eines zyklischen “Modulo 3” -Zählers zu erhalten.

int next1(int n) {
    return (n + 1) % 3;
}

int next2(int n) {
    return n == 2 ? 0 : n + 1;
}

Ich habe es mit der Option gcc -O3 (für die gängige x64-Architektur) und -s kompiliert, um den Assemblercode zu erhalten.

Der Code für die erste Funktion bewirkt unerklärliche Magie

addl    $1, %edi
movl    $1431655766, %edx
movl    %edi, %eax
imull   %edx
movl    %edi, %eax
sarl    $31, %eax
subl    %eax, %edx
leal    (%rdx,%rdx,2), %eax
subl    %eax, %edi
movl    %edi, %eax
ret

Um eine Division zu vermeiden, verwenden Sie trotzdem eine Multiplikation:

leal    1(%rdi), %eax
cmpl    $2, %edi
movl    $0, %edx
cmove   %edx, %eax
ret

Und ist viel länger (und ich wette langsamer) als die zweite Funktion:

Es stimmt also nicht immer, dass “der (moderne) Compiler sowieso einen besseren Job macht als Sie”.

addl    $1, %edi
movl    %edi, %edx
sarl    $31, %edx
shrl    $30, %edx
leal    (%rdi,%rdx), %eax
andl    $3, %eax
subl    %edx, %eax
ret

Interessanterweise führt das gleiche Experiment mit 4 statt 3 zu einer Und-Maskierung für die erste Funktion

aber es ist immer noch und im Großen und Ganzen der zweiten Version unterlegen.

int next3(int n) {
    return (n + 1) & 3;;
}

Deutlicher über die richtige Art und Weise, die Dinge zu tun, sprechen

leal    1(%rdi), %eax
andl    $3, %eax
ret

liefert deutlich bessere Ergebnisse:

– mtraceur

#include <iostream>
#include <array>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std::chrono;

constexpr size_t iter = 1e8;

int main() {
  std::minstd_rand rnd_engine{1234};
  std::uniform_int_distribution<int> dist {-1000, 1000};
  auto gen = [&]() { return dist(rnd_engine); };

  std::array<int, 10> a;
  std::generate( a.begin(), a.end(), gen);

  for (size_t size = 2; size < 10; size++) {
    std::cout << "Modulus size = " << size << '\n';
  
    {
      std::cout << "operator%  ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = (x + 1) % size;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
  
    {
      std::cout << "ternary    ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = ((x + 1) == size) ? 0 : x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
    
    {
      std::cout << "branchless ";
      long sum = 0;
      size_t x = 1;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x-1];
        x = ( x != size ) * x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }

  }
  return 0;
}

1. Oktober 2020 um 1:08 Uhr

$ g++ -Ofast test.cpp && ./a.out
Modulus size = 2
operator%  904.249ms    (sum = -4200000000)
ternary    137.04ms     (sum = -4200000000)
branchless 169.182ms    (sum = -4200000000)
Modulus size = 3
operator%  914.911ms    (sum = -31533333963)
ternary    113.384ms    (sum = -31533333963)
branchless 167.614ms    (sum = -31533333963)
Modulus size = 4
operator%  877.3ms      (sum = -36250000000)
ternary    97.265ms     (sum = -36250000000)
branchless 167.215ms    (sum = -36250000000)
Modulus size = 5
operator%  891.295ms    (sum = -30700000000)
ternary    88.562ms     (sum = -30700000000)
branchless 167.087ms    (sum = -30700000000)
Modulus size = 6
operator%  903.644ms    (sum = -39683333196)
ternary    83.433ms     (sum = -39683333196)
branchless 167.778ms    (sum = -39683333196)
Modulus size = 7
operator%  908.096ms    (sum = -34585713678)
ternary    79.703ms     (sum = -34585713678)
branchless 166.849ms    (sum = -34585713678)
Modulus size = 8
operator%  869ms        (sum = -39212500000)
ternary    76.972ms     (sum = -39212500000)
branchless 167.29ms     (sum = -39212500000)
Modulus size = 9
operator%  875.003ms    (sum = -36500000580)
ternary    75.011ms     (sum = -36500000580)
branchless 172.356ms    (sum = -36500000580)

Hier ist ein zusätzlicher Benchmark. Beachten Sie, dass ich auch eine zweiglose Version hinzugefügt habe: operator% Und hier ist die Ausgabe auf meinem i7-4870HQ

In diesem speziellen Fall sieht der ternäre Operator weit überlegen aus, und es wird noch mehr so, wenn der Verzweigungsprädiktor hochfährt. Beachten Sie jedoch, dass dies ein sehr spezieller Fall ist: Wenn wir den Index nicht um einen nicht konstanten Wert erhöhen würden, verwenden wir den allgemeineren

wäre einfach, während die anderen beiden Methoden sehr kompliziert werden könnten.
Ich möchte diesen sehr unterschätzten Kommentar hervorheben:
Wenn len eine Kompilierzeitkonstante ist, ist dies ein neuerer GCC-Compiler (mit -02). normalerweise schlaue Dinge tun, oft die Modulus-Maschine vermeiden

Anweisung des Zielprozessors. size – Basile Starynkevitch const size_t size = 4; Zum Beispiel durch Entfernen der Schlaufe an der

g++ -Ofast test.cpp && ./a.out
Modulus size = 4
operator%  62.103ms     (sum = -36250000000)
ternary    93.674ms     (sum = -36250000000)
branchless 166.774ms    (sum = -36250000000)

Variable und deklarieren sie als

Ich bekomme: operator%Schlussfolgerungen

Die Ausführungszeit der branchless-Version ist über die verschiedenen Szenarien hinweg ziemlich stabil. Der ternäre ist in den betrachteten Fällen durchweg besser als der verzweigte, insbesondere wenn der Verzweigungsprädiktor einsetzt. Schließlich der

obwohl sie allgemeiner und erheblich langsamer ist, hat Chancen, optimiert zu werden, um die schnellste zu werden, wie im Fall bestimmter const-Werte auf der rechten Seite.

Natürlich ist dies völlig plattformabhängig, wer weiß, wie das auf einem Arduino sein wird 🙂

Wenn ‘len’ in Ihrem Code groß genug ist, ist die Bedingung schneller, da die Verzweigungsprädiktoren fast immer richtig raten.

#include <stdio.h>
#include <stdlib.h>

#define modulo

int main()
{
    int iterations = 1000000000;
    int size = 16;
    int a[size];
    unsigned long long res = 0;
    int i, j;

    for (i=0;i<size;i++)
        a[i] = i;

    for (i=0,j=0;i<iterations;i++)
    {
        j++;
        #ifdef modulo
            j %= size;
        #else
            if (j >= size)
                j = 0;
        #endif
        res += a[j];
    }

    printf("%llu\n", res);
}

Wenn nicht, dann glaube ich, dass dies eng mit zirkulären Warteschlangen verbunden ist, bei denen es oft der Fall ist, dass die Länge eine Potenz von 2 ist. Dies ermöglicht es dem Compiler, Modulo durch ein einfaches UND zu ersetzen.

• Der Code ist folgender:
• Größe=15:

Modulo: 4.868 s

• Bed.: 1.291s
• Größe=16:

Modulo: 1.067 s

Benutzeravatar von steviekm3

Benutzeravatar von Yilmaz

  (i + 1) % len

Yilmaz

if ((i+1)==len){
   return 0
} else {
   return i+1
}