存档在 2013年4月

STL的第二级空间配置器

2013年4月25日

当申请的内存比较小时,频繁的申请与释放很容易造成碎片,而且还会造成配置的负担。所以当小额分配时,在内存池中进行分配,这样就避免了申请和释放带来的碎片,还避免了频繁申请带来的效率问题。
STL的第二级空间配置器的做法是:如果申请的内存大于128字节,则交给第一级,否则在第二级中用内存池管理。基本原理是,每次配置一大块内存,并用自由链表进行维护,内存的申请直接在自由链表中划拨。释放的内存则由自由链表回收。

对于小额区块内存,都会上升到8的倍数,比如13会上升到16.31会上升到32.
第二级配置器维护16个自由链表,分别管理大小为『8,16,24.。。』的区块。以下3个分别为小额内存的上升边界,小额内存的上限,自由链表的个数。
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; » 阅读更多: STL的第二级空间配置器

STL的第一级空间配置器

2013年4月25日

STL的第一级空间配置器,该配置用于超过128K内存申请请求时。其中的allocate直接使用malloc来进行内存分配,如果分配失败则交由oom_malloc (out of memory),如果oom_malloc分配失败则根据函数set_malloc_handler设置的处理方式释放内存并重新申请,如果没有设置set_malloc_handler则在遇到无内存可分配时的处理方式为抛出异常。同理对于realloc也是一样道理。

template <int inst>
class __malloc_alloc_template {

private:
//allocate里调用malloc失败时调用该函数
static void *oom_malloc(size_t);
//reallocate里调用relloc失败时调用该函数
static void *oom_realloc(void *, size_t);
//上边两个函数失败时处理函数
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    static void (* __malloc_alloc_oom_handler)();
#endif
public:
//直接调用malloc分配内存,失败则调用oom_malloc
static void * allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);
    return result;
}

static void deallocate(void *p, size_t /* n */)
{
    free(p);
}

static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
    void * result = realloc(p, new_sz);
    if (0 == result) result = oom_realloc(p, new_sz);
    return result;
}

//设置处理函数,返回旧的处理函数
static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}
};
// malloc_alloc out-of-memory handling
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
#endif

template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;
		//不断重试
    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        result = malloc(n);
        if (result) return(result);
    }
}

template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        result = realloc(p, n);
        if (result) return(result);
    }
}

STL的非标准空间配置器alloc

2013年4月25日

由于STL中既有标准的空间配置器alloctor还有专属的非标准alloc配置器,那么alloc是什么样的呢?
代码中可见

typedef __malloc_alloc_template<0> malloc_alloc;
或者
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

由上可以看出端倪,alloc要么是__malloc_alloc_template或者__default_alloc_template。
» 阅读更多: STL的非标准空间配置器alloc

SGI STL的两个空间配置器

2013年4月25日

1.标准空间配置器std::allocator,这个配置器符合标准,但是性能相对来说差一点,不推荐使用。
2.特殊的空间配置器std::alloc,这个也是默认的配置器。
» 阅读更多: SGI STL的两个空间配置器

STL中的配置器涉及到的几个文件

2013年4月25日

STL配置器定义于memory中,包含的头文件在下面。另外该文件还定义了auto_ptr.

#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_uninitialized.h>

stl_construct.h这个头文件包含全局函数construct与destroy负责对象的构造与析构,不涉及到内存的分配与释放。
stl_alloc.h这个头文件负责空间的分配。包含两级配置器,配置器为alloc.
stl_uninitialized.h该头文件用来填充或者赋值数据。

stl_construct.h中
construct用于在已经获得的内存上构造对象,使用了定位new来生成。

template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
//定位new,在给定的地址空间中,构造一个用value初始化的对象
  new (p) T1(value);
}

这里为什么要定义两个模板参数T1,T2.目的是为了兼容类型,比如int变量是可以赋值给double变量的。
destroy则调用析构函数。
当然为了提高效率,还是针对不同的模板实参进行了特化或者特殊处理。

stl_alloc.h中定义了两级空间配置器__malloc_alloc_template,__default_alloc_template.

stl_uninitialized中则是用来作用于未初始化的空间。包括复制,填充。

STL内存基本内存处理工具

2013年4月25日

介绍5个底层相关的内存处理工具.
construct,destroy,uninitialized_copy,uninitialized_fill_n,uninitialized_fill.
首先是uninitialized_copy,该模板函数针对char,wchar_t进行了特化,使用memmove提高处理效率。
该函数用于将输入区间元素拷贝到输出区间。

template <class InputIterator, class ForwardIterator>
inline ForwardIterator
  uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result) {
  return __uninitialized_copy(first, last, result, value_type(result));
}

inline char* uninitialized_copy(const char* first, const char* last,
                                char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                   wchar_t* result) {
  memmove(result, first, sizeof(wchar_t) * (last - first));
  return result + (last - first);
}

其中针对元素是否是平凡的[拷贝构造函数,默认构造函数,赋值操作符与析构函数],进行不同处理。
参数value_type(result),用于获取元素的类型,通过该类型来获取是否平凡,以下利用__type_traits::is_POD_type来对T进行判断。

template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator
__uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result, T*) {
  typedef typename __type_traits<T>::is_POD_type is_POD;
  return __uninitialized_copy_aux(first, last, result, is_POD());
}

根据不同的元素平凡性来进行分别处理

template <class InputIterator, class ForwardIterator>
inline ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __true_type) {
  return copy(first, last, result);
}

template <class InputIterator, class ForwardIterator>
ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __false_type) {
  ForwardIterator cur = result;
  __STL_TRY {
    for ( ; first != last; ++first, ++cur)
      construct(&*cur, *first);
    return cur;
  }
  __STL_UNWIND(destroy(result, cur));
}

第一个为平凡元素,则可以直接调用高层copy函数。
第二个为非平凡元素,则需要对每个元素进行构造。
其他函数也一样,uninitialized_fill_n,uninitialized_fill类似。

Linux 内核中链表剥离

2013年4月25日

剥离后可以运行在linux与windows平台。
在用户空间编程使用linux内核链表list,hlist宏定义和操作. linux内核中的list_head和hlist_head/hlist_node是将数据结构串起来成为链表的两个重要链表构造工具。利用他们和其对应的宏定义,可以非常容易地将数据构成链表,进行链表的各种操作,和数据查询。 在内核中,这些链表操作宏定义具有通用性,和具体数据结构无关。 利用这些已有的代码,我们就不必要自己处理链表指针,而集中精力关心数据本身。 » 阅读更多: Linux 内核中链表剥离

2013年5月1日前文章目录

2013年4月25日
Linux进程的状态linuxSTL中的特性萃取机iterator_traitsstl
STL的第二级空间配置器代码分析[1]stlSTL的第二级空间配置器代码分析[2]stl
STL的第一级空间配置器stlSTL的第二级空间配置器stl
SGI STL的两个空间配置器stlSTL的非标准空间配置器allocstl
STL内存基本内存处理工具stlSTL中的配置器涉及到的几个文件stl
位运算如何将一个数上调至8的倍数技巧Linux 内核中链表剥离链表
系统调用和库函数的区别系统Linux上有哪些常用的数据库linux
栈为什么比堆的效率高系统内存&数据结构中堆与栈的区别系统
左值与右值理解误区基础左值引用,右值引用基础
C++虚函数表(一般继承时)C++C++虚函数表(虚函数覆盖继承)C++
分治法求数组最大元素与最小元素算法C++虚函数表总览C++
线程与进程异同系统C与C++中const区别其实很大语言
数组名与数组名的地址系统排序算法回顾算法
快速排序sort分析算法windows与linux回车换行(CRLF)系统