Как записать ориентированное на многопотоковое исполнение и эффективное, свободное от блокировок средство выделения памяти в C?

Зависит от того, что вы подразумеваете под эффективностью. Если бы моя забота заключалась в том, чтобы сделать все быстро, то я бы, вероятно, дал каждому потоку свой собственный отдельный пул памяти для работы, и пользовательский "malloc", который забирает память из этого пула. Конечно, если бы моя забота была скорость, я бы, вероятно, избежать распределения в первую очередь.

Нет ни одного ответа, вы будете балансировать ряд проблем. Это будет практически невозможно получить lock-free аллокатор, но вы можете либо сделать блокировку рано и нечасто (путем выделения больших пулов для каждого потока), или вы можете сделать блокировки настолько малы и плотно, что они должны быть правильными.

Вы можете использовать lock free list и пару ведер разного размера.

So :

typedef struct
{
    union{
        SLIST_ENTRY entry;
    void* list;
};
byte mem[];
} mem_block;

typedef struct
{
    SLIST_HEADER root;
} mem_block_list;

#define BUCKET_COUNT 4
#define BLOCKS_TO_ALLOCATE 16

static mem_block_list Buckets[BUCKET_COUNT];

void init_buckets()
{
    for( int i = 0; i < BUCKET_COUNT; ++i )
    {
        InitializeSListHead( &Buckets[i].root );
        for( int j = 0; j < BLOCKS_TO_ALLOCATE; ++j )
        {
            mem_block* p = (mem_block*) malloc( sizeof( mem_block ) + (0x1 << BUCKET_COUNT) * 0x8 );
            InterlockedPushEntrySList( &Buckets[i].root, &p->entry );
        }
    }
}

void* balloc( size_t size )
{
    for( int i = 0; i < BUCKET_COUNT; ++i )
    {
        if( size <= (0x1 << i) * 0x8 )
        {
            mem_block* p = (mem_block*) InterlockedPopEntrySList( &Buckets[i].root );
            p->list = &Buckets[i];
        }
    }

    return 0;   // block to large
}

void  bfree( void* p )
{
    mem_block* block = (mem_block*) (((byte*)p) - sizeof( block->entry ));
    InterlockedPushEntrySList( ((mem_block_list*)block)->root, &block->entry );
}

SLIST_ENTRY, InterlockedPushEntrySList, InterlockedPopEntrySList, InitializeSListHead - это функции для безблокировочных операций с односвязным списком под Win32. Используйте соответствующие операции на других операционных системах.

Недостатки :

• Overhead of sizeof( SLIST_ENTRY )
• Ведра могут эффективно расти только один раз в начале, после чего вы можете исчерпать память и попросить операционную систему/другие ведра. (Другие ведра приводят к фрагментации)
• Этот образец слишком прост и должен быть расширен для обработки большего количества случаев