Implementación de un Pool de Memoria de Alta Concurrencia en C++

Introducción del Proyecto

Este proyecto se enfoca en construir un pool de memoria de alta concurrencia inspirado en tcmalloc (Thread-Caching Malloc) de Google. La implementación simplificada busca capturar la esencia de tcmalloc, que es conocido por su eficiencia en entornos multihilo. Los conocimientos previos requeridos incluyen programación en C++, estructuras de datos como listas enlazadas y tablas hash, gestión de memoria del sistema operativo, patrones de diseño como el singleton, y manejo de concurrencia con mutexes.

Fundamentos de los Pools de Memoria

La técnica de pooling implica solicitar recursos al sistema por adelantado y administrarlos internamente. Esto reduce la sobrecarga de asignaciones frecuentes. Los pools de memoria asignan bloques grandes de una vez y los distribuyen a medida que se necesitan, liberándolos al sistema solo al final. Esto aborda problemas de eficiencia y fragmentación de memoria, tanto externa como interna. La función estándar malloc actúa como un pool de memoria general, pero su rendimiento puede no ser óptimo en entornos de alta concurrencia.

Diseño Preliminar: Pool de Memoria de Tamaño Fijo

Para familiarizarse con los conceptos, comencemos con un pool simple que gestiona objetos de un tamaño específico. Este pool utiliza una lista enlazada libre para reutilizar objetos y asigna memoria del sistema en bloques de páginas.

#include <iostream>
#include <vector>
#include <ctime>

// Función para asignar memoria directamente del sistema en unidades de página
inline static void* SistemaAsignar(size_t paginasK) {
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, paginasK * (1 << 12), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // En Linux, usar mmap o brk
    void* ptr = nullptr; // Implementar aquí
#endif
    if (!ptr) throw std::bad_alloc();
    return ptr;
}

template<class T>
class PoolObjetos {
public:
    T* Nuevo() {
        T* obj = nullptr;
        if (listaLibre) {
            obj = static_cast<T*>(listaLibre);
            listaLibre = *static_cast<void**>(listaLibre);
        } else {
            if (bytesRestantes < sizeof(T)) {
                bytesRestantes = 128 * 1024;
                memoria = static_cast<char*>(SistemaAsignar(bytesRestantes));
                if (!memoria) throw std::bad_alloc();
            }
            obj = reinterpret_cast<T*>(memoria);
            size_t tamObj = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
            memoria += tamObj;
            bytesRestantes -= tamObj;
        }
        new(obj) T; // Inicialización con new de ubicación
        return obj;
    }

    void Eliminar(T* obj) {
        obj->~T(); // Destructor explícito
        *static_cast<void**>(obj) = listaLibre;
        listaLibre = obj;
    }

private:
    char* memoria = nullptr;
    int bytesRestantes = 0;
    void* listaLibre = nullptr;
};

struct NodoArbol {
    int valor;
    NodoArbol* izquierdo;
    NodoArbol* derecho;
    NodoArbol() : valor(0), izquierdo(nullptr), derecho(nullptr) {}
};

void PruebaPoolObjetos() {
    const size_t vueltas = 3;
    const size_t n = 100000;
    size_t inicio1 = clock();
    std::vector<NodoArbol*> v1;
    v1.reserve(n);
    for (size_t j = 0; j < vueltas; ++j) {
        for (size_t i = 0; i < n; ++i) v1.push_back(new NodoArbol);
        for (size_t i = 0; i < n; ++i) delete v1[i];
        v1.clear();
    }
    size_t fin1 = clock();

    PoolObjetos<NodoArbol> poolArbol;
    size_t inicio2 = clock();
    std::vector<NodoArbol*> v2;
    v2.reserve(n);
    for (size_t j = 0; j < vueltas; ++j) {
        for (size_t i = 0; i < n; ++i) v2.push_back(poolArbol.Nuevo());
        for (size_t i = 0; i < n; ++i) poolArbol.Eliminar(v2[i]);
        v2.clear();
    }
    size_t fin2 = clock();

    std::cout << "Tiempo de new: " << fin1 - inicio1 << std::endl;
    std::cout << "Tiempo del pool de objetos: " << fin2 - inicio2 << std::endl;
}

Arquitectura Genarel del Pool de Memoria de Alta Concurrencia

El pool se divide en tres componentes clave para mniimizar la contención de locks y gestionar la memoria eficientemente:

Cache de Hilo (Thread Cache): Cada hilo tiene su propio cache para asignaciones pequeñas (<=256KB). Las operaciones aquí no requieren locks, ya que el cache es privado.
Cache Central (Central Cache): Compartido entre todos los hilos, gestiona bloques de memoria más grandes. Utiliza un lock por cubeta para reducir la competencia. Los hilos solicitan objetos de este cache cuando su cache local está vacío.
Cache de Páginas (Page Cache): Opera a nivel de páginas del sistema, asigna y fusiona bloques grandes. Ayuda a reducir la fragmentación al combinar páginas libres adyacentes.

Cache de Hilo

El cache de hilo es una estructura de cubetas hash donde cada cubeta contiene una lista enlazada libre de objetos de un tamaño alineado. La asignación y liberación son sin locks.

Asignación de Memoria

Para una solicitud de tamaño tam:

Calcular el índice de cubeta correspondiente.
Si la lista enlazada tiene objetos, extraer uno.
De lo contrario, obtener un lote de objetos del cache central (algoritmo de inicio lento similar a TCP).

Liberación de Memoria

Devolver el objeto a la lista enlazada del cache de hilo. Si la lista excede un umbral, devolver objetos al cache central.

Código del Cache de Hilo

// Gestión de alineación y mapeo
class ClaseTamano {
public:
    static size_t RedondearArriba(size_t bytes) {
        if (bytes <= 128) return Alineacion(bytes, 8);
        else if (bytes <= 1024) return Alineacion(bytes, 16);
        else if (bytes <= 8*1024) return Alineacion(bytes, 128);
        else if (bytes <= 64*1024) return Alineacion(bytes, 1024);
        else if (bytes <= 256*1024) return Alineacion(bytes, 8*1024);
        else return Alineacion(bytes, 1 << 13); // Página de 8KB
    }

    static size_t Indice(size_t bytes) {
        // Mapear bytes a índice de cubeta (208 cubetas en total)
        // Implementación detallada omitida por brevedad
        return 0;
    }

    static size_t NumeroMover(size_t tam) {
        size_t num = (256 * 1024) / tam;
        if (num < 2) num = 2;
        if (num > 512) num = 512;
        return num;
    }

private:
    static size_t Alineacion(size_t bytes, size_t alinear) {
        return (bytes + alinear - 1) & ~(alinear - 1);
    }
};

class ListaLibre {
public:
    void Insertar(void* obj) {
        SiguienteObj(obj) = cabeza;
        cabeza = obj;
        tamano++;
    }

    void* Extraer() {
        void* obj = cabeza;
        cabeza = SiguienteObj(obj);
        tamano--;
        return obj;
    }

    bool Vacia() const { return cabeza == nullptr; }
    size_t Tamano() const { return tamano; }

private:
    void*& SiguienteObj(void* obj) const {
        return *static_cast<void**>(obj);
    }
    void* cabeza = nullptr;
    size_t tamano = 0;
};

class CacheHilo {
public:
    void* Asignar(size_t tam) {
        size_t idx = ClaseTamano::Indice(tam);
        if (!listas[idx].Vacia()) return listas[idx].Extraer();
        return ObtenerDeCentral(idx, tam);
    }

    void Liberar(void* ptr, size_t tam) {
        size_t idx = ClaseTamano::Indice(tam);
        listas[idx].Insertar(ptr);
        if (listas[idx].Tamano() > ClaseTamano::NumeroMover(tam)) {
            DevolverACentral(listas[idx], tam);
        }
    }

private:
    void* ObtenerDeCentral(size_t idx, size_t tam);
    void DevolverACentral(ListaLibre& lista, size_t tam);
    ListaLibre listas[208];
};

static __declspec(thread) CacheHilo* cacheHiloLocal = nullptr;

Cache Central

El cache central utiliza cubetas hash con listas de spans (bloques de páginas contiguas). Cada span contiene objetos de un tamaño específico en su lista libre. Se usa un lock por cubeta para sincronización.

Asignación de Memoria

Cuando un cache de hilo solicita objetos, el cache central busca un span con objetos libres. Si no hay, solicita un nuevo span del cache de páginas y lo divide en objetos.

Liberación de Memoria

Los objetos devueltos decrementan un contador de uso del span. Cuando el contador llega a cero, el span se devuelve al cache de páginas.

Estructuras del Cache Central

struct Span {
    size_t idPagina = 0;   // Identificador de página inicial
    size_t numPaginas = 0; // Número de páginas
    Span* siguiente = nullptr;
    Span* anterior = nullptr;
    size_t tamObj = 0;     // Tamaño de los objetos cortados
    size_t usoConteo = 0;  // Conteo de objetos prestados
    void* listaLibre = nullptr;
    bool enUso = false;
};

class ListaSpan {
public:
    ListaSpan() {
        cabeza = new Span;
        cabeza->siguiente = cabeza;
        cabeza->anterior = cabeza;
    }

    void InsertarFrente(Span* span) {
        span->siguiente = cabeza->siguiente;
        span->anterior = cabeza;
        cabeza->siguiente->anterior = span;
        cabeza->siguiente = span;
    }

    Span* ExtraerFrente() {
        if (Vacia()) return nullptr;
        Span* frente = cabeza->siguiente;
        frente->anterior->siguiente = frente->siguiente;
        frente->siguiente->anterior = frente->anterior;
        return frente;
    }

    bool Vacia() const { return cabeza->siguiente == cabeza; }
    std::mutex mtx;

private:
    Span* cabeza;
};

class CacheCentral {
public:
    static CacheCentral* ObtenerInstancia() {
        static CacheCentral instancia;
        return &instancia;
    }

    Span* ObtenerSpan(ListaSpan& lista, size_t tamObj);
    size_t RangoObjetos(void*& inicio, void*& fin, size_t cantidad, size_t tam);
    void DevolverRango(void* inicio, size_t tamObj);

private:
    ListaSpan listasSpan[208];
    CacheCentral() = default;
};

Cache de Páginas

El cache de páginas gestiona memoria en bloques de páginas. Asigna grandes bloques del sistema y los divide en spans para el cache central. También fusiona spans libres adyacentes para reducir fragmentación.

Asignación de Memoria

Para un solicitud de k páginas:

Buscar un span libre de al menos k páginas.
Si no se encuentra, solicitar al sistema un bloque grande (por ejemplo, 128 páginas) y dividirlo.
Dividir spans grandes si es necesario.

Liberación de Memoria

Cuando un span se devuelve, intentar fusionar con spans vecinos libres.

Implementación del Cache de Páginas

inline static void* SistemaAsignarPaginas(size_t paginas) {
    // Implementación similar a SistemaAsignar anterior
    return nullptr;
}

inline static void SistemaLiberar(void* ptr) {
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // Implementar en Linux
#endif
}

class CachePaginas {
public:
    static CachePaginas* ObtenerInstancia() {
        static CachePaginas instancia;
        return &instancia;
    }

    Span* NuevoSpan(size_t paginasK);
    void LiberarSpan(Span* span);
    Span* MapearObjetoASpan(void* obj);

private:
    ListaSpan listas[129]; // 129 cubetas para 1 a 128 páginas
    std::mutex mtx;
    // Estructura para mapear ID de página a span (usar árbol radix)
    // Implementación simplificada usando unordered_map
    std::unordered_map<size_t, Span*> mapaIdSpan;
    CachePaginas() = default;
};

Comparación de Rendimiento

Se realizaron pruebas multihilo para comparar malloc/free con el pool de memoria de alta concurrencia. El pool mostró mejor rendimiento en escenarios de alta concurrencia debido a la reducción de contención de locks y la asignación local por hilo.

void ProbarMalloc(size_t nveces, size_t nhilos, size_t vueltas) {
    std::vector<std::thread> hilos(nhilos);
    std::atomic<size_t> costoMalloc = 0;
    std::atomic<size_t> costoFree = 0;

    for (size_t k = 0; k < nhilos; ++k) {
        hilos[k] = std::thread([&, k]() {
            std::vector<void*> v;
            v.reserve(nveces);
            for (size_t j = 0; j < vueltas; ++j) {
                size_t ini = clock();
                for (size_t i = 0; i < nveces; i++) v.push_back(malloc(16));
                size_t fin = clock();
                costoMalloc += fin - ini;

                ini = clock();
                for (size_t i = 0; i < nveces; i++) free(v[i]);
                fin = clock();
                costoFree += fin - ini;
                v.clear();
            }
        });
    }

    for (auto& h : hilos) h.join();
    std::cout << "Malloc: " << costoMalloc.load() << " ms\n";
    std::cout << "Free: " << costoFree.load() << " ms\n";
}

void ProbarPoolConcurrente(size_t nveces, size_t nhilos, size_t vueltas) {
    // Implementación similar usando ConcurrentAlloc/ConcurrentFree
}

Optimización con Árbol Radix

Para mejorar el mapeo de ID de página a span, se implementa un árbol radix de tres niveles, similar al usado en tcmalloc. Esto permite búsquedas rápidas sin locks en entornos concurrentes.

template<int BITS>
class MapaPaginas3 {
private:
    static const int BITS_INTERIOR = (BITS + 2) / 3;
    static const int LONGITUD_INTERIOR = 1 << BITS_INTERIOR;
    static const int BITS_HOJA = BITS - 2 * BITS_INTERIOR;
    static const int LONGITUD_HOJA = 1 << BITS_HOJA;

    struct Nodo {
        Nodo* punteros[LONGITUD_INTERIOR];
    };

    struct Hoja {
        void* valores[LONGITUD_HOJA];
    };

    Nodo* raiz;
    void* (*asignador)(size_t);

    Nodo* NuevoNodo() {
        Nodo* n = static_cast<Nodo*>(asignador(sizeof(Nodo)));
        if (n) memset(n, 0, sizeof(Nodo));
        return n;
    }

public:
    typedef uintptr_t Numero;

    explicit MapaPaginas3(void* (*asig)(size_t)) : asignador(asig) {
        raiz = NuevoNodo();
    }

    void* Obtener(Numero k) const {
        Numero i1 = k >> (BITS_HOJA + BITS_INTERIOR);
        Numero i2 = (k >> BITS_HOJA) & (LONGITUD_INTERIOR - 1);
        Numero i3 = k & (LONGITUD_HOJA - 1);
        if (i1 >= LONGITUD_INTERIOR || !raiz->punteros[i1] || !raiz->punteros[i1]->punteros[i2]) return nullptr;
        return static_cast<Hoja*>(raiz->punteros[i1]->punteros[i2])->valores[i3];
    }

    void Establecer(Numero k, void* v) {
        Numero i1 = k >> (BITS_HOJA + BITS_INTERIOR);
        Numero i2 = (k >> BITS_HOJA) & (LONGITUD_INTERIOR - 1);
        Numero i3 = k & (LONGITUD_HOJA - 1);
        if (!raiz->punteros[i1]) raiz->punteros[i1] = NuevoNodo();
        if (!raiz->punteros[i1]->punteros[i2]) {
            Hoja* hoja = static_cast<Hoja*>(asignador(sizeof(Hoja)));
            if (hoja) memset(hoja, 0, sizeof(Hoja));
            raiz->punteros[i1]->punteros[i2] = reinterpret_cast<Nodo*>(hoja);
        }
        static_cast<Hoja*>(raiz->punteros[i1]->punteros[i2])->valores[i3] = v;
    }
};

Consideraciones Adicionales

Este pool de memoria puede reemplazar a malloc en sistemas operativos mediante alias débiles o hooks. Las extensiones incluyen mejoras en la gestión de memoria y soporte para diferentes plataformas.

Etiquetas: C++ Gestión de memoria concurrencia cache de hilos cache central

Publicado el 7-20 10:19

Friki Work

Implementación de un Pool de Memoria de Alta Concurrencia en C++

Introducción del Proyecto

Fundamentos de los Pools de Memoria

Diseño Preliminar: Pool de Memoria de Tamaño Fijo

Arquitectura Genarel del Pool de Memoria de Alta Concurrencia

Cache de Hilo

Asignación de Memoria

Liberación de Memoria

Código del Cache de Hilo

Cache Central

Asignación de Memoria

Liberación de Memoria

Estructuras del Cache Central

Cache de Páginas

Asignación de Memoria

Liberación de Memoria

Implementación del Cache de Páginas

Comparación de Rendimiento

Optimización con Árbol Radix

Consideraciones Adicionales

Etiquetas populares