proposito - Reemplazo de C++ para VLA C99(objetivo: preservar el rendimiento)

programacion en c resumen (3)

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

Reemplacé los VLA (asignación de pila) con una clase de matriz que asigna memoria en el montón. El golpe de rendimiento fue enorme, una desaceleración de un factor de 3,2 (ver puntos de referencia a continuación). ¿Qué reemplazo rápido de VLA puedo usar en C ++? Mi objetivo es minimizar el rendimiento alcanzado al reescribir el código para C ++.

Una idea que me sugirieron fue escribir una clase de matriz que contenga un almacenamiento de tamaño fijo dentro de la clase (es decir, se pueda asignar a la pila) y la use para matrices pequeñas, y cambie automáticamente a asignación de pila para matrices más grandes. Mi implementación de esto está al final de la publicación. 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 continuación) a tamaños con los que no me siento cómodo. No quiero asignar matrices demasiado grandes en la pila incluso para las muchas matrices pequeñas que no las necesitan porque me preocupa que desencadene un desbordamiento de la pila. Un C99 VLA es en realidad menos propenso a esto porque nunca usará más almacenamiento del necesario.

Encontré std::dynarray , pero tengo entendido que no fue aceptado en el estándar (¿todavía?).

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

Punto de referencia

MSL refiere al tamaño de la matriz sobre el cual cambio a la asignación de heap. Utilizo diferentes valores para matrices 1D y 2D.

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

El aumento de MSL mejora aún más el rendimiento, pero finalmente 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 "pequeño árbol" que uso. Necesito vectores 1D y 2D. Cambio a la asignación de heap por encima del tamaño de 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]; } };

Con respecto al soporte para MSVC:

_alloca tiene _alloca que asigna espacio de 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 el código para trabajar basado en un puntero al primer elemento de dicha matriz.

Puede terminar necesitando usar una macro que tenga diferentes definiciones dependiendo de la plataforma. Por ejemplo, invoque _alloca o _malloca en _malloca , y en g ++ u otros compiladores, llame a alloca (si lo admiten), o alloca un VLA y un puntero.

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

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

Permita que los clientes soliciten memoria desde FILO (en forma de pila). (Esto imita cómo funciona en C VLAs y es eficiente, ya que cada solicitud / devolución es solo una suma / resta entera).

Obtenga su almacenamiento VLA de ella.

Envuélvela bonita, entonces puedes decir stack_array<T> x(1024); , y hacer que stack_array ocupe de la construcción / destrucción (tenga en cuenta que ->~T() donde T es int es un noop legal, y la construcción también puede ser un noop), o make 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 (optimización de búfer pequeño), que es cuando la localidad realmente importa.

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

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

Stack-buffer basado en el asignador STL? es un SO Q & A con al menos dos asignadores de "pila" en las respuestas. Necesitarán alguna adaptación para obtener automáticamente su memoria intermedia de TLS.

Tenga en cuenta que el TLS es un gran buffer es, en cierto sentido, un detalle de implementación. Podría hacer grandes asignaciones, y cuando se quede sin espacio, haga otra gran asignación. Solo necesita realizar un seguimiento de cada capacidad de la "pila de páginas" y una lista de páginas de la pila, de modo que cuando vacíe una pueda 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 raramente, no que todo el buffer FILO sea uno contiguo.

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 fácil pero también la más lenta.
Use extensiones específicas de la plataforma en aquellas plataformas que los proporcionan. Por ejemplo, GCC admite matrices de longitud variable en C ++ como una extensión. POSIX especifica man7.org/linux/man-pages/man3/alloca.3.html 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 deseará encapsular estas dependencias de la plataforma en una interfaz abstracta que elija automática y transparentemente el mecanismo apropiado para la plataforma actual. Implementar esto para todas las plataformas será un poco laborioso, pero si esta característica única representa las diferencias de velocidad de 3 × como informa, puede valer la pena. Como reserva para plataformas desconocidas, mantendría std::vector en reserva como último recurso. Es mejor correr lento pero correctamente que comportarse de manera errática o no ejecutar en absoluto.
Cree su propio tipo de matriz de tamaño variable que implemente una optimización de "pequeña matriz" incrustada como un búfer dentro del objeto como lo ha mostrado en su pregunta. Notaré que prefiero usar una union de std::array y std::vector lugar de rodar mi propio contenedor.
Una vez que tenga un tipo personalizado en su lugar, puede realizar perfiles interesantes, como mantener una tabla hash global de todas las ocurrencias de este tipo (por ubicación de 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 los tamaños de asignación para las matrices individuales. Esto podría ayudarlo a ajustar la cantidad de almacenamiento para reservar para cada matriz individualmente en la pila.
Use un std::vector con un asignador personalizado. Al iniciar el programa, asigne unos pocos megabytes de memoria y dele un simple apilador de pila. Para un asignador de pila, la asignación es simplemente comparar y agregar dos enteros y la desasignación es simplemente una resta. Dudo que la distribución de la pila generada por el compilador pueda ser mucho más rápida. Su "pila de matriz" pulsan correlacionada con su "pila de programas". Este diseño también tendría la ventaja de que los desbordamientos accidentales del búfer, al tiempo que invocaban comportamientos indefinidos, descartaban datos aleatorios y todas esas cosas malas, no dañaban tan fácilmente la pila del programa (direcciones de retorno) como lo harían con los VLA nativos.
Los asignadores personalizados en C ++ son un asunto un tanto sucio, pero algunas personas informan que los están utilizando con éxito. (No tengo mucha experiencia con el uso de ellos). Es posible que desee comenzar a buscar en cppreference . Alisdair Meredith, quien es una de esas personas que promueve el uso de asignadores personalizados, dio una charla de doble sesión en CppCon''14 titulada "Hacer que los adjudicadores funcionen" ( part 1 , part 2 ) que también puede resultarle interesante. Si la interfaz de std::allocator es demasiado incómoda para usted, también debe poder implementar su propia clase de matriz de tamaño variable (en lugar de dinámica ) con su propio asignador.