c# - ulong - ¿Es más eficiente realizar una verificación de rango al convertir a uint en lugar de verificar los valores negativos?

ulong size

Question

Me topé con este código en el código fuente de la Lista de .NET:

// Following trick can reduce the range check by one
if ((uint) index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}

Aparentemente, esto es más eficiente (?) if (index < 0 || index >= _size)

Tengo curiosidad sobre la razón detrás del truco. ¿Una instrucción de una sola rama es realmente más costosa que dos conversiones para uint ? ¿O hay alguna otra optimización en marcha que hará que este código sea más rápido que una comparación numérica adicional?

Para abordar el elefante en la habitación: sí, esto es micro optimización, no, no tengo la intención de usar esto en todas partes en mi código, solo tengo curiosidad;)

Answer 1

Al explorar esto en un procesador Intel no encontré diferencias en los tiempos de ejecución, posiblemente debido a múltiples unidades de ejecución de enteros.

Pero al hacer esto en un microprocesador en tiempo real de 16MHZ sin predicción de rama ni unidades de ejecución de enteros, hubo diferencias notables.

1 millón de iteraciones del código más lento tomó 1761 ms

int slower(char *a, long i)
{
if (i < 0 || i >= 10)
return 0;
return a[i];
}

El código de 1 millón de iteraciones más rápido tomó 1635 ms

int faster(char *a, long i)
{
if ((unsigned int)i >= 10)
return 0;
return a[i];
}

Answer 2

Aparentemente en la vida real no es más rápido. Verifique esto: https://dotnetfiddle.net/lZKHmn

Resulta que, gracias a la predicción de rama de Intel y la ejecución paralela, el código más obvio y legible en realidad funciona más rápido ...

Aquí está el código:

using System;
using System.Diagnostics;
public class Program
{
const int MAX_ITERATIONS = 10000000;
const int MAX_SIZE = 1000;
public static void Main()
{
var timer = new Stopwatch();
Random rand = new Random();
long InRange = 0;
long OutOfRange = 0;
timer.Start();
for ( int i = 0; i < MAX_ITERATIONS; i++ ) {
var x = rand.Next( MAX_SIZE * 2 ) - MAX_SIZE;
if ( x < 0 || x > MAX_SIZE ) {
OutOfRange++;
} else {
InRange++;
}
}
timer.Stop();
Console.WriteLine( "Comparision 1: " + InRange + "/" + OutOfRange + ", elapsed: " + timer.ElapsedMilliseconds + "ms" );
rand = new Random();
InRange = 0;
OutOfRange = 0;
timer.Reset();
timer.Start();
for ( int i = 0; i < MAX_ITERATIONS; i++ ) {
var x = rand.Next( MAX_SIZE * 2 ) - MAX_SIZE;
if ( (uint) x > (uint) MAX_SIZE ) {
OutOfRange++;
} else {
InRange++;
}
}
timer.Stop();
Console.WriteLine( "Comparision 2: " + InRange + "/" + OutOfRange + ", elapsed: " + timer.ElapsedMilliseconds + "ms" );
}
}

Answer 3

De MS Partition I , sección 12.1 (Tipos de datos admitidos):

Los tipos enteros con signo (int8, int16, int32, int64 e int nativo) y sus tipos enteros sin signo correspondientes (unsigned int8, unsigned int16, unsigned int32, unsigned int64 y native unsigned int) difieren solo en cómo los bits del entero son interpretados Para aquellas operaciones en las que un entero sin signo se trata de manera diferente a un entero con signo (por ejemplo, en comparaciones o aritmética con desbordamiento), hay instrucciones separadas para tratar un entero como sin signo (por ejemplo, cgt.un y add.ovf.un).

Es decir, la conversión de un int a un uint es simplemente una cuestión de contabilidad: de ahora en adelante, ahora se sabe que el valor en la pila / en un registro es un int sin signo en lugar de un int.

Por lo tanto, las dos conversiones deben ser "libres" una vez que el código se JIT, y luego se puede realizar la operación de comparación sin signo.

Answer 4

Digamos que tenemos:

public void TestIndex1(int index)
{
if(index < 0 || index >= _size)
ThrowHelper.ThrowArgumentOutOfRangeException();
}
public void TestIndex2(int index)
{
if((uint)index >= (uint)_size)
ThrowHelper.ThrowArgumentOutOfRangeException();
}

Compilemos estos y miremos ILSpy:

.method public hidebysig
instance void TestIndex1 (
int32 index
) cil managed
{
IL_0000: ldarg.1
IL_0001: ldc.i4.0
IL_0002: blt.s IL_000d
IL_0004: ldarg.1
IL_0005: ldarg.0
IL_0006: ldfld int32 TempTest.TestClass::_size
IL_000b: bge.s IL_0012
IL_000d: call void TempTest.ThrowHelper::ThrowArgumentOutOfRangeException()
IL_0012: ret
}
.method public hidebysig
instance void TestIndex2 (
int32 index
) cil managed
{
IL_0000: ldarg.1
IL_0001: ldarg.0
IL_0002: ldfld int32 TempTest.TestClass::_size
IL_0007: blt.un.s IL_000e
IL_0009: call void TempTest.ThrowHelper::ThrowArgumentOutOfRangeException()
IL_000e: ret
}

Es fácil ver que el segundo tiene menos código, con una rama menos.

Realmente, no hay un elenco en absoluto, existe la opción de usar blt.s y bge.s o usar blt.s.un , donde este último trata los enteros pasados ​​como sin firmar mientras que el primero los trata como firmados.

(Nota para aquellos que no están familiarizados con CIL, ya que esta es una pregunta de C # con una respuesta de CIL, bge.s , blt.s y blt.s.un son las versiones "cortas" de bge , blt y blt.un respectivamente. blt saca dos valores de la pila y se ramifica si el primero es menor que el segundo cuando los considera como valores con signo, mientras que blt.un saca dos valores de la pila y se ramifica si el primero es menor que el segundo cuando los considera como valores sin signo).

Es una microopción, pero hay momentos en los que vale la pena hacerlo. Considere además, que con el resto del código en el cuerpo del método esto podría significar la diferencia entre algo que cae dentro de los límites de inestabilidad para alinearse o no, y si se molestan en tener un ayudante para lanzar excepciones fuera de rango, son Probablemente, si es posible, intente asegurar que la alineación ocurra, y los 4 bytes adicionales podrían hacer toda la diferencia.

De hecho, es bastante probable que esa diferencia de línea sea mucho más importante que la reducción de una rama. No hay muchas ocasiones en las que valga la pena asegurarse de que ocurra la inserción, pero un método básico de una clase de uso tan pesado como List<T> sin duda sería uno de ellos.

Answer 5

Sí, esto es más eficiente. El JIT hace el mismo truco cuando se accede a la matriz de comprobación de rango .

La transformación y el razonamiento son los siguientes:

i >= 0 && i < array.Length convierte en (uint)i < (uint)array.Length porque array.Length <= int.MaxValue para que array.Length tenga el mismo valor que (uint)array.Length . Si resulta que (uint)i > int.MaxValue negativo, entonces (uint)i > int.MaxValue y la verificación falla.

Answer 6

Suponiendo que _size es un número entero, privado de la lista y el index es el argumento de esta función cuya validez necesita ser probada.

Suponiendo además que _size es siempre> = 0.

Entonces la prueba original habría sido:

if(index < 0 || index > size) throw exception

La versión optimizada

if((uint)index > (uint)_size) throw exception

tiene una comparación (como optado por dos en el ejemplo anterior). Debido a que el elenco simplemente reinterpreta los bits y hace que > de hecho sea una comparación sin signo, no se utilizan ciclos de CPU adicionales para ello.

Por que funciona

Los resultados son simples / triviales siempre que index> = 0.

Si index <0, el índice (uint)index lo convertirá en un número muy grande:

Ejemplo: 0xFFFF es -1 como int, pero 65535 como uint, por lo tanto

(uint)-1 > (uint)x 

siempre es cierto si x fue positivo.

Answer 7

Tenga en cuenta que este truco no funcionará si su proyecto está checked lugar de unchecked . En el mejor de los casos, será más lento (porque cada lanzamiento deberá verificarse contra el desbordamiento) (o al menos no más rápido), en el peor de los casos obtendrá una excepción de OverflowException si intenta pasar -1 como index (en lugar de su excepción) .

Si desea escribirlo "correctamente" y de una manera más "seguramente funcionará", debe poner un

unchecked
{
// test
}

todo alrededor de la prueba.