我正在执行C代码，并且我有数百万个malloc的每个都要求20-30字节的内存。
结果，GNU C Malloc和Jemalloc的开销都达到40-50％。DL Malloc效果更好，但开销仍然约为30％。
有没有办法做malloc而不进行任何对齐/填充？我知道这会比较慢，并且可能在某些CPU的C上需要从不同的单词“重建”数据，但是我准备以速度来换取内存使用量。
我也可以使用内存池代替malloc，只要它可以在free（）之后重用内存。
malloc()等。C标准要求它们为任何数据类型提供足够对齐的指针，因此，为了减少分配开销，您需要实现自己的分配器（或使用一些现有的分配器）。
一种可能性是为每个可能的分配大小分配一个池链。在每个池中，您可以使用位图来跟踪分配了哪些项目以及释放了哪些项目。每个项目的开销仅超过一位，但是您最终可能会拥有很多池链。这往往会使free()速度变慢，因为它必须搜索正确的池。
我认为，更好的可能性是为小额分配创建池链。在每个池中，小块形成一个链表，并且仅unsigned char跟踪其长度和分配状态。这会产生未对齐的指针，但是开销仅超过一个字符。
例如：
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <stdio.h>
#define SMALL_POOL_SIZE 131072
#define SMALL_LIMIT ((UCHAR_MAX + 1U) / 2U)
struct small_pool {
struct small_pool *next;
unsigned int size;
unsigned int used;
unsigned char data[];
};
static struct small_pool *list = NULL;
在该data[]成员内，对于该大小的空闲块，第一个字符为1到SMALL_LIMIT-1，对于1个字符或更大的已用块，第一个字符为SMALL_LIMIT + 1或更大。零和SMALL_LIMIT表示错误。可以将空间激进的分配器实现为例如
void *small_alloc(const size_t size)
{
struct small_pool *pool;
if (size < 1 || size >= SMALL_LIMIT) {
errno = EINVAL;
return NULL;
}
pool = list;
while (pool != NULL) {
/* Unused space in the pool? */
if (pool->used + size < pool->size) {
unsigned char *const ptr = pool->data + pool->used;
/* Grab it. */
pool->used += size + 1U;
/* Create new slot. */
(*ptr) = size + SMALL_LIMIT;
/* Done. */
return ptr + 1U;
}
/* Check the free slots in the pool. */
{
unsigned char *const end = pool->data + pool->used;
unsigned char *ptr = pool->data;
unsigned char big_len = SMALL_LIMIT;
unsigned char *big_ptr = NULL;
while (ptr < end)
if (*ptr == 0U || *ptr == SMALL_LIMIT) {
/* Invalid pointer */
errno = EDOM;
return NULL;
} else
if (*ptr > SMALL_LIMIT) {
/* Used slot, skip */
ptr += (*ptr) - SMALL_LIMIT + 1U;
continue;
} else {
if (*ptr < size) {
/* Slot is too small, skip it */
ptr += (*ptr) + 1U;
continue;
} else
if (*ptr == size) {
/* Perfect slot; grab it. */
(*ptr) = size + SMALL_LIMIT;
return ptr + 1U;
} else
/* Remember smallest of the large enough slots */
if (*ptr < big_len) {
big_len = *ptr;
big_ptr = ptr;
}
ptr += (*ptr) + 1U;
}
if (big_ptr != NULL) {
(*big_ptr) = big_len + SMALL_LIMIT;
return big_ptr + 1;
}
}
/* Check the next pool. */
pool = pool->next;
}
/* Need a new pool. */
pool = malloc(SMALL_POOL_SIZE);
if (pool == NULL) {
errno = ENOMEM;
return NULL;
}
/* Initialize pool; use the initial slot for the new allocation. */
pool->used = size + 1;
pool->size = SMALL_POOL_SIZE - sizeof (struct small_pool);
pool->data[0] = size + SMALL_LIMIT;
/* Prepend this pool to the pool chain. */
pool->next = list;
list = pool;
/* Return the slot we used. */
return pool->data + 1;
}
它有一个简单的策略：如果池中有未使用的尾随空间，请使用它。否则，请在池中扫描以找到未使用的插槽。如果插槽大小合适，请使用它。否则，请使用最小的，足够大的未使用插槽。
有许多改进的可能。例如，您可以将完整池保存在单独的列表中，以避免对它们进行扫描。将发现有空闲插槽的池移到池列表的开头可能也是一个好主意。
解除分配更为复杂。如果我们在分配中分配的数量相对较少，并且不必担心释放整个池，那么分配可以很简单
int small_free(void *const item)
{
if (item == NULL)
return 0;
else {
struct small_pool *pool = list;
while (pool != NULL && !((unsigned char *)item > pool->data && (unsigned char *)item < pool->data + pool->used))
pool = pool->next;
if (pool != NULL) {
unsigned char *const ptr = (unsigned char *)item - 1;
if (*ptr > SMALL_LIMIT)
(*ptr) -= SMALL_LIMIT;
return 0;
}
return ENOENT;
}
}
假设您需要该函数返回ENOENT，以防分配实际上不是很小的分配。如果重要的是要验证要释放的指针是否有效（例如进行调试），则
int small_free(void *const item)
{
if (item == NULL)
return 0;
else {
struct small_pool *pool = list;
while (pool != NULL && !((unsigned char *)item > pool->data && (unsigned char *)item < pool->data + pool->used))
pool = pool->next;
if (pool != NULL) {
unsigned char *const end = pool->data + pool->used;
unsigned char *ptr = pool->data;
while (ptr < end)
if (*ptr == 0U || *ptr == SMALL_LIMIT)
return EDOM;
else
if (*ptr < SMALL_LIMIT) {
size_t len = (*ptr) + 1U;
/* Coalesce consecutive slots, if possible. */
while (len + ptr[len] < SMALL_LIMIT) {
(*ptr) = len + ptr[len];
len = (*ptr) + 1U;
}
ptr += len;
} else {
const size_t len = (*ptr) + 1U - SMALL_LIMIT;
/* Within the current slot.. probably should just
* compare item to ptr+1 instead. */
if ((unsigned char *)item > ptr && (unsigned char *)item < ptr + len) {
*ptr = len - 1U;
return 0;
}
ptr += len;
}
}
return ENOENT;
}
}
即使->used释放池中的最后一个块时，后一个版本也不会修剪，也不会释放完全未使用的池。换句话说，上述解除分配只是一个粗略的例子。
在速度方面，以上内容似乎至少比我的机器上的GLIBC malloc()/慢一个数量级free()。这是检查线性分配的简单测试-半随机解除分配模式：
/* Make sure this is prime wrt. 727 */
#define POINTERS 1000000
int main(void)
{
void **array;
size_t i;
fprintf(stderr, "Allocating an array of %lu pointers: ", (unsigned long)POINTERS);
fflush(stderr);
array = malloc((size_t)POINTERS * sizeof array[0]);
if (array == NULL) {
fprintf(stderr, "Failed.\n");
return EXIT_FAILURE;
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Allocating pointers in varying sizes.. ");
fflush(stderr);
for (i = 0; i < POINTERS; i++) {
const size_t n = 1 + ((i * 727) % (SMALL_LIMIT - 1));
if (!(array[i] = small_alloc(n))) {
if (errno == EDOM)
fprintf(stderr, "Failed at %lu; corrupted list.\n", (unsigned long)i + 1UL);
else
fprintf(stderr, "Failed at %lu: %s.\n", (unsigned long)i + 1UL, strerror(errno));
return EXIT_FAILURE;
}
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Deallocating pointers in a mixed order.. ");
fflush(stderr);
for (i = 0; i < POINTERS; i++) {
const size_t p = (i * 727) % POINTERS;
if (small_free(array[p])) {
if (errno == EDOM)
fprintf(stderr, "Failed at %lu: corrupted list.\n", (unsigned long)i + 1UL);
else
fprintf(stderr, "Failed at %lu: %s.\n", (unsigned long)i + 1UL, strerror(errno));
return EXIT_FAILURE;
}
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Deallocating the pointer array.. ");
fflush(stderr);
free(array);
fprintf(stderr, "Done.\n\n");
fflush(stderr);
return EXIT_SUCCESS;
}
我认为，基于池的分配器的真正优势在于您可以一次释放整个池。考虑到这一点，也许您的工作量可以在构建结构时使用专门的分配器，而压缩阶段（能够调整指针）至少在结束时运行，并且在构建期间也可能进行，如果已完成足够数量的删除操作。通过这种方法，您可以将临时需要的内存释放回操作系统。（不进行压缩，大多数池可能至少剩余一个分配，因此无法释放它。）
我认为这根本不是一个好的答案，但是更好的答案将需要更多细节，尤其是有关存储的数据结构以及实践中发生的分配/取消分配模式的信息。在没有这些的情况下，我希望这至少给出了一些有关如何进行的想法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句