¿Son los const_iterators más rápidos?

Question

Nuestras pautas de codificación prefieren const_iterator, porque son un poco más rápidas en comparación con un iterator normal. Parece que el compilador optimiza el código cuando usa const_iterator.

¿Es esto realmente correcto? En caso afirmativo, ¿qué sucede realmente internamente que hace que const_iterator sea más rápido ?.

EDIT: I escribió pequeña de prueba para comprobar const_iterator vs iterator y han encontrado resultados variables:

para iterar 10.000 objetos const_terator estaba tomando un pocos milisegundos (alrededor de 16 ms) menos. Pero no siempre. Hubo iteraciones en las que ambos fueron iguales.

Answer 1

Por lo menos, una const_iterator lee mejor, ya que se dice que cualquiera que lea el código "Estoy interactuando sobre este contenedor, no jugar con los objetos contenidos".

Esa es una gran gran victoria, no importa las diferencias de rendimiento.

Answer 2

container<T>::const_iterator::operator* devuelve un const T& en lugar de T&, por lo que el compilador puede hacer las optimizaciones habituales para los objetos const.

Answer 3

No puedo ver por qué serían - constness es una verificación de tiempo de compilación. Pero la respuesta obvia es escribir una prueba.

Editar: Aquí es mi prueba - que da tiempos idénticos en mi máquina:

#include <vector> 
#include <iostream> 
#include <ctime> 
using namespace std;; 


int main() { 
    vector <int> v; 
    const int BIG = 10000000; 
    for (int i = 0; i < BIG; i++) { 
     v.push_back(i); 
    } 
    cout << "begin\n"; 
    int n = 0; 
    time_t now = time(0); 
    for (int a = 0; a < 10; a++) { 
     for(vector <int>::iterator it = v.begin(); it != v.end(); ++it) { 
      n += *it; 
     } 
    } 
    cout << time(0) - now << "\n"; 
    now = time(0); 
    for (int a = 0; a < 10; a++) { 
     for(vector <int>::const_iterator cit = v.begin(); cit != v.end(); ++cit) { 
      n += *cit; 
     } 
    } 
    cout << time(0) - now << "\n";; 

    return n != 0; 

} 

Answer 4

que mi experiencia, el compilador no hace ninguna optimización medible cuando se utiliza iteradores const. Aunque la afirmación "podría" es verdadera y las referencias no están definidas como punteros en el estándar.

Sin embargo, puede tener dos referencias al mismo objeto, por lo que uno puede ser const, uno no const. Entonces, supongo que se aplican las respuestas en this thread on restrict pointers: el compilador no puede saber si el objeto ha sido cambiado por otro hilo, por ejemplo, o por algún código de manejo de interrupciones.

Answer 5

Nuestras directrices de codificación dicen preferir const_iterator

Tener un vistazo a este article by Scott Meyers here. Él explica por qué uno debería preferir iterador sobre const_iterator.

Answer 6

La pauta que utilizamos es:

prefieren siempre const sobre no constante

Si usted tiende a utilizar objeto constante, que se acostumbre al uso de operaciones única constante en los objetos que recibe y que es tanto como usar const_iterator tanto como sea posible.

Constness tiene viral propiedad. Una vez que lo usa, se propaga a todo su código.Sus métodos no mutantes se vuelven constantes, y eso requiere usar solo operaciones constantes en los atributos, y pasar referencias constantes alrededor, que a su vez fuerza operaciones constantes ...

Para mí, la ventaja de rendimiento de usar iteradores constantes sobre no iteradores constantes (si hay alguno) es mucho menos importante que la mejora en el código en sí. Las operaciones significadas (diseñadas) para no mutar son constantes.

Answer 7

"Const-ness", como la restricción de acceso (público, protegido, privado), beneficia al programador más de lo que ayuda con la optimización.
Los compiladores no se pueden optimizar para tantas situaciones que impliquen const como se podría pensar, por muchas razones (como const_cast, miembros de datos mutables, alias de puntero/referencia). Sin embargo, la razón más relevante aquí es que, solo porque un const_iterator no permite modificar los datos a los que se refiere, eso no significa que esos datos no se puedan cambiar por otros medios. Y si el compilador no puede determinar que los datos son de solo lectura, entonces realmente no puede optimizar mucho más de lo que sería para el caso del iterador no const.
Más información y ejemplos se pueden encontrar en: http://www.gotw.ca/gotw/081.htm

Answer 8

Son para no triviales contenedores/iteradores. Establezca sus hábitos y no perderá rendimiento cuando sí importa.

Además, hay varias razones para preferir const_iterator, no importa qué:

1. El uso de const expresa la intención del código (es decir, la lectura solamente, no hay mutante de estos objetos).
2. El uso de const (_iterator) evita la modificación accidental de datos. (ver arriba)
3. Algunas bibliotecas usan la falta de const begin() para marcar los datos como sucios (es decir, OpenSG) y lo enviarán a otros hilos/sobre red en sincronía, por lo que tiene implicaciones de rendimiento real.
4. Además, permitirle acceder a las funciones miembro no constantes podría tener efectos colaterales que no tiene la intención (más o menos de la misma manera que en el caso anterior), por ejemplo, separar contenedores de copia de escritura de datos compartidos. Qt por uno, hace exactamente eso.

Como ejemplo de este último punto anterior, aquí está un extracto de qmap.h en Qt:

inline iterator begin() { detach(); return iterator(e->forward[0]); } 
inline const_iterator begin() const { return const_iterator(e->forward[0]); } 

Incluso si iterador y const_iterator son prácticamente equivalentes (a excepción de la const), detach() crea una nueva copia de los datos si hay dos o más objetos que la usan. Esto es completamente inútil si solo va a leer los datos, que indica usando const_iterator.

Por supuesto, existen puntos de datos en la otra dirección:

1. Para contenedores STL y muchos contenedores y sencilla-copy-semánticas no importará para el rendimiento. El código es equivalente. Sin embargo, el capaz de escribir código claro y evitar errores gana.
2. Const es viral, por lo que si está trabajando en una base de código heredada donde const tiene poca (o simplemente no) implementación, es posible que tenga que trabajar con iteradores no const.
3. Aparentemente, algunos C++ anteriores a C++ 0x tienen un error por el cual no se pueden usar const_iterators para borrar() elementos de los contenedores.

Answer 9

Depende del contenedor y la implementación que utilice.

Sí, const_iteratorpuede realizar mejor.

Para algunos contenedores, la implementación de const iterators e iteradores mutables puede diferir de. Un primer ejemplo que puedo pensar es el SGI's STL rope container. El iterador mutable tiene un puntero adicional al cable principal para admitir actualizaciones. Esto implica recursos adicionales desperdiciados para las actualizaciones de recuento de referencias + memoria para el puntero a la cuerda principal. Vea el implementation notes here.

Sin embargo, como han dicho otros, el compilador no puede usar const solo para realizar la optimización. const solo otorga acceso de solo lectura al objeto al que se hace referencia en lugar de decir que es inmutable. Para un contenedor como std::vector, cuyos iteradores generalmente se implementan como punteros simples, no habrá ninguna diferencia.

Answer 10

Cuando compara este aspecto, asegúrese de utilizar un nivel de optimización adecuado: obtendrá tiempos increíblemente diferentes utilizando "-O0" contra "-O" y tal.

Answer 11

Deben ser idénticos, ya que la constness es una verificación en tiempo de compilación.

Para probarme a mí mismo que no había caprichos, tomé el código de anon, lo modifiqué para usar clock_gettime, agregué un bucle externo para evitar sesgos en el almacenamiento en caché y lo ejecuté varias veces. Los resultados fueron sorprendentemente inconsistentes: subieron y bajó un 20% (no hay cajas inactivas disponibles), pero veces mínimas para ambos iterator y const_iterator fueron prácticamente idénticos.

entonces conseguí mi compilador (GCC 4.5.2 -O3) para generar salida de ensamblaje y visualmente comparado los dos bucles idénticos: (excepto que el orden de las cargas de un par de registro se invirtió)

iterator bucle

call clock_gettime 
    movl 56(%esp), %esi 
    movl $10, %ecx 
    movl 60(%esp), %edx 
    .p2align 4,,7 
    .p2align 3 
.L35: 
    cmpl %esi, %edx 
    je .L33 
    movl %esi, %eax .p2align 4,,7 
    .p2align 3 
.L34: 
    addl (%eax), %ebx 
    addl $4, %eax 
    cmpl %eax, %edx 
    jne .L34 
.L33: 
    subl $1, %ecx 
    jne .L35 
    leal 68(%esp), %edx 
    movl %edx, 4(%esp) 
    leal 56(%esp), %esi 
    movl $1, (%esp) 

const_iterator bucle:

movl 60(%esp), %edx 
    movl $10, %ecx 
    movl 56(%esp), %esi 
    .p2align 4,,7 
    .p2align 3 
.L38: 
    cmpl %esi, %edx 
    je .L36 
    movl %esi, %eax 
    .p2align 4,,7 
    .p2align 3 
.L37: 
    addl (%eax), %ebx 
    addl $4, %eax 
    cmpl %eax, %edx 
    jne .L37 
.L36: 
    subl $1, %ecx 
    jne .L38 
    leal 68(%esp), %edx 
    movl %edx, 4(%esp) 
    leal 56(%esp), %esi 
    movl $1, (%esp)