Costos de búsquedas versus cálculos

12

Estoy interesado en establecer cálculos para verificar si se cumple un criterio de distancia: es decir, la distancia entre un vector y otro vector x j debería ser menor que algún valor r m a x . Mis datos se dividen de acuerdo con una cuadrícula de coordenadas ortogonal. Dado que mi límite es menor que la distancia entre los puntos finales de las coordenadas vecinas más cercanas, me gustaría agregar una variable "octante" para verificar si las cosas están configuradas correctamente:xixjrmax

if octant[j] in allowed_list continue

como un "cortocircuito" para

if dist(x[i], x[j]) < r_max

Mi pregunta es: ¿cuán eficientes computacionalmente son las búsquedas y comparaciones booleanas en relación con las operaciones de punto flotante? ¿Vale la pena hacerlo en arquitecturas modernas?

aeismail
fuente
3
¿Estaría dispuesto a ramificar su código y probarlo? Siento que la respuesta estándar a la mayoría de estas "¿Es mejor codificarlo (de una manera) o (de otra manera)?" El tipo de preguntas es "Pruébelo y compárelo".
Geoff Oxberry
1
Solo mis 2 centavos. Como escribió Geoff, este tipo de consejo es lo que siempre recibo cuando hago preguntas similares sobre stackoverflow, con respecto al código C ++: codifique todo primero, organice el código para que siga siendo modular y reutilizable, y solo luego comience a refactorizar. Hay una regla 80-20: el software pasa el 80% del tiempo en el 20% del código. Espere hasta que la estructura esté levantada, y luego cambie, pruebe, cambie, pruebe ...
tmaric
@ GeoffOxberry: Mi pregunta no es tan específica: solo quiero saber si hay una ventaja de hardware o compilador dada para hacer una verificación booleana en comparación con una operación de punto flotante.
aeismail
3
Pero tu pregunta es demasiado general. Nadie puede decirlo sin ver un código concreto. Hay una regla general que dice que incluso los mejores programadores no pueden saber dónde están los cuellos de botella de su código sin crear perfiles. He pasado mis últimos 25 años programando y sé que es cierto para mí.
Wolfgang Bangerth

Respuestas:

15

Mi regla general es que si puede calcular cierta cantidad de manera eficiente (buena utilización de la FPU) en menos de 50 flops por valor de doble precisión, es mejor volver a calcular que almacenar. La tendencia, que ha sido constante durante décadas, es que la capacidad de punto flotante mejore más rápido que el rendimiento de la memoria, y no es probable que ceda debido a las restricciones físicas y los requisitos de energía de la memoria rápida. El valor de 50 es de la magnitud adecuada para todas las plataformas informáticas populares (Intel / AMD, Blue Gene y GPU).

Costo aproximado estimado por núcleo

[directrices para las máquinas basadas en Intel y AMD 2011/2012]

  • 0.05
  • 0.2
  • 0.4
  • 0.40.8
  • 2
  • 35
  • 35
  • 5
  • 48
  • 12
  • 12
  • 3050
  • 100
  • 1031 μ
  • 10410 μ
  • 106
  • 2106MPI_Allreduce
  • 107
  • 5108
  • 1.81012

Otras lecturas

Jed Brown
fuente
Encontré esta información realmente útil. Por cierto, ¿de dónde sacaste estos datos? Estoy buscando referencias para citar.
Eldila