¿Diferencia de velocidad entre If-Else y el operador Ternary en C …?

Entonces, a sugerencia de un colega, acabo de probar la diferencia de velocidad entre el operador ternario y el bloque equivalente If-Else … y parece que el operador ternario produce un código que es entre 1x y 2x más rápido que If-Else. Mi código es:

gettimeofday(&tv3, 0); for(i = 0; i < N; i++) { a = i & 1; if(a) a = b; else a = c; } gettimeofday(&tv4, 0); gettimeofday(&tv1, 0); for(i = 0; i < N; i++) { a = i & 1; a = a ? b : c; } gettimeofday(&tv2, 0); 

(Lo siento por usar gettimeofday y no clock_gettime … Me esforzaré por mejorar).

Traté de cambiar el orden en el que sincronicé los bloques, pero los resultados parecen persistir. ¿Lo que da? Además, el If-Else muestra mucha más variabilidad en términos de velocidad de ejecución. ¿Debo examinar el conjunto que genera gcc?

Por cierto, esto es todo en el nivel de optimización cero (-O0).

¿Me estoy imaginando esto o hay algo que no estoy teniendo en cuenta o es algo dependiente de la máquina o qué? Cualquier ayuda es apreciada.

Hay una buena posibilidad de que el operador ternario se compile en un cmov mientras que el if / else resulta en un cmp + jmp . Simplemente eche un vistazo al ensamblaje (usando -S) para estar seguro. Con las optimizaciones habilitadas, no importará más de todos modos, ya que cualquier buen comstackdor debería producir el mismo código en ambos casos.

Esta es una buena explicación: http://www.nynaeve.net/?p=178

Básicamente, hay instrucciones del procesador de “conjunto condicional”, que es más rápido que la bifurcación y la configuración en instrucciones separadas.

También podría ir completamente sin sucursales y medir si hace alguna diferencia:

 int m = -(i & 1); a = (b & m) | (c & ~m); 

En las architectures actuales, este estilo de progtwigción se ha vuelto un poco pasado de moda.

Si hay alguno, ¡cambie su comstackdor!

Para este tipo de preguntas utilizo la página Try Out LLVM . Es un lanzamiento anterior de LLVM (sigue usando el front-end de gcc), pero esos son viejos trucos.

Aquí está mi pequeño progtwig de muestra (versión simplificada de la suya):

 #include  #include  #include  int main (int argc, char* argv[]) { int N = atoi(argv[0]); int a = 0, d = 0, b = atoi(argv[1]), c = atoi(argv[2]); int i; for(i = 0; i < N; i++) { a = i & 1; if(a) a = b+i; else a = c+i; } for(i = 0; i < N; i++) { d = i & 1; d = d ? b+i : c+i; } printf("%d %d", a, d); return 0; } 

Y está el IR de LLVM correspondiente generado:

 define i32 @main(i32 %argc, i8** nocapture %argv) nounwind { entry: %0 = load i8** %argv, align 8 ;  [#uses=1] %N = tail call i32 @atoi(i8* %0) nounwind readonly ;  [#uses=5] %2 = getelementptr inbounds i8** %argv, i64 1 ;  [#uses=1] %3 = load i8** %2, align 8 ;  [#uses=1] %b = tail call i32 @atoi(i8* %3) nounwind readonly ;  [#uses=2] %5 = getelementptr inbounds i8** %argv, i64 2 ;  [#uses=1] %6 = load i8** %5, align 8 ;  [#uses=1] %c = tail call i32 @atoi(i8* %6) nounwind readonly ;  [#uses=2] %8 = icmp sgt i32 %N, 0 ;  [#uses=2] br i1 %8, label %bb, label %bb11 bb: ; preds = %bb, %entry %9 = phi i32 [ %10, %bb ], [ 0, %entry ] ;  [#uses=2] %10 = add nsw i32 %9, 1 ;  [#uses=2] %exitcond22 = icmp eq i32 %10, %N ;  [#uses=1] br i1 %exitcond22, label %bb10.preheader, label %bb bb10.preheader: ; preds = %bb %11 = and i32 %9, 1 ;  [#uses=1] %12 = icmp eq i32 %11, 0 ;  [#uses=1] %.pn13 = select i1 %12, i32 %c, i32 %b ;  [#uses=1] %tmp21 = add i32 %N, -1 ;  [#uses=1] %a.1 = add i32 %.pn13, %tmp21 ;  [#uses=2] br i1 %8, label %bb6, label %bb11 bb6: ; preds = %bb6, %bb10.preheader %13 = phi i32 [ %14, %bb6 ], [ 0, %bb10.preheader ] ;  [#uses=2] %14 = add nsw i32 %13, 1 ;  [#uses=2] %exitcond = icmp eq i32 %14, %N ;  [#uses=1] br i1 %exitcond, label %bb10.bb11_crit_edge, label %bb6 bb10.bb11_crit_edge: ; preds = %bb6 %15 = and i32 %13, 1 ;  [#uses=1] %16 = icmp eq i32 %15, 0 ;  [#uses=1] %.pn = select i1 %16, i32 %c, i32 %b ;  [#uses=1] %tmp = add i32 %N, -1 ;  [#uses=1] %d.1 = add i32 %.pn, %tmp ;  [#uses=1] br label %bb11 bb11: ; preds = %bb10.bb11_crit_edge, %bb10.preheader, %entry %a.0 = phi i32 [ %a.1, %bb10.bb11_crit_edge ], [ %a.1, %bb10.preheader ], [ 0, %entry ] ;  [#uses=1] %d.0 = phi i32 [ %d.1, %bb10.bb11_crit_edge ], [ 0, %bb10.preheader ], [ 0, %entry ] ;  [#uses=1] %17 = tail call i32 (i8*, ...)* @printf(i8* noalias getelementptr inbounds ([6 x i8]* @.str, i64 0, i64 0), i32 %a.0, i32 %d.0) nounwind ;  [#uses=0] ret i32 0 } 

Está bien, entonces es probable que sea chino, a pesar de que fui adelante y cambié el nombre de algunas variables para que sea un poco más fácil de leer.

Los bits importantes son estos dos bloques:

  %.pn13 = select i1 %12, i32 %c, i32 %b ;  [#uses=1] %tmp21 = add i32 %N, -1 ;  [#uses=1] %a.1 = add i32 %.pn13, %tmp21 ;  [#uses=2] %.pn = select i1 %16, i32 %c, i32 %b ;  [#uses=1] %tmp = add i32 %N, -1 ;  [#uses=1] %d.1 = add i32 %.pn, %tmp ;  [#uses=1] 

Que establecen respectivamente a y d .

Y la conclusión es: No hay diferencia

Nota: en un ejemplo más simple, las dos variables realmente se fusionaron, parece que aquí el optimizador no detectó la similitud ...

Cualquier comstackdor decente debería generar el mismo código para estos si la optimización está activada.

Comprenda que depende completamente del comstackdor cómo interpreta la expresión ternaria (a menos que realmente lo fuerce a no hacerlo con (en línea) asm). Podría fácilmente entender la expresión ternaria como ‘if..else’ en su lenguaje de Representación Interna, y dependiendo del back-end de destino, puede optar por generar instrucciones de movimiento condicional (en x86, CMOVcc es tal. También debe haber unos para min / max, abs, etc.). La principal motivación para usar un movimiento condicional es transferir el riesgo de error de trazado a una operación de movimiento de memoria / registro. La advertencia de esta instrucción es que casi todo el tiempo, el registro de operandos que se cargará de forma condicional tendrá que ser evaluado hacia abajo para registrar el formulario para aprovechar la instrucción cmov.

Esto significa que el proceso de evaluación incondicional ahora tiene que ser incondicional, y esto parecerá boost la duración de la ruta incondicional del progtwig. Pero entiendo que el error de la sucursal se resuelve con mayor frecuencia como ‘enjuagar’ la tubería, lo que significa que las instrucciones que habrían terminado de ejecutarse se ignoran (volteadas a las instrucciones de No Operation). Esto significa que el número real de instrucciones ejecutadas es más alto debido a los lockings o NOP, y el efecto aumenta con la profundidad de la canalización del procesador y la tasa de errores de predicción.

Esto trae un dilema interesante para determinar la heurística correcta. En primer lugar, sabemos con certeza que si la canalización es demasiado poco profunda o si la predicción de la twig es totalmente capaz de aprender el patrón a partir del historial de la sucursal, no vale la pena hacerlo. Tampoco vale la pena hacerlo si el costo de la evaluación del argumento condicional es mayor que el costo de la mala predicción en promedio.

Estas son quizás las principales razones por las que los comstackdores tienen dificultades para explotar la instrucción cmov, ya que la determinación heurística depende en gran medida de la información de perfil de tiempo de ejecución. Tiene más sentido usar esto en el comstackdor JIT ya que puede proporcionar retroalimentación de instrumentación de tiempo de ejecución y construir una heurística más fuerte para usar esto (“¿Es la twig verdaderamente impredecible?”). En el lado del comstackdor estático sin datos de formación o perfilador, es más difícil suponer cuándo será útil. Sin embargo, una heurística negativa simple es, como se mencionó anteriormente, si el comstackdor sabe que el conjunto de datos es completamente aleatorio o forza a cond. para olvidar la evaluación es costosa (quizás debido a operaciones irreductibles y costosas como fp divide), sería una buena heurística no hacerlo.

Cualquier comstackdor digno de su sal hará todo eso. La pregunta es, ¿qué hará después de que se hayan agotado todas las heurísticas confiables?