关于我读.NET源码那些事

日常更新维护电脑常用软件的时候看到 dnSpy 似乎很久没有更新了, 于是去 GitHub 上看了看, 发现作者已经把它 archive 了, 于是带着些许震惊下载了最新的版本。之后随便找个 .NET 应用反编译了一下, 看着 System 命名空间, 突然生出了好奇心:“那些类是怎么实现的呢?”

今天遇到了个小问题, 询问学长过程中才想起来 .NET 是在 GitHub 上开源的东西:.NET Runtime, 大可以直接翻找其源代码, 学长又提供了一个看 .NET 源码的网站:.NET Source Browser

此篇文章并未完全结束, 以后更新。

Stack

Link to Stack.cs

点着点着, 翻到了 Stack 类的实现, 也算是比较好奇这个入门级的数据结构是怎么实现的, 于是找了几个好奇的方法看了起来。

1
2
3
4
5
6
7
8
9
10
11
12
// Pops an item from the top of the stack.
// If the stack is empty, Pop throws an InvalidOperationException.
public virtual object? Pop()
{
if (_size == 0)
throw new InvalidOperationException(SR.InvalidOperation_EmptyStack);

_version++;
object? obj = _array[--_size];
_array[_size] = null; // Free memory quicker.
return obj;
}

Pop() 函数, 这个实现也算是意料之中

1
2
3
4
5
6
7
8
9
10
11
12
// Pushes an item to the top of the stack.
public virtual void Push(object? obj)
{
if (_size == _array.Length)
{
object[] newArray = new object[2 * _array.Length];
Array.Copy(_array, newArray, _size);
_array = newArray;
}
_array[_size++] = obj;
_version++;
}

为什么要把空间成2倍增长

看到这段代码我疑惑了, 为什么栈大小会成倍增长呢? 查询相关资料后得到了不少的结论, 其中包含空间是2的倍数的时候有利于资源的回收等等, 这里简单整理一下原因, 具体细节可以参照Reference中知乎的解答。

首先考虑成倍增长这件事, 为什么不每一次增长一个固定的大小呢?

若以成倍的方式增长, 每次增长因子为$m$那么想要向动态数组中添加进入$n$个元素所需扩容的次数最坏即$log_m(n)$次, 在第$i$次重新分配内存的时候会导致复制$m^i$即当前旧数组大小的元素, 于是$n$次添加操作花费的时间复杂度为:

$$\sum_{i=1}^{log_m n} m ^ i \approx \frac{nm}{m -1}$$

由均摊分析可知它的时间复杂度是$\Theta(1)$

而如果每次增加固定大小$k$, 则第$i$次增加时候需要复制的数量就是$ki$, 那么想要向动态数组中添加进入$n$个元素所需扩容的次数即$\frac{n}{k}$次, 于是$n$次添加操作花费的时间复杂度为:

$$\sum_{i = 1}^{\frac{n}{k}} ki = k \sum_{i = 1}^{\frac{n}{k}} i$$

这是一个关于$n$的二次多项式, 由均摊分析可知它的时间复杂度是$\Theta(n)$

因而成倍增加时候可以保证常数级别的时间复杂度

而至于为什么要用2倍, 其原因分析就比较众说纷纭了。

这是另一个比较复杂的问题, 有人说一直以2的倍数扩容利于内存对齐且利于垃圾回收的效率, 有人说以2为倍数会导致以前的内存无法重用, 因此如今很多编译器实现的时候降低到了1.5, 对此我仍有很多疑惑, 故在此不班门弄斧, 发表自己的见解了。

PS: 至于为什么默认大小是10嘛…开心就好

1
private const int _defaultCapacity = 10;

维护_version变量的意义

看这段代码的另一个引起我好奇的地方是为什么要维护一个_version变量, 初看反编译的代码并没有搞明白, 而后搜索和翻找源码的时候看到了:

1
2
3
private object?[] _array; // Storage for stack elements. Do not rename (binary serialization)
private int _size; // Number of items in the stack. Do not rename (binary serialization)
private int _version; // Used to keep enumerator in sync with collection. Do not rename (binary serialization)

它的作用主要是保持迭代器和集合一致, 防止出现一些意外的修改操作, 如在foreach中:

If foreach didn’t force read-only access then your binary tree would degenerate into a tree. The entire data structure would be in disarray.

Others

这里是一些翻阅源码时候的小插曲:

  1. 原来不止我会这样写代码(
    1
    while((num3 = (int)(*ptr2)) != 0)
  2. 居然有如此粗暴的代码
    1
    2
    3
    4
    public object Clone()
    {
    return this;
    }
  3. 自作聪明的以为避免了使用IndexOf
    1
    2
    3
    4
    public bool Contains(string value)
    {
    return this.IndexOf(value, StringComparison.Ordinal) >= 0;
    }
  4. 一段第一次看起来“卧槽牛逼”, 细看之后“啊, 就这”的代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    if (startIndex % 8 == 0)
    {
    return *(long*)ptr;
    }
    if (BitConverter.IsLittleEndian)
    {
    int num = (int)(*ptr) | (int)ptr[1] << 8 | (int)ptr[2] << 16 | (int)ptr[3] << 24;
    int num2 = (int)ptr[4] | (int)ptr[5] << 8 | (int)ptr[6] << 16 | (int)ptr[7] << 24;
    return (long)((ulong)num | (ulong)((ulong)((long)num2) << 32));
    }
    int num3 = (int)(*ptr) << 24 | (int)ptr[1] << 16 | (int)ptr[2] << 8 | (int)ptr[3];
    int num4 = (int)ptr[4] << 24 | (int)ptr[5] << 16 | (int)ptr[6] << 8 | (int)ptr[7];
    return (long)((ulong)num4 | (ulong)((ulong)((long)num3) << 32));

Reference

  1. C++ STL 中 vector 内存用尽后, 为什么每次是 2 倍的增长, 而不是 3 倍或其他值?
  2. STL中vector 扩容为什么要以1.5倍或者2倍扩容?
  3. What is the use of “_version” within collections? [duplicate]
  4. Enumerator.MoveNext() throws ‘Collection was Modified’ on first call