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

Question

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

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

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

Answer 1

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

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 байта. Если вам нужны большие ассигнования, вам придется переключиться на удвоение.

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

Answer 2

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

Вот один такой грубый пример фиксированного alloc, который имеет полностью безветвленный 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;
};

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