¿Por qué este bucle de retardo comienza a ejecutarse más rápido después de varias iteraciones sin suspensión?

Question

¿Por qué este bucle de retardo comienza a ejecutarse más rápido después de varias iteraciones sin suspensión?

Considere:

#include <time.h>
#include <unistd.h>
#include <iostream>
using namespace std;

const int times = 1000;
const int N = 100000;

void run() {
  for (int j = 0; j < N; j++) {
  }
}

int main() {
  clock_t main_start = clock();
  for (int i = 0; i < times; i++) {
    clock_t start = clock();
    run();
    cout << "cost: " << (clock() - start) / 1000.0 << " ms." << endl;
    //usleep(1000);
  }
  cout << "total cost: " << (clock() - main_start) / 1000.0 << " ms." << endl;
}

Aquí está el código de ejemplo. En las primeras 26 iteraciones del bucle de sincronización, la función run cuesta alrededor de 0.4 ms, pero luego el costo se reduce a 0.2 ms.

Cuando el usleep no está comentado, el delay-loop toma 0.4 ms para todas las corridas, nunca acelerando. ¿Por qué?

El código se compila con g++ -O0 (sin optimización), por lo que el bucle de retardo no se optimiza. Se ejecuta en Intel(R) Core(TM) i3-3220 CPU @ 3.30 GHz, con 3.13.0-32-generic Ubuntu 14.04.1 LTS (Trusty Tahr).

70

performance c++linux benchmarking

Author: Peter Cordes, 2016-07-11

Source

2 answers

Una llamada a usleep puede o no resultar en un cambio de contexto. Si lo hace, tomará más tiempo que si no lo hace.

3

Author: David Schwartz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-07-11 04:12:17

score 121 · Accepted Answer

Después de 26 iteraciones, Linux aumenta la CPU hasta la velocidad máxima del reloj ya que su proceso utiliza su rebanada de tiempo completa un par de veces seguidas.

Si se comprueba con contadores de rendimiento en lugar de tiempo de reloj de pared, se vería que los ciclos de reloj de núcleo por delay-loop se mantuvo constante, confirmando que es solo un efecto de DVFS (que todas las CPU modernas utilizan para funcionar a una frecuencia y voltaje más eficiente de energía la mayor parte del tiempo).

Si se realizó la prueba en un Skylake con soporte del kernel para el nuevo modo de administración de energía (donde el hardware toma el control total de la velocidad del reloj) , la aceleración ocurriría mucho más rápido.

Si lo deja funcionando durante un tiempo en una CPU Intel con Turbo, probablemente verá que el tiempo por iteración aumenta nuevamente ligeramente una vez que los límites térmicos requieran que la velocidad del reloj se reduzca nuevamente a la frecuencia máxima sostenida.

Introducción de un usleep evita que el regulador de frecuencia de CPU de Linux aumente la velocidad del reloj, porque el proceso no genera una carga del 100%, incluso a una frecuencia mínima. (Es decir, la heurística del núcleo decide que la CPU se está ejecutando lo suficientemente rápido para la carga de trabajo que se está ejecutando en él.)

Comentarios sobre otras teorías:

Re: La teoría de David de que un posible cambio de contexto desde {[0] } podría contaminar los cachés: No es una mala idea en general, pero no lo hace ayuda a explicar este código.

La contaminación de Cache / TLB no es importante en absoluto para este experimento. Básicamente no hay nada dentro de la ventana de tiempo que toque la memoria que no sea el final de la pila. La mayor parte del tiempo se pasa en un pequeño bucle (1 línea de caché de instrucciones) que solo toca un int de memoria de pila. Cualquier posible contaminación de caché durante usleep es una pequeña fracción del tiempo para este código (el código real será diferente)!

Con más detalle para x86:

La llamada a clock() en sí misma podría fallar en la caché, pero una falla en la caché de recuperación de código retrasa la medición del tiempo de inicio, en lugar de ser parte de lo que se mide. La segunda llamada a clock() casi nunca se retrasará, porque todavía debería estar caliente en caché.

La función run puede estar en una línea de caché diferente de main (ya que gcc marca main como "frío", por lo que se optimiza menos y se coloca con otras funciones/datos fríos). Podemos esperar uno o dos caché de instrucciones misses . Sin embargo, probablemente todavía estén en la misma página 4k, por lo que main habrá disparado el potencial TLB miss antes de ingresar a la región cronometrada del programa.

Gcc-O0 compilará el código del OP a algo como esto (explorador de compiladores de Godbolt): manteniendo el contador de bucle en la memoria en la pila.

El bucle vacío mantiene el contador de bucles en la memoria de pila, por lo que en una CPU típica Intel x86 el bucle se ejecuta en una iteración por ~6 ciclos en los OP's CPU IvyBridge, gracias a la latencia de reenvío de almacén que forma parte de add con un destino de memoria (lectura-modificación-escritura). 100k iterations * 6 cycles/iteration es 600k ciclos, que domina la contribución de como máximo un par de errores de caché (~200 ciclos cada uno para errores de recuperación de código que impiden que se emitan instrucciones adicionales hasta que se resuelvan).

La ejecución fuera de orden y el reenvío de almacenes deben ocultar principalmente la posible falta de caché al acceder a la pila (como parte de la call instrucción).

Incluso si el contador de bucle se mantuvo en un registro, 100k ciclos es mucho.