.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í !.