Iteradores C++ y optimización de bucles

Las dos versiones no son las mismas. En la segunda versión se compara el iterador con list.end() cada vez, y lo que list.end() evalúa podría cambiar en el transcurso del bucle. Ahora, por supuesto, no se puede modificar list a través del const_iterator it; pero nada impide que el código dentro del bucle simplemente llame a métodos en list directamente y lo mute, lo que podría (dependiendo del tipo de estructura de datos list) cambiar el iterador final. Por lo tanto, podría ser incorrecto en algunos circunstancias para almacenar el iterador final de antemano, porque puede que ya no sea el iterador final correcto en el momento en que llegue a él.

El primero probablemente será casi siempre más rápido, pero si crees que esto hará una diferencia, siempre perfila primero para ver cuál es más rápido y por cuánto.

El compilador probablemente podrá insertar la llamada a end() en ambos casos, aunque si end() es suficientemente complicado, puede optar por no insertarla. Sin embargo, la optimización clave es si el compilador puede o no realizar movimiento de código invariante en bucle. Yo postularía que en la mayoría de los casos, el el compilador no puede estar seguro de que el valor de end() no cambiará durante la iteración del bucle, en cuyo caso no tiene más remedio que llamar a end() después de cada iteración.

Elegiría la opción que sea más concisa y legible. No intente adivinar el compilador y las optimizaciones que podría realizar. Recuerde que la gran mayoría de su código no tendrá absolutamente ningún efecto en el rendimiento general, por lo que solo si esto se encuentra en una sección crítica de rendimiento del código debe pasar el tiempo para perfilarlo y elegir una representación de origen adecuadamente eficiente.

Con referencia específica a su ejemplo, la primera versión hace un copy del iterador end(), invocando cualquier código que se ejecute para el constructor de copia del objeto iterador. Los contenedores STL generalmente contienen funciones inline end(), por lo que el compilador tiene muchas oportunidades para optimizar la segunda versión, incluso si no está tratando de ayudarlo. ¿Cuál es el mejor? Mídelos.

Puedes hacer la primera versión más concisa y obtener lo mejor de ambas:

for( const_iterator it = list.begin(), ite = list.end();
     it != ite; ++it)

P.d. Los iteradores no son const, son iteradores a una referencia const. Hay una gran diferencia.

Considere este ejemplo:

for (const_iterator it = list.begin(); it != list.end(); ++list)
{
    if (moonFull())
        it = insert_stuff(list);
    else
        it = erase_stuff(list);
}

En este caso, necesita llamar a list.end() en el bucle, y el compilador no va a optimizar eso.

Otros casos donde el compilador puede probar que end() siempre devuelve el mismo valor, la optimización puede tener lugar.

Si estamos hablando de contenedores STL, entonces creo que cualquier buen compilador puede optimizar múltiples llamadas end() cuando múltiples llamadas end() no son necesarias para la lógica de programación. Sin embargo, si usted tiene un el contenedor personalizado y la implementación de end () no están en la misma unidad de traducción, que la optimización tendrá que ocurrir en el momento del enlace. Sé muy poco sobre la optimización del tiempo de enlace, pero apuesto a que la mayoría de los enlazadores no harán tal optimización.

Aah, la gente parece estar haciendo conjeturas. Abra su código en el depurador y verá que las llamadas a begin (), end (), etc. todo está optimizado. No es necesario utilizar la versión 1. Probado con Visual C++ compiler fullopt.

El compilador podría ser capaz de optimizar el segundo en el primero, pero eso asume que los dos son equivalentes, es decir, end() en realidad es constante. Un problema un poco más problemático es que el compilador puede ser incapaz de deducir que el iterador final es constante debido a un posible aliasing. Sin embargo, suponiendo que la llamada a end() está en línea, la diferencia es solo una carga de memoria.

Tenga en cuenta que esto supone que el optimizador está habilitado. Si el optimizador no está habilitado, como se hace a menudo en las compilaciones de depuración, la segunda formulación implicará N-1 más llamadas a funciones. En las versiones actuales de Visual C++, las compilaciones de depuración también incurrirán en visitas adicionales debido a las comprobaciones de funciones prolog/epilog y a los iteradores de depuración más pesados. Por lo tanto, en código pesado STL, la omisión en el primer caso puede evitar que el código sea desproporcionadamente lento en compilaciones de depuración.

La inserción y eliminación dentro del bucle son una posibilidad, como otros han señalado, pero con este estilo de bucle encuentro que probable. Por un lado, los contenedores basados en nodos list list, set, map't no invalidan end() en ninguna de las operaciones. En segundo lugar, el incremento del iterador con frecuencia tiene que ser movido en bucle para evitar problemas de invalidación:

   // assuming list -- cannot cache end() for vector
   iterator it(c.begin()), end(c.end());
   while(it != end) {
       if (should_remove(*it))
           it = c.erase(it);
       else
           ++it;
   }

Por lo tanto, considero sospechoso un bucle que afirma llamar a end() por razones de mutar durante el bucle y aún tiene ++en la cabecera del bucle.

Siempre he preferido el primero. Aunque con funciones en línea, optimizaciones de compiladores y un tamaño de contenedor relativamente más pequeño (en mi caso, normalmente es un máximo de 20-25 elementos), realmente no hace ninguna gran diferencia con respecto al rendimiento.

const_iterator it = list.begin();
const_iterator endIt = list.end();

for(; it != endIt ; ++it)
{//do something
}

Pero recientemente estoy usando más de std::for_each donde sea posible. Su bucle optimizado que ayuda a hacer que el código se vea más legible que otros dos.

std::for_each(list.begin(), list.end(), Functor());

Usaré el bucle solo cuando std::for_each no pueda ser utilizar. (por ejemplo: std::for_each no le permite romper el bucle a menos que se lance una excepción).

1. Sample en condiciones de estrés y ver si usted está en ** este código muy a menudo ***.
   Si no, no importa.

2. Si es así, mira el desmontaje, o un solo paso.
   Así es como puedes saber cuál es más rápido.

Tienes que tener cuidado con estos iteradores.
Pueden optimizarse en código máquina agradable, pero a menudo no lo hacen, y se convierten en cerdos del tiempo.

** (Donde " in " significa realmente en él, o ser llamado desde se.)

*** (Donde "a menudo" significa un porcentaje significativo del tiempo.)

AGREGADO: No solo vea cuántas veces por segundo se ejecuta el código. Podría ser 1.000 veces por segundo y todavía estar usando menos del 1% del tiempo.

Tampoco cronometres cuánto tiempo lleva. Podría tomar un milisegundo y todavía estar usando menos del 1% del tiempo.

Podrías multiplicar los dos, para tener una mejor idea, pero eso solo funciona si no están demasiado sesgados.

Muestreo de la call stack le dirá si utiliza un porcentaje de tiempo lo suficientemente alto como para importar.

En teoría, el compilador podría optimizar la segunda versión en la primera (suponiendo que el contenedor no cambie durante el bucle, obviamente).

En la práctica, he encontrado varios casos similares al perfilar código de tiempo crítico donde mi compilador ha fallado totalmente en levantar cálculos invariantes fuera de las condiciones de bucle. Así que mientras que la versión un poco más concisa está bien en la mayoría de los casos, no confío en el compilador haciendo cosas sensatas con él para un caso en el que estoy realmente preocupado sobre el rendimiento.