c++ - basic_string的_S_create函数中的__pagesize、__subpagesize、__malloc_header_size是什么意思

Question

1. stl 的basic_string 中的_S_create 函数使用这三个变量来计算实际分配的大小。有谁知道为什么？

2. _S_create 的接口是

   _Rep* _S_create(size_type __capacity, size_type __old_capacity, const _Alloc& __alloc)

为什么需要 __old_capacity 参数？

PS。这是gnu stl。

Answer 1

实际代码很好地解释了它是如何使用_PageSizeand的_malloc_header_size，如果您只是懒得阅读评论（而且不阅读评论是相当可耻的，毕竟有人可能花更多的时间来写这些评论而不是我写这个答案）：

  // The standard places no restriction on allocating more memory
  // than is strictly needed within this layer at the moment or as
  // requested by an explicit application call to reserve().

  // Many malloc implementations perform quite poorly when an
  // application attempts to allocate memory in a stepwise fashion
  // growing each allocation size by only 1 char.  Additionally,
  // it makes little sense to allocate less linear memory than the
  // natural blocking size of the malloc implementation.
  // Unfortunately, we would need a somewhat low-level calculation
  // with tuned parameters to get this perfect for any particular
  // malloc implementation.  Fortunately, generalizations about
  // common features seen among implementations seems to suffice.

  // __pagesize need not match the actual VM page size for good
  // results in practice, thus we pick a common value on the low
  // side.  __malloc_header_size is an estimate of the amount of
  // overhead per memory allocation (in practice seen N * sizeof
  // (void*) where N is 0, 2 or 4).  According to folklore,
  // picking this value on the high side is better than
  // low-balling it (especially when this algorithm is used with
  // malloc implementations that allocate memory blocks rounded up
  // to a size which is a power of 2).

Sebastian 做对了（尽管它的写法略有不同）：

  // The below implements an exponential growth policy, necessary to
  // meet amortized linear time requirements of the library: see
  // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
  // It's active for allocations requiring an amount of memory above
  // system pagesize. This is consistent with the requirements of the
  // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
__capacity = 2 * __old_capacity;

在__pagesize这里使用，将其四舍五入...

  const size_type __adj_size = __size + __malloc_header_size;
  if (__adj_size > __pagesize && __capacity > __old_capacity)
{
  const size_type __extra = __pagesize - __adj_size % __pagesize;
  __capacity += __extra / sizeof(_CharT);
  // Never allocate a string bigger than _S_max_size.
  if (__capacity > _S_max_size)
    __capacity = _S_max_size;
  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
}

我的实现没有_subpagesize，但我希望这是一个类似的舍入。

Answer 2

在不查看 libstdc++ 或询问任何有明确信息的人的情况下，一种可能的实现是

size_type __actual_capacity = max(__capacity, 2 * __old_capacity);
// do other stuff to create a _Rep.

这确保了几何增长，同时也保证了至少与绝对需要一样多的内存。