固定サイズのメモリアロケータ

version_1.cc

#include <stdlib.h>
#include <cstddef>

class NextOnFreeList {
public:
    NextOnFreeList *next;
};

class Rational {
public:
    Rational(int n = 0, int d = 1) : n_(n), d_(d) {};

    void *operator new(size_t size);
    void operator delete(void *doomed, size_t size);

    static void NewMemPool() { ExpandTheFreeList(); }
    static void DeleteMemPool();

    // int n() { return n_; }
    // int d() { return d_; }

private:
    static NextOnFreeList *__free_list;

    static void ExpandTheFreeList();
    enum { EXPANSION_SIZE = 32 };

    int n_;                     // 分子
    int d_;                     // 分母
};

NextOnFreeList *Rational::__free_list = NULL;

void *Rational::operator new(size_t size) {
    if (__free_list == NULL) {
        ExpandTheFreeList();
    }

    NextOnFreeList *head = __free_list;
    __free_list = head->next;

    return head;
}

void Rational::operator delete(void *doomed, size_t size) {
    NextOnFreeList *head = static_cast<NextOnFreeList *>(doomed);
    head->next = __free_list;
    __free_list = head;
}

void Rational::ExpandTheFreeList() {
    size_t size = (sizeof(Rational) > sizeof(NextOnFreeList *)) ?
        sizeof(Rational) :
        sizeof(NextOnFreeList *);

    NextOnFreeList *runner = static_cast<NextOnFreeList *>(malloc(size));
    __free_list = runner;
    for (int i = 0; i < EXPANSION_SIZE; ++i) {
        runner->next = static_cast<NextOnFreeList *>(malloc(size));
        runner = runner->next;
    }
    runner->next = NULL;
}

void Rational::DeleteMemPool() {
    NextOnFreeList *next_ptr;
    for (next_ptr = __free_list; next_ptr != NULL; next_ptr = __free_list) {
        __free_list = __free_list->next;
        delete[] next_ptr;
    }
}

int main(int argc, char **argv) {
    Rational *array[1000];

    for (int j = 0; j < 500; ++j) {
        for (int i = 0; i < 1000; ++i) {
            array[i] = new Rational(i);
        }
        for (int i = 0; i < 1000; ++i) {
            delete array[i];
        }
    }

    return 0;
}

// 組込みの new/delete
// ./version_0  0.08s user 0.00s system 96% cpu 0.088 total 

// これ
// ./version_1  0.01s user 0.00s system 85% cpu 0.018 total