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

Erhält sonst noch jemand das Gegenteil, wenn dies getestet wird?

Math.DivRem = 11.029 sec, 11.780 sec
MyDivRem = 27.330 sec, 27.562 sec
DivRem = 29.689 sec, 30.338 sec

FWIW, Ich verwende einen Intel Core 2 Duo.

Die obigen Zahlen wurden mit einem Debug-Build durchgeführt...

Mit dem Release-Build:

Math.DivRem = 10.314
DivRem = 10.324
MyDivRem = 5.380

Sieht so aus, als wäre der "rem" IL-Befehl weniger effizient als die Kombination aus "mul,sub" in MyDivRem.

Answer 2

Die Effizienz könnte sehr gut von den Zahlen abhängen, die involviert sind. Du testest nur einen WINZIGEN Bruchteil des verfügbaren Problemraums und alles bereits vorab geladen. Du überprüfst die ersten 1 Million * 10 = 1 Milliarde zusammenhängende Eingabekombinationen, aber der tatsächliche Problemraum beträgt ungefähr 4,2 Milliarden im Quadrat oder 1,8e19 Kombinationen.

Die Leistung von allgemeinen Mathematikoperationen in Bibliotheken muss über den gesamten Problemraum amortisiert werden. Mich würde interessieren, die Ergebnisse einer stärker normalisierten Eingabeverteilung zu sehen.

Answer 3

Dies ist wirklich nur ein Kommentar, aber ich habe nicht genug Platz.

Hier ist etwas C# mit Math.DivRem():

    [Fact]
    public void MathTest()
    {
        for (var i = 1; i <= 10; i++)
        {
            int remainder;
            var result = Math.DivRem(10, i, out remainder);
            // Verwenden der Werte, damit sie nicht optimiert werden
            Assert.True(result >= 0);
            Assert.True(remainder >= 0);
        }
    }

Hier ist das entsprechende IL:

.method public hidebysig instance void MathTest() cil managed
{
    .custom instance void [xunit]Xunit.FactAttribute::.ctor()
    .maxstack 3
    .locals init (
        [0] int32 i,
        [1] int32 remainder,
        [2] int32 result)
    L_0000: ldc.i4.1 
    L_0001: stloc.0 
    L_0002: br.s L_002b
    L_0004: ldc.i4.s 10
    L_0006: ldloc.0 
    L_0007: ldloca.s remainder
    L_0009: call int32 [mscorlib]System.Math::DivRem(int32, int32, int32&)
    L_000e: stloc.2 
    L_000f: ldloc.2 
    L_0010: ldc.i4.0 
    L_0011: clt 
    L_0013: ldc.i4.0 
    L_0014: ceq 
    L_0016: call void [xunit]Xunit.Assert::True(bool)
    L_001b: ldloc.1 
    L_001c: ldc.i4.0 
    L_001d: clt 
    L_001f: ldc.i4.0 
    L_0020: ceq 
    L_0022: call void [xunit]Xunit.Assert::True(bool)
    L_0027: ldloc.0 
    L_0028: ldc.i4.1 
    L_0029: add 
    L_002a: stloc.0 
    L_002b: ldloc.0 
    L_002c: ldc.i4.s 10
    L_002e: ble.s L_0004
    L_0030: ret 
}

Hier ist der (relevante) optimierte x86-Assemblercode:

       for (var i = 1; i <= 10; i++)
00000000  push        ebp 
00000001  mov         ebp,esp 
00000003  push        esi 
00000004  push        eax 
00000005  xor         eax,eax 
00000007  mov         dword ptr [ebp-8],eax 
0000000a  mov         esi,1 
        {
            int remainder;
            var result = Math.DivRem(10, i, out remainder);
0000000f  mov         eax,0Ah 
00000014  cdq 
00000015  idiv        eax,esi 
00000017  mov         dword ptr [ebp-8],edx 
0000001a  mov         eax,0Ah 
0000001f  cdq 
00000020  idiv        eax,esi 

Beachten Sie die 2 Aufrufe von idiv. Der erste speichert den Rest (EDX) in dem remainder-Parameter auf dem Stack. Der 2. dient dazu, den Quotienten (EAX) zu bestimmen. Dieser 2. Aufruf ist eigentlich nicht erforderlich, da EAX nach dem ersten Aufruf von idiv den richtigen Wert hat.

Answer 4

Hier sind meine Zahlen:

15170 MyDivRem
29579 DivRem (gleicher Code wie unten)
29579 Math.DivRem
30031 inlined

Der Test wurde leicht geändert; Ich habe eine Zuweisung zum Rückgabewert hinzugefügt und den Release-Build ausgeführt.

Core 2 Duo 2.4

Meinung:

Sie scheinen eine schöne Optimierung gefunden zu haben ;)

Answer 5

Ich würde vermuten, dass der Großteil der zusätzlichen Kosten bei der Einrichtung und dem Abbau des statischen Methodenaufrufs liegt.

Was den Grund dafür betrifft, würde ich vermuten, dass dies teilweise für die Vollständigkeit und teilweise zum Nutzen anderer Sprachen existiert, die möglicherweise keine leicht zu bedienenden Implementierungen für die ganzzahlige Division und Modulberechnung haben.