c++ - una - vectorizar imagen gimp

¿Por qué la vectorización de árboles hace que este algoritmo de clasificación sea 2 veces más lento?

Question

El algoritmo de clasificación de esta pregunta se vuelve dos veces más rápido (!) Si se habilita -fprofile-arcs en gcc (4.7.2). El código C muy simplificado de esa pregunta (resultó que puedo inicializar la matriz con todos los ceros, el comportamiento extraño del rendimiento permanece pero hace que el razonamiento sea mucho más simple):

#include <time.h>
#include <stdio.h>

#define ELEMENTS 100000

int main() {
  int a[ELEMENTS] = { 0 };
  clock_t start = clock();
  for (int i = 0; i < ELEMENTS; ++i) {
    int lowerElementIndex = i;
    for (int j = i+1; j < ELEMENTS; ++j) {
      if (a[j] < a[lowerElementIndex]) {
        lowerElementIndex = j;
      }
    }
    int tmp = a[i];
    a[i] = a[lowerElementIndex];
    a[lowerElementIndex] = tmp;
  } 
  clock_t end = clock();
  float timeExec = (float)(end - start) / CLOCKS_PER_SEC;
  printf("Time: %2.3f/n", timeExec);
  printf("ignore this line %d/n", a[ELEMENTS-1]);
}

Después de jugar con las banderas de optimización por un largo tiempo, resultó que -ftree-vectorize también produce este comportamiento extraño, por lo que podemos -fprofile-arcs de la pregunta. Después de perfilar con perf , he encontrado que la única diferencia relevante es:

Caso rápido gcc -std=c99 -O2 simp.c (se ejecuta en 3.1s)

    cmpl    %esi, %ecx
    jge .L3
    movl    %ecx, %esi
    movslq  %edx, %rdi
.L3:

Caso lento gcc -std=c99 -O2 -ftree-vectorize simp.c (funciona en 6.1s)

    cmpl    %ecx, %esi
    cmovl   %edx, %edi
    cmovl   %esi, %ecx

En cuanto al primer fragmento de código: dado que la matriz solo contiene ceros, siempre .L3 a .L3 . Puede beneficiarse enormemente de la predicción de la rama.

Supongo que las instrucciones de cmovl no pueden beneficiarse de la predicción de rama.

Preguntas:

1. ¿Son correctas todas mis suposiciones anteriores? ¿Esto hace que el algoritmo sea lento?

2. En caso afirmativo, ¿cómo puedo evitar que gcc -fno-tree-vectorization esta instrucción (aparte de la -fno-tree-vectorization trivial de -fno-tree-vectorization supuesto) pero que siga haciendo tantas optimizaciones como sea posible?

3. ¿Qué es esta -ftree-vectorization ? La documentación es bastante vaga, necesitaría un poco más de explicación para entender lo que está sucediendo.

Actualización: desde que surgió en los comentarios: el extraño comportamiento de desempeño en la -ftree-vectorize permanece con datos aleatorios. Como señala Yakk , para la clasificación por selección, en realidad es difícil crear un conjunto de datos que podría resultar en muchas predicciones erróneas de las sucursales.

Como también surgió: tengo una CPU Core i5.

Basado en el comentario de Yakk , creé una prueba. El código a continuación (en línea sin aumento ) ya no es un algoritmo de clasificación; Solo saqué el bucle interno. Su único objetivo es examinar el efecto de la predicción de rama: omitimos la rama if en el bucle for con probabilidad p .

#include <algorithm>
#include <cstdio>
#include <random>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::chrono;
constexpr int ELEMENTS=1e+8; 
constexpr double p = 0.50;

int main() {
  printf("p = %.2f/n", p);
  int* a = new int[ELEMENTS];
  mt19937 mt(1759);
  bernoulli_distribution rnd(p);
  for (int i = 0 ; i < ELEMENTS; ++i){
    a[i] = rnd(mt)? i : -i;
  }
  auto start = high_resolution_clock::now();
  int lowerElementIndex = 0;
  for (int i=0; i<ELEMENTS; ++i) {
    if (a[i] < a[lowerElementIndex]) {
      lowerElementIndex = i;
    }
  } 
  auto finish = high_resolution_clock::now();
  printf("%ld  ms/n", duration_cast<milliseconds>(finish-start).count());
  printf("Ignore this line   %d/n", a[lowerElementIndex]);
  delete[] a;
}

Los bucles de interés:

Esto será referido como cmov

g++ -std=c++11 -O2 -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L30:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    movslq  %eax, %rdx
    cmovl   %rdx, %rbp
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L30

Esto se denominará como no cmov , la -fno-if-conversion fue señalada por Turix en su respuesta.

g++ -std=c++11 -O2 -fno-if-conversion -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L29:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    jge .L28
    movslq  %eax, %rbp
.L28:
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L29

La diferencia lado a lado

cmpl    %edx, (%rbx,%rax,4) |     cmpl  %edx, (%rbx,%rax,4)
movslq  %eax, %rdx          |     jge   .L28
cmovl   %rdx, %rbp          |     movslq    %eax, %rbp
                            | .L28:

El tiempo de ejecución en función del parámetro p Bernoulli.

El código con la instrucción cmov es absolutamente insensible a p . El código sin la instrucción cmov es el ganador si p<0.26 o 0.81<p y es 4.38x más rápido ( p=1 ). Por supuesto, la peor situación para el predictor de rama es alrededor de p=0.5 donde el código es 1.58x más lento que el código con la instrucción cmov .

Answer 1

Nota: Respondida antes de agregar la actualización del gráfico a la pregunta Algunas referencias de código ensamblador aquí pueden ser obsoletas.

(Adaptado y extendido de nuestro chat anterior, que fue lo suficientemente estimulante como para que yo haga un poco más de investigación).

Primero (según nuestro chat anterior), parece que la respuesta a su primera pregunta es "sí". En el vector "código optimizado", la optimización que afecta (negativamente) al rendimiento es la predicción de ramificación, mientras que en el código original el rendimiento se ve (positivamente) afectado por la predicción de ramificación. (Note la '' a '' extra en el primero.)

Re su tercera pregunta: aunque en su caso, en realidad no se está haciendo vectorización, desde el paso 11 ("Ejecución condicional") here parece que uno de los pasos asociados con las optimizaciones de vectorización es "aplanar" los condicionales dentro de los bucles dirigidos, como este bit en tu bucle:

if (a[j] < a[lowerElementIndex]
    lowerElementIndex = j;

Aparentemente, esto sucede incluso si no hay vectorización.

Esto explica por qué el compilador está utilizando las instrucciones de movimiento condicional ( cmovl ). El objetivo es evitar una rama por completo (en lugar de intentar predecirla correctamente). En su lugar, las dos instrucciones de cmovl se enviarán por la tubería antes de que se conozca el resultado del cmpl anterior y el resultado de la comparación se "reenviará" para habilitar / prevenir los movimientos antes de su escritura (es decir, antes de que realmente tengan efecto) ).

Tenga en cuenta que si el bucle se ha vectorizado, esto podría haber valido la pena para llegar al punto en el que múltiples iteraciones a través del bucle podrían realizarse efectivamente en paralelo.

Sin embargo, en su caso, el intento de optimización realmente fracasa porque en el bucle aplanado, los dos movimientos condicionales se envían a través de la tubería cada vez que se realiza el bucle. Esto en sí mismo tampoco puede ser tan grave, excepto que existe un peligro de datos RAW que hace que el segundo movimiento ( cmovl %esi, %ecx ) tenga que esperar hasta que el acceso a la matriz / memoria ( movl (%rsp,%rsi,4), %esi ) se completa, incluso si el resultado se ignorará en última instancia. Por lo tanto, el gran tiempo dedicado a ese cmovl particular. (Espero que esto sea un problema porque su procesador no tenga una lógica lo suficientemente compleja incorporada en su implementación de predicción / reenvío para enfrentar el peligro).

Por otro lado, en el caso no optimizado, como acertadamente descubrió, la predicción de bifurcaciones puede ayudar a evitar tener que esperar el resultado del acceso de matriz / memoria correspondiente allí (el movl (%rsp,%rcx,4), %ecx instrucción movl (%rsp,%rcx,4), %ecx ). En ese caso, cuando el procesador predice correctamente una rama tomada (que para una matriz todo-0 será cada vez, pero [incluso] en una matriz aleatoria debería [todavía] estar aproximadamente más de [editado por @ el comentario de Yakk] la mitad del tiempo), no tiene que esperar a que termine el acceso a la memoria para continuar y poner en cola las siguientes instrucciones del bucle. Por lo tanto, en las predicciones correctas, obtienes un impulso, mientras que en las predicciones incorrectas, el resultado no es peor que en el caso "optimizado" y, además, es mejor debido a la capacidad de evitar a veces tener las instrucciones " cmovl " desperdiciadas de cmovl en la tubería .

[Lo siguiente se eliminó debido a mi suposición errónea acerca de su procesador por su comentario.]
De vuelta a sus preguntas, sugeriría buscar en el enlace de arriba para obtener más información sobre las banderas relevantes para la vectorización, pero al final, estoy bastante seguro de que está bien ignorar esa optimización dado que Celeron no es capaz de usarla (En este contexto) de todos modos.

[Agregado después de que se eliminó lo anterior]
Con respecto a la segunda pregunta (" ... ¿cómo puedo evitar que gcc emita esta instrucción ... "), puede probar los -fno-if-conversion y -fno-if-conversion2 (no estoy seguro de si siempre funcionan - - ya no funcionan en mi mac), aunque no creo que su problema sea con la instrucción cmovl en general (es decir, no siempre usaría esas banderas), solo con su uso en este contexto particular (donde la predicción de rama es va a ser muy útil dado el punto de @ Yakk sobre su algoritmo de clasificación).