Менеджер безотраслевой памяти?

Question

Кто-нибудь задумывался о том, как написать менеджер памяти (на C ++), который полностью свободен от веток? Я написал пул, стек, очередь и связанный список (выделение из пула), но мне интересно, насколько правдоподобно писать свободный диспетчер общей ветки памяти.

Это все для того, чтобы помочь создать действительно многократно используемую платформу для непрерывной, бесперебойной разработки процессора и дружественной кэш-памяти разработки.

Редактировать: я имею в виду без ответвлений без прямых или косвенных вызовов функций и без использования ifs. Я думал, что, возможно, смогу реализовать что-то, что сначала изменит запрошенный размер на ноль для ложных вызовов, но на самом деле не получил намного больше, чем это. Я чувствую, что это не невозможно, но другой аспект этого упражнения заключается в том, чтобы профилировать его на указанных «недружественных» процессорах, чтобы понять, стоит ли стараться изо всех сил, чтобы избежать ветвления.

Answer 1

Хотя я не думаю, что это хорошая идея, одним из решений было бы иметь заранее выделенные сегменты разных размеров журнала ₂ , глупый псевдокод:

class Allocator {

    void* malloc(size_t size) {
        int bucket = log2(size + sizeof(int));
        int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back());
        m_buckets[bucket].pop_back();
        *pointer = bucket; //Store which bucket this was allocated from
        return pointer + 1; //Dont overwrite header
    }

    void free(void* pointer) {
        int* temp = reinterpret_cast<int*>(pointer) - 1;
        m_buckets[*temp].push_back(temp);
    }

    vector< vector<void*> > m_buckets;
};

(Вы, конечно, также замените std::vector на простой массив + счетчик).

РЕДАКТИРОВАТЬ: Для того чтобы сделать это устойчивым (то есть справиться с ситуацией, когда корзина пуста), вам придется добавить некоторую форму ветвления.

РЕДАКТИРОВАТЬ 2: Вот небольшая безветвленная log2 функция:

//returns the smallest x such that value <= (1 << x)
int
log2(int value) {
    union Foo {
        int x;
        float y;
    } foo;
    foo.y = value - 1;
    return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number
}

Это дает правильный результат для распределений <33554432 байта. Если вам нужны большие ассигнования, вам придется переключиться на удвоения. </p>

Вот ссылка на представление чисел с плавающей запятой в памяти.

Answer 2

Единственный известный мне способ создания распределителя без ветвей - зарезервировать всю память, которую он потенциально может использовать заранее. В противном случае всегда будет где-нибудь скрытый код, чтобы увидеть, превышаем ли мы текущую емкость, находится ли он в скрытом push_back в векторе, проверяющем, превышает ли размер емкость, использованную для его реализации, или что-то в этом роде.

Вот один такой пример грубого фиксированного выделения, в котором используется метод без ветвей malloc и free.

class FixedAlloc
{
public:
    FixedAlloc(int element_size, int num_reserve)
    {
        element_size = max(element_size, sizeof(Chunk));
        mem = new char[num_reserve * element_size];

        char* ptr = mem;
        free_chunk = reinterpret_cast<Chunk*>(ptr);
        free_chunk->next = 0;

        Chunk* last_chunk = free_chunk;
        for (int j=1; j < num_reserve; ++j)
        {
            ptr += element_size;
            Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
            chunk->next = 0;
            last_chunk->next = chunk;
            last_chunk = chunk;
        }
    }

    ~FixedAlloc()
    {
        delete[] mem;
    }

    void* malloc()
    {
        assert(free_chunk && free_chunk->next && "Reserve memory exhausted!");
        Chunk* chunk = free_chunk;
        free_chunk = free_chunk->next;
        return chunk->mem;
    }

    void free(void* mem)
    {
        Chunk* chunk = static_cast<Chunk*>(mem);
        chunk->next = free_chunk;
        free_chunk = chunk;
    }

private:
    union Chunk
    {
        Chunk* next;
        char mem[1];
    };
    char* mem;
    Chunk* free_chunk;
};

Поскольку он полностью без ветвей, он просто вызывает ошибки, если вы пытаетесь выделить больше памяти, чем изначально зарезервировано. Он также имеет неопределенное поведение при попытке освободить нулевой указатель. Я также избегал иметь дело с выравниванием ради более простого примера.