.net - net - mscorsw

¿Por qué Math.DivRem es tan ineficiente? (11)

En mi computadora, este código toma 17 segundos (1000 millones de veces):

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

mientras Math.DivRem toma 27 segundos.

.NET Reflector me da este código para 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 }

En teoría, puede ser más rápido para computadoras con múltiples núcleos, pero de hecho no debería necesitar hacer dos operaciones en primer lugar, porque las CPU x86 devuelven tanto el cociente como el resto cuando hacen una división entera usando DIV o IDIV ( http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-2.html#HEADING2-451 )!

¿Alguien más obtiene lo opuesto cuando prueba esto?

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

FWIW, estoy ejecutando un Intel Core 2 Duo.

Los números anteriores estaban con una construcción de depuración ...

Con la versión de lanzamiento:

Math.DivRem = 10.314 DivRem = 10.324 MyDivRem = 5.380

Parece que el comando IL "rem" es menos eficiente que el combo "mul, sub" en MyDivRem.

Aquí están mis números:

15170 MyDivRem 29579 DivRem (same code as below) 29579 Math.DivRem 30031 inlined

La prueba fue ligeramente modificada; Agregué la asignación al valor de retorno y estaba ejecutando la versión de lanzamiento.

Core 2 Duo 2.4

Opinión:

Parecía haber encontrado una buena optimización;)

Está en parte en la naturaleza de la bestia. A mi leal saber y entender, no hay una forma general rápida de calcular el resto de una división. Esto tomará una cantidad correspondientemente grande de ciclos de reloj, incluso con x cientos millones de transistores.

Esto es solo un comentario, pero no tengo suficiente espacio.

Aquí hay algunos C # usando Math.DivRem() :

[Fact] public void MathTest() { for (var i = 1; i <= 10; i++) { int remainder; var result = Math.DivRem(10, i, out remainder); // Use the values so they aren''t optimized away Assert.True(result >= 0); Assert.True(remainder >= 0); } }

Aquí está el IL correspondiente:

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

Aquí está el ensamblaje x86 optimizado (relevante) generado:

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

Tenga en cuenta las 2 llamadas a idiv . El primero almacena el resto ( EDX ) en el parámetro remainder en la pila. El segundo es determinar el cociente ( EAX ). Esta segunda llamada no es realmente necesaria, ya que EAX tiene el valor correcto después de la primera llamada a idiv .

Grrr. La única razón para que exista esta función es aprovechar la instrucción de la CPU para esto, ¡y ni siquiera lo hicieron!

La eficiencia puede muy bien depender de los números involucrados. Está probando una fracción TINY del espacio problemático disponible, y todo cargado frontalmente. Está comprobando las primeras combinaciones de entrada contigua de 1 millón * 10 = 1 mil millones, pero el espacio del problema real es de aproximadamente 4,2 mil millones cuadrados o 1.8e19 combinaciones.

El rendimiento de las operaciones de matemáticas de la biblioteca general como este debe amortizarse en todo el espacio problemático. Me interesaría ver los resultados de una distribución de entrada más normalizada.

La respuesta probablemente sea que nadie ha pensado que esto sea una prioridad, es lo suficientemente bueno. El hecho de que esto no se haya solucionado con ninguna versión nueva de .NET Framework es un indicador de la poca frecuencia con la que se usa, lo más probable es que nadie se haya quejado nunca.

Mientras .NET Framework 4.6.2 aún utiliza el módulo subóptimo y divide, Core de .NET (CoreCLR) currently reemplaza la división con un reste:

public static int DivRem(int a, int b, out int result) { // TODO https://github.com/dotnet/coreclr/issues/3439: // Restore to using % and / when the JIT is able to eliminate one of the idivs. // In the meantime, a * and - is measurably faster than an extra /. int div = a / b; result = a - (div * b); return div; }

Y hay un problema abierto para mejorar DivRem específicamente (a través de intrínseco), o detectar y optimizar el caso general en RyuJIT.

Si tuviera que adivinar, diría que quien implementó Math.DivRem no tenía idea de que los procesadores x86 son capaces de hacerlo en una sola instrucción, entonces lo escribieron como dos operaciones. Eso no es necesariamente algo malo si el optimizador funciona correctamente, aunque es otro indicador de que el conocimiento de bajo nivel lamentablemente falta en la mayoría de los programadores hoy en día. Yo esperaría que el optimizador colapsara el módulo y luego dividiera las operaciones en una sola instrucción, y las personas que escriben optimizadores deberían conocer este tipo de cosas de bajo nivel ...

Supongo que la mayor parte del costo adicional está en la configuración y el desmontaje de la llamada al método estático.

En cuanto a por qué existe, supongo que se debe en parte a la integridad y en parte al beneficio de otros lenguajes que pueden no tener implementaciones fáciles de usar de división de enteros y cálculo de módulo.

Wow, eso realmente se ve estúpido, ¿no?

El problema es que, de acuerdo con el libro de Microsoft Press ".NET IL Assembler" de Lidin, las instrucciones de IL rem y div atithmetic son exactamente eso: calcular el resto y calcular el divisor.

Todas las operaciones aritméticas excepto la operación de negación toman dos operandos de la pila y colocan el resultado en la pila.

Aparentemente, la forma en que está diseñado el lenguaje ensamblador IL no permite tener una instrucción IL que produzca dos salidas y las empuje a la pila eval. Dada esa limitación, no puede tener una instrucción de división en el ensamblador de IL que calcule la forma en que lo hacen las instrucciones x86 DIV o IDIV.

IL fue diseñado para la seguridad, la verificabilidad y la estabilidad, NO para el rendimiento. Cualquiera que tenga una aplicación de cálculo intensivo y se preocupe principalmente por el rendimiento usará código nativo y no .NET.

Recientemente asistí a Supercomputing ''08, y en una de las sesiones técnicas, un evangelista de Microsoft Compute Server me dio la regla general de que .NET usualmente tenía la mitad de velocidad que el código nativo, ¡que es exactamente el caso aquí !.