Làm thế nào để triển khai một custom allocator trong C++?

Triển khai một custom allocator trong C++ đòi hỏi bạn phải hiểu về Allocator Requirements của STL (Standard Template Library). Một custom allocator cần tuân thủ quy ước của std::allocator, đảm bảo nó hoạt động tốt với các container STL như std::vector, std::map, v.v.

1. Các bước triển khai một custom allocator

Allocator trong C++ cần cung cấp các thành phần sau:

• allocate(size_t n): Cấp phát bộ nhớ cho n phần tử.
• deallocate(T* p, size_t n): Giải phóng bộ nhớ đã cấp phát.
• construct(T* p, Args&&... args): Gọi constructor của đối tượng trên bộ nhớ đã cấp phát.
• destroy(T* p): Gọi destructor của đối tượng.

Dưới đây là một ví dụ về custom allocator sử dụng malloc/free thay vì new/delete:

2. Ví dụ về Custom Allocator

#include <iostream>
#include <memory>
#include <vector>

template <typename T>
struct CustomAllocator {
    using value_type = T;

    CustomAllocator() = default;

    // Cấp phát bộ nhớ
    T* allocate(std::size_t n) {
        std::cout << "Allocating " << n << " elements\n";
        return static_cast<T*>(std::malloc(n * sizeof(T)));
    }

    // Giải phóng bộ nhớ
    void deallocate(T* p, std::size_t n) {
        std::cout << "Deallocating " << n << " elements\n";
        std::free(p);
    }

    // Hàm so sánh hai Allocator (cần thiết cho STL)
    bool operator==(const CustomAllocator&) const { return true; }
    bool operator!=(const CustomAllocator&) const { return false; }
};

int main() {
    std::vector<int, CustomAllocator<int>> vec;
    vec.reserve(5); // Allocating memory

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

    for (int v : vec) {
        std::cout << v << " ";
    }

    return 0;
}

3. Giải thích

• allocate(size_t n): Cấp phát bộ nhớ đủ chứa n phần tử kiểu T bằng malloc.
• deallocate(T* p, size_t n): Giải phóng bộ nhớ bằng free.
• operator== và operator!=: Cần thiết để các container STL có thể kiểm tra allocator có thể hoán đổi được không.

4. Khi nào nên dùng Custom Allocator?

• Khi bạn cần tối ưu hiệu suất cấp phát bộ nhớ, như pool allocator hoặc arena allocator.
• Khi bạn muốn giám sát bộ nhớ (ví dụ: logging số lần cấp phát / giải phóng).
• Khi cần sử dụng bộ nhớ đặc biệt (ví dụ: cấp phát từ shared memory, GPU memory, hoặc aligned memory).

Nếu bạn cần triển khai một allocator phức tạp hơn (ví dụ memory pool), có thể dùng các thư viện như Boost.Pool hoặc Google TCMalloc.

Tuyệt! Hãy thử triển khai một Memory Pool Allocator, giúp cấp phát bộ nhớ nhanh hơn bằng cách tránh gọi malloc/free nhiều lần. Thay vào đó, chúng ta cấp phát trước một vùng lớn rồi quản lý các khối bộ nhớ bên trong.

🏗 1. Ý tưởng về Memory Pool Allocator

• Thay vì cấp phát từng phần tử một, ta cấp phát trước một mảng lớn.
• Khi cần cấp phát, ta lấy phần tử từ mảng đó thay vì gọi malloc.
• Khi giải phóng, ta chỉ đánh dấu phần tử là "có thể dùng lại" thay vì gọi free.

📝 2. Code: Memory Pool Allocator

Dưới đây là một bộ nhớ đệm (pool) đơn giản với std::vector để giữ bộ nhớ.

#include <iostream>
#include <vector>
#include <list>

template <typename T, size_t PoolSize = 128>
class MemoryPoolAllocator {
private:
    std::vector<T> pool;        // Vùng nhớ lớn
    std::list<T*> freeList;     // Danh sách các ô nhớ chưa sử dụng

public:
    using value_type = T;

    MemoryPoolAllocator() {
        pool.resize(PoolSize);  // Cấp phát trước bộ nhớ
        for (size_t i = 0; i < PoolSize; ++i) {
            freeList.push_back(&pool[i]);
        }
    }

    // Cấp phát bộ nhớ từ pool
    T* allocate(size_t n) {
        if (n != 1 || freeList.empty()) {
            throw std::bad_alloc();
        }
        T* ptr = freeList.front();
        freeList.pop_front();
        return ptr;
    }

    // Giải phóng bộ nhớ và đưa lại vào danh sách trống
    void deallocate(T* p, size_t n) {
        if (n == 1) {
            freeList.push_back(p);
        }
    }

    bool operator==(const MemoryPoolAllocator&) const { return true; }
    bool operator!=(const MemoryPoolAllocator&) const { return false; }
};

// Sử dụng Memory Pool Allocator trong vector
int main() {
    std::vector<int, MemoryPoolAllocator<int, 10>> vec;

    for (int i = 0; i < 5; ++i) {
        vec.push_back(i * 10);
    }

    for (int v : vec) {
        std::cout << v << " ";
    }

    return 0;
}

🔥 3. Giải thích

✅ Hiệu suất cao hơn:

• Thay vì gọi malloc/free liên tục, ta tái sử dụng vùng nhớ đã cấp phát trước.
• Chỉ cần lấy ra từ freeList khi cần cấp phát.

✅ Dễ mở rộng:

• Có thể dễ dàng mở rộng số lượng khối nhớ.

Để làm cho Memory Pool Allocator an toàn trong môi trường đa luồng (thread-safe), ta cần:

1. Bảo vệ danh sách bộ nhớ rảnh (freeList) bằng std::mutex để tránh xung đột giữa các luồng.
2. Sử dụng std::lock_guard<std::mutex> để đảm bảo chỉ một luồng có thể truy cập danh sách bộ nhớ tại một thời điểm.

📝 1. Code: Thread-Safe Memory Pool Allocator

#include <iostream>
#include <vector>
#include <list>
#include <mutex>

template <typename T, size_t PoolSize = 128>
class ThreadSafeMemoryPoolAllocator {
private:
    std::vector<T> pool;         // Vùng nhớ lớn
    std::list<T*> freeList;      // Danh sách ô nhớ rảnh
    std::mutex mutex;            // Bảo vệ freeList

public:
    using value_type = T;

    ThreadSafeMemoryPoolAllocator() {
        pool.resize(PoolSize);  
        for (size_t i = 0; i < PoolSize; ++i) {
            freeList.push_back(&pool[i]);
        }
    }

    // Cấp phát bộ nhớ - Được bảo vệ bởi mutex
    T* allocate(size_t n) {
        if (n != 1) throw std::bad_alloc();
        
        std::lock_guard<std::mutex> lock(mutex);  // Đảm bảo thread-safe
        if (freeList.empty()) throw std::bad_alloc();

        T* ptr = freeList.front();
        freeList.pop_front();
        return ptr;
    }

    // Giải phóng bộ nhớ - Được bảo vệ bởi mutex
    void deallocate(T* p, size_t n) {
        if (n == 1) {
            std::lock_guard<std::mutex> lock(mutex);
            freeList.push_back(p);
        }
    }

    bool operator==(const ThreadSafeMemoryPoolAllocator&) const { return true; }
    bool operator!=(const ThreadSafeMemoryPoolAllocator&) const { return false; }
};

// Kiểm tra với nhiều luồng
#include <thread>

void threadTask(std::vector<int, ThreadSafeMemoryPoolAllocator<int, 100>>& vec, int start) {
    for (int i = 0; i < 5; ++i) {
        vec.push_back(start + i);
    }
}

int main() {
    std::vector<int, ThreadSafeMemoryPoolAllocator<int, 100>> vec;

    std::thread t1(threadTask, std::ref(vec), 0);
    std::thread t2(threadTask, std::ref(vec), 100);

    t1.join();
    t2.join();

    for (int v : vec) {
        std::cout << v << " ";
    }

    return 0;
}

🔥 2. Giải thích

✅ An toàn trong môi trường đa luồng nhờ std::mutex.
✅ Hiệu suất cao hơn so với malloc/free từng phần tử.
✅ Dễ sử dụng với container STL như std::vector.

🚀 Lock-Free Memory Pool với std::atomic

Để tăng hiệu suất hơn nữa, ta sẽ triển khai một Lock-Free Memory Pool dùng std::atomic thay vì std::mutex. Điều này giúp giảm chi phí lock/unlock khi nhiều luồng truy cập cùng lúc.

📌 1. Ý tưởng

Thay vì dùng std::mutex, ta dùng:
✅ Một danh sách liên kết đơn lock-free để quản lý bộ nhớ rảnh.
✅ std::atomic để thực hiện các thao tác an toàn giữa nhiều luồng.
✅ CAS (Compare-And-Swap) để đảm bảo chỉ một luồng có thể lấy hoặc trả lại một khối nhớ tại một thời điểm.

📝 2. Code: Lock-Free Memory Pool

Dưới đây là phiên bản lock-free sử dụng std::atomic và danh sách liên kết đơn:

#include <iostream>
#include <atomic>
#include <vector>
#include <thread>

template <typename T, size_t PoolSize = 128>
class LockFreeMemoryPoolAllocator {
private:
    struct Node {
        T data;
        Node* next;
    };

    alignas(64) std::vector<Node> pool;  // Dữ liệu được cấp phát trước
    std::atomic<Node*> freeList;         // Danh sách rảnh (dùng atomic để tránh race condition)

public:
    using value_type = T;

    LockFreeMemoryPoolAllocator() {
        pool.resize(PoolSize);
        for (size_t i = 0; i < PoolSize - 1; ++i) {
            pool[i].next = &pool[i + 1];  // Tạo danh sách liên kết các phần tử
        }
        pool[PoolSize - 1].next = nullptr;
        freeList.store(&pool[0]);  // Đưa toàn bộ pool vào danh sách rảnh
    }

    // 🚀 Cấp phát bộ nhớ bằng CAS (Compare-And-Swap)
    T* allocate(size_t n) {
        if (n != 1) throw std::bad_alloc();

        Node* oldHead = freeList.load(std::memory_order_acquire);
        while (oldHead && !freeList.compare_exchange_weak(oldHead, oldHead->next, 
                                                           std::memory_order_release, 
                                                           std::memory_order_relaxed)) {
            // Nếu compare_exchange_weak thất bại, oldHead được cập nhật -> thử lại
        }

        if (!oldHead) throw std::bad_alloc();
        return reinterpret_cast<T*>(oldHead);
    }

    // 🚀 Giải phóng bộ nhớ bằng CAS
    void deallocate(T* p, size_t n) {
        if (n != 1) return;
        
        Node* node = reinterpret_cast<Node*>(p);
        Node* oldHead = freeList.load(std::memory_order_acquire);
        
        do {
            node->next = oldHead;
        } while (!freeList.compare_exchange_weak(oldHead, node, 
                                                 std::memory_order_release, 
                                                 std::memory_order_relaxed));
    }

    bool operator==(const LockFreeMemoryPoolAllocator&) const { return true; }
    bool operator!=(const LockFreeMemoryPoolAllocator&) const { return false; }
};

// Kiểm tra với nhiều luồng
void threadTask(std::vector<int, LockFreeMemoryPoolAllocator<int, 100>>& vec, int start) {
    for (int i = 0; i < 5; ++i) {
        vec.push_back(start + i);
    }
}

int main() {
    std::vector<int, LockFreeMemoryPoolAllocator<int, 100>> vec;

    std::thread t1(threadTask, std::ref(vec), 0);
    std::thread t2(threadTask, std::ref(vec), 100);

    t1.join();
    t2.join();

    for (int v : vec) {
        std::cout << v << " ";
    }

    return 0;
}

🔥 3. Giải thích

✅ Không dùng std::mutex, thay vào đó dùng std::atomic<Node*> để quản lý danh sách rảnh.
✅ CAS (Compare-And-Swap) đảm bảo nhiều luồng có thể cấp phát / giải phóng bộ nhớ mà không cần khóa.
✅ Cực kỳ nhanh, phù hợp cho các ứng dụng đa luồng yêu cầu hiệu suất cao.