¿Los punteros de función fuerzan a borrar una canalización de instrucciones?

En algunos procesadores, una rama indirecta siempre borrará al menos parte de la canalización, porque siempre se malinterpreta. Este es especialmente el caso de los procesadores en orden.

Por ejemplo, Ejecuté algunos tiempos en el procesador para el que desarrollamos, comparando la sobrecarga de una llamada a una función en línea, versus una llamada a una función directa, versus una llamada a una función indirecta (función virtual o puntero de función; son idénticos en esta plataforma).

Escribí una pequeña función cuerpo y lo midió en un bucle apretado de millones de llamadas, para determinar el costo de solo la penalización de llamada. La función "inline" era un grupo de control que medía solo el costo del cuerpo de la función (básicamente un op de una sola carga). La función directa midió la penalización de una rama correctamente predicha (porque es un objetivo estático y el predictor de PPC siempre puede hacerlo bien) y el prólogo de la función. La función indirecta mide la penalización de una rama indirecta bctrl.

614,400,000 llamadas a funciones :

inline:   411.924 ms  (   2 cycles/call )
direct:  3406.297 ms  ( ~17 cycles/call )
virtual: 8080.708 ms  ( ~39 cycles/call )

Como puede ver, la llamada directa cuesta 15 ciclos más que el cuerpo de la función, y la llamada virtual (exactamente equivalente a una llamada de puntero de función) cuesta 22 ciclos más que la llamada directa. Eso pasa a ser aproximadamente cuántas etapas de canalización hay entre el inicio de la pipline (búsqueda de instrucciones) y el final de la rama ALU. Por lo tanto, en esta arquitectura, una rama indirecta (también conocida como una llamada virtual) causa un claro de 22 etapas de la tubería el 100% del tiempo.

Otras arquitecturas pueden variar. Debe hacer estas determinaciones a partir de mediciones empíricas directas, o de las especificaciones de canalización de la CPU, en lugar de suposiciones sobre lo que los procesadores "deberían" predecir, porque las implementaciones son muy diferentes. En este caso, el pipeline clear se produce porque no hay forma de que el predictor de bifurcación sepa a dónde irá el bctrl hasta que se haya retirado. En el mejor de los casos podría adivinar que es al mismo objetivo que el último bctrl, y esta CPU en particular ni siquiera intenta esa suposición.

No hay mucha diferencia entre una llamada de puntero de función y una llamada "normal", aparte de un nivel extra de indirección. Así que potencialmente hay una mayor latencia involucrada; si la dirección de destino no está ya en caché o registros, entonces la CPU potencialmente tiene que esperar mientras se recupera de la memoria principal.

Así que la respuesta es; sí, la canalización puede estancarse, pero esto no es diferente a las llamadas a funciones normales. Y como de costumbre, mecanismos como la predicción de ramas y la ejecución fuera de orden puede ayudar a minimizar la penalización.

Una llamada a través de un puntero de función no necesariamente causa una canalización clara, pero puede, dependiendo del escenario. La clave es si la CPU puede predecir efectivamente el destino de la rama con anticipación.

La forma en que los núcleos modernos "grandes" fuera de orden manejan las llamadas indirectas¹ es más o menos como sigue:

• Una vez que haya ejecutado la rama indirecta varias veces, el predictor de rama indirecta intentará predecir la dirección a la que la rama se producirá en el futuro.
• Los primeros predictores de ramificación indirecta eran muy simples, capaces de "predecir" solo una ubicación fija.
• Los predictores posteriores, incluidos los de la mayoría de las CPU modernas, son mucho más complejos, a menudo capaces de predecir bien un patrón repetido de saltos indirectos y también correlacionar el objetivo de salto con la dirección de las ramas condicionales o indirectas anteriores.
• Si la predicción es exitosa, la la llamada tiene un costo similar a una llamada directa normal, y este costo está en gran parte "fuera de línea" con el resto del código (es decir, no participa en cadenas de dependencias), por lo que el impacto en el tiempo de ejecución final del código es probable que sea pequeño a menos que las llamadas sean muy densas.
• Por otro lado, si la predicción no tiene éxito, se obtiene una mala predicción completa, similar a una mala predicción dirección de rama. No se puede poner un número fijo en el costo de esta mala predicción, ya que depende del código circundante, pero generalmente causa una burbuja de aproximadamente 20 ciclos en el front-end, y el costo total en tiempo de ejecución a menudo termina siendo similar.

Así que dados esos conceptos básicos podemos hacer algunas conjeturas educadas sobre lo que sucede en algunos escenarios específicos:

1. Un puntero de función siempre apunta a la misma función casi siempre¹ estar bien pronosticado y costar aproximadamente lo mismo que una llamada de función regular.
2. Un puntero de función que alterna aleatoriamente entre varios objetivos casi siempre se malinterpretarán. En el mejor de los casos, podemos esperar que el predictor siempre predice cualquier objetivo es más común, por lo que en el peor de los casos que los objetivos se eligen uniformemente al azar entre los objetivos N la tasa de éxito de la predicción está limitada por 1 / N (es decir, va a cero como N va a infinito). En este sentido, las ramas indirectas tienen un peor comportamiento en el peor de los casos que las ramas condicionales, que generalmente tienen una tasa de 50%².
3. La tasa de predicción para un puntero de función con comportamiento en algún lugar en el medio, por ejemplo, algo predecible (por ejemplo, siguiendo un patrón repetido), dependerá en gran medida de los detalles del hardware y la sofisticación del predictor. Los chips Intel modernos tienen predictores indirectos bastante buenos, pero los detalles no se han publicado públicamente. La sabiduría convencional sostiene que están utilizando algunos variante indirecta de un predictor TAGE usado también para predictores condicionales rama.

¹ Un caso que podría malinterpretar incluso para un solo objetivo incluye la primera vez (o pocas veces) que se encuentra la función, ya que el predictor no puede predecir llamadas indirectas que aún no ha visto. Además, el tamaño de los recursos de predicción en la CPU es limitado, por lo que si el puntero de función no se ha utilizado en un tiempo, eventualmente los recursos de predicción se utilizarán para otras ramas y sufrirá una mala predicción la próxima vez que llame se.

² De hecho, un predictor condicional muy simple que simplemente predice la dirección más a menudo vista recientemente debería tener una tasa de predicción del 50% en direcciones de ramificación totalmente aleatorias. Para obtener un resultado significativamente peor que el 50%, tendría que diseñar un algoritmo adversarial que esencialmente modela el predictor y siempre elige ramificar en la dirección opuesta al modelo.