c++ c++11 vector compiler-optimization unique-ptr

c++ - Rendimiento de redimensionamiento std:: vector<std:: unique_ptr<T>>



c++11 compiler-optimization (2)

La idea general parece ser que std::unique_ptr no tiene una sobrecarga de tiempo en comparación con los punteros std::unique_ptr que se usan correctamente, dada una optimización suficiente .

Pero ¿qué pasa con el uso de std::unique_ptr en estructuras de datos compuestos, en particular std::vector<std::unique_ptr<T>> ? Por ejemplo, cambiar el tamaño de los datos subyacentes de un vector, lo que puede ocurrir durante push_back . Para aislar el rendimiento, pop_back , shrink_to_fit , emplace_back :

#include <chrono> #include <vector> #include <memory> #include <iostream> constexpr size_t size = 1000000; constexpr size_t repeat = 1000; using my_clock = std::chrono::high_resolution_clock; template<class T> auto test(std::vector<T>& v) { v.reserve(size); for (size_t i = 0; i < size; i++) { v.emplace_back(new int()); } auto t0 = my_clock::now(); for (int i = 0; i < repeat; i++) { auto back = std::move(v.back()); v.pop_back(); v.shrink_to_fit(); if (back == nullptr) throw "don''t optimize me away"; v.emplace_back(std::move(back)); } return my_clock::now() - t0; } int main() { std::vector<std::unique_ptr<int>> v_u; std::vector<int*> v_p; auto millis_p = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_p)); auto millis_u = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_u)); std::cout << "raw pointer: " << millis_p.count() << " ms, unique_ptr: " << millis_u.count() << " ms/n"; for (auto p : v_p) delete p; // I don''t like memory leaks ;-) }

Compilando el código con -O3 -o -march=native -std=c++14 -g con gcc 7.1.0, clang 3.8.0 y 17.0.4 en Linux en un Intel Xeon E5-2690 v3 @ 2.6 GHz ( sin turbo):

raw pointer: 2746 ms, unique_ptr: 5140 ms (gcc) raw pointer: 2667 ms, unique_ptr: 5529 ms (clang) raw pointer: 1448 ms, unique_ptr: 5374 ms (intel)

La versión del puntero sin memmove gasta todo el tiempo en un memmove optimizado (intel parece tener uno mucho mejor que clang y gcc). El código unique_ptr parece copiar primero los datos vectoriales de un bloque de memoria al otro y asignar el original con cero, todo en un bucle horriblemente no optimizado. Luego, vuelve a pasar por el bloque de datos original para ver si alguno de los que se acaban de cero son distintos de cero y deben eliminarse. El detalle completo y sangriento se puede ver en godbolt . La pregunta no es cómo difiere el código compilado , eso es bastante claro. La pregunta es por qué el compilador no puede optimizar lo que generalmente se considera una abstracción de no-extra-overhead.

Tratando de entender cómo razonan los compiladores sobre el manejo de std::unique_ptr , estaba buscando un poco más el código aislado. Por ejemplo:

void foo(std::unique_ptr<int>& a, std::unique_ptr<int>& b) { a.release(); a = std::move(b); }

o el similar

a.release(); a.reset(b.release());

ninguno de los compiladores x86 parece ser capaz de optimizar el sentido sin sentido if (ptr) delete ptr; . El compilador de Intel incluso le da a la eliminación un 28% de posibilidades. Sorprendentemente, la verificación de eliminación se omite constantemente para:

auto tmp = b.release(); a.release(); a.reset(tmp);

Estos bits no son el aspecto principal de esta pregunta, pero todo esto me hace sentir que me falta algo.

¿Por qué varios compiladores no pueden optimizar la reasignación dentro de std::vector<std::unique_ptr<int>> ? ¿Hay algo en el estándar que evite la generación de código tan eficiente como con los punteros sin formato? ¿Es esto un problema con la implementación de la biblioteca estándar? ¿O los compiladores no son lo suficientemente inteligentes (todavía)?

¿Qué se puede hacer para evitar el impacto en el rendimiento en comparación con el uso de punteros crudos?

Nota: Suponga que T es polimorfo y costoso de mover, por lo que std::vector<T> no es una opción.

La afirmación de que unique_ptr funciona tan bien como un puntero sin formato después de la optimización se aplica principalmente solo a las operaciones básicas en un único puntero, como creación, desreferencia, asignación de un único puntero y eliminación. Esas operaciones se definen con la suficiente simplicidad como para que un compilador de optimización pueda realizar las transformaciones requeridas de modo que el código resultante sea equivalente (o casi) en rendimiento a la versión sin formato 0 .

Un lugar en el que esto se desmorona es especialmente las optimizaciones de alto nivel basadas en el lenguaje en contenedores basados ​​en arrays, como std::vector , como ha notado con su prueba. Estos contenedores usualmente usan optimizaciones de nivel de fuente que dependen de características de tipo para determinar en tiempo de compilación si un tipo puede ser copiado de manera segura usando una copia byte-wise como memcpy , y delegar a dicho método si es así, o recurrir a un elemento -wise copia loop.

Para poder copiarse de forma segura con memcpy un objeto debe ser copiable trivialmente . Ahora std::unique_ptr no se puede copiar de manera trivial ya que de hecho falla varios de los requirements , como tener constructores de copia y movimiento triviales o eliminados. El mecanismo exacto depende de la biblioteca estándar involucrada, pero en general una implementación estándar de calidad terminará llamando a una forma especializada de algo así como std::uninitialized_copy uninitialized_copy para tipos trivially-copyable que simplemente delega en memmove .

Los detalles de implementación típicos son bastante libstc++ , pero para libstc++ (utilizado por gcc ) puede ver la divergencia de alto nivel en std::uninitialized_copy :

template<typename _InputIterator, typename _ForwardIterator> inline _ForwardIterator uninitialized_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result) { ... return std::__uninitialized_copy<__is_trivial(_ValueType1) && __is_trivial(_ValueType2) && __assignable>:: __uninit_copy(__first, __last, __result); }

A partir de ahí, puede asumir mi palabra de que muchos de los métodos de "movimiento" std::vector terminan aquí, y que __uninitialized_copy<true>::__uinit_copy(...) finalmente llama a memmove mientras que la versión <false> no lo hace - o puede rastrear el código usted mismo (pero ya vio el resultado en su punto de referencia).

Finalmente, termina con varios bucles que realizan los pasos de copia necesarios para objetos no triviales, como llamar al constructor de movimiento del objeto de destino y, posteriormente, llamar al destructor de todos los objetos de origen. Estos son bucles separados e incluso los compiladores modernos no podrán razonar sobre algo así como "OK, en el primer ciclo moví todos los objetos de destino para que su miembro ptr sea ​​nulo, por lo que el segundo ciclo es no-operativo" . Finalmente, para igualar la velocidad de los punteros sin procesar, los compiladores no solo necesitarían optimizar a través de estos dos bucles, sino que tendrían que tener una transformación que reconozca que todo el conjunto puede ser reemplazado por memcpy o memmove 2 .

Así que una respuesta a su pregunta es que los compiladores simplemente no son lo suficientemente inteligentes como para hacer esta optimización, pero es principalmente porque la versión "en bruto" tiene una gran cantidad de ayuda en tiempo de compilación para omitir la necesidad de esta optimización por completo.

Loop Fusion

Como se mencionó, las implementaciones de vector existentes implementan una operación de tipo de cambio de tamaño en dos bucles separados (además del trabajo sin bucles, como la asignación del nuevo almacenamiento y la liberación del almacenamiento anterior):

  • Copia de los objetos de origen en la matriz de destino recientemente asignada (conceptualmente usando algo como colocación nueva llamando al constructor de movimiento).
  • Destruyendo los objetos de origen en la antigua región.

Conceptualmente, podrías imaginar una forma alternativa: haciendo esto todo en un ciclo, copiando cada elemento y destruyéndolo inmediatamente. Es posible que un compilador incluso notara que los dos bucles iteran sobre el mismo conjunto de valores y fusionan los dos bucles en uno. [Aparentemente], sin embargo, ( https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html ) gcc no hace ninguna fusión de bucle hoy, y tampoco lo hace clang o icc si usted cree que esta prueba .

Entonces, nos queda tratar de poner los bucles juntos explícitamente en el nivel de origen.

Ahora la implementación de dos bucles ayuda a preservar el contrato de seguridad de excepción de la operación al no destruir ningún objeto de origen hasta que sepamos que la parte de construcción de la copia se ha completado, pero también ayuda a optimizar la copia y la destrucción cuando tenemos copia trivial y objetos trivially destructibles, respectivamente. En particular, con la selección basada en rasgos simples, podemos reemplazar la copia con un memmove y el ciclo de destrucción puede ser completamente eliminado 3 .

Entonces, el enfoque de dos ciclos ayuda cuando se aplican esas optimizaciones, pero en realidad duele en el caso general de objetos que no se pueden copiar ni destruir de manera trivial. Significa que necesita dos pasadas sobre los objetos y pierde la oportunidad de optimizar y eliminar el código entre la copia del objeto y su posterior destrucción. En el caso unique_ptr , se pierde la capacidad del compilador de propagar el conocimiento de que la fuente unique_ptr tendrá un miembro de ptr interno NULL y, por lo tanto, omitirá if (ptr) delete ptr check enteramente 4 .

Trivially Movable

Ahora uno podría preguntar si podríamos aplicar la misma optimización de tiempo de compilación tipo-rasgos al caso unique_ptr . Por ejemplo, uno puede ver los requisitos trivially que se pueden copiar y ver que son quizás demasiado estrictos para las operaciones de movimiento comunes en std::vector . Claro, un unique_ptr evidentemente no es copiable trivialmente ya que una copia bit-wise dejaría tanto el objeto de origen como el de destino debido al mismo puntero (y daría como resultado una doble eliminación), pero parece que debería ser movible por bits: si mover un unique_ptr de un área de memoria a otra, de modo que ya no considere la fuente como un objeto en vivo (y por lo tanto no llame a su destructor) debería "funcionar", para la implementación unique_ptr típica .

Desafortunadamente, no existe ese concepto de "movimiento trivial", aunque podrías intentar hacer el tuyo. Parece que hay un debate abierto sobre si esto es UB o no para objetos que pueden copiarse byte-wise y no dependen de su comportamiento de constructor o destructor en el escenario de movimiento.

Siempre puedes implementar tu propio concepto trivialmente móvil, que sería algo así como (a) el objeto tiene un constructor de movimiento trivial y (b) cuando se usa como argumento de origen del constructor de movimiento, el objeto queda en un estado donde su destructor tiene sin efecto Tenga en cuenta que tal definición actualmente es en su mayoría inútil, ya que el "constructor de movimientos triviales" (básicamente copia de elementos y nada más) no es consistente con ninguna modificación del objeto fuente. Entonces, por ejemplo, un constructor de movimientos trivial no puede establecer el miembro ptr de la fuente unique_ptr en cero. Por lo tanto, necesitaría saltar algunos aros más, como introducir el concepto de una operación de movimiento destructivo que deja el objeto fuente destruido, en lugar de hacerlo en un estado válido pero no especificado.

Puede encontrar una discusión más detallada de este "móvil trivial" en este hilo en el grupo de discusión Usenet de C ++. En particular, en la respuesta vinculada, se aborda el problema exacto de los vectores de unique_ptr :

Resulta que muchos punteros inteligentes (unique_ptr y shared_ptr incluidos) se encuentran en las tres categorías y, al aplicarlos, puede tener vectores de punteros inteligentes con una sobrecarga esencialmente nula sobre punteros sin procesar, incluso en compilaciones de depuración no optimizadas.

Ver también la propuesta del relocator .

0 Aunque los ejemplos no vectoriales al final de su pregunta muestran que este no es siempre el caso. Aquí se debe a un posible aliasing como zneak explica en su respuesta . Los punteros sin formato evitarán muchos de estos problemas de alias ya que carecen de la dirección indirecta que tiene unique_ptr (por ejemplo, pasa un puntero sin formato por valor, en lugar de una estructura con un puntero por referencia) y a menudo puede omitir el if (ptr) delete ptr enteramente.

2 Esto es realmente más difícil de lo que podría pensar, porque memmove , por ejemplo, tiene una semántica sutilmente diferente a un ciclo de copia de objeto, cuando el origen y el destino se superponen. Por supuesto, el código de rasgos de tipo de alto nivel que funciona para puntos brutos sabe (por contrato) que no hay superposición, o que el comportamiento de memmove es constante incluso si hay solapamiento, pero probando lo mismo en algún pase de optimización arbitrario posterior puede ser mucho más duro.

3 Es importante tener en cuenta que estas optimizaciones son más o menos independientes. Por ejemplo, muchos objetos son trivialmente destructibles y no son trivialmente reproducibles.

4 Aunque en mi prueba ni gcc ni clang pudieron suprimir el control, incluso con __restrict__ aplicado, aparentemente debido a un análisis de aliasing insuficientemente poderoso, o tal vez porque std::move elimina el calificador "restringir" de alguna manera.

No tengo una respuesta precisa para lo que te está mordiendo en la parte posterior con vectores; parece que BeeOnRope ya podría tener uno para ti.

Afortunadamente, puedo decirle qué le está mordiendo en la parte posterior de su micro-ejemplo que implica diferentes maneras de restablecer los punteros: análisis de alias. Específicamente, los compiladores no pueden probar (o no quieren inferir) que las dos referencias unique_ptr no se superponen. Se obligan a volver a cargar el valor unique_ptr en caso de que la escritura en el primero haya modificado el segundo. baz no lo sufre porque el compilador puede probar que ninguno de los parámetros, en un programa bien formado, podría alias con tmp , que tiene un almacenamiento automático local de funciones.

Puede verificar esto agregando la palabra clave __restrict__ (que, como el doble subrayado algo implica, no es C ++ estándar) al parámetro de referencia unique_ptr . Esa palabra clave informa al compilador que la referencia es la única referencia a través de la cual se puede acceder a esa memoria, y por lo tanto no hay riesgo de que algo más pueda alias con ella. Cuando lo hace, las tres versiones de su función se compilan con el mismo código de máquina y no se molestan en verificar si el unique_ptr necesita ser eliminado.