¿Cuáles son algunos algoritmos que pueden experimentar beneficios de rendimiento al reemplazar funciones con búsquedas de tablas? (es decir, seno, cuadrar un número, raíz cuadrada, coseno)?

Answer 1

Este es un gran tema! ¡Empecemos!

Resuelto: la búsqueda en la tabla es una pérdida de tiempo

¿Por qué? Porque la aritmética es mucho más barata que los accesos a memoria. Un chip superescalar moderno puede realizar 4 o más operaciones aritméticas . Una lectura de memoria que no está en caché puede tomar 160 ciclos. Así que piense en la búsqueda de tablas cuando la búsqueda puede desplazar 640 operaciones aritméticas. Duro, estoy en lo cierto?

Por supuesto, esto no siempre es cierto: los procesadores integrados (arduinos, etc.) tienen una aritmética mucho más lenta en comparación con la memoria, por lo que la búsqueda de tablas puede tener sentido.

Las tablas de búsqueda tampoco pueden estar en la memoria principal, se almacenarán en caché como cualquier otra cosa, y una búsqueda de una tabla pequeña podría tomar tan solo 3 ciclos. Sin embargo, el espacio de caché es limitado, y si la tabla está en caché, los demás datos de su programa no lo estarán, por lo que la búsqueda de la tabla podría ser rápida, ¡pero ralentizaría todo lo demás!

Entonces la respuesta es, ¡depende! Aquí es donde las herramientas de creación de perfiles son útiles, le dirán si las funciones que está pensando en reemplazar por la búsqueda de tabla realmente están utilizando una cantidad apreciable de tiempo de cálculo. Si (poco probable) alguna función toma el 10% del tiempo de ejecución, incluso si fuera infinitamente rápido, el programa solo se aceleraría en un 10%.

Resuelto: ¡la búsqueda en la mesa es genial!

Si (a) la tabla es pequeña y (b) se usa con frecuencia, entonces la búsqueda de tablas puede tener sentido. Esto sucede a menudo para funciones irregulares como las que clasifican los caracteres “isupper” “islower”, etc.

Si la informática es lenta en comparación con la memoria (ver arriba)

Si una tabla pequeña puede acelerar una función iterativa convergente. Muchas implementaciones de máquina de raíz cuadrada tienen una pequeña tabla de inicio, por ejemplo.

“Memorización”: el almacenamiento en caché de las respuestas a llamadas recientes a una función puede ser increíblemente efectivo y es una técnica general que no requiere mucha reflexión.

La búsqueda en la tabla también es aproximadamente un tiempo constante, y la función subyacente puede tardar un tiempo variable en ejecutarse. Los sistemas de tiempo real con frecuencia usan tablas por este motivo. Como ejemplo, obtener el control del discurso codificado de la ley u es súper rápido con una tabla de 256 entradas, pero doloroso sin él. Los sintetizadores de música a menudo usan tablas para la síntesis de ondas.

Para las funciones citadas en la pregunta: cuadrado, seno de raíz cuadrada, coseno, sospecho que será difícil superar las versiones de la biblioteca matemática. Square, por supuesto, es una instrucción, no se puede superar eso La raíz cuadrada es aritmética pura y converge increíblemente rápido. Las expansiones en serie de seno y coseno también son aritmética pura. Para tales cosas si desea una precisión apreciable, tomará tablas que son muy grandes y no ahorrará tiempo, ya que es probable que valores particulares no estén en caché.