内存分配从本质上来说是一种空间管理算法，给你一块连续的空间，提供存储服务，那么你的空间管理跟分配要采用什么样的算法才会比较高效？
Bump-the-Pointer
Bump-the-Pointer是最简单的算法。HotSpot的MM白皮书是这么描述btp的，
That is, the end of the previously allocated object is always kept track of. When a new allocation request needs to be satisfied, all that needs to be done is to check whether the object will fit in the remaining part of the generation and, if so, to update the pointer and initialize the object.
我们只需要一个指针来记录可用空间的起始地址，收到分配请求，先检查可用空间是否足够分配给这次请求，如果足够，则分配空间，并且更新指针；如果不够就需要进行垃圾回收了。我们再来看看HotSpot的SerialCollector是怎么使用btp的。
SerialCollector使用Mark-Sweep-Compact算法来对OldGen进行GC，对于OldGen的分配，简单的bump the pointer，如果这时候剩余的可用空间已经不够，SerialCollector需要Stop-the-World，然后执行Mark-Sweep-Compact，即标记活着的对象，清除死去的对象，最后做sliding compaction，将活着的对象全部压缩到一边，这样剩余的可用空间就可以继续简单的使用btp算法来分配空间了。
btp还有几个点说下，
Slab Allocator
现在让我们来看另外一种采用分治策略的管理方法。我们可以将连续空间划分成一个个的组，每个组内又包含若干个坑位，同组内每个坑位的空间大小都是一样的，至于坑位的大小是可以根据使用情况来进行调优的。
只需要再维护每个组的metadata，这样每次一有分配请求，先查看metadata就能做到Best Fit。
Slab Allocator便是以上述方式工作的。与Bumb-the-Pointer相比，Slab不需要Stop-the-World来做GC，但是会造成一定的空间浪费，因为我们只能做到Best Fit。
Memcached Slab
Talk is cheap，下面来看看Memcached中的Slab实现。先看SlabClass的定义和初始化的方法，
typedef struct {perslab; sl_curr; slabs;list_size; killing; /* index+1 of dying slab, or zero if none */size_t requested; /* The number of requested bytes */} slabclass_t;prealloc) {int i = POWER_SMALLEST – 1;unsigned int size = sizeof(item) + settings.chunk_size;mem_limit = limit;if (prealloc) {/* Allocate everything in a big chunk with malloc */mem_base = malloc(mem_limit);if (mem_base != NULL) {mem_current = mem_base;mem_avail = mem_limit;} else {fprintf(stderr, “Warning: Failed to allocate requested memory in”” one large chunk.\nWill allocate in smaller chunks\n”);}}memset(slabclass, 0, sizeof(slabclass));while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {/* Make sure items are always n-byte aligned */if (size % CHUNK_ALIGN_BYTES)size += CHUNK_ALIGN_BYTES – (size % CHUNK_ALIGN_BYTES);slabclass[i].size = size;slabclass[i].perslab = settings.item_size_max / slabclass[i].size;size *= factor;if (settings.verbose > 1) {fprintf(stderr, “slab class %3d: chunk size %9u perslab %7u\n”,i, slabclass[i].size, slabclass[i].perslab);}}power_largest = i;slabclass[power_largest].size = settings.item_size_max;slabclass[power_largest].perslab = 1;if (settings.verbose > 1) {fprintf(stderr, “slab class %3d: chunk size %9u perslab %7u\n”,i, slabclass[i].size, slabclass[i].perslab);}/* for the test suite: faking of how much we’ve already malloc’d */{char *t_initial_malloc = getenv(“T_MEMD_INITIAL_MALLOC”);if (t_initial_malloc) {mem_malloced = (size_t)atol(t_initial_malloc);}}if (prealloc) {slabs_preallocate(power_largest);}}
slabs_init方法中可以看到我们上面所说的坑位大小的调优，Memcached是通过配置一个factor来实现，坑位的大小是按factor倍增长的。
需要注意这里的size是sizeof(item) + settings.chunk_size，item是Memcached所存储的数据，在memcache.h中定义。存储系统的数据结构设计又是另一个可以深究的话题，后面再探讨。
typedef struct _stritem {struct _stritem *next;struct _stritem *prev;struct _stritem *h_next; /* hash chain next */rel_time_ttime;/* least recent access */rel_time_texptime; refcount;uint8_tnsuffix; /* length of flags-and-length string */uint8_tit_flags; /* ITEM_* above */uint8_tslabs_clsid;/* which slab class we’re in */uint8_tnkey;/* key length, w/terminating null and padding *//* this odd type prevents type-punning issues when we do* the little shuffle to save space when not using CAS. */union {uint64_t cas;char end;} data[];} item;你曾经说，你曾经说。走在爱的旅途，我们的脚步多么轻松……
