Modernas CPU Inner Loop indirección optimizaciones

Question

http://www.boost.org/community/implementation_variations.html

" ... diferencias de codificación como el cambio de una clase de lo virtual a los miembros no virtuales y extracción de un nivel de indirección son poco probable que cualquier diferencia medible a menos profunda en un bucle interno. E incluso en un bucle interno, las CPU modernas menudo ejecutar tales secuencias de código que compiten en el mismo número de ciclos de reloj! "

Estoy tratando de comprender el papel que "incluso en el bucle interno". Específicamente qué mecanismos no implementan las CPU para ejecutar los dos códigos (virtuales vs no virtual o un nivel adicional de indirección) dentro del mismo número de ciclos de reloj? Yo sé acerca de la canalización de instrucciones y caché, pero ¿cómo es posible realizar una llamada virtual dentro del mismo número de ciclos de reloj como una llamada no virtual? ¿Cómo es la vía indirecta "perdido"?

Answer 1

El almacenamiento en caché (por ejemplo rama objetivo almacenamiento en caché ), unidades de carga paralelas (parte de la canalización, sino también cosas como "golpe bajo miss" que no interrumpen la tubería), y ejecución fuera de orden es probable que ayuda a transformar una load-load-branch en algo que está más cerca de un branch fijo. Instrucción de plegado / eliminación (lo que es el término adecuado para esto?) En la etapa de decodificación o de predicción de ramificación de la tubería también puede contribuir.

Todo esto se basa en un montón de cosas diferentes, sin embargo: la cantidad de diferentes objetivos de las ramificaciones existen (por ejemplo, la cantidad de diferentes sobrecargas virtuales son lo más probable es que el gatillo), cuántas cosas se recorre (es la caché de destino del salto " caliente "? ¿y el Icaché / dcache?), la forma en tablas o tablas de indirección lo virtual se organizada en memoria (¿son caché de usar, o está cada nueva carga vtable posiblemente desalojando un viejo vtable?), se invalida la memoria caché en repetidas ocasiones debido a las múltiples núcleos de ping-ponging, etc ...

(exención de responsabilidad: yo soy definitivamente no es un experto aquí, y una gran parte de mi conocimiento proviene del estudio en orden procesadores embebidos, por lo que algo de esto es la extrapolación Si usted tiene correcciones, no dude en comentar.!)

La forma correcta para determinar si va a ser un problema para un programa específico es, por supuesto, al perfil. Si es posible, hacerlo con la ayuda de los contadores de hardware -. Se le puede decir mucho acerca de lo que está pasando en las diferentes etapas de la tubería

---

Editar:

Como Hans Passant señala en un comentario anterior moderna CPU Inner Loop indirección optimizaciones , la clave para conseguir estas dos cosas a tomar la misma cantidad de tiempo es la capacidad efectiva "retirarse" más de una instrucción por ciclo. eliminación instrucción puede ayudar con esto, pero superescalar diseñar es probablemente más importante (hit bajo la señorita es un muy pequeño y específico ejemplo, unidades de carga completamente redundantes podría ser una mejor uno).

Vamos a tomar una situación ideal, y asumir una rama directa es una sola instrucción:

branch dest

... y una rama indirecta es de tres (tal vez usted puede conseguirlo en dos, pero es mayor que uno):

load vtable from this
load dest from vtable
branch dest

Vamos a suponer una situación absolutamente perfecta: * esto y toda la viable están en caché L1, caché L1 es lo suficientemente rápido como para el apoyo amortiza un ciclo por el costo de instrucciones para las dos cargas. (Usted puede incluso asumir el procesador reordena las cargas y los entremezcla con las instrucciones anteriores para dar tiempo a que se completen antes de la sucursal; no importa para este ejemplo.) También suponga la caché de ramificación objetivo es caliente, y no hay tuberías coste ras de la rama, y ??la instrucción de salto se reduce a un solo ciclo (amortizado).

La mínimo teórico tiempo para el primer ejemplo, por lo tanto es 1 ciclo (amortizado).

El mínimo teórico para el segundo ejemplo, la eliminación de instrucciones ausente o unidades funcionales o algo que le permitirá que se retiran más de una instrucción por ciclo redundante, es de 3 ciclos (hay 3 instrucciones)!

La carga indirecta siempre será más lento, porque hay más instrucciones, hasta llegar en algo así como el diseño superescalar que permite retirarse más de una instrucción por ciclo.

Una vez que tenga esto, el mínimo para ambos ejemplos se convierte en algo entre 0 y 1 ciclos, de nuevo, siempre y todo lo demás es ideal. Podría decirse que hay que tener más circunstancias ideales para el Second ejemplo para realmente llegar a ese mínimo teórico que en el primer ejemplo, pero es ahora posible.

En algunos de los casos que le interesan, es probable que no va a llegar a ese mínimo para cualquier ejemplo. O bien el caché de ramificación objetivo será frío, o la vtable no estará en la caché de datos, o la máquina no será capaz de reordenar las instrucciones para sacar el máximo provecho de las unidades funcionales redundantes.

... aquí es donde entra en perfiles, que es generalmente una buena idea de todos modos.

puede simplemente abrazar una ligera paranoia sobre los virtuales en el primer lugar. Véase el artículo Noel Llopis en los datos orientados diseño, la excelente Errores de Programación de diapositivas , y orientada a objetos presentaciones de mal humor-todavía-educativos de Mike Acton . Ahora se ha mudado de repente en los patrones que la CPU es ya probable que sea feliz, si está procesando una gran cantidad de datos.

características del lenguaje de alto nivel como virtuales son generalmente un compromiso entre la expresividad y control. Creo sinceramente que, sin embargo, con sólo el aumento de su conciencia de lo que está haciendo en realidad virtual (no tenga miedo de leer la opinión de desmontaje de vez en cuando, y sin duda vistazo a los manuales de arquitectura de la CPU), que tenderá a usarlo cuando tiene sentido y no cuando no lo hace, y un generador de perfiles puede cubrir el resto, si es necesario.

Una talla única para todos Afirmaciones "no usan virtual" o "uso virtual es poco probable que haga una diferencia medible" me hacen mal humor. La realidad suele ser más complicado, y ya sea que vas a estar en una situación en la que se preocupa lo suficiente para perfilar o evitarla, o le esté en ese otro 95% en los que no probablemente vale la pena cuidar excepto por el posible contenido educativo.

Answer 2

tuberias de diferentes tipos es la forma principal.

Puede ser que tome 20 ciclos de reloj para cargar una instrucción, decodificarlo, realizarlo de acciones y cargar las referencias a memoria indirectos. Pero debido a la pipleline el procesador puede ser la ejecución de partes de otros 19 instrucciones que aparecen al mismo tiempo en diferentes etapas de la tubería dando un rendimiento global del 1 instrucción de cada ciclo de reloj, independientemente del tiempo que realmente se necesita para alimentar a que la instrucción a través de la tubería.

Answer 3

¿Qué ocurre, creo que es que el procesador tiene un caché especial que contiene las ubicaciones y los objetivos de ramas y saltos indirectos. Si un salto indirecto se encuentra en $ 12345678, y la última vez que se encontró fue a atender $ 12348765, el procesador puede iniciar la ejecución especulativa de las instrucciones en la dirección $ 12348765, incluso antes de que se resuelva la dirección de la sucursal. En muchos casos, dentro del bucle interior de una función, un salto indirecto particular, siempre salta a la misma dirección durante toda la duración del bucle. El caché indirecta-salto puede pues evitar sanciones de ramificación.

Answer 4

CPUs modernos utilizan una técnica de predicción de saltos de adaptación que puede predecir muchos saltos indirectos tales como que se obtiene con una aplicación vtable de funciones virtuales. Ver http://en.wikipedia.org/wiki/Branch_prediction#Prediction_of_indirect_jumps

Answer 5

Si la CPU ya cuenta con la dirección de memoria en la memoria caché, a continuación, ejecutar una instrucción de carga es trivial, si acaso.