paso eficiente de std :: vector

Question

Cuando una función C++ acepta un argumento std::vector, el patrón habitual es pasar por const de referencia, tales como:

int sum2(const std::vector<int> &v) 
{ 
    int s = 0; 
    for(size_t i = 0; i < v.size(); i++) s += fn(v[i]); 
    return s; 
} 

Creo que los resultados de este código en doble desreferencia cuando se accede a los elementos del vector, ya que la CPU debe primero desreferenciar v para leer el puntero al primer elemento, cuyo puntero necesita desreferenciarse nuevamente para leer el primer elemento. Esperaría que sería más eficiente pasar una copia superficial del objeto vector en la pila. Dicha copia superficial encapsularía un puntero al primer elemento y el tamaño, con el puntero haciendo referencia a la misma área de memoria que el vector original.

int sum2(vector_ref<int> v) 
{ 
    int s = 0; 
    for(size_t i = 0; i < v.size(); i++) s += fn(v[i]); 
    return s; 
} 

rendimiento similar, pero mucho menos de conveniencia podrían lograrse haciendo pasar un par iterador de acceso aleatorio. Mi pregunta es: ¿qué tiene defectos con esta idea? Espero que haya alguna buena razón para que las personas inteligentes acepten pagar el costo de rendimiento de la referencia de vector, o que hagan frente a la inconveniencia de los iteradores.

Editar: Con base en los comentarios a continuación, ten en cuenta la situación si simplemente cambiar el nombre de la clase sugerido vector_ref a rebanada o gama. La intención es usar pares de iteradores de acceso aleatorio con una sintaxis más natural.

Answer 1

Creo que este código da como resultado el doble desreferenciar cuando se accede a los elementos del vector

No necesariamente. Los compiladores son bastante inteligentes y deberían ser capaces de eliminate common subexpressions.. Pueden ver que el operador [] no cambia el 'puntero al primer elemento', por lo que no es necesario que la CPU lo recargue de la memoria para cada ciclo de iteración.

Answer 2

Pase por valor a menos que esté seguro de que pasar por referencia mejora el rendimiento.

Cuando pasa por valor, puede producirse una elisión de copia que dará como resultado un rendimiento similar, si no mejor.

de Dave escribió sobre él aquí:

http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

Answer 3

¿Qué tiene defecto con esta idea?

Simple: Optimización prematura. Alternativas: acepte un vector<int> const& y use iteradores o pase iteradores directamente a la función.

Answer 4

No hay doble desreferenciación porque el compilador probablemente pasará el puntero real al vector como argumento y no a un puntero a un puntero. Simplemente puede probar esto y consultar la vista en el desmontaje de su IDE de lo que realmente está pasando detrás de las escenas:

void Method(std::vector<int> const& vec) { 
int i = vec.back(); 
} 


void SomeOtherMethod() { 
    std::vector<int> vec; 
    vec.push_back(1); 
    Method(vec); 
} 

¿Qué pasa aquí? El vector está asignado en la pila.La primera vuelta de empuje se traduce a:

push  eax // this is the constant one that has been stored in eax 
lea   ecx,[ebp-24h] // ecx is the pointer to vec on the stack 
call  std::vector<int,std::allocator<int> >::push_back 

Ahora que llamamos Método(), pasando el vector const &:

lea   ecx,[ebp-24h] 
push  ecx 
call  Method (8274DC0h) 

Como era de esperar, el puntero al vector se pasa como referencias no son más que de forma permanente punteros desreferenciados Ahora dentro Método(), el vector se accede de nuevo:

mov   ecx,dword ptr [ebp+8] 
call  std::vector<int,std::allocator<int> >::back (8276100h) 

El puntero vector se toma directamente de la pila y se escribe en ecx.

Answer 5

Tiene razón en que hay una indirecta adicional aquí. Es concebible (aunque sería sorprendente) si el compilador (con la ayuda de la generación de código de tiempo de enlace) lo optimizara.

Lo que ha propuesto se denomina a veces slicing, y se usa extensamente en algunas situaciones. Aunque, en general, no estoy seguro de que valga la pena los peligros. Debes tener mucho cuidado al invalidar tu porción (o la de otra persona).

Tenga en cuenta que si se ha utilizado iteradores para el bucle en lugar de indexación, entonces lo que DEREF la referencia solamente un par de veces (para llamar begin() y end()) en lugar de n veces (para indexar en el vector).

int sum(const vector<int> &v) 
{ 
    int s = 0; 
    for (auto it = v.begin(); it != v.end(); ++it) { 
     s += fn(*it); 
    } 
    return s; 
} 

(estoy suponiendo que el optimizador izar las end() llamadas fuera del circuito. Usted puede hacerlo de forma explícita para estar seguro.)

Pasar un par de iteradores en lugar del propio recipiente parece como el lenguaje STL. Eso le daría más generalidad, ya que el tipo de contenedor puede variar, pero también lo puede hacer la cantidad de referencias necesarias.

Answer 6

¿Qué pasa con su idea es que ya tiene dos perfectamente buenas soluciones:

• pase el vector como es, ya sea por el valor (en la que el compilador menudo eliminará la copia), o por (const) referencia, y confíe en el compilador para eliminar el doble direccionamiento indirecto, o
• Pase un par de iteradores.

Por supuesto, puede argumentar que el par de iteradores es "sintaxis menos natural", pero no estoy de acuerdo. Es perfectamente natural para cualquiera que esté acostumbrado a STL. Es eficiente y le proporciona exactamente lo que necesita para trabajar con el rango, utilizando algoritmos std o sus propias funciones.

Los pares de iteradores son una expresión común de C++, y un programador de C++ que lea su código los comprenderá sin problemas, mientras que se sorprenderán con sus envoltorios de vectores elaborados en casa.

Si eres realmente paranoico sobre el rendimiento, pasa el par de iteradores. Si la sintaxis realmente te molesta, pasa el vector y confía en el compilador.