¿Por que un array ordenado se ejecuta más rápido?. Por Branch Prediction

Aquí está un pedazo de código de C ++ que parece muy peculiar. Por alguna extraña razón, ordenar los datos milagrosamente hace que el código casi seis veces más rápido.

 

 

Estos son los tiempos de ejecución

  • Sin std::sort(data, data + arraySize); el código se ejecuta en 11.54 segundos.

  • Con los datos ordenados, el código se ejecuta en 1,93 segundos.

Inicialmente, puede pensarse que esto podría ser sólo una anomalía del lenguaje o del compilador. Así que lo probé en Java.

Y lo que fue es que obtuve los mismos resultados, aunque no con tanda diferencia entre un array ordenado y uno no ordenado.

Abajo trato de explicar que es lo que pasa ejemplificando el concepto de Branch Prediction de los procesadores modernos.

¿Que es Branch Prediction?

Considere un cruce ferroviario.

Ahora, por razones de argumento, supongamos que esto está de vuelta en la década de 1800 – antes de la larga distancia o comunicación por radio.

Usted es el operador de un cruce y escucha un tren que viene. No tienes ni idea de cómo se supone que var ir. Paras el tren para preguntar al conductor en qué dirección quieren ir. Y entonces usted fija el interruptor del cruce apropiadamente.

Los trenes son pesados y tienen mucha inercia. Así que tardan una eternidad en arrancar y retrasar.

¿Hay una mejor manera? ¡Adivinar en qué dirección va el tren!

Si adivinaste bien, sigue adelante.
Si adivinaste mal, el capitán se detendrá, retrocederá y te gritará para que tu le des la vuelta al interruptor. Entonces puede reiniciar por el otro camino.
Si conjeturas bien cada vez, el tren nunca tendrá que parar.
Si se equivoca demasiado a menudo, el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciándose.

Usted es un procesador y ve una ramificación del código. No tienes ni idea de hacia dónde irá. ¿Qué haces? Detener la ejecución y esperar hasta que las instrucciones anteriores estén completas. Luego continúa por el camino correcto.

Los procesadores modernos son complicados y tienen tuberías largas. Así que tardan una eternidad en “calentarse” y “reducir la velocidad”.

¿Hay una mejor manera? ¡Adivinar en qué dirección va la rama!

Si adivinaste bien, continuas ejecutando.
Si usted adivinó mal, usted necesita limpiar la tubería y volver a la rama. A continuación, puede reiniciar el otro camino.
Si usted adivina bien cada vez, la ejecución nunca tendrá que parar.
Si usted adivina mal demasiado a menudo, usted pasa mucho tiempo atascado, rueda hacia atrás y recomienza.

Esta es la predicción de la rama (Branch Prediction). Admito que no es la mejor analogía ya que el tren sólo podría señalar la dirección con una bandera. Pero en las computadoras, el procesador no sabe a qué dirección va una rama hasta el último momento.

Entonces, ¿cómo usted puede estratégicamente adivinar para minimizar el número de veces que el tren debe volver y bajar por el otro camino? ¡Mirando la historia pasada! Si el tren va a la izquierda el 99% del tiempo, entonces usted adivina a la izquierda. Si se alterna, entonces alternas tus conjeturas. Si va una manera cada 3 veces, usted adivina lo mismo …

En otras palabras, intenta identificar un patrón y seguirlo. Esto es más o menos cómo predictores de rama de trabajo.

La mayoría de las aplicaciones tienen ramas bien comportadas. Por lo tanto, los predictores de ramas modernas normalmente alcanzarán tasas de éxito > 90%. Pero cuando se enfrentan con ramas impredecibles sin patrones reconocibles, los predictores de ramas son prácticamente inútiles.

Ver: “Branch predictor” en Wikipedia.

Deja un comentario

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.