- 浏览: 202777 次
- 性别:
- 来自: 重庆
文章分类
最新评论
三种的allocator实现源代码的对比
- 博客分类:
- c++
转自:http://blog.csdn.net/eagleatustb/article/details/8031549
最近看空间配置器的内容,把ACE的ACE_Allocator类实现,SGI的allocator类实现和MS的allocator实现也参考了侯捷先生的《STL源码剖析》,有不少收获。
我听说是有说明STL中allocator实现标准的文件,但我没有找到,据我实验推测,标准allocator需要实现rebind,allocate,deallocate,max_size和构造及析构函数一共六个函数。也就是说,我要写一个在标准vector可用的allocator最小只需要上面的几个接口实现就可以了。
先来说一下微软的allocator。文件名是xmemory,我觉得是最没有看头的,基本就是new和delete的封装,为了迎合C++标准库的标准做的。没有什么技巧,更别说微妙了。上面的六个接口下面都有实现。
[cpp] view plaincopy
// TEMPLATE CLASS allocator
emplate<class _Ty>
class allocator
: public _Allocator_base<_Ty>
{ // generic allocator for objects of class _Ty
ublic:
typedef _Allocator_base<_Ty> _Mybase;
typedef typename _Mybase::value_type value_type;
typedef value_type _FARQ *pointer;
typedef value_type _FARQ& reference;
typedef const value_type _FARQ *const_pointer;
typedef const value_type _FARQ& const_reference;
typedef _SIZT size_type;
typedef _PDFT difference_type;
template<class _Other>
struct rebind
{ // convert an allocator<_Ty> to an allocator <_Other>
typedef allocator<_Other> other;
};
pointer address(reference _Val) const
{ // return address of mutable _Val
return (&_Val);
}
const_pointer address(const_reference _Val) const
{ // return address of nonmutable _Val
return (&_Val);
}
allocator() _THROW0()
{ // construct default allocator (do nothing)
}
allocator(const allocator<_Ty>&) _THROW0()
{ // construct by copying (do nothing)
}
template<class _Other>
allocator(const allocator<_Other>&) _THROW0()
{ // construct from a related allocator (do nothing)
}
template<class _Other>
allocator<_Ty>& operator=(const allocator<_Other>&)
{ // assign from a related allocator (do nothing)
return (*this);
}
void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
::operator delete(_Ptr);
}
pointer allocate(size_type _Count)
{ // allocate array of _Count elements
return (_Allocate(_Count, (pointer)0));
}
pointer allocate(size_type _Count, const void _FARQ *)
{ // allocate array of _Count elements, ignore hint
return (allocate(_Count));
}
void construct(pointer _Ptr, const _Ty& _Val)
{ // construct object at _Ptr with value _Val
_Construct(_Ptr, _Val);
}
void destroy(pointer _Ptr)
{ // destroy object at _Ptr
_Destroy(_Ptr);
}
_SIZT max_size() const _THROW0()
{ // estimate maximum array size
_SIZT _Count = (_SIZT)(-1) / sizeof (_Ty);
return (0 < _Count ? _Count : 1);
}
};
2. SGI STL实现的allocator。作为C++作者都主推的STL实现版本,当然是符合标准的。它的主站:http://www.sgi.com/tech/stl/ ,怎么去配置调试我已经在上一篇讲过了。它的实现通过阅读侯捷先生的书得到更深入的了解。当然代码与侯先生解析的那个版本有一些不同,无非是加了一些代理以及包装之类的,影响不大。我们可以看到这些接口大都通过__sgi_alloc中的函数去实现。
[cpp] view plaincopy
template <class _Tp>
struct __stlport_class
{ typedef _Tp _Type; };
template <class _Tp>
class allocator //: public _AllocatorAux<_Tp>
/* A small helper struct to recognize STLport allocator implementation
* from any user specialization one.
*/
: public __stlport_class<allocator<_Tp> >
{
public:
typedef _Tp value_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
#if defined (_STLP_MEMBER_TEMPLATE_CLASSES)
template <class _Tp1> struct rebind {
typedef allocator<_Tp1> other;
};
#endif
allocator() _STLP_NOTHROW {}
#if defined (_STLP_MEMBER_TEMPLATES)
template <class _Tp1> allocator(const allocator<_Tp1>&) _STLP_NOTHROW {}
#endif
allocator(const allocator<_Tp>&) _STLP_NOTHROW {}
#if !defined (_STLP_NO_MOVE_SEMANTIC)
allocator(__move_source<allocator<_Tp> > src) _STLP_NOTHROW {}
#endif
~allocator() _STLP_NOTHROW {}
pointer address(reference __x) const {return &__x;}
const_pointer address(const_reference __x) const { return &__x; }
// __n is permitted to be 0. The C++ standard says nothing about what the return value is when __n == 0.
_Tp* allocate(size_type __n, const void* = 0) {
if (__n > max_size()) {
_STLP_THROW_BAD_ALLOC;
}
if (__n != 0) {
size_type __buf_size = __n * sizeof(value_type);
_Tp* __ret = __REINTERPRET_CAST(_Tp*, __sgi_alloc::allocate(__buf_size));
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__ret, _STLP_SHRED_BYTE, __buf_size);
#endif
return __ret;
}
return 0;
}
// __p is permitted to be a null pointer, only if n==0.
void deallocate(pointer __p, size_type __n) {
_STLP_ASSERT( (__p == 0) == (__n == 0) )
if (__p != 0) {
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__p, _STLP_SHRED_BYTE, __n * sizeof(value_type));
#endif
__sgi_alloc::deallocate((void*)__p, __n * sizeof(value_type));
}
}
#if !defined (_STLP_NO_ANACHRONISMS)
// backwards compatibility
void deallocate(pointer __p) const { if (__p != 0) __sgi_alloc::deallocate((void*)__p, sizeof(value_type)); }
#endif
size_type max_size() const _STLP_NOTHROW { return size_t(-1) / sizeof(value_type); }
void construct(pointer __p, const_reference __val) { _STLP_STD::_Copy_Construct(__p, __val); }
void destroy(pointer __p) { _STLP_STD::_Destroy(__p); }
#if defined (_STLP_NO_EXTENSIONS)
/* STLport extension giving rounded size of an allocated memory buffer
* This method do not have to be part of a user defined allocator implementation
* and won't even be called if such a function was granted.
*/
protected:
#endif
_Tp* _M_allocate(size_type __n, size_type& __allocated_n) {
if (__n > max_size()) {
_STLP_THROW_BAD_ALLOC;
}
if (__n != 0) {
size_type __buf_size = __n * sizeof(value_type);
_Tp* __ret = __REINTERPRET_CAST(_Tp*, __sgi_alloc::allocate(__buf_size));
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__ret, _STLP_SHRED_BYTE, __buf_size);
#endif
__allocated_n = __buf_size / sizeof(value_type);
return __ret;
}
return 0;
}
#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
void _M_swap_workaround(allocator<_Tp>& __other) {}
#endif
};
在我调试的时候是用内存分配函数_M_allocate来从内存池(按侯先生的说法是空间,不一定是内存)中分配可用空间到自由链以及返回用户使用。若想更进一步了解,必须自己去看源代码:RTFSC。小结一下,SGI 的这份代码符合标准规范,结合侯先生的书,可以让你看清STL的实现本质。
3. 最后说一下ACE的allocator实现。应该说,ACE的实现可能在设计的时候,就不打算遵守C++标准库的规范,只是为了高效安全的在ACE内部使用。我们也可以看以下接口代码。基类ACE_Allocator直接使用了malloc和free让子类去实现。这份代码完全可以结合侯先生的书来看,只是在一些实现的名字前面加上ACE或者_S等前缀,实现的原理和SGI是很相似的。在内存块管理方面,小块内存(小于128),也是用自由链去管理,大块内存(大于128)直接分配。在自由链表方面它也使用了一个和SGI一样的小技巧,就是把next指针放在未使用内存块的开头处(我第一次看到这种技巧,有点怪怪的,但是能很好的实现,主要是效率有提升,多少就不考究了)。比SGI加多了一个block块链的管理,可以更灵活的使用(应该是限于ACE的应用了,因为它不遵守标准)。
[cpp] view plaincopy
class ACE_Export ACE_Allocator
{
public:
/// Unsigned integer type used for specifying memory block lengths.
typedef size_t size_type;
// = Memory Management
/// Get pointer to a default ACE_Allocator.
static ACE_Allocator *instance (void);
/// Set pointer to a process-wide ACE_Allocator and return existing
/// pointer.
static ACE_Allocator *instance (ACE_Allocator *);
/// Delete the dynamically allocated Singleton
static void close_singleton (void);
/// "No-op" constructor (needed to make certain compilers happy).
ACE_Allocator (void);
/// Virtual destructor
virtual ~ACE_Allocator (void);
/// Allocate @a nbytes, but don't give them any initial value.
virtual void *malloc (size_type nbytes) = 0;
/// Allocate @a nbytes, giving them @a initial_value.
virtual void *calloc (size_type nbytes, char initial_value = '\0') = 0;
/// Allocate <n_elem> each of size @a elem_size, giving them
/// @a initial_value.
virtual void *calloc (size_type n_elem,
size_type elem_size,
char initial_value = '\0') = 0;
/// Free <ptr> (must have been allocated by <ACE_Allocator::malloc>).
virtual void free (void *ptr) = 0;
/// Remove any resources associated with this memory manager.
virtual int remove (void) = 0;
// = Map manager like functions
/**
* Associate @a name with @a pointer. If @a duplicates == 0 then do
* not allow duplicate @a name/@a pointer associations, else if
* @a duplicates != 0 then allow duplicate @a name/@a pointer
* assocations. Returns 0 if successfully binds (1) a previously
* unbound @a name or (2) @a duplicates != 0, returns 1 if trying to
* bind a previously bound @a name and @a duplicates == 0, else
* returns -1 if a resource failure occurs.
*/
virtual int bind (const char *name, void *pointer, int duplicates = 0) = 0;
/**
* Associate @a name with @a pointer. Does not allow duplicate
* @a name/@a pointer associations. Returns 0 if successfully binds
* (1) a previously unbound @a name, 1 if trying to bind a previously
* bound @a name, or returns -1 if a resource failure occurs. When
* this call returns @a pointer's value will always reference the
* void * that @a name is associated with. Thus, if the caller needs
* to use @a pointer (e.g., to free it) a copy must be maintained by
* the caller.
*/
virtual int trybind (const char *name, void *&pointer) = 0;
/// Locate @a name and pass out parameter via pointer. If found,
/// return 0, returns -1 if failure occurs.
virtual int find (const char *name, void *&pointer) = 0;
/// Returns 0 if the name is in the mapping. -1, otherwise.
virtual int find (const char *name) = 0;
/// Unbind (remove) the name from the map. Don't return the pointer
/// to the caller
virtual int unbind (const char *name) = 0;
/// Break any association of name. Returns the value of pointer in
/// case the caller needs to deallocate memory.
virtual int unbind (const char *name, void *&pointer) = 0;
// = Protection and "sync" (i.e., flushing memory to persistent
// backing store).
/**
* Sync @a len bytes of the memory region to the backing store
* starting at @c this->base_addr_. If @a len == -1 then sync the
* whole region.
*/
virtual int sync (ssize_t len = -1, int flags = MS_SYNC) = 0;
/// Sync @a len bytes of the memory region to the backing store
/// starting at @a addr.
virtual int sync (void *addr, size_type len, int flags = MS_SYNC) = 0;
/**
* Change the protection of the pages of the mapped region to @a prot
* starting at <this->base_addr_> up to @a len bytes. If @a len == -1
* then change protection of all pages in the mapped region.
*/
virtual int protect (ssize_t len = -1, int prot = PROT_RDWR) = 0;
/// Change the protection of the pages of the mapped region to @a prot
/// starting at @a addr up to @a len bytes.
virtual int protect (void *addr, size_type len, int prot = PROT_RDWR) = 0;
#if defined (ACE_HAS_MALLOC_STATS)
/// Dump statistics of how malloc is behaving.
virtual void print_stats (void) const = 0;
#endif /* ACE_HAS_MALLOC_STATS */
/// Dump the state of the object.
virtual void dump (void) const = 0;
private:
// DO NOT ADD ANY STATE (DATA MEMBERS) TO THIS CLASS!!!! See the
// <ACE_Allocator::instance> implementation for explanation.
/// Pointer to a process-wide ACE_Allocator instance.
static ACE_Allocator *allocator_;
/// Must delete the <allocator_> if non-0.
static int delete_allocator_;
};
最近自己也写了几个allocator,还没有研究更好的实现方式。不过看上去,侯先生书上说空间配置器,我应该可以考虑一下读取硬盘空间来做allocator的空间,虚拟内存估计就是这么实现的吧。
随想:回想一年前,我第一次使用标准库,觉得allocator实现是很高深的学问,自己什么时候才能学会啊。后来看侯先生的allocator这本书,觉得我也可以做到,但由于自己的懒惰,很久都没有实践,最近有时间,再把标准库认认真真的读一下,写一些深得体会,也对得起自己这三年的工作学习。其实有很多事情,一开始觉得那么高深而自己难为之,只要有信心,方法用对了,坚持下来就会有突破的,而且一旦突破,那种快乐是相当舒服的。
最近有一个用了C++快五年的程序员,对C++及开源的了解相当深入,我觉得他也是一步一步走过来的。对于一些元编程,模板的灵活用法,网络编程的高级使用,服务器的负载均衡,linux内核机制,window底层原理,他都有所深入了解,他现在说的很多我都还不懂,我需要坚持自己的步伐,加快一点。
发表评论
-
C++的原子操作
2012-12-20 17:43 4658在多进程(线程)访问资源时,能够确保所有其他的进程(线程 ... -
匿名namespace的作用以及它与static的区别
2012-12-20 17:24 1773一。匿名namespace的作用 在C语言中,如果我们 ... -
C++类型萃取技术
2012-12-19 15:16 1117Traits技术可以用来获得一个 类型 的相关信息的。 ... -
数值压缩存储方法Varint
2012-12-19 14:35 819转自:http://www.cnblogs.com/smark ... -
TypeList
2012-12-19 13:49 1120转自:http://blog.csdn.n ... -
template <unsigned int N>
2012-12-19 11:51 1466详见:http://stackoverflow.com/ ... -
二维指针*(void **)的研究(uC/OS-II案例)
2012-12-19 22:20 3259原文 : http://blog.csdn ... -
多级指针和链表
2012-12-18 22:28 0如果看到一个声明:t ... -
理解*(void**)b
2012-12-18 22:03 0#include <stdio.h> ... -
STL标准库:Allocator能做什么
2012-12-18 20:10 0The Standard Librarian: Wha ... -
结构体内变量相对便宜与list_entry()宏
2012-12-18 17:59 907#define list_entry(ptr, t ... -
声明与函数、函数指针---(*(void (*)( ) )0)( ) 解析
2012-12-18 17:33 1084概述 在很 ... -
c++模板(类型依赖)说明例子
2012-12-18 16:57 1131#include <iostream> # ... -
C++中三种new的用法
2012-12-18 16:44 1817我评价自己的C++水平还未入门的确不够准确,应该是远远未 ... -
C++,永久改变你写异常安全代码的方式(神奇的Loki::ScopeGuard)
2012-12-17 20:19 2483作者:Andrei Alexandrescu and P ... -
C++的make_pair函数
2012-12-17 17:19 3436Pairs C++标准程序库中凡是“必须返回两 ... -
C++的explicit构造函数
2012-12-13 15:59 628按照默认规定,只有一个参数的构造函数也定义了一个隐式转换 ...
相关推荐
linux下c++ allocator 共享内存,内存池实现
STL中allocator相关源代码
将arena由原来的两种状态明确处理成三种状态——empty、usable、full,使得以统一的方式处理pool与arena(两组函数完全类似,从而也使得我写了两个通用的链表处理函数PREPEND_NODE和POP_NODE),改进后的处理方式使...
The Slab Allocator An Object-Caching Kernel Memory Allocator
代码实现了大的内存池以及由此实现的stl allocator代码。
Linux中Slub allocator工作原理介绍
49.Loki_allocator总结
关于stl中的Allocator的深入了解
Malloc Lab: Writing a Dynamic Storage Allocator
Memory allocators form interesting case studies ... This allocator provides implementations of the the standard C routines malloc(), free(), and realloc(), as well as a few auxiliary utility routines. T
不同于书上的解决办法,根据traces十分高效
结合网上版本及c++ primer及visual sudio2017,ubuntu 16.04实测,实现标准库中vector的实现,缺少部分函数,包含了主要的push_back,resize,reserve,[],size()函数,若有疑问请发送至2268047160@qq.com,最近在详细...
《C++内存管理机制_60_侯捷》13.Per-class allocator 2
《C++内存管理机制_60_侯捷》15.Macro for static allocator
buddy_allocator buddy system memory allocator from Linux kernel System Storage 两个大小相等且邻接的内存块被称作伙伴。 如果两个伙伴都是空闲的,会将其合并成一个更大的内存块,作为下一层次上某个内存块的...
一种快速安全的GPU堆分配器,陈浩,吴江,图形处理单元(GPUs)广泛应用于在诸多领域中执行通用计算,例如科学计算,深度学习。为了在GPU编程中提供更大的灵活性,在GPU编程��
游戏编程精粹7光盘源代码 01 General Programming 部分 原版光盘copy,有需要的朋友可以看看. 目录: 02 High Performance Heap Allocator 03 Optical Flow For Videogames Played With Webcams 04 Design and ...
游戏编程high performance heap allocator
Linux memory slob slab slub allocator. Three different memory allocators comprision.
《深入理解计算机系统》课程的实验5材料 解答过程在:http://blog.csdn.net/u010560443/article/details/50611251