Fast Sin/Cos utilizando una matriz de traducción calculada previamente

Question

Tengo el siguiente código haciendo la función Sin/Cos usando una tabla de memoria precalculada. en el siguiente ejemplo, la tabla tiene 1024 * 128 ítems que cubren todos los valores Sin/Cos de 0 a 2pi. Sé que puedo usar la simetría Sin/Cos y mantener solo 1/4 de los valores, pero tendré más 'si' al calcular el valor.

private const double PI2 = Math.PI * 2.0; 
private const int TABLE_SIZE = 1024 * 128; 
private const double TABLE_SIZE_D = (double)TABLE_SIZE; 
private const double FACTOR = TABLE_SIZE_D/PI2; 

private static double[] _CosineDoubleTable; 
private static double[] _SineDoubleTable; 

Establecer la tabla de traducción

private static void InitializeTrigonometricTables(){ 
    _CosineDoubleTable = new double[TABLE_SIZE]; 
    _SineDoubleTable = new double[TABLE_SIZE]; 

    for (int i = 0; i < TABLE_SIZE; i++){ 
     double Angle = ((double)i/TABLE_SIZE_D) * PI2; 
     _SineDoubleTable[i] = Math.Sin(Angle); 
     _CosineDoubleTable[i] = Math.Cos(Angle); 
    } 
} 

El valor es un doble en radianes.

Value %= PI2; // In case that the angle is larger than 2pi 
if (Value < 0) Value += PI2; // in case that the angle is negative 
int index = (int)(Value * FACTOR); //from radians to index and casted in to an int 
double sineValue = _SineDoubleTable[index]; // get the value from the table 

Estoy buscando una forma más rápida de hacerlo. Las 4 líneas anteriores son ~ 25% del proceso completo (ejecutadas miles de millones de veces).

Answer 1

Puede intentar utilizar un código no seguro para eliminar la comprobación de límites de matriz.
Pero incluso una versión optimizada e insegura no parece acercarse a Math.Sin.

Resultados basados ​​en 1'000'000'000 iteraciones con valores aleatorios:

(1) 00:00:57.3382769 // original version 
(2) 00:00:31.9445928 // optimized version 
(3) 00:00:21.3566399 // Math.Sin 

Código:

static double SinOriginal(double Value) 
{ 
    Value %= PI2; 
    if (Value < 0) Value += PI2; 
    int index = (int)(Value * FACTOR); 
    return _SineDoubleTable[index]; 
} 

static unsafe double SinOptimized(double* SineDoubleTable, double Value) 
{ 
    int index = (int)(Value * FACTOR) % TABLE_SIZE; 
    return (index < 0) ? SineDoubleTable[index + TABLE_SIZE] 
         : SineDoubleTable[index]; 
} 

Programa de prueba:

InitializeTrigonometricTables(); 
Random random = new Random(); 

SinOriginal(random.NextDouble()); 
var sw = System.Diagnostics.Stopwatch.StartNew(); 
for (long i = 0; i < 1000000000L; i++) 
{ 
    SinOriginal(random.NextDouble()); 
} 
sw.Stop(); 
Console.WriteLine("(1) {0} // original version", sw.Elapsed); 

fixed (double* SineDoubleTable = _SineDoubleTable) 
{ 
    SinOptimized(SineDoubleTable, random.NextDouble()); 
    sw = System.Diagnostics.Stopwatch.StartNew(); 
    for (long i = 0; i < 1000000000L; i++) 
    { 
     SinOptimized(SineDoubleTable, random.NextDouble()); 
    } 
    sw.Stop(); 
    Console.WriteLine("(2) {0} // optimized version", sw.Elapsed); 
} 

Math.Sin(random.NextDouble()); 
sw = System.Diagnostics.Stopwatch.StartNew(); 
for (long i = 0; i < 1000000000L; i++) 
{ 
    Math.Sin(random.NextDouble()); 
} 
sw.Stop(); 
Console.WriteLine("(3) {0} // Math.Sin", sw.Elapsed); 

Answer 2

Si tiene que calcular tantas veces,

1. utilizar una biblioteca matemática específica del procesador como el IKML o ACML y
   1. Calcular los valores en grupos (vectores).
   2. Cuando necesite ambos, siempre calcule el sin y cos de un valor al mismo tiempo.
2. Compruebe la complejidad de su algoritmo y el diseño de implementación.
3. Asegúrate de estar utilizando todo lo que el procesador tiene para ofrecer: la arquitectura x64, además de cualquier instrucción vectorial que pueda ayudar.

Answer 3

Eso va a ser bastante rápido como lo es.

Si realmente necesita exprimir cualquier caída imaginable del rendimiento de este código, le recomendamos que escriba esta parte (incluido el bucle externo que se repite miles de millones de veces) en un dll C++ (o incluso ASM) . Asegúrese de que su compilador esté configurado para permitir el mayor conjunto de instrucciones posibles disponibles para usted.

[Editar] Eché de menos lo grandes que son las tablas, esto podría muy bien ralentizar su código significativamente debido a fallas en la caché. ¿Ha intentado compararlo con Math.Cos() u otros métodos de aproximación de funciones trigonométricas (puede obtener muy buenas aproximaciones con algunas multiplicaciones simples usando Taylor Series)

Answer 4

Esto se ve bastante bien, excepto por la operación de modificación. ¿Puedes prescindir de eso?

Si los valores son cercanos a cero, puede utilizar

while(Value > PI2) Value -= PI2; 
while(Value < 0) Value += PI2; 

o puede ser más rápido para lanzar el índice a un número entero (posiblemente fuera de rango) en primer lugar, a continuación, mod que a medida como número entero. Si el tamaño de la tabla va a ser un múltiplo de 2, incluso puede usar operaciones de bits (si el compilador ya no lo hace).

Answer 5

No hay garantía de que vaya a hacer mucho bien, pero dependiendo de su procesador, las matemáticas enteras son a menudo más rápidas que las matemáticas de coma flotante. Siendo ese el caso, probablemente reacomodaré las primeras tres líneas para calcular primero un número entero, luego reduciré su rango (si es necesario). Por supuesto, como señaló BlueRaja, usar C++ seguramente también ayudará.Sin embargo, el uso del lenguaje ensamblador no servirá de mucho; para una búsqueda de tablas como esta, un compilador C++ puede generalmente producir código bastante bueno.

Si es posible, también me parecen muy duro en sus requisitos de precisión - sin saber lo que está haciendo con los valores, es difícil de decir, pero para muchos de propósitos, el tamaño de la mesa y la precisión que está almacenando es ahora más allá de lo necesario o incluso cerca de lo útil.

Finalmente, señalaría que vale la pena, al menos, analizar si esta estrategia en sí vale la pena. En un momento, no había duda de que el uso de tablas para evitar cálculos complejos era una estrategia sólida. Sin embargo, los procesadores aceleraron un lote más rápido que la memoria, hasta el punto de que una búsqueda de tabla así es a menudo una pérdida neta en la actualidad. De hecho, casi la única forma en que la mesa tiene una posibilidad es si es lo suficientemente pequeña como para caber en la memoria caché del procesador.

Answer 6

Una cosa que podrías probar sería usar el hecho de que cos (x) = sin (x + pi/2). Y haga que la mesa sinusoidal sea un cuarto más grande, para poder reutilizarla como la mesa del coseno comenzando un cuarto de pulgada. No estoy seguro si C# le permite obtener un puntero al centro de la mesa, como lo haría C. Pero incluso si no, el uso reducido de la memoria caché podría valer más que el tiempo agregado para la compensación en la tabla sinusoidal.

Eso, es decir, expresado con C:

double* _CosineDoubleTable = &_SineDoubleTable[TABLESIZE/4]; 

Answer 7

Estoy asumiendo expansiones de Taylor no sirven de nada para usted. Por lo tanto, si desea utilizar una tabla: , solo necesita una tabla la mitad de grande.

1. cos(x) = sin(pi/2-x).
2. sin(pi + x) = -sin(x)

Puede hacer que su código de no-ramificación. Convertir primero a formato int.

int index = (int)(Value * FACTOR); 
index %= TABLE_SIZE; // one instuction (mask) 
index = (index >= 0) ? index :TABLE_SIZE-index; // one instruction isel 
double sineValue = _SineDoubleTable[index]; 

Comparar de todas formas con Math.Sin. Perfil Perfil Priofile. (La falta de caché puede ralentizar el código en ejemplos reales).

Answer 8

hay algunas grandes notas en el cálculo rápido de seno y coseno aquí: http://www.research.scea.com/gdc2003/fast-math-functions.html

Cubre cómo mapear los valores de entrada en el rango deseado, y también utilizando polinomios mini-max (minimizando el error máximo durante el intervalo, que es diferente de la serie de Taylor), e incluso optimizaciones SIMD.