Reemplazo de C++ para VLAs C99 (objetivo: preservar el rendimiento)

Question

Reemplazo de C++ para VLAs C99 (objetivo: preservar el rendimiento)

Estoy portando código C99 que hace un uso intensivo de matrices de longitud variable (VLA) a C++.

He reemplazado el VLAs (stack allocation) con una clase array que asigna memoria en el montón. El impacto en el rendimiento fue enorme, una desaceleración de un factor de 3,2 (consulte los puntos de referencia a continuación). ¿Qué reemplazo rápido de VLA puedo usar en C++? Mi objetivo es minimizar el impacto en el rendimiento al reescribir el código para C++.

Una idea que se me sugirió fue escribir una clase de matriz que contiene un almacenamiento de tamaño fijo dentro de la clase (es decir, se puede asignar a la pila) y lo usa para arreglos pequeños, y cambia automáticamente a la asignación de montones para arreglos más grandes. Mi implementación de esto está al final del post. Funciona bastante bien, pero todavía no puedo alcanzar el rendimiento del código C99 original. Para acercarme a él, debo aumentar este almacenamiento de tamaño fijo (MSL a continuación) a tamaños con los que no me siento cómodo. No quiero asignar matrices demasiado grandes en la pila incluso para los muchos arreglos pequeños que no lo necesitan porque me preocupa que se desencadene un desbordamiento de pila. Un C99 VLA es en realidad menos propenso a esto porque nunca usará más almacenamiento del necesario.

Me encontré con std::dynarray, pero mi entendimiento es que no fue aceptado en el estándar (¿todavía?).

Sé que clang y gcc soportan VLAs en C++, pero lo necesito para trabajar con MSVC también. De hecho, una mejor portabilidad es uno de los principales objetivos de la reescritura como C++ (el otro objetivo es convertir el programa, que originalmente era una herramienta de línea de comandos, en una biblioteca reutilizable).

Punto de referencia

MSL se refiere al tamaño del array por encima del cual cambio a heap-allocation. Utilizo diferentes valores para matrices 1D y 2D.

Código C99 original: 115 segundos.
MSL = 0 (es decir, asignación de montón) : 367 segundos (3.2 x).
1D-MSL = 50, 2D-MSL = 1000: 187 segundos (1.63 x).
1D-MSL = 200, 2D-MSL = 4000: 143 segundos (1.24 x).
1D-MSL = 1000, 2D-MSL = 20000: 131 (1.14 x).

Aumentar MSL mejora aún más el rendimiento, pero eventualmente el programa comenzará a devolver resultados incorrectos (supongo que debido al desbordamiento de la pila).

Estos puntos de referencia son con clang 3.7 en OS X, pero gcc 5 muestra resultados muy similares.

Código

Esta es la implementación actual de "smallvector" que uso. Necesito vectores 1D y 2D. Cambio a heap-allocation above size MSL.

template<typename T, size_t MSL=50>
class lad_vector {
    const size_t len;
    T sdata[MSL];
    T *data;
public:
    explicit lad_vector(size_t len_) : len(len_) {
        if (len <= MSL)
            data = &sdata[0];
        else
            data = new T[len];
    }

    ~lad_vector() {
        if (len > MSL)
            delete [] data;
    }

    const T &operator [] (size_t i) const { return data[i]; }
    T &operator [] (size_t i) { return data[i]; }

    operator T * () { return data; }
};


template<typename T, size_t MSL=1000>
class lad_matrix {
    const size_t rows, cols;
    T sdata[MSL];
    T *data;

public:
    explicit lad_matrix(size_t rows_, size_t cols_) : rows(rows_), cols(cols_) {
        if (rows*cols <= MSL)
            data = &sdata[0];
        else
            data = new T[rows*cols];
    }

    ~lad_matrix() {
        if (rows*cols > MSL)
            delete [] data;
    }

    T const * operator[] (size_t i) const { return &data[cols*i]; }
    T * operator[] (size_t i) { return &data[cols*i]; }
};

36

performance c++arrays variable-length-array stack-allocation

Author: Szabolcs, 2016-04-03

Source

3 answers

Creo que ya ha enumerado la mayoría de las opciones en su pregunta y los comentarios.

Use std::vector. Esta es la solución más obvia, más libre de problemas, pero tal vez también la más lenta.
Utilice extensiones específicas de la plataforma en aquellas plataformas que las proporcionan. Por ejemplo, GCC soporta arrays de longitud variable en C++ como una extensión. POSIX especifica alloca que es ampliamente compatible para asignar memoria en la pila. Incluso Microsoft Windows proporciona _malloca, como me dijo una búsqueda rápida en la web.

Para evitar pesadillas de mantenimiento, realmente querrá encapsular estas dependencias de la plataforma en una interfaz abstracta que elija de forma automática y transparente el mecanismo apropiado para la plataforma actual. Implementar esto para todas las plataformas será un poco de trabajo, pero si esta característica única tiene en cuenta las diferencias de velocidad de 3 × a medida que informa, podría valer la pena. Como alternativa para plataformas desconocidas, Mantendría std::vector en reserva como último recurso. Es mejor correr lento pero correctamente que comportarse errático o no correr en absoluto.
Construya su propio tipo de matriz de tamaño variable que implemente una optimización de "matriz pequeña" incrustada como un búfer dentro del objeto en sí, como ha mostrado en su pregunta. Voy a tener en cuenta que prefiero tratar de usar un union de un std::array y un std::vector en lugar de rodar mi propio contenedor.

Una vez que tenga un tipo personalizado en su lugar, puede hacer perfiles interesantes como mantener una tabla hash global de todas las ocurrencias de este tipo (por ubicación del código fuente) y registrar cada tamaño de asignación durante una prueba de estrés de su programa. A continuación, puede volcar la tabla hash al salir del programa y trazar las distribuciones en tamaños de asignación para los arrays individuales. Esto podría ayudarle a ajustar la cantidad de almacenamiento a reservar para cada matriz individualmente en la pila.
Utilice un std::vector con un asignador personalizado. Al iniciar el programa, asigne unos pocos megabytes de memoria y entréguelos a un simple asignador de pila. Para un asignador de pila, la asignación es solo comparar y agregar dos enteros y la desasignación es simplemente una resta. Dudo que la asignación de pila generada por el compilador pueda ser mucho más rápida. Su " pila de matriz "pulsaría correlacionada con su"pila de programa". Este diseño también tendría la ventaja de que los desbordamientos accidentales de búfer, al mismo tiempo que invocan un comportamiento indefinido, destruyen datos aleatorios y todas esas cosas malas-no corromperían tan fácilmente la pila de programas (direcciones de retorno) como lo harían con VLAS nativas.

Los asignadores personalizados en C++ son un negocio algo sucio, pero algunas personas informan que los están utilizando con éxito. (Yo no tengo mucha experiencia con su uso.) Es posible que desee comenzar a mirar cppreference. Alisdair Meredith, que es una de esas personas que promueven el uso de asignadores personalizados, dio una charla de doble sesión en CppCon'14 titulada "Haciendo que los asignadores funcionen" (parte 1, parte 2) que usted podría encontrar interesante también. Si la interfaz std::allocator es demasiado difícil de usar para usted, implementar su propia variable (a diferencia de dinámicamente) clase de matriz de tamaño con su propio asignador también debería ser factible.

17

Author: 5gon12eder,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-03 20:48:34

Respecto al soporte para MSVC:

MSVC tiene _alloca que asigna el espacio de la pila. También tiene _malloca que asigna espacio de pila si hay suficiente espacio de pila libre, de lo contrario vuelve a la asignación dinámica.

No puede aprovechar el sistema de tipo VLA, por lo que tendría que cambiar su código para trabajar basado en un puntero al primer elemento de dicho array.

Puede terminar necesitando usar una macro que tiene diferentes definiciones dependiendo de la plataforma. Por ejemplo, invoke _alloca or _malloca on MSVC, and on g++ or other compilers, either calls alloca (if they support it), or makes a VLA and a pointer.

Considere investigar formas de reescribir el código sin necesidad de asignar una cantidad desconocida de pila. Una opción es asignar un búfer de tamaño fijo que sea el máximo que necesitará. (Si eso causaría un desbordamiento de pila, significa que su código está pinchado de todos modos).

8

Author: M.M,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-03 23:49:39

score 38 · Accepted Answer

Cree un búfer grande (MB+) en el almacenamiento local de subprocesos. (Memoria real en el montón, gestión en TLS).

Permite a los clientes solicitar memoria de ella de manera FILO (similar a la pila). (esto imita cómo funciona en C VLAs; y es eficiente, ya que cada solicitud / retorno es solo una suma/resta de enteros).

Obtenga su almacenamiento VLA de él.

Envolverlo bastante, por lo que se puede decir stack_array<T> x(1024);, y tienen que stack_array tratar con la construcción / destrucción (tenga en cuenta que ->~T() donde T es int es un legal noop, y la construcción puede ser de manera similar un noop), o hacer stack_array<T> wrap a std::vector<T, TLS_stack_allocator>.

Los datos no serán tan locales como los datos de C VLA porque estarán efectivamente en una pila separada. Puede usar SBO (small buffer optimization), que es cuando la localidad realmente importa.

Un SBO stack_array<T> se puede implementar con un asignador y un vector std unificados con una matriz std, o con un ptr único y destructor personalizado, o una miríada de otras formas. Probablemente pueda adaptar su solución, reemplazar su nuevo / malloc / free / delete con llamadas al almacenamiento TLS anterior.

Digo ir con TLS ya que elimina la necesidad de sobrecarga de sincronización mientras permite el uso de subprocesos múltiples, y refleja el hecho de que la pila en sí es implícitamente TLS.

¿Asignador STL basado en Stack-buffer? es un SO Q&A con al menos dos asignadores "stack" en las respuestas. Necesitarán alguna adaptación para obtener automáticamente su búfer de TLS.

Tenga en cuenta que el TLS es un búfer grande es en cierto sentido un detalle de implementación. Usted podría hacer grandes asignaciones, y cuando se queda sin espacio hacer otra gran asignación. Solo necesita realizar un seguimiento de cada" página de pila " capacidad actual y una lista de páginas de pila, por lo que cuando se vacía uno puede pasar a una anterior. Eso le permite ser un poco más conservador en su asignación inicial de TLS sin preocuparse por ejecutar OOM; la parte importante es que usted es FILO y asigna rara vez, no que todo el búfer FILO sea un contiguo una.