内存池--定长内存池

简介

STL的 __pool_alloc, __mt_alloc,boost的pool系列, ace的ACE_Cached_Allocator均为定长内存池。

说明

内存池,根据存储的元素的长度是否可变,分为变长,与定长两种内存池。

从逻辑上来讲,定长内存池只需存储相同大小的元素,因此无须花费额外的空间(数据结构)来存储元素长度的信息。

以上几种定长内存池都可以较好的处理定长内存频繁分配的问题。

STL--pool_alloc

pool_alloc,原理是挂了16个链表(_S_free_list),每个链表存储分配大小为[1,8],[9-16],[17-24],...,[120,128]的数据。

1.下图(图一)为数据结构:

 1     class __pool_alloc_base
 2     {   
 3     protected:
 4 
 5       enum { _S_align = 8 };
 6       enum { _S_max_bytes = 128 };
 7       enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
 8 
 9       union _Obj
10       {   
11     union _Obj* _M_free_list_link;
12     char        _M_client_data[1];    // The client sees this.
13       };  
14 
15       static _Obj* volatile         _S_free_list[_S_free_list_size];
16 
17       // Chunk allocation state.
18       static char*                  _S_start_free;
19       static char*                  _S_end_free;
20       static size_t                 _S_heap_size;
21 
22         ... 
23     };

 2.下图(图二)为链表示意图:

 3.allocate

 __pool_alloc<_Tp>::allocate(size_type __n, const void*)

allocate时,该函数会根据请求的__n乘以sizeof(T)来计算,决定由哪个链表分配。

4.deallocate

__pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)

这点需要重点注意,__n必须要传。如果__n的值与allocate分配时的大小不一致,将会导致deallocate失败。原因是__pool_alloc不会保存实际元素有多长,他需要根据__n来计算数据到底存于哪个链表。 

 STL--mt_alloc

mt_alloc实现相对复杂,我本地有一篇详细的文档,但由于篇幅的原因,不适宜在本文中添加。

定义 

template<typename _Tp, 
       typename _Poolp = __common_pool_policy<__pool, __thread_default> >
    class __mt_alloc : public __mt_alloc_base<_Tp>

说明

allocate和deallocate实际都是使用的__pool来分配和管理内存。

实际上,__pool会在freelist上查找是否有free的block;

而1.线程ID(对应的,非原始线程ID) 2.数据大小这两个条件将必然能从多个freelist集合中对应出唯一freelist来操作。

  1. 数据大小->bin
  2. 每个bin包含每个线程的freelist。 
因此每个线程在做allocate时,不需要等待,都是在各自的freelist上去操作,这样提高了并发。

allocate: 

  1 template<typename _Tp, typename _Poolp>

 2 typename __mt_alloc<_Tp, _Poolp>::pointer
 3      __mt_alloc<_Tp, _Poolp>::
 4      allocate(size_type __n, const void*)
 5      {
 6          ...
 7          // Requests larger than _M_max_bytes are handled by operator
 8          // new/delete directly.
 9      
10                // Round up to power of 2 and figure out which bin to use.
11        const size_t __which = __pool._M_get_binmap(__bytes);
12        const size_t __thread_id = __pool._M_get_thread_id();
13      
14        // Find out if we have blocks on our freelist.  If so, go ahead
15        // and use them directly without having to lock anything.
16  
17          ...
18      }

deallocate类似,不在此赘述。

 

 
原文地址:https://www.cnblogs.com/onlyforcloud/p/4398138.html