c++ - para - manual de programacion android pdf

C++ 11 patrón de diseño de grupo de memoria?

Question

Tengo un programa que contiene una fase de procesamiento que necesita usar varias instancias de objetos diferentes (todas asignadas en el montón) de un árbol de tipos polimórficos, todos derivados eventualmente de una clase base común.

Como las instancias pueden referenciar cíclicamente entre sí, y no tienen un propietario claro, quiero asignarlas con new , manejarlas con punteros sin formato y dejarlas en memoria para la fase (incluso si no se referencian), y luego después del fase del programa que usa estas instancias, quiero eliminarlas todas a la vez.

Cómo pensé estructurarlo es el siguiente:

struct B; // common base class

vector<unique_ptr<B>> memory_pool;

struct B
{
    B() { memory_pool.emplace_back(this); }

    virtual ~B() {}
};

struct D : B { ... }

int main()
{
    ...

    // phase begins
    D* p = new D(...);

    ...

    // phase ends
    memory_pool.clear();
    // all B instances are deleted, and pointers invalidated

    ...
}

Además de tener cuidado de que todas las instancias B se asignen con nuevas, y que nadie las use después de borrar el grupo de memoria, ¿hay problemas con esta implementación?

Específicamente, me preocupa el hecho de que this puntero se use para construir un std::unique_ptr en el constructor de la clase base, antes de que el constructor de la clase derivada se haya completado. ¿Esto resulta en un comportamiento indefinido? ¿Si es así, hay alguna solución?

Answer 1

Hmm, necesitaba casi exactamente lo mismo recientemente (grupo de memoria para una fase de un programa que se borra todo de una vez), excepto que tenía la restricción de diseño adicional de que todos mis objetos serían bastante pequeños.

Se me ocurrió el siguiente "grupo de memoria de objetos pequeños": tal vez te sea útil:

#pragma once

#include "defs.h"
#include <cstdint>      // uintptr_t
#include <cstdlib>      // std::malloc, std::size_t
#include <type_traits>  // std::alignment_of
#include <utility>      // std::forward
#include <algorithm>    // std::max
#include <cassert>      // assert


// Small-object allocator that uses a memory pool.
// Objects constructed in this arena *must not* have delete called on them.
// Allows all memory in the arena to be freed at once (destructors will
// be called).
// Usage:
//     SmallObjectArena arena;
//     Foo* foo = arena::create<Foo>();
//     arena.free();        // Calls ~Foo
class SmallObjectArena
{
private:
    typedef void (*Dtor)(void*);

    struct Record
    {
        Dtor dtor;
        short endOfPrevRecordOffset;    // Bytes between end of previous record and beginning of this one
        short objectOffset;             // From the end of the previous record
    };

    struct Block
    {
        size_t size;
        char* rawBlock;
        Block* prevBlock;
        char* startOfNextRecord;
    };

    template<typename T> static void DtorWrapper(void* obj) { static_cast<T*>(obj)->~T(); }

public:
    explicit SmallObjectArena(std::size_t initialPoolSize = 8192)
        : currentBlock(nullptr)
    {
        assert(initialPoolSize >= sizeof(Block) + std::alignment_of<Block>::value);
        assert(initialPoolSize >= 128);

        createNewBlock(initialPoolSize);
    }

    ~SmallObjectArena()
    {
        this->free();
        std::free(currentBlock->rawBlock);
    }

    template<typename T>
    inline T* create()
    {
        return new (alloc<T>()) T();
    }

    template<typename T, typename A1>
    inline T* create(A1&& a1)
    {
        return new (alloc<T>()) T(std::forward<A1>(a1));
    }

    template<typename T, typename A1, typename A2>
    inline T* create(A1&& a1, A2&& a2)
    {
        return new (alloc<T>()) T(std::forward<A1>(a1), std::forward<A2>(a2));
    }

    template<typename T, typename A1, typename A2, typename A3>
    inline T* create(A1&& a1, A2&& a2, A3&& a3)
    {
        return new (alloc<T>()) T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3));
    }

    // Calls the destructors of all currently allocated objects
    // then frees all allocated memory. Destructors are called in
    // the reverse order that the objects were constructed in.
    void free()
    {
        // Destroy all objects in arena, and free all blocks except
        // for the initial block.
        do {
            char* endOfRecord = currentBlock->startOfNextRecord;
            while (endOfRecord != reinterpret_cast<char*>(currentBlock) + sizeof(Block)) {
                auto startOfRecord = endOfRecord - sizeof(Record);
                auto record = reinterpret_cast<Record*>(startOfRecord);
                endOfRecord = startOfRecord - record->endOfPrevRecordOffset;
                record->dtor(endOfRecord + record->objectOffset);
            }

            if (currentBlock->prevBlock != nullptr) {
                auto memToFree = currentBlock->rawBlock;
                currentBlock = currentBlock->prevBlock;
                std::free(memToFree);
            }
        } while (currentBlock->prevBlock != nullptr);
        currentBlock->startOfNextRecord = reinterpret_cast<char*>(currentBlock) + sizeof(Block);
    }

private:
    template<typename T>
    static inline char* alignFor(char* ptr)
    {
        const size_t alignment = std::alignment_of<T>::value;
        return ptr + (alignment - (reinterpret_cast<uintptr_t>(ptr) % alignment)) % alignment;
    }

    template<typename T>
    T* alloc()
    {
        char* objectLocation = alignFor<T>(currentBlock->startOfNextRecord);
        char* nextRecordStart = alignFor<Record>(objectLocation + sizeof(T));
        if (nextRecordStart + sizeof(Record) > currentBlock->rawBlock + currentBlock->size) {
            createNewBlock(2 * std::max(currentBlock->size, sizeof(T) + sizeof(Record) + sizeof(Block) + 128));
            objectLocation = alignFor<T>(currentBlock->startOfNextRecord);
            nextRecordStart = alignFor<Record>(objectLocation + sizeof(T));
        }
        auto record = reinterpret_cast<Record*>(nextRecordStart);
        record->dtor = &DtorWrapper<T>;
        assert(objectLocation - currentBlock->startOfNextRecord < 32768);
        record->objectOffset = static_cast<short>(objectLocation - currentBlock->startOfNextRecord);
        assert(nextRecordStart - currentBlock->startOfNextRecord < 32768);
        record->endOfPrevRecordOffset = static_cast<short>(nextRecordStart - currentBlock->startOfNextRecord);
        currentBlock->startOfNextRecord = nextRecordStart + sizeof(Record);

        return reinterpret_cast<T*>(objectLocation);
    }

    void createNewBlock(size_t newBlockSize)
    {
        auto raw = static_cast<char*>(std::malloc(newBlockSize));
        auto blockStart = alignFor<Block>(raw);
        auto newBlock = reinterpret_cast<Block*>(blockStart);
        newBlock->rawBlock = raw;
        newBlock->prevBlock = currentBlock;
        newBlock->startOfNextRecord = blockStart + sizeof(Block);
        newBlock->size = newBlockSize;
        currentBlock = newBlock;
    }

private:
    Block* currentBlock;
};

Para responder a su pregunta, no está invocando un comportamiento indefinido, ya que nadie está utilizando el puntero hasta que el objeto esté completamente construido (el valor del puntero en sí mismo es seguro para copiar hasta ese momento). Sin embargo, es un método bastante intrusivo, ya que los objetos necesitan saber sobre el grupo de memoria. Además, si está construyendo una gran cantidad de objetos pequeños, probablemente sería más rápido usar un grupo de memoria real (como mi pool) en lugar de llamar a new para cada objeto.

Cualquiera que sea el método de agrupación que use, tenga cuidado de que los objetos nunca se eliminen manualmente, ¡porque eso daría lugar a una doble gratis!

Answer 2

Tu idea es excelente y millones de aplicaciones ya la están usando. Este patrón es más conocido como «grupo de autorrelease». Forma una base para la administración de memoria "inteligente" en los marcos Cocoa y Cocoa Touch Objective-C. A pesar de que C ++ ofrece muchísimas otras alternativas, sigo pensando que esta idea tuvo muchas ventajas. Pero hay algunas cosas en las que creo que su implementación, tal como está, puede quedar corta.

El primer problema que puedo pensar es la seguridad del hilo. Por ejemplo, ¿qué ocurre cuando se crean objetos de la misma base a partir de diferentes hilos? Una solución podría ser proteger el acceso al grupo con bloqueos mutuamente excluyentes. Aunque creo que una mejor forma de hacerlo es hacer que ese grupo sea un objeto específico de subprocesos.

El segundo problema es invocar un comportamiento indefinido en caso de que el constructor de la clase derivada arroje una excepción. Verá, si eso sucede, el objeto derivado no será construido, pero el constructor de su B ya habría empujado un puntero al vector. Más adelante, cuando se borre el vector, intentará llamar a un destructor a través de una tabla virtual del objeto que o bien no existe o es de hecho un objeto diferente (porque lo new podría reutilizar esa dirección).

La tercera cosa que no me gusta es que solo tiene un grupo global, incluso si es específico de subprocesos, eso simplemente no permite un control más detallado sobre el alcance de los objetos asignados.

Tomando lo anterior en cuenta, haría un par de mejoras:

1. Tenga una pila de piscinas para un control más preciso del alcance.
2. Haga que ese grupo apile un objeto específico de subprocesos.
3. En caso de fallas (como la excepción en el constructor de clase derivada), asegúrese de que el grupo no tenga un puntero colgante.

Aquí está mi solución literal de 5 minutos, no juzgue por rápida y sucia:

#include <new>
#include <set>
#include <stack>
#include <cassert>
#include <memory>
#include <stdexcept>
#include <iostream>

#define thread_local __thread // Sorry, my compiler doesn''t C++11 thread locals

struct AutoReleaseObject {
    AutoReleaseObject();
    virtual ~AutoReleaseObject();
};

class AutoReleasePool final {
  public:
    AutoReleasePool() {
        stack_.emplace(this);
    }

    ~AutoReleasePool() noexcept {
        std::set<AutoReleaseObject *> obj;
        obj.swap(objects_);
        for (auto *p : obj) {
            delete p;
        }
        stack_.pop();
    }

    static AutoReleasePool &instance() {
        assert(!stack_.empty());
        return *stack_.top();
    }

    void add(AutoReleaseObject *obj) {
        objects_.insert(obj);
    }

    void del(AutoReleaseObject *obj) {
        objects_.erase(obj);
    }

    AutoReleasePool(const AutoReleasePool &) = delete;
    AutoReleasePool &operator = (const AutoReleasePool &) = delete;

  private:
    // Hopefully, making this private won''t allow users to create pool
    // not on stack that easily... But it won''t make it impossible of course.
    void *operator new(size_t size) {
        return ::operator new(size);
    }

    std::set<AutoReleaseObject *> objects_;

    struct PrivateTraits {};

    AutoReleasePool(const PrivateTraits &) {
    }

    struct Stack final : std::stack<AutoReleasePool *> {
        Stack() {
            std::unique_ptr<AutoReleasePool> pool
                (new AutoReleasePool(PrivateTraits()));
            push(pool.get());
            pool.release();
        }

        ~Stack() {
            assert(!stack_.empty());
            delete stack_.top();
        }
    };

    static thread_local Stack stack_;
};

thread_local AutoReleasePool::Stack AutoReleasePool::stack_;

AutoReleaseObject::AutoReleaseObject()
{
    AutoReleasePool::instance().add(this);
}

AutoReleaseObject::~AutoReleaseObject()
{
    AutoReleasePool::instance().del(this);
}

// Some usage example...

struct MyObj : AutoReleaseObject {
    MyObj() {
        std::cout << "MyObj::MyObj(" << this << ")" << std::endl;
    }

    ~MyObj() override {
        std::cout << "MyObj::~MyObj(" << this << ")" << std::endl;
    }

    void bar() {
        std::cout << "MyObj::bar(" << this << ")" << std::endl;
    }
};

struct MyObjBad final : AutoReleaseObject {
    MyObjBad() {
        throw std::runtime_error("oops!");
    }

    ~MyObjBad() override {
    }
};

void bar()
{
    AutoReleasePool local_scope;
    for (int i = 0; i < 3; ++i) {
        auto o = new MyObj();
        o->bar();
    }
}

void foo()
{
    for (int i = 0; i < 2; ++i) {
        auto o = new MyObj();
        bar();
        o->bar();
    }
}

int main()
{
    std::cout << "main start..." << std::endl;
    foo();
    std::cout << "main end..." << std::endl;
}

Answer 3

En caso de que aún no lo haya hecho, familiarícese con Boost.Pool . De la documentación

¿Qué es Pool?

La asignación de grupo es un esquema de asignación de memoria que es muy rápido, pero limitado en su uso. Para obtener más información sobre la asignación de grupos (también llamada almacenamiento segregado simple, consulte Conceptos de conceptos y Almacenamiento segregado simple).

¿Por qué debería usar Pool?

El uso de Pools te da más control sobre cómo se usa la memoria en tu programa. Por ejemplo, podría tener una situación en la que desea asignar un grupo de objetos pequeños en un punto, y luego llegar a un punto en su programa donde ya no se necesitan ninguno. Utilizando interfaces de grupo, puede elegir ejecutar sus destructores o simplemente dejarlos en el olvido; la interfaz del grupo garantizará que no haya pérdidas de memoria del sistema.

¿Cuándo debería usar Pool?

Las agrupaciones se utilizan generalmente cuando hay una gran cantidad de asignación y desasignación de objetos pequeños. Otro uso común es la situación anterior, donde muchos objetos pueden perderse de memoria.

En general, use Pools cuando necesite una forma más eficiente de realizar un control de memoria inusual.

¿Qué asignador de grupo debo usar?

pool_allocator es una solución de propósito más general, orientada a atender de manera eficiente las solicitudes de cualquier cantidad de fragmentos contiguos.

fast_pool_allocator es también una solución de propósito general, pero está orientada a atender de manera eficiente las solicitudes de un fragmento a la vez; funcionará para fragmentos contiguos, pero no tan bien como pool_allocator .

Si está muy preocupado por el rendimiento, use fast_pool_allocator cuando fast_pool_allocator con contenedores como std::list y use pool_allocator cuando pool_allocator con contenedores como std::vector .

La administración de la memoria es una tarea difícil (subprocesamiento, almacenamiento en caché, alineación, fragmentación, etc.). Para obtener un código de producción serio, las librerías bien diseñadas y cuidadosamente optimizadas son el camino a seguir, a menos que su generador de perfiles demuestre un cuello de botella.

Answer 4

Esto suena a lo que he oído llamar un Allocator lineal. Explicaré los conceptos básicos de cómo entiendo cómo funciona.

1. Asigne un bloque de memoria usando :: operator new (size);
2. Tiene un vacío * que es su puntero al próximo espacio libre en la memoria.
3. Tendrás una función alloc (size_t size) que te dará un puntero a la ubicación en el bloque desde el primer paso para que puedas construir usando Placement New
4. La ubicación nueva parece ... int * i = new (ubicación) int (); donde la ubicación es un vacío * a un bloque de memoria asignado desde el asignador.
5. Cuando hayas terminado con toda tu memoria, llamarás a una función Flush () que desasignará la memoria del grupo o al menos borrará los datos.

Programé uno de estos recientemente y publicaré mi código aquí para ti, y haré todo lo posible para explicarlo.

    #include <iostream>
    class LinearAllocator:public ObjectBase
    {
    public:
        LinearAllocator();
        LinearAllocator(Pool* pool,size_t size);
        ~LinearAllocator();
        void* Alloc(Size_t size);
        void Flush();
    private:
        void** m_pBlock;
        void* m_pHeadFree;
        void* m_pEnd;
    };

no te preocupes por lo que estoy heredando. He estado usando este asignador junto con un grupo de memoria. pero básicamente, en lugar de obtener la memoria del operador nuevo, obtengo memoria de un grupo de memoria. el funcionamiento interno es el mismo esencialmente.

Aquí está la implementación:

LinearAllocator::LinearAllocator():ObjectBase::ObjectBase()
{
    m_pBlock = nullptr;
    m_pHeadFree = nullptr;
    m_pEnd=nullptr;
}

LinearAllocator::LinearAllocator(Pool* pool,size_t size):ObjectBase::ObjectBase(pool)
{
    if (pool!=nullptr) {
        m_pBlock = ObjectBase::AllocFromPool(size);
        m_pHeadFree = * m_pBlock;
        m_pEnd = (void*)((unsigned char*)*m_pBlock+size);
    }
    else{
        m_pBlock = nullptr;
        m_pHeadFree = nullptr;
        m_pEnd=nullptr;
    }
}
LinearAllocator::~LinearAllocator()
{
    if (m_pBlock!=nullptr) {
        ObjectBase::FreeFromPool(m_pBlock);
    }
    m_pBlock = nullptr;
    m_pHeadFree = nullptr;
    m_pEnd=nullptr;
}
MemoryBlock* LinearAllocator::Alloc(size_t size)
{
    if (m_pBlock!=nullptr) {
        void* test = (void*)((unsigned char*)m_pEnd-size);
        if (m_pHeadFree<=test) {
            void* temp = m_pHeadFree;
            m_pHeadFree=(void*)((unsigned char*)m_pHeadFree+size);
            return temp;
        }else{
            return nullptr;
        }
    }else return nullptr;
}
void LinearAllocator::Flush()
{
    if (m_pBlock!=nullptr) {
        m_pHeadFree=m_pBlock;
        size_t size = (unsigned char*)m_pEnd-(unsigned char*)*m_pBlock;
        memset(*m_pBlock,0,size);
    }
}

Este código es completamente funcional a excepción de algunas líneas que necesitarán ser cambiadas debido a mi herencia y uso del conjunto de memoria. pero apuesto a que puedes descubrir lo que debe cambiar y solo avísame si necesitas una mano para cambiar el código. Este código no ha sido probado en ningún tipo de mansión profesional y no se garantiza que sea seguro para subprocesos o algo así. Simplemente lo elevé y pensé que podría compartirlo contigo ya que parecías necesitar ayuda.

También tengo una implementación en funcionamiento de un grupo de memoria totalmente genérico si cree que puede ser útil. Puedo explicarte cómo funciona si lo necesitas.

Una vez más, si necesita ayuda, avíseme. Buena suerte.

Answer 5

Sigo pensando que esta es una pregunta interesante sin una respuesta definitiva, pero permítanme desglosarla en las diferentes preguntas que en realidad están haciendo:

1.) La inserción de un puntero a una clase base en un vector antes de la inicialización de una subclase previene o causa problemas con la recuperación de clases heredadas de ese puntero. [rebanando, por ejemplo.]

Respuesta: No, siempre y cuando esté 100% seguro del tipo relevante que se está señalando, este mecanismo no causa estos problemas, sin embargo, tenga en cuenta los siguientes puntos:

Si el constructor derivado falla, te queda un problema más adelante cuando es probable que tengas un puntero colgando al menos sentado en el vector, ya que el espacio de direcciones que [la clase derivada] pensó que estaba obteniendo se liberaría al entorno operativo. en caso de error, pero el vector todavía tiene la dirección como del tipo de clase base.

Tenga en cuenta que un vector, aunque útil, no es la mejor estructura para esto, e incluso si lo fuera, debería haber alguna inversión de control involucrada aquí para permitir que el vector objeto controle la inicialización de sus objetos, para que tenga conciencia de éxito / fracaso

Estos puntos llevan a la segunda pregunta implícita:

2.) ¿Es este un buen patrón para agrupar?

Respuesta: No realmente, por las razones mencionadas anteriormente, más otras (Empujar un vector pasado su punto final básicamente termina con un malloc que es innecesario y afectará el rendimiento.) Lo ideal sería utilizar una biblioteca de agrupación, o una clase de plantilla, y aún mejor, separe la implementación de la política de asignación / desasociación de la implementación de la agrupación, con una solución de bajo nivel ya insinuada, que es asignar la memoria de la agrupación adecuada desde la inicialización de la agrupación, y luego usar esta usando punteros para anular desde dentro el espacio de direcciones del grupo (Vea la solución anterior de Alex Zywicki). Usando este patrón, la destrucción del grupo es segura ya que el grupo que será memoria contigua puede destruirse en masa sin ningún problema pendiente, o la memoria pierde al perder todas las referencias a un objeto ( perder toda la referencia a un objeto cuya dirección es asignada a través del grupo por el administrador de almacenamiento lo deja con trozos sucios, pero no causará una pérdida de memoria ya que es administrado por el grupo impl ementación.

En los primeros días de C / C ++ (antes de la proliferación masiva de la STL), este fue un patrón bien discutido y muchas implementaciones y diseños se pueden encontrar en buena literatura: como un ejemplo:

Knuth (1973 El arte de la programación informática: múltiples volúmenes), y para obtener una lista más completa, con más información sobre agrupación, consulte:

http://www.ibm.com/developerworks/library/l-memory/

La tercera pregunta implícita parece ser:

3) ¿Es este un escenario válido para usar el agrupamiento?

Respuesta: Esta es una decisión de diseño localizado basada en aquello con lo que se siente cómodo, pero para ser honesto, su implementación (sin estructura de control / agregado, posiblemente compartición cíclica de subconjuntos de objetos) me sugiere que estaría mejor con una lista básica vinculada de objetos contenedoras, cada uno de los cuales contiene un puntero a su superclase, que se usa solo para propósitos de direccionamiento. Sus estructuras cíclicas se basan en esto, y usted simplemente modifica / reduce la lista según sea necesario para acomodar todos sus objetos de primera clase según sea necesario, y cuando termine, puede destruirlos fácilmente en una operación O (1) desde dentro de la lista enlazada.

Habiendo dicho eso, yo personalmente recomendaría que en este momento (cuando tienes un escenario donde la agrupación tiene un uso y por lo tanto estás en la mentalidad correcta) para llevar a cabo la construcción de un conjunto de clases de gestión de almacenamiento / agrupación que están paramaterizados / sin tipo ahora, ya que te mantendrán en una buena posición para el futuro.