performance - una - paso por referencia en c++

¿Por qué no se pasa struct por referencia una optimización común? (12)

Hasta el día de hoy, siempre he pensado que los compiladores decentes convierten automáticamente struct pass-by-value en pass-by-reference si la estructura es lo suficientemente grande como para que la última sea más rápida. Según mi leal saber y entender, esto parece una optimización sin complicaciones. Sin embargo, para satisfacer mi curiosidad sobre si esto realmente sucede, creé un caso de prueba simple tanto en C ++ como en D y miré la salida tanto de GCC como de Digital Mars D. Ambos insistieron en pasar las estructuras de 32 bytes por valor cuando todo el La función en cuestión hizo fue sumar los miembros y devolver los valores, sin modificación de la estructura pasada. La versión de C ++ está debajo.

#include "iostream.h" struct S { int i, j, k, l, m, n, o, p; }; int foo(S s) { return s.i + s.j + s.k + s.l + s.m + s.n + s.o + s.p; } int main() { S s; int bar = foo(s); cout << bar; }

Mi pregunta es, ¿por qué diablos no sería optimizado por el compilador para pasar por referencia en lugar de empujar todos los int s en la pila?

Nota: Compiladores utilizados: GCC -O2 (-O3 inline foo ().), DMD -O -inline-release.

Editar: Obviamente, en el caso general, la semántica de pass-by-value vs. pass-by-reference no será la misma, como si los constructores de copia están involucrados o la estructura original se modifica en el destinatario. Sin embargo, en muchos escenarios del mundo real, la semántica será idéntica en términos de comportamiento observable. Estos son los casos sobre los que estoy preguntando.

Bueno, la respuesta trivial es que la ubicación de la estructura en la memoria es diferente, y por lo tanto, los datos que está pasando son diferentes. La respuesta más compleja, creo, está enhebrando.

Su compilador necesitaría detectar a) que foo no modifica la estructura; b) que foo no hace ningún cálculo en la ubicación física de los elementos de la estructura; Y c) que la persona que llama, u otro hilo generado por la persona que llama, no modifica la estructura antes de que foo termine de ejecutarse.

En su ejemplo, es concebible que el compilador pueda hacer estas cosas, pero la memoria guardada es intrascendente y probablemente no valga la pena suponerlo. ¿Qué sucede si ejecuta el mismo programa con una estructura que tiene dos millones de elementos?

Cambiar de por valor a por referencia cambiará la firma de la función. Si la función no es estática, esto causaría errores de enlace para otras unidades de compilación que no conocen la optimización que usted hizo.
De hecho, la única forma de hacer tal optimización es mediante algún tipo de fase de optimización global posterior al enlace. Estos son notoriamente difíciles de hacer, sin embargo, algunos compiladores los hacen en cierta medida.

Creo que definitivamente se trata de una optimización que podría implementar (según algunas suposiciones, consulte el último párrafo), pero no tengo claro si sería rentable. En lugar de insertar argumentos en la pila (o pasarlos a través de registros, dependiendo de la convención de llamadas), presionaría un puntero a través del cual leería los valores. Esta indirección adicional costaría ciclos. También requeriría que el argumento pasado esté en la memoria (para que pueda señalarlo) en lugar de en los registros. Solo sería beneficioso si los registros que se pasan tienen muchos campos y la función que recibe el registro solo lee algunos de ellos. Los ciclos adicionales desperdiciados por la indirección tendrían que compensar los ciclos no desperdiciados empujando los campos innecesarios.

Puede sorprenderse que la optimización inversa, la promoción de argumentos , en realidad se implemente en LLVM. Esto convierte un argumento de referencia en un argumento de valor (o un agregado en escalares) para funciones internas con un pequeño número de campos que solo se leen. Esto es particularmente útil para los idiomas que pasan casi todo por referencia. Si sigues esto con eliminación de argumento muerto , tampoco tienes que pasar campos que no se tocan.

Cabe mencionar que las optimizaciones que cambian la forma en que se llama a una función solo pueden funcionar cuando la función que se está optimizando es interna al módulo que se está compilando (se obtiene declarando una función static en C y con plantillas en C ++). El optimizador debe reparar no solo la función sino también todos los puntos de llamada. Esto hace que dichas optimizaciones sean bastante limitadas en su alcance a menos que las haga en tiempo de enlace. Además, nunca se llamaría a la optimización cuando se trata de un constructor de copias (como han mencionado otros carteles) porque podría cambiar la semántica del programa, algo que un buen optimizador nunca debería hacer.

El problema es que le está pidiendo al compilador que tome una decisión sobre la intención del código de usuario. Tal vez quiero que mi estructura súper grande pase por valor para que pueda hacer algo en el constructor de copias. Créanme, alguien por ahí tiene algo que necesitan ser llamados válidamente en un constructor de copia para ese escenario. Cambiar a a por ref omitirá el constructor de copia.

Tener esto como una decisión generada por el compilador sería una mala idea. La razón es que hace que sea imposible razonar sobre el flujo de su código. No puede mirar una llamada y saber exactamente qué hará. Tienes que a) conocer el código yb) adivinar la optimización del compilador.

En muchas plataformas, las estructuras grandes se pasan de hecho por referencia, pero se espera que el que llama pase una referencia a una copia que la función puede manipular a su gusto ¹ , o se espera que la función llamada haga una copia del estructura a la que recibe una referencia y luego realizar cualquier manipulación en la copia.

Si bien hay muchas circunstancias en las que las operaciones de copia podrían de hecho omitirse, a menudo será difícil para un compilador probar que tales operaciones pueden ser eliminadas. Por ejemplo, dado:

struct FOO { ... }; void func1(struct FOO *foo1); void func2(struct FOO foo2); void test(void) { struct FOO foo; func1(&foo); func2(foo); }

no hay forma de que un compilador pueda saber si foo podría modificarse durante la ejecución de func2 ( func1 podría haber almacenado una copia de foo1 o un puntero derivado de ella en un objeto de alcance de archivo que luego es utilizado por func2 ). Tales modificaciones, sin embargo, no deberían afectar la copia de foo (es decir, foo2 ) recibida por func2 . Si foo se pasó por referencia y func2 no hizo una copia, las acciones que afectan a foo afectarían indebidamente a foo2 .

Tenga en cuenta que incluso void func3(const struct FOO); no es significativo: el destinatario puede deshacerse de const , y la convención de invocación de asm normal aún permite que el destinatario modifique la memoria que contiene la copia con valores por debajo.

Desafortunadamente, hay relativamente pocos casos en que el examen de la llamada o la función llamada de forma aislada sería suficiente para demostrar que una operación de copia puede omitirse con seguridad, y hay muchos casos en que incluso el examen de ambos sería insuficiente. Por lo tanto, reemplazar el pase por valor con pass-by-reference es una optimización difícil cuyo pago a menudo es insuficiente para justificar la dificultad.

Nota al pie 1: por ejemplo, Windows x64 pasa objetos de más de 8 bytes por referencia no const (callee "posee" la memoria apuntada). Esto no ayuda a evitar la copia en absoluto; la motivación es hacer que todos los argumentos de funciones se ajusten en 8 bytes cada uno, de forma que formen una matriz en la pila (después de derramar registros args en el espacio sombreado), haciendo que las funciones variadas sean fáciles de implementar.

Por el contrario, x86-64 System V hace lo que la pregunta describe para objetos de más de 16 bytes: copiándolos a la pila. (Los objetos más pequeños se empaquetan en hasta dos registros).

Es cierto que los compiladores en algunos idiomas pueden hacer esto si tienen acceso a la función que se llama y si pueden suponer que la función llamada no cambiará. Esto a veces se denomina optimización global y parece probable que algunos compiladores C o C ++ de hecho optimicen casos como este, más probablemente al insertar el código para una función tan trivial.

Hay muchas razones para pasar de valor, y hacer que el compilador optimice su intención puede romper su código.

Ejemplo, si la función llamada modifica la estructura de cualquier manera. Si pretendía que los resultados se transmitieran a la persona que llama, entonces podría pasar un puntero / referencia o devolverlo usted mismo.

Lo que le pides al compilador que haga es cambiar el comportamiento de tu código, que se consideraría un error del compilador.

Si desea realizar la optimización y pasar por referencia, modifique las definiciones de función / método existentes de alguien para aceptar referencias; no es tan difícil de hacer. Puede que se sorprenda de la rotura que causa sin darse cuenta.

No olvide que en C / C ++ el compilador necesita poder compilar una llamada a una función basada solo en la declaración de la función.

Dado que las personas que llaman pueden estar usando solo esa información, no hay forma de que un compilador compile la función para aprovechar la optimización de la que está hablando. La persona que llama no puede saber que la función no modificará nada y por lo tanto no puede pasar por ref. Como algunas personas que llaman pueden pasar por alto debido a la falta de información detallada, la función debe compilarse asumiendo el valor de paso por paso y todos deben pasar por el valor.

Tenga en cuenta que incluso si marcó el parámetro como '' const '', el compilador aún no puede realizar la optimización, porque la función podría estar mintiendo y descartando la constness (esto está permitido y bien definido siempre que el objeto se pase en en realidad no es const).

Creo que para las funciones estáticas (o aquellas en un espacio de nombres anónimo), el compilador posiblemente podría hacer la optimización de la que está hablando, ya que la función no tiene enlaces externos. Siempre que la dirección de la función no se pase a alguna otra rutina o se almacene en un puntero, no se podrá llamar desde otro código. En este caso, el compilador podría tener un conocimiento completo de todas las personas que llaman, por lo que supongo que podría hacer la optimización.

No estoy seguro si alguno lo hace (en realidad, me sorprendería si lo hiciera, ya que probablemente no podría aplicarse con mucha frecuencia).

Por supuesto, como programador (cuando usa C ++) puede obligar al compilador a realizar esta optimización usando const& parámetros siempre que sea posible. Sé que estás preguntando por qué el compilador no puede hacerlo automáticamente, pero supongo que es la mejor opción.

Pasar efectivamente una struct por referencia, incluso cuando la declaración de la función indica el valor por pase, es una optimización común: simplemente sucede que normalmente ocurre indirectamente a través de la alineación, por lo que no es obvio desde el código generado.

Sin embargo, para que esto suceda, el compilador necesita saber que el destinatario no modifica el objeto pasado mientras está compilando a la persona que llama . De lo contrario, estará restringido por la plataforma / lenguaje ABI que dicta exactamente cómo se pasan los valores a las funciones.

¡ Puede suceder incluso sin forzar!

Aún así, algunos compiladores implementan esta optimización incluso en ausencia de creación de líneas, aunque las circunstancias son relativamente limitadas, al menos en plataformas que usan SysV ABI (Linux, OSX, etc.) debido a las restricciones del diseño de la pila. Considere el siguiente ejemplo simple, basado directamente en su código:

__attribute__((noinline)) int foo(S s) { return s.i + s.j + s.k + s.l + s.m + s.n + s.o + s.p; } int bar(S s) { return foo(s); }

Aquí, en el nivel de idioma, la bar llama a foo con semántica de valor de paso según lo requiera C ++. Si examinamos el conjunto generado por gcc , sin embargo, se ve así:

foo(S): mov eax, DWORD PTR [rsp+12] add eax, DWORD PTR [rsp+8] add eax, DWORD PTR [rsp+16] add eax, DWORD PTR [rsp+20] add eax, DWORD PTR [rsp+24] add eax, DWORD PTR [rsp+28] add eax, DWORD PTR [rsp+32] add eax, DWORD PTR [rsp+36] ret bar(S): jmp foo(S)

Tenga en cuenta que la bar simplemente llama directamente a foo , sin hacer una copia: bar usará la misma copia de s que se pasó a la bar (en la pila). En particular , no hace ninguna copia, como lo implica la semántica del lenguaje (ignorando como si fuera ). Entonces, gcc ha realizado exactamente la optimización que solicitó. Clang no lo hace: hace una copia en la pila que pasa a foo() .

Desafortunadamente, los casos donde esto puede funcionar son bastante limitados: SysV requiere que estas estructuras grandes se pasen en la pila en una posición específica, por lo que dicha reutilización solo es posible si el destinatario espera el objeto exactamente en el mismo lugar.

Eso es posible en el ejemplo de foo/bar ya que bar toma su S como el primer parámetro de la misma manera que foo , y bar realiza una llamada de cola a foo que evita la necesidad del impulso implícito de dirección de retorno que de otro modo arruinaría la capacidad de reutiliza el argumento de la pila.

Por ejemplo, si simplemente agregamos un + 1 a la llamada a foo :

int bar(S s) { return foo(s) + 1; }

El truco está arruinado, ya que ahora la posición de bar::s es diferente de la ubicación donde foo esperará su argumento, y necesitamos una copia:

bar(S): push QWORD PTR [rsp+32] push QWORD PTR [rsp+32] push QWORD PTR [rsp+32] push QWORD PTR [rsp+32] call foo(S) add rsp, 32 add eax, 1 ret

Esto no significa que la bar() llamadas bar() tiene que ser totalmente trivial. Por ejemplo, podría modificar su copia de s, antes de pasarlo:

int bar(S s) { s.i += 1; return foo(s); }

... y la optimización se preservaría:

bar(S): add DWORD PTR [rsp+8], 1 jmp foo(S)

En principio, esta posibilidad para este tipo de optimización es bienvenida en la convención de llamadas Win64 que usa un puntero oculto para pasar estructuras grandes. Esto le da mucha más flexibilidad al reutilizar las estructuras existentes en la pila o en otro lugar para implementar la referencia de paso bajo las cubiertas.

En línea

Sin embargo, aparte de eso, la principal forma en que ocurre esta optimización es a través de la línea.

Por ejemplo, en la compilación de -O2 , todos los clang, gcc y MSVC no hacen ninguna copia del objeto S ¹ . Tanto clang como gcc realmente no crean el objeto en absoluto, sino que simplemente calculan el resultado más o menos directamente sin siquiera referir campos no utilizados. MSVC sí asigna espacio de pila para una copia, pero nunca la usa: llena solo una copia de S y lee de ella, al igual que pass-by-reference (MSVC genera un código mucho peor que los otros dos compiladores para este caso) .

Tenga en cuenta que, aunque foo está incluido en main los compiladores también generan una copia separada e independiente de la función foo() , ya que tiene un enlace externo y, por lo tanto, podría ser utilizado por este archivo objeto. En esto, el compilador está restringido por la interfaz binaria de la aplicación : SysV ABI (para Linux) o Win64 ABI (para Windows) define exactamente cómo se deben pasar los valores, según el tipo y el tamaño del valor. Las estructuras grandes pasan por un puntero oculto, y el compilador debe respetar eso al compilar foo . También debe respetar la compilación de algunos usuarios de foo cuando foo no se puede ver: ya que no tiene idea de qué foo hará.

Por lo tanto, hay muy poca ventana para que el compilador realice una optimización efectiva que transforme el valor de paso por paso debido a que:

1) Si puede ver tanto a la persona que llama como a la persona que llama ( main y foo en su ejemplo), es probable que la llamada entre en la persona que llama si es lo suficientemente pequeña, y como la función se vuelve grande e ininteligible, la El efecto de costos fijos como la sobrecarga de convenciones de llamadas se vuelve relativamente más pequeño.

2) Si el compilador no puede ver tanto al llamador como al destinatario al mismo tiempo ² , generalmente tiene que compilar cada uno de acuerdo con la plataforma ABI. No hay margen para la optimización de la llamada en el sitio de llamada ya que el compilador no sabe lo que hará el destinatario, y no hay margen para la optimización dentro del destinatario porque el compilador tiene que hacer suposiciones conservadoras sobre lo que hizo el llamador.

¹ Mi ejemplo es un poco más complicado que el original para evitar que el compilador simplemente optimice todo por completo (en particular, acceda a la memoria no inicializada, para que su programa ni siquiera tenga un comportamiento definido): llene algunos de los campos de s con argc que es un valor que el compilador no puede predecir.

² Un compilador puede ver ambos "al mismo tiempo" generalmente significa que están en la misma unidad de traducción o que se está utilizando la optimización del tiempo de enlace.

Pass-by-reference es solo azúcar sintáctico para pass-by-address / puntero. Por lo tanto, la función debe desreferencia implícitamente un puntero para leer el valor del parámetro. La desreferenciación del puntero puede ser más costosa (si está en un bucle) que la copia de estructura para copia por valor.

Más importante aún, como han mencionado otros, pass-by-reference tiene una semántica diferente a pass-by-value. const referencias const no significan que el valor referenciado no cambie. otras llamadas a funciones pueden cambiar el valor al que se hace referencia.

Una respuesta es que el compilador debería detectar que el método llamado no modifica los contenidos de la estructura de ninguna manera. Si lo hiciera, entonces el efecto de pasar por referencia diferiría del de pasar por el valor.

el compilador debería asegurarse de que la estructura que se pasa (como se menciona en el código de llamada) no se modifique

double x; // using non structs, oh-well void Foo(double d) { x += d; // ok x += d; // Oops } void main() { x = 1; Foo(x); }