C# List.Capacity 深入剖析

引子

之前在网络上看到，C++ 中若 Vector 在初始化或者使用前，指定 Capacity 大小的话，会减少由于新增元素导致超出 Capacity 时的元素拷贝。(以下 源码均为 MSVC C++ 编译器下)

void test_with_no_reserve(size_t loop_count) {
  std::vector<std::string> aa{};

  for (size_t i = 0; i < loop_count; ++i) {
    aa.emplace_back(std::to_string(i));
  }
}

void test_with_capacity(size_t loop_count) {
  std::vector<std::string> a{};
  a.reserve(loop_count);

  for (size_t i = 0; i < loop_count; ++i) {
    a.emplace_back(std::to_string(i));
  }
}

两者在执行效率上 1000 * 10000 loop_count
test_with_no_reserve: 24486 ms
test_with_capacity: 11989 ms

可以看下 Vector Capacity 的自增算法如下所示：

_CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
        // given _Oldcapacity and _Newsize, calculate geometric growth
        const size_type _Oldcapacity = capacity();
        const auto _Max              = max_size();
        if (_Oldcapacity > _Max - _Oldcapacity / 2) {
            return _Max; // geometric growth would overflow
        }
        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
        if (_Geometric < _Newsize) {
            return _Newsize; // geometric growth would be insufficient
        }
        return _Geometric; // geometric growth is sufficient
    }

在 C++ 中，Vector 提供了 Reserve 这个方法。（以下 C++ 源码均为 MSVC 下的源码），用于初始 Vector Capacity 的设置。在 C++11 之前网上搜索 push_back 和 emplace_back 时可能都会推荐后者，其实上 C++11 之后，两者其实都是调用 后者的方法 emplace_back。

_CONSTEXPR20 void _Reallocate_exactly(const size_type _Newcapacity) {
        // set capacity to _Newcapacity (without geometric growth), provide strong guarantee
        auto& _Al         = _Getal();
        auto& _My_data    = _Mypair._Myval2;
        pointer& _Myfirst = _My_data._Myfirst;
        pointer& _Mylast  = _My_data._Mylast;
        const auto _Size = static_cast<size_type>(_Mylast - _Myfirst);
        const pointer _Newvec = _Al.allocate(_Newcapacity);
        _TRY_BEGIN
        if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
            _Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
        } else {
            _Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
        }
        _CATCH_ALL
        _Al.deallocate(_Newvec, _Newcapacity);
        _RERAISE;
        _CATCH_END
        _Change_array(_Newvec, _Size, _Newcapacity);
    }

_Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
_Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
这两个的区别简述一下，一个是调用了 std::move 也就是对象的移动拷贝构造函数，一个是调用了 对象的拷贝构造函数。
std::move 只是相当于转移了对象的使用权，并不重新创建对象，所以会比 copy_constructor 高效。
Move declare: _ty(_ty &&) (右值引用)
copy constructor declare: _ty(const _ty&)

跑偏到了C++, 现在开始讲 C# 命名空间 Collections.Generic 下的 List
，List

可以说是大家用的最多的Collection 中的一个泛型类。我们还是从 Capacity 开始。

Path 在 dotnet/runtime repo下 src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

C# List
.Capacity

 public int Capacity {
            get {
                Contract.Ensures(Contract.Result<int>() >= 0);
                return _items.Length;
            }
            set {
                if (value < _size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
                }
                Contract.EndContractBlock();
 
                if (value != _items.Length) {
                    if (value > 0) {
                        T[] newItems = new T[value];
                        if (_size > 0) {
                            Array.Copy(_items, 0, newItems, 0, _size);
                        }
                        _items = newItems;
                    }
                    else {
                        _items = _emptyArray;
                    }
                }
            }
        }

其中 Array.Copy 实际上是调用了 C++ 底层的 memmove 方法

List
.Add Capacity 自增算法

 private void EnsureCapacity(int min) {
            if (_items.Length < min) {
                int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
                // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
                // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
                if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
                if (newCapacity < min) newCapacity = min;
                Capacity = newCapacity;
            }
        }

与 C++ 自增算法的对比

C++：const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

C# ：DefaultCapacity : 2 * _items.Length;
C# 看来还是比较粗狂的，对于分配空间上，C++ 的话比C#，每次在自增超出空间的分配上默认会多 50%。

Capacity 代码中的分析

T[] newItems = new T[value];
这里我们知道，创建的是一个新的数组，大小就是为 Capacity 的大小，并且为引用类型，分配在堆上，由GC管理其空间的释放。
那么就是比如我有一个1000大小的数组，DefaultCapacity = 4;
那么其需要进行 Array.Copy 的次数为 2^10 = 1024
4->8->16->32->64->128->256->512->1024 八次。
若事先指定了 Capacity 则只有在 初始化这个 List 时，申请了这些空间。

原文地址：http://www.cnblogs.com/xiyin/p/16796778.html