oldworm

有些时候需要给资源分配一个唯一id(32bit or 64bit or CHAR[N])，这里主要说下分配方法问题。

首先我们有个基本前提，如果是单线程分配，那么我们无需下面的方法，直接++value即可(CHAR型无论几线程都可使用GUID)顺序产生不重复序列，下面讨论的方法都是多线程下的分配策略：

方法1、 win下做简单的方法莫过于使用InterlocckedIncrement(or InterlockedIncrement64)了，这个调用也很简单，每次递增一个，多线程间保证顺序递增绝无重复。此方法只可在单一进程上使用。

 

方法2、区间法，每个线程一次申请一个id区间[m, n]，用完了再申请下一个区段，申请的时候锁一次，其他时间都不用锁，效率比3略低，比1高。此方法也只可在一个进程上使用，当然如果申请的策略修改一下也可实现多个进程甚至不同机器上的进程之间独立分配id。

 

方法3、方法1虽然简单但毕竟InterlockedXXX系列函数调用还是有些耗时的，大概50cpu周期级别，更简单的方法可以使用线程切分原理，如有3个线程参与id分配，我们这样分配：

线程1 base=1, step =3，序列1,4,7,10,…

线程2 base=2, step=3，序列2,5,8,11,…

线程3 base=3, step=3，序列3,6,9,12,…

绝无重复，调用非常简单每个线程id = base; base += step;即可。

此方法在单进程上使用很简单，如果要拓展到多个进程上使用要通过配置来实现，但也是不难的。

 

方法4、如果id可用GUID表示那么方法要简单一点，生成id直接调用guid生成算法，这个id生成算法即使在多个进程之间甚至不同机器之间也可以保证唯一，也有其价值。

执行100w次的结果（单位：微妙）
------------------------------------------------------------------------------------
线程 volatile读 volatile写 InterlockedInc  CS SRWLock共享 SRWLock独占 互斥量
  1     8            8               35                 66      66                       67       1060
  2     8           76             153                268    134                   148      11082
  4     9           145           361                768    244                   307      23785

volatile读 long lvalue = gv_value;

volatile写 gv_value = 0;

InterlockedIncrement(&gv_value);

EnterCriticalSection(&cs);
gv_value = 0;
LeaveCriticalSection(&cs);

AcquireSRWLockShared/Exclusive(&g_srwlock);
gv_value = 0;
ReleaseSRWLockShared/Exclusive(&g_srwlock);

WaitForSingleObject(&g_hMutex, INFINITE);
gv_value = 0;
RleaseMutex(g_hMutex);

如果希望应用程序获得最佳性能，那么首先应该尝试不要共享数据，然后依次使用
volatile读取，volatile写入，Interlocked API, SRWLock以及关键段，当前仅当
所有这些都不满足要求的时候再使用内核对象。

来自Jeffrey Riched《windows核心编程（5）》的数据，录在这里备查。

从2004年使用iocp开始，尝试过很多种client生存期管理，最初使用
一个锁userlock，在sendcomp和recvcomp以及senddata等都用一个锁，而且是
进去的地方就开始锁，这种方式最简单，也产生了最初的版本，之后为
追求更高效率，慢慢演变为使用两个锁，readlock和writelock，再之后
演变为send使用一个锁，recv使用interlockedxxx，再之后演变为
send使用一个cs锁和一个sending，recv使用一个ref，经历了如此多种演变。

1、一个锁userlock, sendcomp recvcomp senddata都用这个锁。
2、两个锁，userlock, sendlock
3、一个锁userlock+socket查找，锁范围比1小，多一次全局查找操作。
4、一个锁sendlock，一个ref（InterlockedXXX）
   wsasend wsarecv 对象生存期等都用ref计数
5、一个锁sendlock和一个sending（InterlockedXXX），一个ref（InterlockedXXX）
   wsasend用sending计数，wsarecv等用ref计数

历经如此几个版本的修改，锁的范围越来越小，interlocked次数越来越少，反应自然
越来越快。
今天为了写总结文章，拿1 4 5进行了一次比较，1除了大量连接的时候比4 5 反应
慢了很多之外在cpu mem等占用方面几乎和4 5 相当，也就是说除了实时性方面差一些
其他方面没有太大差别。
但4 5都是用到了线程级别的内存池，1的测试例程还是用老的内存池，这个差别也
很大，所以综合地看，虽然做了很多优化却是花费80%的时间，做了20%的鸟事。

5、线程关联内存池再提速

 

 

上一节已经提到问题，解决办法是这样的

struct tm_bufunit

{

        tm_pool *pool;                        //pool指针

        union

        {

                tm_bufunit *next;   //下一个块指针

                char data[4];           //数据区域

        };

};

 

static void *tm_malloc(size_t size, size_t *osize=NULL)

{

        tm_bufunit *p = (tm_bufunit *)malloc(sizeof(tm_bufunit)-offsetof(tm_bufunit, data)+size);

        if(p)

        {

                p->pool = NULL;

                if(osize) *osize = size;

                return p->data;

        }

        return      NULL;

}

看上面的代码应该很容易明白，就是将由该池malloc的内存块也打上统一的标记，这样由该池分配的任何内存块都可用最简单的判断释放，省去了查找线程查找目标池的两次查询，不光提速了而且解决了上一节提到的那个bug。

最终实现的线程关联内存池通用分配函数tm_new大概相当于malloc 15倍左右的速度，定位到pool之后的newobj相当于malloc 45倍左右的速度。通用函数大致相当于nedmalloc速度的2.6-3倍，直接定位到pool的分配速度大概相当于dlmalloc 的2倍。

 

关于线程关联的内存池还有一些细节问题我没有展开讨论，如free表是每个线程保留一份还是全局保留一份，如果是全局保留一份则涉及到复用的时候如何分配，还有就是tls系列函数我看nedmalloc也在用，我第一版也在用，但后来实测发现这些函数貌似效率不高，后面的版本没有采用tls系列函数。

关于线程关联的内存池我写了5个版本，当然最重要的还是第一个版本，后面的版本除了这一节提到的重要改进之外变化不是很大，最后的第五版增了一些和我的私有lib相关的功能。

 

以前写文章太少，总是看别人的文章，在网络时代觉得自己挺自私，这次一鼓作气，一口气写了出来，可能写得很粗略，不知道有多少人能看明白，如能给读者一点启示我将感到很欣慰。

4、线程关联的内存池

 

每每想到单线程下内存池飞一般的速度和多线程下蜗牛一般的速度我就不能原谅自己，为什么差这么多，就不能让多线程下内存分配更快一点吗？解决方法有了，那就是让缓存线程化，各个线程有自己私有的缓存，分配的时候预先从当前线程私有缓存分配，分配空了的时候去全局free表取一组freeunit或直接向系统申请一大块缓存（各个线程缓存完全独立），不管具体采用什么方式，速度都大幅度的提高了，虽然还是比单线程下内存池慢了许多，不过比前面提到的多线程内存池以及nedmalloc都要快很多，我的实现大概比nedmalloc快1.6 ~ 2倍，离单线程下内存池速度也很近了，只是多了些查找线程id比较线程id等动作而已，基本上达到了自己的目标。

 

看看第一版线程关联内存池的一些代码：

 

struct tm_bufunit

{

        tm_pool *pool;                        //pool指针

        union

        {

                tm_bufunit *next;   //下一个块指针

                char data[4];           //数据区域

        };

};

 

struct tm_gcontrol

{

        tm_bufunit *gfree;

        CRITICAL_SECTION gcs;

 

        tm_gcontrol() : gfree(NULL) { InitializeCriticalSection(&gcs); }

        ~tm_gcontrol()        { DeleteCriticalSection(&gcs); }

        Inline void lock()     { EnterCriticalSection(&gcs); }

        Inline void unlock() { LeaveCriticalSection(&gcs); }

        void free(tm_bufunit *buf)

        {

                lock();

                buf->next = gfree;

                gfree = buf;

                unlock();

        }

};

 

struct tm_memblock

{

        tm_memblock *next;

};

 

class tm_pool

{

private:

        size_t bksize;                   //一个分配块大小

        size_t onebknum;            //一次分配多少个bksize

        DWORD thid;                          //线程id

        tm_bufunit *next;           //pool中自由块链

        tm_memblock *mbk;              //trunk表

        tm_gcontrol gcontrol;     //全局free表

       

        friend tm_poolset;

private:

        void expand();

 

public:

        tm_pool(size_t size, size_t bknum);

        ~tm_pool();

 

        void destroy();

        void *newobj();

        static void delobj(void *pbuf);

};

 

class tm_poolset

{

public:

        tm_poolset();

        virtual ~tm_poolset();

 

        //添加分配池

        bool addpool(size_t size, size_t allocnum);

        void *newobj(size_t size, size_t *osize=NULL);

        void delobj(void *pbuf, size_t size);

        void destroy();

 

        tm_pool *findpool(size_t size)

        {

                TMPOOLS::iterator it = tmpools.lower_bound(size);

                if(it != tmpools.end())

                        return it->second;

                return NULL;

        }

protected:

        typedef std::map<size_t, tm_pool *> TMPOOLS;

        TMPOOLS tmpools;

};

 

//公开的数据及函数

extern DWORD tm_tlsindex; //tls索引

 

//app初始化，分配index

void tm_init();

void tm_free();

 

//关联到该线程

void tm_attach();

void tm_detach();

 

tm_poolset *tm_getpoolset();

//添加trunk

bool tm_addtrunk(size_t size, size_t allocnum);

//tls相关分配

void *tm_new(size_t size, size_t *osize=NULL);

//tls相关释放

void tm_del(void *buf, size_t size);

 

 

 

.cpp代码如下：

tm_pool::tm_pool(size_t size, size_t bknum) :

        next(NULL), mbk(NULL),

        bksize(size), onebknum(bknum)

{

        thid = GetCurrentThreadId();

}

 

tm_pool::~tm_pool()

{

        destroy();

}

 

void tm_pool::destroy()

{

        for(tm_memblock *p = mbk; p; )

        {

                tm_memblock *q = p->next;

                free((char *)p);

                p = q;

        }

        mbk = NULL;

        next = NULL;

}

 

void *tm_pool::newobj()

{

        if(! next)

        {

                gcontrol.lock();

                if(gcontrol.gfree)

                {

                        next = gcontrol.gfree;

                        gcontrol.gfree = NULL;

                }

                gcontrol.unlock();

        }

        if(! next)

        {

                expand();

        }

        tm_bufunit *head = next;

        next = head->next;

//     return (void *)head;

        return (void *)head->data;

}

 

void tm_pool::delobj(void *pbuf)

{

//     tm_bufunit *head = (tm_bufunit*)(pbuf);

        tm_bufunit *head = (tm_bufunit *)((char *)pbuf-offsetof(tm_bufunit, data));

        tm_pool *pool = head->pool;

        if(pool->thid == GetCurrentThreadId())

        {

                head->next = pool->next;

                pool->next = head;

        }

        else

        {

                pool->gcontrol.free(head);

        }

}

 

void tm_pool::expand()

{

        size_t unitsize = offsetof(tm_bufunit, data) + bksize;

        size_t size = (unitsize * onebknum + sizeof(tm_memblock));

        tm_memblock *pbk = (tm_memblock *)malloc(size);

        pbk->next = mbk;

        mbk = pbk;

        tm_bufunit *p = (tm_bufunit*)((char *)pbk+sizeof(tm_memblock));

        p->pool = this;

        next = p;

        for(size_t i=0; i<onebknum-1; ++i)

        {

                p->next = (tm_bufunit *)((char *)p+unitsize);

                p = p->next;

                p->pool = this;

        }

        p->next = NULL;

}

 

…

这一版基本实现了第一步的提速目标，并且每个分配块还记录了来自哪个pool，这样free的时候就省去了查找pool的动作，只是还有一些问题，如何判断一个内存是来源于malloc的分配还是来源于pool的分配没有做终结的判断，而且还留下了一个bug，对于a线程来说，可能只有256，512两个块的缓存，b线程可能多一个块1024，这样a线程分配的1024字节的内存是用malloc分配，到b线程释放的时候会调用pool释放，这个bug将在下一章解决。

     摘要: 2、多线程内存池   上一节很简略的说了下单线程内存池，单线程内存池如果要放在多线程环境下使用是不安全的，我们需要进行保护，如何保护，最简单的方法就是加临界区，云风的实现里面是用原子操作模拟一个临界区，我实测跟临界区性能非常接近，甚至很多时候不如临界区，所以我就不追求用原子操作模拟临界区了，还是直接用临界区最简单。   class CMemPool { publi...  阅读全文

1、单线程内存池

 

内存池的基本思想是大块向系统申请内存，内部切割为小块，内部cache之后有选择的分配，不够的时候继续向系统大块申请内存，示例代码如下：

 

struct tm_memblock

{

        tm_memblock *next;

};

class tm_pool

{

…

        tm_bufunit *next;           //pool中自由块链

        tm_memblock *mbk;              //trunk表

…

};

 

void *tm_pool::newobj()

{

        if(! next)

        {

                expand();

        }

        tm_bufunit *head = next;

        next = head->next;

        return (void *)head;

}

 

void tm_pool::delobj(void *pbuf)

{

        tm_bufunit *head = (tm_bufunit*)(pbuf);

        head->next = next;

next = head;

}

详细实现建议看云风的内存池，我也不过是学习了它的实现而已。

不要小看了单线程内存池，它是我们走向更复杂应用的基础，它是我们后面提及的多线程内存池以及线程关联内存池的基础。

这种单线程的内存池分配释放速度是很快的，比dlmalloc更快近1倍，大约相当于malloc/free的50-100倍(具体倍率视分配的大小而不同，分配小块倍率小，分配大块倍率大)。

 

有的朋友可能会考虑使用std::list之类的东西来构建内存池，我奉劝有这种想法的人打住，std::list是效率很低的，此外用一个高层的东西构建底层模块，总体上属于本末倒置。

0、内存池之引言

 

 

这是关于内存池的一系列简短文章，当然它不是短期的研究结果，而是长期使用经验的总结，介绍得可能不会很详细，一些别人介绍得很细节的东西我就基本掠过。

转载请署名作者：袁斌

 

内容如下：

1、 单线程内存池。

2、 多线程内存池。

3、 Dlmalloc nedmalloc

4、 实现线程关联的内存池。

5、 线程关联内存池再提速。

 

关于内存池有一些经典资源可参考，如早期侯杰《池内春秋》，云风（网易核心开发人员）《我的编程感悟》中提及的内存池，以及许世伟（原金山CTO，现盛大创新院技术专家）关于内存池的系列文章。

 

可以通过QQ：345585946和我讨论

也可加入我的群：41947449 一起讨论游戏开发。

前些天无意中在网上看到一篇文章，写的是几种脚本语言以及c的速度比较，大意是测试下来lua的速度很慢，只相当于c的1/60左右，看了一下测试函数，如下（命名版本1）：

 

tkstart = os.clock()

 

local count = 10000000

local accumv = 34.5;

local function iterate (times,accumv)

    if 0 == times then

        return accumv

    else

        return iterate (times - 1, accumv + 2)

    end

end

print(iterate(count,accumv))

 

print(os.clock() - tkstart)

 

这是个迭代调用，理论上这种调用速度不快，所以改写了一下，命名版本2

 

tkstart = os.clock()

 

local i=0.0;

local function process (ret)

 while(i < 10000000.0) do

 i = i+1.0

 ret = ret + 2.0

 end

 return ret

 

end

 

process(34.5)

print(os.clock() - tkstart)

 

再改写了一下，版本3，如下:

 

tkstart = os.clock()

 

local i=0.0;

local function process (ret)

 local t = ret

 while(i < 10000000.0) do

 i = i+1.0

 t = t + 2.0

 end

 return ret

 

end

 

process(34.5)

print(os.clock() - tkstart)

 

用for循环再改写了一个版本，版本4，如下：

 

tkstart = os.clock()

 

local count = 10000000

local accumv = 34.5;

local function calc (times,accumv)

        local result = accumv

        for i=1,times do

                result = result + 2.0

        end

        return result

end

print(calc(count,accumv))

 

print(os.clock() - tkstart)

 

简单测试耗时如下

版本1 0.945

版本2 0.484

版本3 0.475

版本4 0.138   编译成.out跟直接执行.lua耗时差不多，没明显变化。

虽然是一个功能很简单实现也很简单的lua函数，但速度差别很大，由此可见不同写法对执行效率影响很大，跟版本4差不多的c程序执行耗时大约为0.016秒, lua大致相当于c的1/8 - 1/9速度，而不是那篇文章的作者认为的只相当于c的1/60。

 

从上面四个不同代码大致可以看出以下问题：

1、 迭代算法是很慢的（版本1）。

2、 While的效率比for慢很多（版本23和4的比较）。

3、 临时变量比参数效率高（版本23）。

 

测试次数	传统线程池耗时	系统线程池耗时	完成端口线程池耗时
1	49250	72234	20391
2	50906	71266	20281
3	50156	73000	20297
4	50437	71157	20000
5	49250	73078	19547
6	49844	73156	19469

 

 

线程池模型	适用操作系统	效率	易用性
传统线程池	任意	中	较麻烦，大多数人写不出好的线程池
系统线程池	Win2000之后	低	最简单
完成端口线程池	Win2000之后	高	较简单