c++ - Stack-buffer basado en el asignador STL?

allocator

Question

Me preguntaba si sería factible tener un allocator compatible con la biblioteca estándar de C ++ que use un búfer (de tamaño fijo) que se encuentre en la pila.

De alguna manera, parece que esta pregunta aún no se ha formulado de esta manera sobre el SO, aunque puede haber sido respondida implícitamente en otra parte.

Básicamente, parece que , en lo que respecta a mis búsquedas, debería ser posible crear un asignador que use un búfer de tamaño fijo. Ahora, a primera vista, esto debería significar que también debería ser posible tener un asignador que use un búfer de tamaño fijo que "viva" en la pila, pero parece que no existe una implementación generalizada de este tipo.

Déjame dar un ejemplo de lo que quiero decir:

{ ...
  char buf[512];
  typedef ...hmm?... local_allocator; // should use buf
  typedef std::basic_string<char, std::char_traits<char>, local_allocator> lstring;
  lstring str; // string object of max. 512 char
}

¿Cómo sería esto implementable?

La respuesta a esta otra pregunta (gracias a R. Martinho Fernandes) se vincula a un asignador basado en pila desde las fuentes de cromo: http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h

Sin embargo, esta clase parece extremadamente peculiar, especialmente porque este StackAllocator no tiene un ctor predeterminado , y en ese momento pensaba que cada clase asignadora necesita un ctor predeterminado .

Answer 1

Aparentemente, hay un Asignador de Apilamiento conforme de un Howard Hinnant .

Funciona utilizando un búfer de tamaño fijo (a través de un objeto de arena referenciado) y retrocediendo al montón si se solicita demasiado espacio.

Este asignador no tiene un ctor predeterminado, y desde Howard dice:

He actualizado este artículo con un nuevo asignador que se ajusta completamente a C ++ 11.

Diría que no es un requisito que un asignador tenga un ctor predeterminado.

Answer 2

Esta es en realidad una práctica extremadamente útil y se usa bastante en el desarrollo del desempeño, como los juegos. Para incrustar la memoria en línea en la pila o dentro de la asignación de una estructura de clase puede ser crítico para la velocidad y la administración del contenedor.

Para responder a su pregunta, todo se reduce a la implementación del contenedor stl. Si el contenedor no solo crea instancias, sino que también mantiene la referencia a su asignador como miembro, entonces es bueno ir para crear un montón fijo, he descubierto que esto no siempre es así ya que no es parte de la especificación. De lo contrario se vuelve problemático. Una solución puede ser envolver el contenedor, el vector, la lista, etc. con otra clase que contenga el almacenamiento. A continuación, puede utilizar un asignador para extraer de eso. Esto podría requerir una gran cantidad de plantillas de magia (tm).

Answer 3

Realmente depende de sus requisitos, seguro si lo desea puede crear un asignador que opere solo en la pila, pero sería muy limitado ya que el mismo objeto de la pila no es accesible desde cualquier lugar del programa como lo haría un objeto de montón.

Creo que este artículo explica muy bien los asignadores

http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

Answer 4

Un asignador STL basado en pila es de una utilidad tan limitada que dudo que encuentre mucha técnica anterior. Incluso el ejemplo simple que cites explota rápidamente si luego decides que quieres copiar o alargar la lstring inicial.

Para otros contenedores de STL como los asociativos (internamente basados ​​en árboles) o incluso vector y deque que usan uno o varios bloques contiguos de RAM, la semántica de uso de memoria rápidamente se vuelve inmanejable en la pila en casi cualquier uso del mundo real.

Answer 5

Definitivamente es posible crear un asignador de pila conformado completamente C ++ 11 / C ++ 14 *. Pero debe considerar algunas de las ramificaciones sobre la implementación y la semántica de la asignación de la pila y cómo interactúan con los contenedores estándar.

Aquí hay un asignador de pila que cumple con C ++ 11 / C ++ 14 (también alojado en mi github ):

#include <functional>
#include <memory>

template <class T, std::size_t N, class Allocator = std::allocator<T>>
class stack_allocator
{
    public:

    typedef typename std::allocator_traits<Allocator>::value_type value_type;
    typedef typename std::allocator_traits<Allocator>::pointer pointer;
    typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename std::allocator_traits<Allocator>::size_type size_type;
    typedef typename std::allocator_traits<Allocator>::difference_type difference_type;

    typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
    typedef Allocator allocator_type;

    public:

    explicit stack_allocator(const allocator_type& alloc = allocator_type()) 
        : m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
    { }

    explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
        : m_allocator(alloc), m_begin(buffer), m_end(buffer + N), 
            m_stack_pointer(buffer)
    { }

    template <class U>
    stack_allocator(const stack_allocator<U, N, Allocator>& other)
        : m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
            m_stack_pointer(other.m_stack_pointer)
    { }

    constexpr static size_type capacity()
    {
        return N;
    }

    pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
    {
        if (n <= size_type(std::distance(m_stack_pointer, m_end)))
        {
            pointer result = m_stack_pointer;
            m_stack_pointer += n;
            return result;
        }

        return m_allocator.allocate(n, hint);
    }

    void deallocate(pointer p, size_type n)
    {
        if (pointer_to_internal_buffer(p))
        {
            m_stack_pointer -= n;
        }
        else m_allocator.deallocate(p, n);  
    }

    size_type max_size() const noexcept
    {
        return m_allocator.max_size();
    }

    template <class U, class... Args>
    void construct(U* p, Args&&... args)
    {
        m_allocator.construct(p, std::forward<Args>(args)...);
    }

    template <class U>
    void destroy(U* p)
    {
        m_allocator.destroy(p);
    }

    pointer address(reference x) const noexcept
    {
        if (pointer_to_internal_buffer(std::addressof(x)))
        {
            return std::addressof(x);
        }

        return m_allocator.address(x);
    }

    const_pointer address(const_reference x) const noexcept
    {
        if (pointer_to_internal_buffer(std::addressof(x)))
        {
            return std::addressof(x);
        }

        return m_allocator.address(x);
    }

    template <class U>
    struct rebind { typedef stack_allocator<U, N, allocator_type> other; };

    pointer buffer() const noexcept
    {
        return m_begin;
    }

    private:

    bool pointer_to_internal_buffer(const_pointer p) const
    {
        return (!(std::less<const_pointer>()(p, m_begin)) && (std::less<const_pointer>()(p, m_end)));
    }

    allocator_type m_allocator;
    pointer m_begin;
    pointer m_end;
    pointer m_stack_pointer;
};

template <class T1, std::size_t N, class Allocator, class T2>
bool operator == (const stack_allocator<T1, N, Allocator>& lhs, 
    const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
    return lhs.buffer() == rhs.buffer();
}

template <class T1, std::size_t N, class Allocator, class T2>
bool operator != (const stack_allocator<T1, N, Allocator>& lhs, 
    const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
    return !(lhs == rhs);
}

Este asignador utiliza un búfer de tamaño fijo proporcionado por el usuario como fuente inicial de memoria, y luego recurre a un asignador secundario ( std::allocator<T> de manera predeterminada) cuando se queda sin espacio.

Cosas para considerar:

Antes de seguir adelante y usar un asignador de pila, debe tener en cuenta sus patrones de asignación. En primer lugar, cuando se utiliza un búfer de memoria en la pila, debe considerar qué significa exactamente asignar y desasignar la memoria.

El método más simple (y el método empleado anteriormente) es simplemente incrementar un puntero de pila para asignaciones y disminuirlo para desasignaciones. Tenga en cuenta que esto limita severamente la forma en que puede usar el asignador en la práctica. Funcionará bien para, digamos, un std::vector (que asignará un solo bloque de memoria contiguo) si se usa correctamente, pero no funcionará para, por ejemplo, un std::map , que asignará y desasignará los objetos de nodo en orden variable .

Si su asignador de pila simplemente incrementa y disminuye un puntero de pila, entonces obtendrá un comportamiento indefinido si sus asignaciones y desasignaciones no están en el orden LIFO. Incluso un std::vector causará un comportamiento indefinido si primero asigna un solo bloque contiguo de la pila, luego asigna un segundo bloque de pila, luego desasigna el primer bloque, lo que sucederá cada vez que el vector incremente su capacidad a un valor que sea aún más pequeño que stack_size . Es por eso que deberás reservar el tamaño de la pila por adelantado. (Pero consulte la nota a continuación sobre la implementación de Howard Hinnant).

Lo que nos lleva a la pregunta ...

¿Qué es lo que realmente quieres de un asignador de pila?

¿Realmente desea un asignador de propósito general que le permita asignar y desasignar fragmentos de memoria de varios tamaños en orden variable (como malloc ), excepto que se extrae de un búfer de pila asignado previamente en lugar de llamar a sbrk ? Si es así, básicamente estás hablando de implementar un asignador de propósito general que mantenga de alguna manera una lista libre de bloques de memoria, solo el usuario puede proporcionarle un búfer de pila preexistente. Este es un proyecto mucho más complejo. (¿Y qué debería hacer si se agota el espacio? Throw std::bad_alloc ? ¿Volver al montón?)

La implementación anterior asume que usted desea un asignador que simplemente utilizará los patrones de asignación LIFO y recurrirá a otro asignador si se queda sin espacio. Esto funciona bien para std::vector , que siempre utilizará un único búfer contiguo que se puede reservar por adelantado. Cuando std::vector necesita un búfer más grande, asignará un búfer más grande, copiará (o moverá) los elementos en el búfer más pequeño y luego desasignará el búfer más pequeño. Cuando el vector solicita un búfer más grande, la implementación del stack_allocator anterior simplemente retrocederá a un asignador secundario (que es std::allocator por defecto).

Así por ejemplo:

const static std::size_t stack_size = 4;
int buffer[stack_size];

typedef stack_allocator<int, stack_size> allocator_type;

std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
vec.reserve(stack_size); // attempt to reserve space for 4 elements

std::cout << vec.capacity() << std::endl;

vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);

// Assert that the vector is actually using our stack
//
assert(
    std::equal(
        vec.begin(), 
        vec.end(), 
        buffer, 
        [](const int& v1, const int& v2) {
            return &v1 == &v2;
        }
    )
);

// Output some values in the stack, we see it is the same values we
// inserted in our vector.
//
std::cout << buffer[0] << std::endl;
std::cout << buffer[1] << std::endl;
std::cout << buffer[2] << std::endl;
std::cout << buffer[3] << std::endl;

// Attempt to push back some more values.  Since our stack allocator only has 
// room for 4 elements, we cannot satisfy the request for an 8 element buffer.  
// So, the allocator quietly falls back on using std::allocator.
//
// Alternatively, you could modify the stack_allocator implementation
// to throw std::bad_alloc
//
vec.push_back(50);
vec.push_back(60);
vec.push_back(70);
vec.push_back(80);

// Assert that we are no longer using the stack buffer
//
assert(
    !std::equal(
        vec.begin(), 
        vec.end(), 
        buffer, 
        [](const int& v1, const int& v2) {
            return &v1 == &v2;
        }
    )
);

// Print out all the values in our vector just to make sure 
// everything is sane.
//
for (auto v : vec) std::cout << v << ", ";
std::cout << std::endl;

Ver: http://ideone.com/YhMZxt

De nuevo, esto funciona bien para vector, pero debes preguntarte qué es exactamente lo que pretendes hacer con el asignador de pila. Si quiere un asignador de memoria de propósito general que simplemente se extrae de un buffer de pila, está hablando de un proyecto mucho más complejo. Un simple apilador de pila, sin embargo, que simplemente incrementa y disminuye un puntero de pila funcionará para un conjunto limitado de casos de uso. Tenga en cuenta que para los tipos que no son POD, deberá usar std::aligned_storage<T, alignof(T)> para crear el búfer de pila real.

También observaría que, a diferencia de la implementación de Howard Hinnant , la implementación anterior no comprueba explícitamente que cuando se llama a deallocate() , el puntero que se pasa es el último bloque asignado. La implementación de Hinnant simplemente no hará nada si el puntero pasado no es una desasignación ordenada por LIFO. Esto le permitirá usar un std::vector sin reservar por adelantado porque el asignador básicamente ignorará el intento del vector de desasignar el búfer inicial. Pero esto también difumina un poco la semántica del asignador y se basa en un comportamiento que está específicamente ligado a la forma en que se sabe que funciona std::vector . Mi sensación es que podemos decir simplemente que pasar cualquier puntero a deallocate() que no se devolvió a través de la última llamada a allocate() dará lugar a un comportamiento indefinido y lo dejará así.

* Finalmente: la siguiente advertencia: parece ser debatable si la función que comprueba si un puntero está dentro de los límites del búfer de pila está o no definida por el estándar. La comparación de pedidos de dos punteros de diferentes new / malloc ''d buffers es posiblemente un comportamiento definido por la implementación (incluso con std::less ), lo que tal vez hace imposible escribir una implementación del asignador de pila conforme a los estándares que recurre a la asignación del montón. (Pero en la práctica esto no importará a menos que esté ejecutando un 80286 en MS-DOS).

** Finalmente (realmente ahora), también vale la pena señalar que la palabra "pila" en el asignador de pila está sobrecargada para referirse tanto a la fuente de memoria (una matriz de pila de tamaño fijo) como al método de asignación (un incremento de LIFO / decremento puntero de pila). Cuando la mayoría de los programadores dicen que quieren un asignador de pila, están pensando en el significado anterior sin considerar necesariamente la semántica de este último, y cómo estas semánticas restringen el uso de dicho asignador con contenedores estándar.