夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
C++STL中vector的扩容机制能用realloc()吗?

前言

昨天刷知乎看到一个有意思的问题,大意是

C++STL中vector的push_back()扩容机制为什么不考虑使用C语言的自带函数realloc()实现?

对于一个看过部分STL源码的人,还是对vector有一定了解的。vector的内存管理使用的是STL中的allocator,而其一种扩容机制是当size > capacity时vector通过allocator申请大小为2*capacity的空间,并将当前数据拷贝到新申请的空间中。说来惭愧,我一直对malloc()家族的实现没有深入了解过,那就现查一下。

Reallocate memory block

void* realloc (void* ptr, size_t size);

Changes the size of the memory block pointed to by ptr.

The function may move the memory block to a new location (whose address is returned by the function).

The content of the memory block is preserved up to the lesser of the new and old sizes, even if the block is moved to a new location. If the new size is larger, the value of the newly allocated portion is indeterminate.

In case that ptr is a null pointer, the function behaves like malloc, assigning a new block of size bytes and returning a pointer to its beginning.

If size is zero, the return value depends on the particular library implementation: it may either be a null pointer or some other location that shall not be dereferenced.

If the function fails to allocate the requested block of memory, a null pointer is returned, and the memory block pointed to by argument ptr is not deallocated (it is still valid, and with its contents unchanged).

我来简单分析一下。就单纯实现而言,vector的确可以只使用realloc()实现,下面是一个极简版本

template <class T>
class vector{
private:
    ...
    T* begin;
    T* end;
    size_t size;
    size_t capacity;
    ...
public:
    ...
    void push_back(const T& x){
        if(size==capacity)
            begin = realloc(begin,(capacity+1)*sizeof(T));
        capacity++;
        end = begin + size;
        *end = x;
        end++;
        size++;
    }
    ...
};

那么显然,在size==capacity时不断地push_back会不停地调用realloc(),即使每次realloc()调用时在vector尾部都有足够的空间可以直接分配,其效率肯定较一次性设置capacity=2*capacity低。那如果改进一下,将realloc()参数中的size由capacity+1变为更大的值,比如2*capacity,它的情况会不会比原先使用allocator效率高呢?毕竟realloc()的空间是有可能在尾部直接分配的啊
。。。

TriviallyCopyable

为什么这里会出现TriviallyCopyable这个东西呢?其实我也不知道
可平凡复制的要求如下

  • 每个复制构造函数均为平凡或弃置的
  • 每个移动构造函数均为平凡或弃置的
  • 每个复制赋值运算符均为平凡或弃置的
  • 每个移动赋值运算符均为平凡或弃置的
  • 至少一个复制构造函数、移动构造函数、复制赋值运算符或移动赋值运算符未弃置
  • 平凡而未弃置的析构函数
    这意味着该类没有虚函数或虚基类。
    标量类型和可平凡复制 (TriviallyCopyable) 对象的数组也是可平凡复制 (TriviallyCopyable) 的。

我们再来看看其中平凡复制构造函数的要求

  • 它不是用户提供的(即它是隐式定义或预置的),且若它被预置,则其签名与隐式定义的相同 (C++14 前);
  • T 没有虚成员函数;
  • T 没有虚基类;
  • 为 T 的每个直接基类选择的复制构造函数都是平凡的;
  • 为 T 的每个类类型(或类类型数组)的非静态成员选择的复制构造函数都是平凡的;

这和vector有什么关系呢?如果使用使用realloc()为其push_back扩容,让我们来看看realloc()的具体实现。emmm代码有点长,节选自glibc/malloc.c

void *
__libc_realloc (void *oldmem, size_t bytes)
{
  mstate ar_ptr;
  INTERNAL_SIZE_T nb;         /* padded request size */

  void *newp;             /* chunk to return */

  void *(*hook) (void *, size_t, const void *) =
    atomic_forced_read (__realloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));

#if REALLOC_ZERO_BYTES_FREES
  if (bytes == 0 && oldmem != NULL)
    {
      __libc_free (oldmem); return 0;
    }
#endif

  /* realloc of null is supposed to be same as malloc */
  if (oldmem == 0)
    return __libc_malloc (bytes);

  /* chunk corresponding to oldmem */
  const mchunkptr oldp = mem2chunk (oldmem);
  /* its size */
  const INTERNAL_SIZE_T oldsize = chunksize (oldp);

  if (chunk_is_mmapped (oldp))
    ar_ptr = NULL;
  else
    {
      MAYBE_INIT_TCACHE ();
      ar_ptr = arena_for_chunk (oldp);
    }

  /* Little security check which won't hurt performance: the allocator
     never wrapps around at the end of the address space.  Therefore
     we can exclude some size values which might appear here by
     accident or by "design" from some intruder.  We need to bypass
     this check for dumped fake mmap chunks from the old main arena
     because the new malloc may provide additional alignment.  */
  if ((__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
       || __builtin_expect (misaligned_chunk (oldp), 0))
      && !DUMPED_MAIN_ARENA_CHUNK (oldp))
      malloc_printerr ("realloc(): invalid pointer");

  if (!checked_request2size (bytes, &nb))
    {
      __set_errno (ENOMEM);
      return NULL;
    }

  if (chunk_is_mmapped (oldp))
    {
      /* If this is a faked mmapped chunk from the dumped main arena,
     always make a copy (and do not free the old chunk).  */
      if (DUMPED_MAIN_ARENA_CHUNK (oldp))
    {
      /* Must alloc, copy, free. */
      void *newmem = __libc_malloc (bytes);
      if (newmem == 0)
        return NULL;
      /* Copy as many bytes as are available from the old chunk
         and fit into the new size.  NB: The overhead for faked
         mmapped chunks is only SIZE_SZ, not 2 * SIZE_SZ as for
         regular mmapped chunks.  */
      if (bytes > oldsize - SIZE_SZ)
        bytes = oldsize - SIZE_SZ;
      memcpy (newmem, oldmem, bytes);
      return newmem;
    }

      void *newmem;

#if HAVE_MREMAP
      newp = mremap_chunk (oldp, nb);
      if (newp)
        return chunk2mem (newp);
#endif
      /* Note the extra SIZE_SZ overhead. */
      if (oldsize - SIZE_SZ >= nb)
        return oldmem;                         /* do nothing */

      /* Must alloc, copy, free. */
      newmem = __libc_malloc (bytes);
      if (newmem == 0)
        return 0;              /* propagate failure */

      memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
      munmap_chunk (oldp);
      return newmem;
    }

  if (SINGLE_THREAD_P)
    {
      newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
      assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
          ar_ptr == arena_for_chunk (mem2chunk (newp)));

      return newp;
    }

  __libc_lock_lock (ar_ptr->mutex);

  newp = _int_realloc (ar_ptr, oldp, oldsize, nb);

  __libc_lock_unlock (ar_ptr->mutex);
  assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
          ar_ptr == arena_for_chunk (mem2chunk (newp)));

  if (newp == NULL)
    {
      /* Try harder to allocate memory in other arenas.  */
      LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
      newp = __libc_malloc (bytes);
      if (newp != NULL)
        {
          memcpy (newp, oldmem, oldsize - SIZE_SZ);
          _int_free (ar_ptr, oldp, 0);
        }
    }

  return newp;
}

可见当其不能进行原地扩充时,使用memcpy()函数申请新的内存空间,而memcpy()有如下要求:

若对象潜在重叠或不可平凡复制 (TriviallyCopyable) ,则 memcpy 的行为未指定而且可能未定义

vector中存在非平凡拷贝/移动构造函数,故使用realloc()扩展内存是有问题的,尤其对于一些存在引用自身的类型如std::string,在拷贝的时候很可能会出错。

allocator VS realloc()

抛开上文所述的可平凡复制不谈,我们假设存在一些情况使得realloc()可以在vector中正常工作(事实上确实存在,此处不做深入讨论),那么vector实现所使用的空间配置器和这里讨论的realloc()函数有什么差别呢?

allocator

我们要搞清楚这个allocator是干什么的,它在STL中起到一个怎样的作用等等问题。
这里发现 github.com/steveLauwh/SGI-STL-master/The Annotated STL Sources V3.3/allocator/README.md(这个repo已经被删除)中讲的很清楚,这里直接进行引用


配置器(allocator)

配置器:负责空间配置与管理,从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。

空间配置器:整个 STL 的操作对象(所有的数值)都存放在容器之内,而容器一定需要配置空间以存放内容。

具有次配置力(sub-allocation)的 SGI 空间配置器

SGI STL 空间配置器的结构

SGI STL 的配置器,其名称是 alloc 而不是 allocator,而且不接受任何参数。

SGI STL 的每一个容器都已经指定其缺省的空间配置器为 alloc。

template <class T, class Alloc = alloc>  // 缺省使用 alloc 为配置器
class vector {...};

vector<int, std::alloc> iv; 
  • —-SGI 标准的空间配置器,std::allocator

    allocator 只是基层内存配置/释放行为(::operator::new 和 ::operator::delete)的一层薄薄的包装,并没有考虑到任何效率上的强化。

  • SGI 特殊的空间配置器,std::alloc

    • :定义了全局函数 construct() 和 destroy(),负责对象的构造和析构。
    • :定义了一、二级配置器,配置器名为 alloc。
    • :定义了全局函数,用来填充(fill)或复制(copy)大块内存数据。
  • 构造和析构基本工具

    具体看 <stl_construct.h> 源码,功能是构造和析构操作。

  • 空间的配置和释放,std::alloc

    • 向 system heap 要求空间
    • 考虑多线程(multi-threads)状态
    • 考虑内存不足时的应变措施
    • 考虑过多 “小型区块” 可能造成的内存碎片问题

    对象构造前的空间配置 和 对象析构后的空间释放,具体看 <stl_alloc.h>。

SGI STL 空间配置器的分析

考虑到小型区块可能造成内存碎片问题,SGI 采用两级配置器,第一级配置器直接使用 malloc() 和 free() 实现;第二级配置器使用 memory pool 内存池管理。

第二级配置器的原理:

  • 当配置区块超过 128 bytes,就使用第一级配置器
  • 当配置区块小于 128 bytes,使用内存池管理
enum {_ALIGN = 8};  // 小型区块的上调边界
enum {_MAX_BYTES = 128}; // 小区区块的上限
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN  free-list 的个数

// free-list 的节点结构,降低维护链表 list 带来的额外负担
union _Obj {
    union _Obj* _M_free_list_link;  // 利用联合体特点
    char _M_client_data[1];    /* The client sees this. */
};
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];  // 注意,它是数组,每个数组元素包含若干相等的小额区块

其中 free-list 是指针数组,16 个数组元素,就是 16 个 free-list,各自管理大小分别为 8, 16, 24, 32,…128 bytes(8 的倍数)的小额区块。

小额区块的结构体 union _Obj 使用链表连接起来。

配置器负责配置,同时也负责回收。


对于SGI STL中allocator的实现,这里就不做深入分析了。总结来说,allocator对以下几种情况进行了优化

  • 多线程的问题
  • 内存不足时的应变措施
  • 过多小型区块可能造成的内存碎片问题

realloc()的情况在之前就介绍过了。抛去可平凡复制的问题,对比来看,在小块且无多线程对于内存的干扰情况下,realloc()要比SGI STL的次级空间配置器高效的多;而在大块内存分配的情况下,realloc()会调用malloc()实现内存申请,与SGI STL allocator的一级配置器相同,效率基本相同,此时专门针对container设计的allocator在内存复制时会使用专门的函数处理非POD的复制问题,更占有优势。

总结

综合来说,realloc()函数作为可以直接原地扩充的内存分配函数,在部分情况中确实展现出极高的扩充效率,然而其对于非平凡复制、内存碎片和多线程等问题并没有有效的解决方案。allocator的综合性能依然较realloc优越。

以上为个人观点,欢迎大家指正与交流!

暂无评论

发送评论 编辑评论


				
上一篇
下一篇