原文链接：http://blog.ddup.us/?p=241
—————————————————————————-
那天看到微博上看到讨论如何设计网络程序Buffer（链接）。其中@简悦风云 给出个使用Ring Buffer的思路同时也顺带着嘲讽了一下C++和STL（链接），结果引出混战。本文不关心事件，纯粹讨论其中的两个技术点——RingBuffer和Memory Poll。
两者都是内存管理中比较常用的技术。我们知道C语言中使用malloc/free库函数来申请/释放内存，C++中对应的是new/delete，终归也是调用malloc/free。有些程序会非常频繁的申请/释放内存，这就导致内存碎片的产生，进而引起性能下降甚至内存分配失败。像Memcached这种内存kv数据库为了解决这种问题都是在应用层自己又实现了一套内存管理模块。Redis早期版本直接使用malloc/free库函数，后来忍受不了其性能，在后续版本中使用freebsd中的内存管理算法jemalloc来代替。所以在高性能程序中，优良的内存管理算法至关重要。
Ring Buffer
Ring Buffer也叫Circular Buffer，是一种缓冲区数据结构，一般用于生产者-消费者模式的程序中，一个或多个生产者不停产生数据，同时一个或多个消费者使用数据，数据使用完这块缓冲区就可以释放了。简单的Ring Buffer其实就是基于连续内存地址的循环队列，稍有不同的是当队列满时，某些Ring Buffer应用场景可以直接覆盖掉队尾的数据。风云给出的socket连接例子（链接）就是这种情况。建立Ring Buffer首先就是先malloc出一大块连续内存空间，然后遵循先入先出FIFO原则申请释放内存，后续的内存操作都在这块实现开辟的内存区域完成，这也就省去了每来一条数据就申请一次内存的开销。可见不仅是从执行时间上还是从减少内存碎片角度看，这种方法都比原生的malloc要好。
但是这种方式的缺点也是显而易见的：1）只适用于数据是FIFO的这种情况，一旦数据不是按照先申请先释放原则进行，那内存碎片问题还是解决不了。2）需要预估缓冲区大小，因为缓冲区一次申请完毕，后续调整代价比较大，所以需要预估大小。3）队列管理，这其实是数据结构与算法的问题。不过一旦其中存放时的变长数据的话，解决起来要稍稍复杂一些。
摘一段Wikipedia上的简单Ring Buffer代码：
/* Circular buffer example, keeps one slot open */
#include
#include/* Opaque buffer element type. This would be defined by the application. */
typedef struct{int value;} ElemType;/* Circular buffer object */
typedefstruct{
int size; /* maximum number of elements */
int start; /* index of oldest element */
int end; /* index at which to write new element */
ElemType *elems; /* vector of elements */
} CircularBuffer;void cbInit(CircularBuffer *cb,int size){
cb->size = size +1;/* include empty elem */
cb->start =0;
cb->end =0;
cb->elems =(ElemType *)calloc(cb->size,sizeof(ElemType));
}void cbFree(CircularBuffer *cb){
free(cb->elems);/* OK if null */
}int cbIsFull(CircularBuffer *cb){
return(cb->end +1)% cb->size == cb->start;
}int cbIsEmpty(CircularBuffer *cb){
return cb->end == cb->start;
}/* Write an element, overwriting oldest element if buffer is full. App can
choose to avoid the overwrite by checking cbIsFull(). */
void cbWrite(CircularBuffer *cb, ElemType *elem){
cb->elems[cb->end]=*elem;
cb->end =(cb->end +1)% cb->size;
if(cb->end == cb->start)
cb->start =(cb->start +1)% cb->size;/* full, overwrite */
}/* Read oldest element. App must ensure !cbIsEmpty() first. */
void cbRead(CircularBuffer *cb, ElemType *elem){
*elem = cb->elems[cb->start];
cb->start =(cb->start +1)% cb->size;
}int main(int argc,char**argv){
CircularBuffer cb;
ElemType elem ={0};int testBufferSize =10;/* arbitrary size */
cbInit(&cb, testBufferSize);/* Fill buffer with test elements 3 times */
for(elem.value=0; elem.value<3* testBufferSize;++ elem.value) cbWrite(&cb,&elem); /* Remove and print all elements */ while(!cbIsEmpty(&cb)){ cbRead(&cb,&elem); printf("%d\n", elem.value); } cbFree(&cb); return0; }
Memory Poll
内存池技术更是由来已久，以至于基本上遇到内存管理一般人首先想到的就是这个。的确不管是在操作系统内核中还是在应用层程序中，内存池技术广泛的应用。之前说的memcached就是自己在应用层实现了一套内存池。另外SGI版本的STL中为了应对频繁申请/释放小内存块产生的内存碎片问题，同样用到了内存池技术。
SGI版本的STL中默认的内存分配是通过std::alloc完成的，其中将内存分配划分为两级：小于等于128B的在第一级中分配；大于128B的在第二级中分配。第二级内存分配就是简单的调用operator new完成。第一级实际是一个内存池：其中有11个slot，每个slot对应一个同样大小空闲块链表。块从8B开始，按照8B的倍数递增直到128。这样在分配小内存时，显示将请求的容量向上按8的倍数取整，然后从空闲链表中拿一个空闲区块出来。回收的时候采用类似的方法，将空闲块归还到空闲链表中。这样就能有效避免频繁分配释放小内存块。
可见内存池技术相对于上边的Ringbuffer的优点是：不用关心内存申请释放的顺序。缺点是：1）数据结构更复杂；2）按照固定大小的块划分存在内存浪费。这种浪费是不能避免的，但是可以通过合理的选择块的大小，尽量减少浪费。Memcached提供了可以根据用户自定义的递增因子设置间隔slot中块的增长量。这样就可以针对特定业务做特定优化。
参考
http://en.wikipedia.org/wiki/Circular_buffer
http://blog.codingnow.com/2012/02/ring_buffer.html
《STL源码详解》
发表回复