Warum ist Math.DivRem so ineffizient?

Question

In meinem Computer dauert dieser Code 17 Sekunden (1000 Millionen Mal):

static void Main(string[] args) {
   var sw = new Stopwatch(); sw.Start();
   int r;
   for (int i = 1; i <= 100000000; i++) {
      for (int j = 1; j <= 10; j++) {
         MyDivRem (i,j, out r);
      }
   }
   Console.WriteLine(sw.ElapsedMilliseconds);
}

static int MyDivRem(int dividend, int divisor, out int remainder) {
   int quotient = dividend / divisor;
   remainder = dividend - divisor * quotient;
   return quotient;
}

während Math.DivRem 27 Sekunden dauert.

.NET Reflector gibt mir diesen Code für Math.DivRem:

public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a / b);
}

CIL

.method public hidebysig static int32 DivRem(int32 a, int32 b, [out] int32& result) cil managed
{
    .maxstack 8
    L_0000: ldarg.2
    L_0001: ldarg.0
    L_0002: ldarg.1
    L_0003: rem
    L_0004: stind.i4
    L_0005: ldarg.0
    L_0006: ldarg.1
    L_0007: div
    L_0008: ret
}

Theoretisch könnte es für Computer mit mehreren Kernen schneller sein, aber eigentlich sollte es überhaupt nicht notwendig sein, zwei Operationen durchzuführen, weil x86 CPUs sowohl den Quotienten als auch den Rest zurückgeben, wenn sie eine Ganzzahldivision mit DIV oder IDIV durchführen (http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-2.html#HEADING2-451)!

Answer 1

Grrr. Der einzige Grund für das Bestehen dieser Funktion besteht darin, die CPU-Anweisung dafür zu nutzen, und sie haben es noch nicht einmal gemacht!

Answer 2

Während .NET Framework 4.6.2 immer noch das suboptimale Modulo und die Division verwendet, ersetzt .NET Core (CoreCLR) derzeit die Division durch eine Subtraktion:

    public static int DivRem(int a, int b, out int result)
    {
        // TODO https://github.com/dotnet/runtime/issues/5213:
        // Wiederherstellen der Verwendung von % und /, wenn der JIT in der Lage ist, eines der idivs zu eliminieren.
        // In der Zwischenzeit ist * und - messbar schneller als ein zusätzliches /.

        int div = a / b;
        result = a - (div * b);
        return div;
    }

Und es gibt ein offenes Problem, entweder speziell DivRem zu verbessern (via Intrinsik), oder den allgemeinen Fall in RyuJIT zu erkennen und zu optimieren.

Answer 3

Wow, das sieht wirklich dumm aus, oder?

Das Problem ist, dass laut dem Microsoft Press Buch ".NET IL Assembler" von Lidin die IL-rem- und div-arithmetischen Anweisungen genau das sind: Rest berechnen und Divisor berechnen.

Alle arithmetischen Operationen außer der Negationsoperation nehmen zwei Operanden vom Stapel und legen das Ergebnis auf den Stapel.

Angeblich ist es aufgrund der Struktur der IL-Assembler-Sprache nicht möglich, eine IL-Anweisung zu haben, die zwei Ausgaben erzeugt und sie auf den Eval-Stapel drückt. Angesichts dieser Einschränkung kann man in der IL-Assembler keine Divisionsanweisung haben, die beide Berechnungen genauso durchführt wie die x86-DIV- oder IDIV-Anweisungen.

IL wurde für Sicherheit, Überprüfbarkeit und Stabilität entworfen, NICHT für Leistung. Jeder, der eine rechenintensive Anwendung hat und hauptsächlich an Leistung interessiert ist, wird nativen Code verwenden und nicht .NET.

Ich habe kürzlich an der Supercomputing '08 teilgenommen, und in einer der technischen Sitzungen sagte ein Evangelist für Microsoft Compute Server die Faustregel, dass .NET in der Regel halb so schnell wie nativer Code ist - was genau hier der Fall ist!

Answer 4

Wenn ich raten müsste, würde ich sagen, dass die Person, die Math.DivRem implementiert hat, keine Ahnung hatte, dass x86-Prozessoren dies in einer einzigen Anweisung durchführen können, und es daher als zwei Operationen geschrieben hat. Das ist nicht unbedingt schlecht, wenn der Optimierer richtig funktioniert, obwohl es ein weiterer Hinweis darauf ist, dass es heutzutage den meisten Programmierern an grundlegendem Wissen mangelt. Ich würde erwarten, dass der Optimierer den Modulus zusammenführt und dann die Divisionsoperationen in eine Anweisung umwandelt, und die Personen, die Optimierer schreiben, sollten solche grundlegenden Dinge kennen...

Answer 5

Die Antwort lautet wahrscheinlich, dass niemand dies als Priorität betrachtet hat - es ist gut genug. Die Tatsache, dass dies mit keiner neuen Version des .NET Frameworks behoben wurde, ist ein Indikator dafür, wie selten dies verwendet wird - höchstwahrscheinlich hat sich noch nie jemand beschwert.