最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

淺談C++空間配置器allocator

 更新時(shí)間:2021年06月09日 09:25:02   作者:lsgxeva  
在STL中,Memory Allocator處于最底層的位置,為一切的Container提供存儲(chǔ)服務(wù),是一切其他組件的基石。對(duì)于一般使用 STL 的用戶而言,Allocator是不可見(jiàn)的。本文將主要介紹C++空間配置器allocator

概述

在C++中,一個(gè)對(duì)象的內(nèi)存配置和釋放一般都包含兩個(gè)步驟,對(duì)于內(nèi)存的配置,首先是調(diào)用operator new來(lái)配置內(nèi)存,然后調(diào)用對(duì)象的類的構(gòu)造函數(shù)進(jìn)行初始化;而對(duì)于內(nèi)存釋放,首先是調(diào)用析構(gòu)函數(shù),然后調(diào)用 operator delete進(jìn)行釋放。 如以下代碼:

class Foo { ... };
Foo* pf = new Foo;
...
delete pf;

Allocator 的作用相當(dāng)于operator new 和operator delete的功能,只是它考慮得更加細(xì)致周全。SGI STL 中考慮到了內(nèi)存分配失敗的異常處理,內(nèi)置輕量級(jí)內(nèi)存池(主要用于處理小塊內(nèi)存的分配,應(yīng)對(duì)內(nèi)存碎片問(wèn)題)實(shí)現(xiàn), 多線程中的內(nèi)存分配處理(主要是針對(duì)內(nèi)存池的互斥訪問(wèn))等,本文就主要分析 SGI STL 中在這三個(gè)方面是如何處理的。在介紹著三個(gè)方面之前,我們先來(lái)看看 Allocator的標(biāo)準(zhǔn)接口。

1. Allocator 的標(biāo)準(zhǔn)接口

在 SGI STL 中,Allocator的實(shí)現(xiàn)主要在文件alloc.h和stl_alloc.h文件中。根據(jù) STL 規(guī)范,Allocator 需提供如下的一些接口(見(jiàn)stl_alloc.h文件的第588行開(kāi)始的class template allocator):

// 標(biāo)識(shí)數(shù)據(jù)類型的成員變量,關(guān)于中間的6個(gè)變量的涵義見(jiàn)后續(xù)文章(關(guān)于Traits編程技巧)
typedef alloc _Alloc;
typedef size_t     size_type;
typedef ptrdiff_t  difference_type;
typedef _Tp*       pointer;
typedef const _Tp* const_pointer;
typedef _Tp&       reference;
typedef const _Tp& const_reference;
typedef _Tp        value_type;
template <class _Tp1> struct rebind {
  typedef allocator<_Tp1> other;
}; // 一個(gè)嵌套的class template,僅包含一個(gè)成員變量 other
// 成員函數(shù)
allocator() __STL_NOTHROW {}  // 默認(rèn)構(gòu)造函數(shù),其中__STL_NOTHROW 在 stl_config.h中定義,要么為空,要么為 throw()
allocator(const allocator&) __STL_NOTHROW {}  // 拷貝構(gòu)造函數(shù)
template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {} // 泛化的拷貝構(gòu)造函數(shù)
~allocator() __STL_NOTHROW {} // 析構(gòu)函數(shù)
pointer address(reference __x) const { return &__x; } // 返回對(duì)象的地址
const_pointer address(const_reference __x) const { return &__x; }  // 返回const對(duì)象的地址
_Tp* allocate(size_type __n, const void* = 0) {
  return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; 
  // 配置空間,如果申請(qǐng)的空間塊數(shù)不為0,那么調(diào)用 _Alloc 也即 alloc 的 allocate 函數(shù)來(lái)分配內(nèi)存,
} //這里的 alloc 在 SGI STL 中默認(rèn)使用的是__default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>這個(gè)實(shí)現(xiàn)(見(jiàn)第402行)
void deallocate(pointer __p, size_type __n) { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } // 釋放空間
size_type max_size() const __STL_NOTHROW  // max_size() 函數(shù),返回可成功配置的最大值
    { return size_t(-1) / sizeof(_Tp); }  //這里沒(méi)看懂,這里的size_t(-1)是什么意思?
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } // 調(diào)用 new 來(lái)給新變量分配空間并賦值
void destroy(pointer __p) { __p->~_Tp(); } // 調(diào)用 _Tp 的析構(gòu)函數(shù)來(lái)釋放空間

在SGI STL中設(shè)計(jì)了如下幾個(gè)空間分配的 class template:

template <int __inst> class __malloc_alloc_template // Malloc-based allocator.  Typically slower than default alloc
typedef __malloc_alloc_template<0> malloc_alloc
template<class _Tp, class _Alloc> class simple_alloc
template <class _Alloc> class debug_alloc
template <bool threads, int inst> class __default_alloc_template // Default node allocator.
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc
typedef __default_alloc_template<false, 0> single_client_alloc
template <class _Tp>class allocator
template<>class allocator<void>
template <class _Tp, class _Alloc>struct __allocator
template <class _Alloc>class __allocator<void, _Alloc>

其中simple_alloc,debug_alloc,allocator和__allocator的實(shí)現(xiàn)都比較簡(jiǎn)單,都是對(duì)其他適配器的一個(gè)簡(jiǎn)單封裝(因?yàn)閷?shí)際上還是調(diào)用其他配置器的方法,如_Alloc::allocate)。而真正內(nèi)容比較充實(shí)的是__malloc_alloc_template和__default_alloc_template這兩個(gè)配置器,這兩個(gè)配置器就是 SGI STL 配置器的精華所在。其中__malloc_alloc_template是SGI STL 的第一層配置器,只是對(duì)系統(tǒng)的malloc,realloc函數(shù)的一個(gè)簡(jiǎn)單封裝,并考慮到了分配失敗后的異常處理。而__default_alloc_template是SGI STL 的第二層配置器,在第一層配置器的基礎(chǔ)上還考慮了內(nèi)存碎片的問(wèn)題,通過(guò)內(nèi)置一個(gè)輕量級(jí)的內(nèi)存池。下文將先介紹第一級(jí)配置器的異常處理機(jī)制,然后介紹第二級(jí)配置器的內(nèi)存池實(shí)現(xiàn),及在多線程環(huán)境下內(nèi)存池互斥訪問(wèn)的機(jī)制。

2. SGI STL 內(nèi)存分配失敗的異常處理

內(nèi)存分配失敗一般是由于out-of-memory(oom),SGI STL 本身并不會(huì)去處理oom問(wèn)題,而只是提供一個(gè) private 的函數(shù)指針成員和一個(gè) public 的設(shè)置該函數(shù)指針的方法,讓用戶來(lái)自定義異常處理邏輯:

private:
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  static void (* __malloc_alloc_oom_handler)();  // 函數(shù)指針
#endif
public:
  static void (* __set_malloc_handler(void (*__f)()))() // 設(shè)置函數(shù)指針的public方法
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
  }

如果用戶沒(méi)有調(diào)用該方法來(lái)設(shè)置異常處理函數(shù),那么就不做任何異常處理,僅僅是想標(biāo)準(zhǔn)錯(cuò)誤流輸出一句out of memory并退出程序(對(duì)于使用new和C++特性的情況而言,則是拋出一個(gè)std::bad_alloc()異常), 因?yàn)樵摵瘮?shù)指針的缺省值為0,此時(shí)對(duì)應(yīng)的異常處理是__THROW_BAD_ALLOC:

// line 152 ~ 155
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif
// in _S_oom_malloc and _S_oom_realloc
__my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
// in preprocess, line 41 ~ 50
#ifndef __THROW_BAD_ALLOC
#  if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)
#    include <stdio.h>
#    include <stdlib.h>
#    define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
#  else /* Standard conforming out-of-memory handling */
#    include <new>
#    define __THROW_BAD_ALLOC throw std::bad_alloc()
#  endif
#endif

SGI STL 內(nèi)存配置失敗的異常處理機(jī)制就是這樣子了,提供一個(gè)默認(rèn)的處理方法,也留有一個(gè)用戶自定義處理異常的接口。

3. SGI STL 內(nèi)置輕量級(jí)內(nèi)存池的實(shí)現(xiàn)

第一級(jí)配置器__malloc_alloc_template僅僅只是對(duì)malloc的一層封裝,沒(méi)有考慮可能出現(xiàn)的內(nèi)存碎片化問(wèn)題。內(nèi)存碎片化問(wèn)題在大量申請(qǐng)小塊內(nèi)存是可能非常嚴(yán)重,最終導(dǎo)致碎片化的空閑內(nèi)存無(wú)法充分利用。SGI 于是在第二級(jí)配置器__default_alloc_template中 內(nèi)置了一個(gè)輕量級(jí)的內(nèi)存池。 對(duì)于小內(nèi)存塊的申請(qǐng),從內(nèi)置的內(nèi)存池中分配。然后維護(hù)一些空閑內(nèi)存塊的鏈表(簡(jiǎn)記為空閑鏈表,free list),小塊內(nèi)存使用完后都回收到空閑鏈表中,這樣如果新來(lái)一個(gè)小內(nèi)存塊申請(qǐng),如果對(duì)應(yīng)的空閑鏈表不為空,就可以從空閑鏈表中分配空間給用戶。具體而言SGI默認(rèn)最大的小塊內(nèi)存大小為128bytes,并設(shè)置了128/8=16 個(gè)free list,每個(gè)list 分別維護(hù)大小為 8, 16, 24, …, 128bytes 的空間內(nèi)存塊(均為8的整數(shù)倍),如果用戶申請(qǐng)的空間大小不足8的倍數(shù),則向上取整。

SGI STL內(nèi)置內(nèi)存池的實(shí)現(xiàn)請(qǐng)看__default_alloc_template中被定義為 private 的這些成員變量和方法(去掉了部分預(yù)處理代碼和互斥處理的代碼):

private:
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
    enum {_ALIGN = 8}; // 對(duì)齊大小
    enum {_MAX_BYTES = 128}; // 最大有內(nèi)置內(nèi)存池來(lái)分配的內(nèi)存大小
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN  // 空閑鏈表個(gè)數(shù)
# endif
  static size_t  _S_round_up(size_t __bytes) // 不是8的倍數(shù),向上取整
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
__PRIVATE:
  union _Obj { // 空閑鏈表的每個(gè)node的定義
        union _Obj* _M_free_list_link;
        char _M_client_data[1];   };
  static _Obj* __STL_VOLATILE _S_free_list[]; // 空閑鏈表數(shù)組
  static size_t _S_freelist_index(size_t __bytes) { // __bytes 對(duì)應(yīng)的free list的index
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }
  static void* _S_refill(size_t __n); // 從內(nèi)存池中申請(qǐng)空間并構(gòu)建free list,然后從free list中分配空間給用戶
  static char* _S_chunk_alloc(size_t __size, int& __nobjs); // 從內(nèi)存池中分配空間
  static char* _S_start_free;  // 內(nèi)存池空閑部分的起始地址
  static char* _S_end_free; // 內(nèi)存池結(jié)束地址
  static size_t _S_heap_size; // 內(nèi)存池堆大小,主要用于配置內(nèi)存池的大小

函數(shù)_S_refill的邏輯是,先調(diào)用_S_chunk_alloc從內(nèi)存池中分配20塊小內(nèi)存(而不是用戶申請(qǐng)的1塊),將這20塊中的第一塊返回給用戶,而將剩下的19塊依次鏈接,構(gòu)建一個(gè)free list。這樣下次再申請(qǐng)同樣大小的內(nèi)存就不用再?gòu)膬?nèi)存池中取了。有了_S_refill,用戶申請(qǐng)空間時(shí),就不是直接從內(nèi)存池中取了,而是從 free list 中取。因此allocate和reallocate在相應(yīng)的free list為空時(shí)都只需直接調(diào)用_S_refill就行了。其中_S_refill和_S_chunk_alloc這兩個(gè)函數(shù)是該內(nèi)存池機(jī)制的核心。

__default_alloc_template對(duì)外提供的 public 的接口有allocate,deallocate和reallocate這三個(gè),其中涉及內(nèi)存分配的allocate和reallocate的邏輯思路是,首先看申請(qǐng)的size(已round up)對(duì)應(yīng)的free list是否為空,如果為空,則調(diào)用_S_refill來(lái)分配,否則直接從對(duì)應(yīng)的free list中分配。而deallocate的邏輯是直接將空間插入到相應(yīng)free list的最前面。

這里默認(rèn)是依次申請(qǐng)20塊,但如果內(nèi)存池空間不足以分配20塊時(shí),會(huì)盡量分配足夠多的塊,這些處理都在_S_chunk_alloc函數(shù)中。該函數(shù)的處理邏輯如下(源代碼這里就不貼了):

1) 能夠分配20塊

從內(nèi)存池分配20塊出來(lái),改變_S_start_free的值,返回分配出來(lái)的內(nèi)存的起始地址

2) 不足以分配20塊,但至少能分配一塊

分配經(jīng)量多的塊數(shù),改變_S_start_free的值,返回分配出來(lái)的內(nèi)存的起始地址

3) 一塊也分配不了

首先計(jì)算新內(nèi)存池大小size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
將現(xiàn)在內(nèi)存池中剩余空間插入到適當(dāng)?shù)膄ree list中調(diào)用malloc來(lái)獲取一大片空間作為新的內(nèi)存池:

– 如果分配成功,則調(diào)整_S_end_free和_S_heap_size的值,并重新調(diào)用自身,從新的內(nèi)存池中給用戶分配空間; – 否則,分配失敗,考慮從比當(dāng)前申請(qǐng)的空間大的free list中分配空間,如果無(wú)法找不到這樣的非空f(shuō)ree list,則調(diào)用第一級(jí)配置器的allocate,看oom機(jī)制能否解決問(wèn)題。

SGI STL的輕量級(jí)內(nèi)存池的實(shí)現(xiàn)就是醬紫了,其實(shí)并不復(fù)雜。

4. SGI STL 內(nèi)存池在多線程下的互斥訪問(wèn)

最后,我們來(lái)看看SGI STL中如何處理多線程下對(duì)內(nèi)存池互斥訪問(wèn)的(實(shí)際上是對(duì)相應(yīng)的free list進(jìn)行互斥訪問(wèn),這里訪問(wèn)是只需要對(duì)free list進(jìn)行修改的訪問(wèn)操作)。在SGI的第二級(jí)配置器中與內(nèi)存池互斥訪問(wèn)相關(guān)的就是_Lock這個(gè)類了,它僅僅只包含一個(gè)構(gòu)造函數(shù)和一個(gè)析構(gòu)函數(shù),但這兩個(gè)函數(shù)足夠了。在構(gòu)造函數(shù)中對(duì)內(nèi)存池加鎖,在析構(gòu)函數(shù)中對(duì)內(nèi)存池解鎖:

//// in __default_alloc_template
# ifdef __STL_THREADS
    static _STL_mutex_lock _S_node_allocator_lock; // 互斥鎖變量
# endif
class _Lock {
    public:
        _Lock() { __NODE_ALLOCATOR_LOCK; }
        ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
};
//// in preprocess
#ifdef __STL_THREADS
# include <stl_threads.h> // stl 的線程,只是對(duì)linux或windows線程的一個(gè)封裝
# define __NODE_ALLOCATOR_THREADS true
# ifdef __STL_SGI_THREADS
#   define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
                { _S_node_allocator_lock._M_acquire_lock(); }  // 獲取鎖
#   define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
                { _S_node_allocator_lock._M_release_lock(); }  // 釋放鎖
# else /* !__STL_SGI_THREADS */
#   define __NODE_ALLOCATOR_LOCK \
        { if (threads) _S_node_allocator_lock._M_acquire_lock(); }
#   define __NODE_ALLOCATOR_UNLOCK \
        { if (threads) _S_node_allocator_lock._M_release_lock(); }
# endif
#else /* !__STL_THREADS */
#   define __NODE_ALLOCATOR_LOCK
#   define __NODE_ALLOCATOR_UNLOCK
#   define __NODE_ALLOCATOR_THREADS false
#endif

由于在__default_alloc_template的對(duì)外接口中,只有allocate和deallocate中直接涉及到對(duì)free list進(jìn)行修改的操作,所以在這兩個(gè)函數(shù)中,在對(duì)free list進(jìn)行修改之前,都要實(shí)例化一個(gè)_Lock的對(duì)象__lock_instance,此時(shí)調(diào)用構(gòu)造函數(shù)進(jìn)行加鎖,當(dāng)函數(shù)結(jié)束時(shí),的對(duì)象__lock_instance自動(dòng)析構(gòu),釋放鎖。這樣,在多線程下,可以保證free list的一致性。

以上就是淺談C++空間配置器allocator的詳細(xì)內(nèi)容,更多關(guān)于C++空間配置器allocator的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 使用C++實(shí)現(xiàn)鏈表元素的反轉(zhuǎn)

    使用C++實(shí)現(xiàn)鏈表元素的反轉(zhuǎn)

    反轉(zhuǎn)鏈表是鏈表操作中一個(gè)經(jīng)典的問(wèn)題,也是面試中常見(jiàn)的考題,本文將從思路到實(shí)現(xiàn)一步步地講解如何實(shí)現(xiàn)鏈表的反轉(zhuǎn),幫助初學(xué)者理解這一操作,我們將使用C++代碼演示具體實(shí)現(xiàn),同時(shí)分析時(shí)間復(fù)雜度和空間復(fù)雜度,需要的朋友可以參考下
    2025-02-02
  • C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官

    C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官

    這篇文章主要為大家介紹了C/C++哈希表優(yōu)化題解997找到小鎮(zhèn)的法官示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-12-12
  • C++二維數(shù)組中的查找算法示例

    C++二維數(shù)組中的查找算法示例

    這篇文章主要介紹了C++二維數(shù)組中的查找算法,結(jié)合實(shí)例形式分析了C++二維數(shù)組進(jìn)行查找的原理與具體實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2017-05-05
  • C語(yǔ)言一看就懂的選擇與循環(huán)語(yǔ)句及函數(shù)介紹

    C語(yǔ)言一看就懂的選擇與循環(huán)語(yǔ)句及函數(shù)介紹

    函數(shù)是一個(gè)功能模塊,它把實(shí)現(xiàn)某個(gè)功能的代碼塊包含起來(lái),并起一個(gè)函數(shù)名,供別人調(diào)用,如printf函數(shù),如system函數(shù)。是程序運(yùn)行當(dāng)中包裝起來(lái)的一個(gè)步驟;選擇與循環(huán)是編程中最常用的結(jié)構(gòu),本篇文章用最簡(jiǎn)單的文字帶你了解它們
    2022-04-04
  • C語(yǔ)言結(jié)構(gòu)體(struct)常見(jiàn)使用方法(細(xì)節(jié)問(wèn)題)

    C語(yǔ)言結(jié)構(gòu)體(struct)常見(jiàn)使用方法(細(xì)節(jié)問(wèn)題)

    這篇文章主要介紹了C語(yǔ)言結(jié)構(gòu)體(struct)常見(jiàn)使用方法(細(xì)節(jié)問(wèn)題),需要的朋友可以參考下
    2017-03-03
  • shared_ptr線程安全性全面分析

    shared_ptr線程安全性全面分析

    正如boost文檔所宣稱的,boost為shared_ptr提供了與內(nèi)置類型同級(jí)別的線程安全性。這包括:1. 同一個(gè)shared_ptr對(duì)象可以被多線程同時(shí)讀取。2. 不同的shared_ptr對(duì)象可以被多線程同時(shí)修改成
    2013-09-09
  • C語(yǔ)言內(nèi)存泄漏常見(jiàn)情況及解決方案詳解

    C語(yǔ)言內(nèi)存泄漏常見(jiàn)情況及解決方案詳解

    這篇文章主要為大家介紹了C語(yǔ)言內(nèi)存泄漏常見(jiàn)情況及解決方案詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • c++定義全局變量詳解

    c++定義全局變量詳解

    這篇文章主要給大家介紹了C++語(yǔ)言中定義全局變量,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。
    2021-10-10
  • C++如何實(shí)現(xiàn)廣義表詳解

    C++如何實(shí)現(xiàn)廣義表詳解

    廣義表是非線性結(jié)構(gòu),其定義是遞歸的。那么下面跟著小編一起看看如何用C++實(shí)現(xiàn)廣義表,有需要的可以參考借鑒。
    2016-08-08
  • VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法

    VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法

    這篇文章主要介紹了VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法,對(duì)于理解windows程序運(yùn)行原理的進(jìn)程問(wèn)題有一定的幫助,需要的朋友可以參考下
    2014-07-07

最新評(píng)論

星座| 田东县| 安平县| 灵璧县| 石柱| 鲁甸县| 公安县| 呼图壁县| 襄城县| 中西区| 大名县| 昌黎县| 喀喇沁旗| 南城县| 洛川县| 上林县| 阿勒泰市| 锦屏县| 西平县| 兴海县| 扬中市| 岳普湖县| 资兴市| 长汀县| 毕节市| 迁安市| 二手房| 正定县| 开原市| 嘉鱼县| 丹寨县| 灌阳县| 沾化县| 土默特右旗| 哈尔滨市| 崇阳县| 西平县| 红安县| 北安市| 上高县| 南阳市|