Pregunta Rendimiento de redimensionamiento std :: vector >


La concepción general parece ser que std::unique_ptr tiene sin tiempo por encima en comparación con los punteros sin procesar propiamente usados, dada la suficiente optimización.

Pero, ¿qué pasa con el uso 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, doy la vuelta 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 formato gasta todo el tiempo en un optimizado memmove (Intel parece tener uno mucho mejor que clang y gcc). los unique_ptr el código 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 sangriento completo se puede ver en Godbolt. La pregunta no es cómo difiere el código compiladoeso es bastante claro La pregunta es por qué el compilador no puede optimizar lo que generalmente se considera como una abstracción de no-extra-overhead.

Tratando de entender cómo los compiladores razonan sobre el manejo std::unique_ptr, Estaba buscando un poco más en 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 de distancia el 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 logran 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: Supongamos que T es polimorfo y costoso de mover, por lo std::vector<T> no es una opinión.


32
2017-07-13 19:01


origen


Respuestas:


La afirmación de que unique_ptr realiza tan bien como un puntero sin procesar después de la optimización en su mayoría se aplica solo a las operaciones básicas en un solo puntero, como creación, eliminación de referencias, 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 forma que el código resultante sea equivalente (o casi) en rendimiento a la versión bruta0.

Un lugar donde esto se derrumba es especialmente optimizaciones basadas en el lenguaje de nivel superior en contenedores basados ​​en arreglos tales como std::vector, como ha notado con su prueba. Estos contenedores usualmente usan nivel de fuente optimizaciones que dependen de características de tipo para determinar en tiempo de compilación si un tipo se puede copiar de forma segura utilizando una copia byte-wise como memcpy, y delegue a dicho método si es así, o de lo contrario recurra a un ciclo de copia de elementos.

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

Los detalles típicos de implementación son bastante tortuosos, pero para libstc++ (usado por gcc) se 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 std::vector Los métodos de "movimiento" terminan aquí, y eso __uninitialized_copy<true>::__uinit_copy(...) finalmente llamadas memmove mientras que la <false> la versión no lo hace, o usted 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 casi no podrán razonar sobre algo así como "OK, en el primer bucle moví todos los objetos de destino para que su ptr miembro será nulo, por lo que el segundo ciclo es no-operativo. "Finalmente, para igualar la velocidad de los punteros crudos, los compiladores no solo necesitarían optimizar a través de estos dos bucles, necesitarían tener una transformación que reconozca que el conjunto cosa puede ser reemplazada por memcpy o memmove2.

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ó el existente vector las implementaciones implementan una operación de tipo de cambio de tamaño en dos bucles separados (además del trabajo sin bucles como asignar el nuevo almacenamiento y liberar el 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 pueda notar que los dos bucles iteran sobre el mismo conjunto de valores y fusible los dos bucles en uno. [Aparentemente], howevever, (https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html) gcc no hace ningún fusión de bucle hoy, y no hacer clang o icc Si tu crees 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 eliminado por completo3.

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 unique_ptr caso de que pierda la capacidad del compilador de propagar el conocimiento de que la fuente unique_ptr tendrá un NULL interno ptr miembro y por lo tanto, omita el if (ptr) delete ptr verificar completamente4.

Trivially Movable

Ahora uno podría preguntar si podríamos aplicar la misma optimización de tiempo de compilación tipo-rasgos a la unique_ptr caso. Por ejemplo, uno podría mirar el trivially copyable requisitos y ver que son tal vez demasiado estrictos para el común movimiento operaciones en std::vector. Claro, una 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 eliminación doble), pero parece que debería ser un poco sabio móvil: si mueves un unique_ptr de un área de memoria a otra, de modo que ya no considere la fuente como un objeto vivo (y por lo tanto no llame a su destructor) debería "funcionar", para el típico  unique_ptr implementación.

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

Siempre podría implementar su 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 el argumento fuente del constructor de movimiento, el objeto se deja en un estado donde su destructor no tiene 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 movimiento trivial no puede configurar el ptr miembro de la fuente unique_ptr a cero. Así que necesitaría saltar algunos aros más, como introducir el concepto de movimiento destructivo operación que deja el objeto fuente destruido, en lugar de 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, la cuestión exacta de los vectores de unique_ptr está dirigido:

Resulta que muchos punteros inteligentes (unique_ptr y shared_ptr incluidos)   caer en las tres de esas categorías y mediante su aplicación puede   tener vectores de punteros inteligentes con esencialmente sobrecarga cero en bruto   punteros incluso en compilaciones de depuración no optimizadas.

Ver también el relocador propuesta.


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 indirección que unique_ptr tiene (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 verificar por completo.

2 Esto es realmente más difícil de lo que piensas, porque memmove, por ejemplo, tiene una semántica sutilmente diferente de un bucle 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 el comportamiento de memmove es consistente incluso si hay superposición, pero probar lo mismo en algún pase posterior de optimización arbitraria puede ser mucho más difícil.

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 ninguno gcc ni clang fueron capaces de suprimir el cheque, 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.


36
2017-07-13 20:02



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 los dos unique_ptr las referencias no se superponen. Se obligan a recargar el unique_ptr valor 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 almacenamiento automático local de función.

Puedes verificar esto por agregando el __restrict__ palabra clave (que, como lo implica el doble guión bajo, no es C ++ estándar) unique_ptr parámetro de referencia 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_ptrnecesita ser eliminado


8
2017-07-13 20:55