El algoritmo de clasificación deesta pregunta se vuelve dos veces más rápido (!) si-fprofile-arcs está habilitado 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 para que podamos tomar-fprofile-arcs fuera de la cuestión. Después de perfilar conperf He encontrado queLa única diferencia relevante es:

Caso rapidogcc -std=c99 -O2 simp.c (se ejecuta en 3.1s)

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

Caso lentogcc -std=c99 -O2 -ftree-vectorize simp.c (se ejecuta 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 saltamos a.L3. Puede beneficiarse enormemente de la predicción de la rama.

Supongo que elcmovl Las instrucciones no pueden beneficiarse de la predicción de rama.

Preguntas:

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

En caso afirmativo, ¿cómo puedo evitar que gcc emita esta instrucción (aparte del trivial)?-fno-tree-vectorization solución por supuesto) pero sigue haciendo tantas optimizaciones como sea posible?

Que es esto-ftree-vectorization? La documentación es bastante vago, necesitaría un poco más de explicación para entender lo que está sucediendo.

Actualizar: Desde que surgió en los comentarios: El comportamiento de rendimiento extraño w.r.t. la-ftree-vectorize La bandera permanece con datos aleatorios.Como señala YakkPara el tipo de selección, en realidad es difícil crear un conjunto de datos que podría dar lugar a muchas predicciones erróneas de sucursales.

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

Basado en el comentario de Yakk., He creado una prueba. El código de abajo (en línea sin impulso) por supuesto 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:Nos saltamos elif rama en elfor bucle con probabilidadp.

#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 comocmov

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 será referido comono cmov, la-fno-if-conversion bandera fue señalada porTurix 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 de Bernoulli.p

El código con elcmov la instrucción es absolutamente insensible ap. El códigosin lacmov la instrucción es el ganador sip<0.26 o0.81<p y es a lo sumo 4.38x más rápido (p=1). Por supuesto, la peor situación para el predictor de rama es alrededor dep=0.5 donde el código es 1.58x más lento que el código con elcmov instrucción.