c++ - clase - ¿Son const_iterators más rápidos?

list iterator c++

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 ?.

EDITAR: Escribí una pequeña prueba para verificar const_iterator vs const_iterator y encontré resultados variables:

Para iterar 10.000 objetos, const_terator unos pocos milisegundos (alrededor de 16 ms) menos. Pero no siempre Hubo iteraciones en las que ambos fueron iguales.

Answer 1

Nuestras pautas de codificación dicen que prefieren const_iterator

Echa un vistazo a este artículo de Scott Meyers aquí . Él explica por qué uno debería preferir iterador sobre const_iterator.

Answer 2

"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 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:

Answer 3

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 peculiaridades, 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, subiendo y bajando un 20% (no hay cajas inactivas disponibles), pero los tiempos mínimos para iterator y const_iterator fueron prácticamente idénticos .

Luego obtuve mi compilador (GCC 4.5.2-O3) para generar salida de ensamblaje y comparé visualmente los dos bucles: idéntico (excepto que el orden de un par de cargas de registro se invirtió)

bucle iterator

 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 loop:

 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)

Answer 4

Depende del contenedor y la implementación que utilice.

Sí, const_iterator puede funcionar mejor.

Para algunos contenedores, la implementación de const iterators e iteradores mutables puede diferir . Un primer ejemplo que puedo pensar es el contenedor de cuerda STL de la SGI . 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 las notas de implementación aquí .

Sin embargo, como otros dijeron, el compilador no puede usar const por sí mismo para hacer 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 5

En mi experiencia, el compilador no realiza ninguna optimización mensurable cuando usa 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 las respuestas en este hilo en restringir punteros se aplican: el compilador no puede saber si el objeto es cambiado por otro hilo, por ejemplo, o por algún código de manejo de interrupciones.

Answer 6

La pauta que usamos es:

Siempre prefiero const sobre non-const

Si tiende a usar objetos const, se acostumbra a usar solo operaciones constantes en los objetos que obtiene y eso es tanto como usar const_iterator tanto como sea posible.

Constness tiene una propiedad viral . 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 utilizar iteradores constantes sobre iteradores no constantes (si es que los hay) 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

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í está mi prueba: 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 8

Si nada más, un const_iterator lee mejor, ya que le dice a cualquiera que lea el código "Solo estoy iterando sobre este contenedor, sin meterme con los objetos que contiene".

Esa es una gran gran victoria, sin importar las diferencias de rendimiento.

Answer 9

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

Además, hay varias razones para preferir const_iterator, sin importar qué:

1. El uso de const expresa la intención del código (es decir, solo lectura, no mutación de estos objetos).
2. El uso de const (_iterator) evita la modificación accidental de datos. (véase más arriba)
3. Algunas bibliotecas utilizan la función de falta de consistencia begin() para marcar los datos como sucios (es decir, OpenSG) y lo enviarán a otros hilos / sobre la red en sincronización, por lo que tiene implicaciones de rendimiento reales.
4. Además, permitirle acceder a las funciones de miembros no const puede tener efectos colaterales que no tiene la intención (de la misma manera que en el caso anterior), por ejemplo, separar los contenedores de copia de escritura de los datos compartidos. Qt por uno, hace exactamente eso.

Como ejemplo del último punto anterior, aquí hay 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 iterator y const_iterator son prácticamente equivalentes (excepto para 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 vas a leer los datos, que const_iterator usar const_iterator .

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

1. Para contenedores STL y muchos contenedores semánticos de copia simple, no tendrá importancia 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 ++ previos 0x STL tienen un error donde los const_iterators no pueden usarse para borrar () elementos de los contenedores.

Answer 10

cuando evalúes algo de esto, asegúrate de usar un nivel de optimización apropiado: obtendrás sincronizaciones tremendamente diferentes usando "-O0" contra "-O" y tal.

Answer 11

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