结果是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表示该大小的可用块,或者大于SMALL_LIMIT+1表示已用的一块或多块。0和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
,也不会完全释放未使用的池。换句话说,上述回收只是一个粗略的示例。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;
}
它不一定更慢。 如果块的大小是固定的(或有限范围内的大小),或者您实际上按逻辑顺序分配和取消分配(FIFO / FILO),则可以通过处理“池”来改善性能和内存管理。
有一个Boost库实现了这个功能,可能适合您的需求。
http://www.boost.org/doc/libs/1_57_0/libs/pool/doc/html/boost_pool/pool/interfaces.html
或者您可以自己动手 - 分配大块内存并自行切割。
请注意,这种方法可能不仅速度较慢,而且可能会失败。许多对齐的机器在被要求加载地址不对齐的数据时会出现问题。例如,实际上加载的是舍入的地址,其中包含正确值之前的随机数据。编译器绝对没有义务“重构”值,我认为它们不这样做比这样做更常见。
因此,为了可移植性,您可能需要使用 memcpy()
将不对齐的数据移动到对齐位置后再使用。这并不一定会有您想象中的所有开销,因为一些编译器会将 memcpy()
内联。
因此,池管理分配通常可以更快(潜在地快得多),但 memcpy()
可能会更慢(虽然可能不会慢太多)。
这是个权衡。
free(ptr, size)
)会有所帮助;这样你只需要扫描与大小兼容的池子,而不是所有池子。如果你一次性释放整个池子而不是单个元素,你可以使用原子内置函数使分配非常快且线程安全。 - Nominal Animal