c++ - Rendimiento de pIter!=Cont.end() en for loop
performance stl (7)
Herb Sutter estaba recibiendo el "Excepcional C ++" últimamente, y tengo serias dudas sobre una recomendación en particular que él da en el Ítem 6 - Objetos temporales.
Se ofrece a encontrar objetos temporales innecesarios en el siguiente código:
string FindAddr(list<Employee> emps, string name)
{
for (list<Employee>::iterator i = emps.begin(); i != emps.end(); i++)
{
if( *i == name )
{
return i->addr;
}
}
return "";
}
Como uno de los ejemplos, recomienda emps.end() el valor de emps.end() antes del bucle, ya que hay un objeto temporal creado en cada iteración:
Para la mayoría de los contenedores (incluida la lista), llamar a end () devuelve un objeto temporal que se debe construir y destruir. Debido a que el valor no cambiará, volver a calcularlo (y reconstruirlo y volverlo a diseñar) en cada iteración de bucle es innecesariamente ineficiente e inestable. El valor debe calcularse solo una vez, almacenarse en un objeto local y reutilizarse.
Y sugiere sustituir por lo siguiente:
list<Employee>::const_iterator end(emps.end());
for (list<Employee>::const_iterator i = emps.begin(); i != end; ++i)
Para mí, esta es una complicación innecesaria. Incluso si uno reemplaza las declaraciones de tipo feo por un auto compacto, todavía obtiene dos líneas de código en lugar de una. Aún más, tiene esta variable end en el ámbito externo.
Estaba seguro de que los compiladores modernos optimizarán este fragmento de código de todos modos, porque en realidad estoy usando const_iterator aquí y es fácil verificar si el contenido del bucle está accediendo al contenedor de alguna manera. Los compiladores se hicieron más inteligentes en los últimos 13 años, ¿verdad?
De todos modos, preferiré la primera versión con i != emps.end() en la mayoría de los casos, donde no estoy tan preocupado por el rendimiento. ¿Pero quiero saber con certeza si este es un tipo de construcción en la que podría confiar en un compilador para optimizar?
Actualizar
Gracias por sus sugerencias sobre cómo mejorar este código inútil. Tenga en cuenta que mi pregunta es sobre el compilador, no sobre técnicas de programación. Las únicas respuestas relevantes por ahora son de NPE y Ellioh .
Utilizar algoritmos std
Tiene razón, por supuesto; El end llamada puede instanciar y destruir un objeto temporal, que generalmente es malo.
Por supuesto, el compilador puede optimizar esto en muchos casos.
Hay una solución mejor y más robusta: encapsule sus bucles .
El ejemplo que dio es de hecho std::find , give or take the value devuelto. Muchos otros bucles también tienen algoritmos std , o al menos algo lo suficientemente similar como para que puedas adaptarlo: mi biblioteca de utilidades tiene una implementación transform_if , por ejemplo.
Por lo tanto, oculte los bucles en una función y tome una const& para end . La misma solución que tu ejemplo, pero mucho más limpia.
Contrariamente a la creencia popular, no veo ninguna diferencia entre VC ++ y gcc a este respecto. Hice una comprobación rápida con g ++ 4.7.2 y MS C ++ 17 (también conocido como VC ++ 2012).
En ambos casos, comparé el código generado con el código como en la pregunta (con encabezados y demás agregados para permitir que se compile), con el siguiente código:
string FindAddr(list<Employee> emps, string name)
{
auto end = emps.end();
for (list<Employee>::iterator i = emps.begin(); i != end; i++)
{
if( *i == name )
{
return i->addr;
}
}
return "";
}
En ambos casos, el resultado fue esencialmente idéntico para las dos piezas de código. VC ++ incluye comentarios de número de línea en el código, que cambiaron debido a la línea adicional, pero esa fue la única diferencia. Con g ++ los archivos de salida eran idénticos.
Al hacer lo mismo con std::vector lugar de std::list , obtuvimos prácticamente el mismo resultado, sin diferencias significativas. Por alguna razón, g ++ cambió el orden de los operandos para una instrucción, de cmp esi, DWORD PTR [eax+4] a cmp DWORD PTR [eax+4], esi , pero (de nuevo) esto es absolutamente irrelevante.
En /O2b2 : no, no es probable que obtenga algo al levantar manualmente el código fuera del ciclo con un compilador moderno (al menos con la optimización habilitada; estaba usando /O2b2 con VC ++ y /O3 con g ++; comparando la optimización con la optimización apagada me parece bastante inútil).
He compilado el siguiente código ligeramente pirateado utilizando g++ 4.7.2 con -O3 -std=c++11 , y obtuve un ensamblaje idéntico para ambas funciones:
#include <list>
#include <string>
using namespace std;
struct Employee: public string { string addr; };
string FindAddr1(list<Employee> emps, string name)
{
for (list<Employee>::const_iterator i = emps.begin(); i != emps.end(); i++)
{
if( *i == name )
{
return i->addr;
}
}
return "";
}
string FindAddr2(list<Employee> emps, string name)
{
list<Employee>::const_iterator end(emps.end());
for (list<Employee>::const_iterator i = emps.begin(); i != end; i++)
{
if( *i == name )
{
return i->addr;
}
}
return "";
}
En cualquier caso, creo que la elección entre las dos versiones debería basarse principalmente en motivos de legibilidad. Sin datos de perfil, las microoptimizaciones como ésta me parecen prematuras.
Los contenedores como vector devuelven la variable, que almacena el puntero al final, en la llamada end() , que optimiza. Si ha escrito un contenedor que hace algunas búsquedas, etc. en la llamada end() considere considerar escribir
for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i)
{
...
}
por velocidad
Si realmente necesita el rendimiento, deje que su nuevo compilador C ++ 11 lo escriba por usted:
for (const auto &i : emps) {
/* ... */
}
Sí, esto es irónico (más o menos). El ejemplo de Herb aquí está ahora fuera de fecha. Pero como su compilador todavía no lo admite, vamos a la pregunta real:
¿Es este un tipo de construcción en la que podría confiar en un compilador para optimizar?
Mi regla de oro es que los escritores de compiladores son mucho más inteligentes que yo. No puedo confiar en un compilador para optimizar cualquier pieza de código, ya que podría elegir optimizar otra cosa que tenga un impacto mayor. La única manera de saberlo con certeza es probar ambos enfoques en su compilador en su sistema y ver qué sucede. Compruebe los resultados de su perfilador. Si la llamada a .end() sobresale, .end() en una variable separada. De lo contrario, no te preocupes por eso.
Un par de cosas ... la primera es que, en general, el costo de construir un iterador (en el modo de versión, asignadores sin marcar) es mínimo. Por lo general, son envoltorios alrededor de un puntero. Con los asignadores marcados (por defecto en VS) puede tener algún costo, pero si realmente necesita el rendimiento, después de probar la reconstrucción con asignadores no verificados.
El código no tiene por qué ser tan feo como lo que publicaste:
for (list<Employee>::const_iterator it=emps.begin(), end=emps.end();
it != end; ++it )
La decisión principal sobre si desea utilizar uno u otro enfoque debe ser en términos de qué operaciones se aplican al contenedor. Si el contenedor puede cambiar su tamaño, es posible que desee volver a calcular el iterador end en cada iteración. Si no es así, solo puede calcular una vez y reutilizar como en el código anterior.
UPD: El libro del que estás hablando se publicó en 1999, a menos que me equivoque. Eso es hace 14 años, y en la programación moderna, 14 años es mucho tiempo. Muchas recomendaciones que fueron buenas y confiables en 1999, pueden estar completamente obsoletas a estas alturas. Aunque mi respuesta es sobre un solo compilador y una sola plataforma, también hay una idea más general.
Preocuparse por las variables adicionales, reutilizar un valor de retorno de métodos triviales y trucos similares de los antiguos C ++ es un paso atrás hacia el C ++ de los 90. Los métodos triviales, como end() deben estar en línea bastante bien, y el resultado de la línea debe optimizarse como parte del código desde el que se llama. Las situaciones del 99% no requieren acciones manuales, como la creación de una variable end . Tales cosas deben hacerse solo si:
- SABES que en algunos de los compiladores / plataformas que debes ejecutar en el código no está bien optimizado.
- Se ha convertido en un cuello de botella en su programa ("evitar la optimización prematura").
He visto lo que genera g ++ de 64 bits:
gcc version 4.6.3 20120918 (prerelease) (Ubuntu/Linaro 4.6.3-10ubuntu1)
Inicialmente, pensé que con optimizaciones debería estar bien y que no debería haber diferencia entre dos versiones. Pero parece que las cosas son extrañas: la versión que consideraste no óptima en realidad es mejor . Creo que la moraleja es que no hay razón para intentar ser más inteligente que un compilador . Veamos ambas versiones.
#include <list>
using namespace std;
int main() {
list<char> l;
l.push_back(''a'');
for(list<char>::iterator i=l.begin(); i != l.end(); i++)
;
return 0;
}
int main1() {
list<char> l;
l.push_back(''a'');
list<char>::iterator e=l.end();
for(list<char>::iterator i=l.begin(); i != e; i++)
;
return 0;
}
Entonces deberíamos compilar esto con optimizaciones en (uso g++ 64 bits, puedes probar tu compilador) y desarmar main y main1 :
Por main :
(gdb) disas main
Dump of assembler code for function main():
0x0000000000400650 <+0>: push %rbx
0x0000000000400651 <+1>: mov $0x18,%edi
0x0000000000400656 <+6>: sub $0x20,%rsp
0x000000000040065a <+10>: lea 0x10(%rsp),%rbx
0x000000000040065f <+15>: mov %rbx,0x10(%rsp)
0x0000000000400664 <+20>: mov %rbx,0x18(%rsp)
0x0000000000400669 <+25>: callq 0x400630 <_Znwm@plt>
0x000000000040066e <+30>: cmp $0xfffffffffffffff0,%rax
0x0000000000400672 <+34>: je 0x400678 <main()+40>
0x0000000000400674 <+36>: movb $0x61,0x10(%rax)
0x0000000000400678 <+40>: mov %rax,%rdi
0x000000000040067b <+43>: mov %rbx,%rsi
0x000000000040067e <+46>: callq 0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
0x0000000000400683 <+51>: mov 0x10(%rsp),%rax
0x0000000000400688 <+56>: cmp %rbx,%rax
0x000000000040068b <+59>: je 0x400698 <main()+72>
0x000000000040068d <+61>: nopl (%rax)
0x0000000000400690 <+64>: mov (%rax),%rax
0x0000000000400693 <+67>: cmp %rbx,%rax
0x0000000000400696 <+70>: jne 0x400690 <main()+64>
0x0000000000400698 <+72>: mov %rbx,%rdi
0x000000000040069b <+75>: callq 0x400840 <std::list<char, std::allocator<char> >::~list()>
0x00000000004006a0 <+80>: add $0x20,%rsp
0x00000000004006a4 <+84>: xor %eax,%eax
0x00000000004006a6 <+86>: pop %rbx
0x00000000004006a7 <+87>: retq
Mire los comandos ubicados en 0x0000000000400683-0x000000000040068b. Ese es el cuerpo del bucle y parece estar perfectamente optimizado:
0x0000000000400690 <+64>: mov (%rax),%rax
0x0000000000400693 <+67>: cmp %rbx,%rax
0x0000000000400696 <+70>: jne 0x400690 <main()+64>
Para main1 :
(gdb) disas main1
Dump of assembler code for function main1():
0x00000000004007b0 <+0>: push %rbp
0x00000000004007b1 <+1>: mov $0x18,%edi
0x00000000004007b6 <+6>: push %rbx
0x00000000004007b7 <+7>: sub $0x18,%rsp
0x00000000004007bb <+11>: mov %rsp,%rbx
0x00000000004007be <+14>: mov %rsp,(%rsp)
0x00000000004007c2 <+18>: mov %rsp,0x8(%rsp)
0x00000000004007c7 <+23>: callq 0x400630 <_Znwm@plt>
0x00000000004007cc <+28>: cmp $0xfffffffffffffff0,%rax
0x00000000004007d0 <+32>: je 0x4007d6 <main1()+38>
0x00000000004007d2 <+34>: movb $0x61,0x10(%rax)
0x00000000004007d6 <+38>: mov %rax,%rdi
0x00000000004007d9 <+41>: mov %rsp,%rsi
0x00000000004007dc <+44>: callq 0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
0x00000000004007e1 <+49>: mov (%rsp),%rdi
0x00000000004007e5 <+53>: cmp %rbx,%rdi
0x00000000004007e8 <+56>: je 0x400818 <main1()+104>
0x00000000004007ea <+58>: mov %rdi,%rax
0x00000000004007ed <+61>: nopl (%rax)
0x00000000004007f0 <+64>: mov (%rax),%rax
0x00000000004007f3 <+67>: cmp %rbx,%rax
0x00000000004007f6 <+70>: jne 0x4007f0 <main1()+64>
0x00000000004007f8 <+72>: mov (%rdi),%rbp
0x00000000004007fb <+75>: callq 0x4005f0 <_ZdlPv@plt>
0x0000000000400800 <+80>: cmp %rbx,%rbp
0x0000000000400803 <+83>: je 0x400818 <main1()+104>
0x0000000000400805 <+85>: nopl (%rax)
0x0000000000400808 <+88>: mov %rbp,%rdi
0x000000000040080b <+91>: mov (%rdi),%rbp
0x000000000040080e <+94>: callq 0x4005f0 <_ZdlPv@plt>
0x0000000000400813 <+99>: cmp %rbx,%rbp
0x0000000000400816 <+102>: jne 0x400808 <main1()+88>
0x0000000000400818 <+104>: add $0x18,%rsp
0x000000000040081c <+108>: xor %eax,%eax
0x000000000040081e <+110>: pop %rbx
0x000000000040081f <+111>: pop %rbp
0x0000000000400820 <+112>: retq
El código para el bucle es similar, es:
0x00000000004007f0 <+64>: mov (%rax),%rax
0x00000000004007f3 <+67>: cmp %rbx,%rax
0x00000000004007f6 <+70>: jne 0x4007f0 <main1()+64>
Pero hay un montón de cosas extra alrededor del bucle. Al parecer, el código extra ha hecho que las cosas se vean peores.