* str y * str ++

Question

tengo este código (mi función strlen)

size_t slen(const char *str) 
{ 
    size_t len = 0; 
    while (*str) 
    { 
     len++; 
     str++; 
    } 
    return len; 
} 

Haciendo while (*str++), como se muestra a continuación, el tiempo de ejecución del programa es mucho más grande:

while (*str++) 
{ 
    len++; 
} 

que estoy haciendo este para sondear el código

int main() 
{ 
    double i = 11002110; 
    const char str[] = "long string here blablablablablablablabla" 
    while (i--) 
     slen(str); 

    return 0; 
} 

en primer caso, el tiempo de ejecución es de alrededor de 6.7 segundos, mientras que en el segundo (utilizando *str++), ¡el tiempo es alrededor de 10 segundos!

¿Por qué tanta diferencia?

Answer 1

Probablemente porque el operador de incremento posterior (utilizado en la condición de la declaración while) implica mantener una copia temporal de la variable con su valor anterior.

Lo while (*str++) realmente quiere decir es:

while (tmp = *str, ++str, tmp) 
    ... 

Por el contrario, cuando se escribe str++; como una sola instrucción en el cuerpo del bucle while, es en un contexto vacío, por lo tanto, el valor antiguo no es buscado porque no es necesario.

En resumen, en el caso *str++ tiene una asignación, 2 incrementos y un salto en cada iteración del ciclo. En el otro caso, solo tienes 2 incrementos y un salto.

Answer 2

Probando esto en ideone.com, obtengo una ejecución de 0.5s con * str ++ here. Sin, lleva poco más de un segundo (here). Usar * str ++ fue más rápido. Tal vez con la optimización en * str ++ se puede hacer de manera más eficiente.

Answer 3

Esto depende de su compilador, indicadores del compilador y su arquitectura. Con LLVM gcc 4.2.1 de Apple, no obtengo un cambio notable en el rendimiento entre las dos versiones, y realmente no debería haber. Un buen compilador convertir la versión *str en algo así como

IA-32 (EN & T Sintaxis):

slen: 
     pushl %ebp    # Save old frame pointer 
     movl %esp, %ebp  # Initialize new frame pointer 
     movl -4(%ebp), %ecx # Load str into %ecx 
     xor %eax, %eax  # Zero out %eax to hold len 
loop: 
     cmpb (%ecx), $0  # Compare *str to 0 
     je done    # If *str is NUL, finish 
     incl %eax    # len++ 
     incl %ecx    # str++ 
     j  loop    # Goto next iteration 
done: 
     popl %ebp    # Restore old frame pointer 
     ret     # Return 

La versión *str++ se pudo efectuar exactamente el mismo (ya que los cambios a str no son visibles fuera slen, cuando el incremento se produce en realidad no es importante), o el cuerpo del bucle podría ser:

loop: 
     incl %ecx    # str++ 
     cmpb -1(%ecx), $0  # Compare *str to 0 
     je done    # If *str is NUL, finish 
     incl %eax    # len++ 
     j  loop    # Goto next iteration 

Answer 4

otros ya han proporcionado un excelente commen tary, incluido el análisis del código ensamblador generado. Recomiendo encarecidamente que los lea cuidadosamente. Como han señalado, este tipo de preguntas no pueden ser respondidas sin una cierta cuantificación, así que vamos a jugar un poco.

Primero, vamos a necesitar un programa. Nuestro plan es este: generaremos cadenas cuyas longitudes sean potencias de dos, y probaremos todas las funciones sucesivamente. Lo ejecutamos una vez para preparar el caché y luego, por separado, cronometrar 4096 iteraciones usando la resolución más alta disponible para nosotros. Una vez que hayamos terminado, calcularemos algunas estadísticas básicas: mínimo, máximo y el promedio de movimiento simple y lo volcaremos. Entonces podemos hacer un análisis rudimentario.

Además de los dos algoritmos que ya has mostrado, mostraré una tercera opción que no implica el uso de un contador en absoluto, confiando en cambio en una resta, y mezclaré cosas lanzando en std::strlen, solo para ver qué pasa. Será un lanzamiento interesante.

A través de la magia de la televisión de nuestro pequeño programa que ya está escrito, por lo que compilarlo con gcc -std=c++11 -O3 speed.c y obtenemos el arranque producir algunos datos. He hecho dos gráficos separados, uno para cadenas cuyo tamaño es de 32 a 8192 bytes y otro para cadenas cuyo tamaño es desde 16384 hasta 1048576 bytes de longitud. En los siguientes gráficos, el eje Y es el tiempo consumido en nanosegundos y el eje X muestra la longitud de la cadena en bytes.

Sin más preámbulos, vamos a ver el rendimiento para las "pequeñas" cuerdas de 32 a 8192 bytes:

ahora este es interesante. No solo la función std::strlen supera a todo en todos los ámbitos, sino que también lo hace con entusiasmo, ya que su rendimiento es mucho más estable.

¿Cambiará la situación si nos fijamos en las cadenas más grandes, desde 16.384 hasta llegar a 1.048.576 bytes de longitud?

o menos. La diferencia es cada vez más pronunciada. Como nuestras funciones escritas a medida huff-and-puff, std::strlen continúa funcionando admirablemente.

Una observación interesante es que no se puede traducir necesariamente el número de instrucciones de C++ (o incluso el número de instrucciones de ensamblaje) al rendimiento, ya que las funciones cuyos cuerpos contienen menos instrucciones a veces tardan más en ejecutarse.

Una observación aún más interesante - y importante es darse cuenta de lo bien que funciona la función str::strlen.

Entonces, ¿qué significa todo esto nos llegar?

Primera conclusión: No reinventar la rueda. Use las funciones estándar disponibles para usted. No solo están ya escritos, sino que están muy optimizados y seguramente superará a todo lo que pueda escribir a menos que sea Agner Fog.

Segunda conclusión: a menos que tenga datos duros de un generador de perfiles que una sección particular de código o función es punto caliente en su aplicación, no se moleste en optimizar el código. Los programadores son notoriamente malos a la hora de detectar puntos críticos observando la función de alto nivel.

Tercera conclusión: prefieren optimizaciones algorítmicas con el fin de mejorar el rendimiento del código. Pon tu mente a trabajar y deja que el compilador baraje los bits.

Su pregunta original era: "¿por qué la función slen2 es más lenta que slen1?" Podría decir que no es fácil responder sin mucha más información, y aun así podría ser mucho más larga y más complicada de lo que usted desea. En cambio, lo que voy a decir es lo siguiente:

quién le importa por qué?¿Por qué te molestas con esto? Utilice std::strlen - que es mejor que cualquier cosa que pueda armar - y pase a resolver problemas más importantes - porque estoy seguro de que este no es el mayor problema en su aplicación.