Ryuu 的个人博客

详情

Unity 对象的空检测

UnityEngine.Object 有其自定义的空检测方法。

因此 UnityEngine.Object 有两种空检测：

1. 检测 Unity 原生对象是否被销毁 (使用 UnityEngine.Object 自定义空检测)
2. 检测 Unity 对象是否初始化与正确引用 (使用 object.ReferenceEquals(monoBehaviour, null))

Unity 对象的生与死

原生对象与包装对象：

Unity 是基于 C/C++ 的引擎，GameObject 的所有实际信息 (name、component list、HideFlags 等等) 都存储在 C++ 对象中。此类对象被称为**”原生对象” (native object)**。

C# GameObject 所有的仅是指向原生对象的指针 (pointer)。此类对象被称为**”包装对象” (wrapper object)**。

C# 与 C++ 有不同的内存管理方式，这意味着包装对象与其包裹的原生对象有着不同的生命周期。

当原生对象已被销毁，包装对象依然存在时，将包装对象其与 null 比较，**UnityEngine 的 == 运算符严格执行 Unity object 底层的生命周期检查，返回 “true”**。

Real null 与 Fake null：

**在 Editor only 时，MonoBehaviour 不是 “real null” 而是 “fake null”**。[1]

Unity 在 fake null object 中存储信息。当执行其方法 (method)，或访问其属性 (property) 时，可提供更多的上下文信息：

在 fake null object 中存储信息，Unity 能够在检视窗口 (Inspector) 中高亮该 GameObject，并给出更多指引。如:”looks like you are accessing a non initialized field in this MonoBehaviour over here, use the inspector to make the field point to something” (看来您试图访问此 MonoBehaviour 的未实例化字段，请在检视窗口使其指向实例)。

若不在 fake null object 中存储信息，只能得到 NullReferenceException 与堆栈跟踪。并不知道具体是哪个带有 MonoBehaviour 的 GameObject 有字段为 null。

UnityEngine 的 == 运算符能够检测是否存在 fake null object。

Unity 相关代码

反编译获得，不是源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

// UnityEngine.Object
public static bool operator ==(Object x, Object y) => Object.CompareBaseObjects(x, y);

public static bool operator !=(Object x, Object y) => !Object.CompareBaseObjects(x, y);

public static implicit operator bool(Object exists) => !Object.CompareBaseObjects(exists, (Object) null);

public override bool Equals(object other)
{
    Object rhs = other as Object;
    return (!(rhs == (Object) null) || other == null || other is Object) && Object.CompareBaseObjects(this, rhs);
}

private static bool CompareBaseObjects(Object lhs, Object rhs)
{
  bool flag1 = (object) lhs == null;
  bool flag2 = (object) rhs == null;
  if (flag2 & flag1)
    return true;
  if (flag2)
    return !Object.IsNativeObjectAlive(lhs);
  return flag1 ? !Object.IsNativeObjectAlive(rhs) : lhs.m_InstanceID == rhs.m_InstanceID;
}

private static bool IsNativeObjectAlive(Object o)
{
  if (o.GetCachedPtr() != IntPtr.Zero)
    return true;
  return !(o is MonoBehaviour) && !(o is ScriptableObject) && Object.DoesObjectWithInstanceIDExist(o.GetInstanceID());
}

/// <summary>
///   <para>Returns the instance id of the object.</para>
/// </summary>
[SecuritySafeCritical]
public int GetInstanceID()
{
  this.EnsureRunningOnMainThread();
  return this.m_InstanceID;
}

private void EnsureRunningOnMainThread()
{
  if (!Object.CurrentThreadIsMainThread())
    throw new InvalidOperationException("EnsureRunningOnMainThread can only be called from the main thread");
}

private IntPtr GetCachedPtr() => this.m_CachedPtr;

[NativeMethod(IsFreeFunction = true, IsThreadSafe = true, Name = "UnityEngineObjectBindings::DoesObjectWithInstanceIDExist")]
[MethodImpl(MethodImplOptions.InternalCall)]
internal static extern bool DoesObjectWithInstanceIDExist(int instanceID);

[NativeMethod(IsFreeFunction = true, IsThreadSafe = true, Name = "CurrentThreadIsMainThread")]
[MethodImpl(MethodImplOptions.InternalCall)]
private static extern bool CurrentThreadIsMainThread();

如上所示，Unity 实现了自己的空判断，并将其应用于重载的 != 运算符、== 运算符、隐式 bool 转换运算符及重写的 System.Object 的 Equals(object obj) 中。

其中涉及许多的逻辑，如确保方法调用于主线程，指定实例 id 的 UnityEngine.Object 是否存在，缓存的指针是否为 IntPtr.Zero，比较的两 UnityEngine.Object 的 实例 id 是否相同。及其他的外部方法调用。因此，相比于 object.ReferenceEquals() 的调用会被编译器优化为简单的空检查，Unity的自定义比较需要执行许多逻辑，速度较慢。

编写规范

上文提到了 Unity 对象的两种 null 检测，编写代码时，一定要明确表意，确定为其中的一种。

特别的，C# 的空合并运算符与空条件运算符将会绕过 Unity 的生命周期检查，导致表意不明：[2]

空合并运算符

以下示例的表意不明确：是检查 gameObject 是否正确引用，还是检查原生 Unity 引擎对象是否已销毁？

1
2

// DON'T DO THIS!
var go = gameObject ?? CreateNewGameObject();

若目的是检查底层引擎对象的生命周期，则此代码不正确，因为生命周期检查被绕过。

使用显式 null 或 boolean 比较修复代码：

1
2
3

var go = gameObject != null ? gameObject : CreateNewGameObject();
// 也可使用隐式的 bool 转换运算符进行同样的检测
go = gameObject ? gameObject : CreateNewGameObject();

若目的是确保 gameObject 变量已被初始化并分配了有效的 C# 引用，推荐使用 object.ReferenceEquals()：

1

return !object.ReferenceEquals(gameObject, null) ? gameObject : CreateNewGameObject();

虽然稍显冗长，但表意十分明确。

空条件运算符

以下示例的表意同样不明确：

1
2

// DON'T DO THIS!
monoBehaviour?.Invoke("Attack", 1.0f);

同样的，若目的是简单地检查 monoBehaviour 变量是否已正确初始化与引用，推荐使用 object.ReferenceEquals()：

1
2

if (!object.ReferenceEquals(monoBehaviour, null))
  monoBehaviour.Invoke("Attack", 1.0f);

若目的是检查底层引擎对象的生命周期，推荐使用显式的 null 或 boolean 比较：

1
2
3
4
5

if (monoBehaviour != null)
  monoBehaviour.Invoke("Attack", 1.0f);
// 也可使用隐式的 bool 转换运算符
if (otherBehaviour)
  otherBehaviour.Invoke("Attack", 1.0f);

个人解决方案

如果只是想检测 GameObject 是否初始化与正确引用，可以考虑使用 unity 平台宏 以及 C# 扩展方法对 ReferenceEquals 进行封装。[3]

这样避免了在 editor 时 fake null object 引发的 ReferenceEquals 判断错误的问题，也提高了代码的可读性。

1
2
3
4
5
6
7
8

public static bool IsSet(this GameObject gameObject)
{
#if UNITY_EDITOR
	return gameObject;
#else
	return !ReferenceEquals(gameObject, null);
#endif
}

个人思考

Unity 在与 null 进行比较时判断原生对象是否存活，而是不是检测 C# 对象。这种设计是反直觉的，大多数用户未注意到这种自定义比较。Custom == operator, should we keep it? | Unity Blog Unity 自己的开发者都忘记了。

C# 的引用类型，若不是”值类” (Value class)，应采用默认的比较逻辑 (直接对引用进行比较)，不应重载的 !=、== 及隐式 bool 转换运算符，不应重写 System.Object 的 Equals(object obj) 方法。

UnityEngine.Object 的比较逻辑有把自己的本职工作做好 (直接对引用进行比较)，又做了其他的工作 (判断原生对象是否存活)，这不符合单一职责原则。导致了两种空判断的存在，造成了可能的语义不明，与潜在的性能下降。这样增添的逻辑也导致其表现与 C# 的空合并运算符和空条件运算符不一致。导致在使用 UnityEngine.Object 没法很好的使用这两种运算符。若使用，则表意不明确，若不使用，则降低了代码的可读性 (见编写规范)。

更好的方法可能是在 UnityEngine.Object 中加入 destroyed 这样的字段标识原生对象的存活情况。当用户想到知道时进行调用。[4]

参阅

Unity 的说明 Custom == operator, should we keep it? | Unity Blog

译文 Unity-自定义==运算符，我们应该保留它吗

Resharper-unity 的说明 Possible unintended bypass of lifetime check of underlying Unity engine object · JetBrains/resharper-unity Wiki

译文 Unity-Resharper-可能意外绕过Unity引擎对象的底层生命周期检查

?? 和 ??= 运算符 - C# 参考 | Microsoft Docs

成员访问运算符和表达式 Null 条件运算符 ?. 和 ?[] - C# 参考

扩展方法 - C# 编程指南 | Microsoft Docs

Real null 与 Fake null 的测试可见我的 github 仓库：UnityEngineObjectNullCheck (分别打包运行与编辑器运行对比区别)

注释

[1] 仅在编辑器中有这种情况。这也是为什么调用GetComponent() 查询不存在的组件时，有 C# 内存分配产生，因为此时 fake null object 中正在生成自定义警告字符串。

这也是为什么测试游戏需要打包测试，而不是在编辑器测试。为了给用户提供便利，编辑器中做了很多额外的工作 (用例、安全检查等)，但是牺牲了性能。

[2] 空合并运算符与空条件运算符是无法重载的，可能是因为这点，Unity 无法令其进行自定义的空检查

[3] 扩展方法 - C# 编程指南 | Microsoft Docs

[4] Unity 最终选择了不对其修改，而是修复由此带来的种种问题。

(Ryuu: 附上原文地址 : Possible unintended bypass of lifetime check of underlying Unity engine object · JetBrains/resharper-unity Wiki)

这是 Unity 特定的检查。此检查仅在 Unity 项目中运行。

若从 UnityEngine.Object 派生的类型使用空合并 (??) 或空传播或条件 (?.) 运算符，则会显示此警告。 这些运算符不会使用 UnityEngine.Object 上声明的自定义相等运算符，将绕过 Unity 原生(native)对象的存活检测。 为了阐明意图，最好使用显式 null 或 bool 比较，或调用 System.Object.ReferenceEquals()。

详情

从 UnityEngine.Object 派生的类型是托管 .NET 对象，在 C# 脚本中用于表示与使用原生 Unity 引擎对象。这两种类型的对象具有不同的生命周期。托管的 .NET 对象在没有更多引用时被垃圾收集，而本地 Unity 引擎对象在加载新场景或通过显式调用 UnityEngine.Object.Destroy() 时被销毁。这意味着托管的 .NET 对象指向的原生对象可能已被销毁。

UnityEngine.Object 类定义了自定义相等运算符，当与 null 进行比较时，这些运算符将检查底层原生 Unity 引擎对象是否已被破坏。换句话说， myMonoBehaviour == null 将检查是否已分配 myMonoBehaviour 变量，并且还将检查原生引擎对象是否已被销毁。可以使用布尔比较执行相同的检查，例如 if (myMonoBehaviour == true) 或 if (!myMonoBehaviour) 或是 if (myMonoBehaviour)。

如果使用空合并或条件运算符，则表意不明确，并且可能绕过预期的生命周期检查。如果打算进行生命周期检查，推荐使用与 null 或布尔比较的显式比较。若不打算进行生命周期检查，请调用 System.Object.ReferenceEquals() 以明确表意。注意，对 object.ReferenceEquals() 的调用被编译器优化为简单的空检查，比调用自定义相等运算符更快。

空合并运算符

以下示例的表意不明确：是检查 gameObject是否正确引用，还是检查原生 Unity 引擎对象是否已销毁？

1

var go = gameObject ?? CreateNewGameObject();

若目的是检查底层引擎对象的生命周期，则此代码不正确，因为生命周期检查被绕过。使用显式 null 或 boolean 比较修复代码：

1
2
3

var go = gameObject != null ? gameObject : CreateNewGameObject();
// 也可使用隐式的 bool 转换运算符进行同样的检测
go = gameObject ? gameObject : CreateNewGameObject();

若目的是确保 gameObject 变量已被初始化并分配了有效的 C# 引用，推荐使用显式调用 object.ReferenceEquals()：

1

return !object.ReferenceEquals(gameObject, null) ? gameObject : CreateNewGameObject();

虽然这种更改稍显冗长，但表意十分明确。

空条件运算符

以下示例的表意同样不明确：

1

monoBehaviour?.Invoke("Attack", 1.0f);

同样的，如果目的是简单地检查 monoBehaviour 变量是否已正确初始化与引用，推荐使用显式调用 object.ReferenceEquals()：

1
2

if (!object.ReferenceEquals(monoBehaviour, null))
  monoBehaviour.Invoke("Attack", 1.0f);

但是，如果目的是检查底层引擎对象的生命周期，推荐使用显式的 null 或 boolean 比较：

1
2
3
4
5

if (monoBehaviour != null)
  monoBehaviour.Invoke("Attack", 1.0f);
// 也可使用隐式的 bool 转换运算符
if (otherBehaviour)
  otherBehaviour.Invoke("Attack", 1.0f);

参阅

有关此主题的更多详细信息，请参阅 Unity 博客文章 “Custom == operator, should we keep it?”.

已翻译：Unity-Resharper-可能意外绕过Unity引擎对象的底层生命周期检查

(Ryuu: 附上原文地址 : Custom == operator, should we keep it?)

正文

Unity 的 == 运算符有特殊实现 (UnityEngine.Object 重载了 == 及 != 运算符)。

1. 当一个 MonoBehaviour 有字段，在 editor only [1] 时，这些字段不是 “real null”，而是 “fake null”。UnityEngine 的 == 运算符能够检测是否存在 fake null object。

   虽然这样做很奇怪，但这能让 Unity 在 fake null object 中存储信息。当执行其方法 (method)，或访问其属性 (property)，提供更多的上下文信息。

   若不在 fake null object 中存储信息，只能得到 NullReferenceException，堆栈跟踪。并不知道具体是哪个带有 MonoBehaviour 的 GameObject 有字段为 null。

   在 fake null object 中存储信息，Unity 能够在检视窗口 (Inspector) 中高亮该 GameObject，并给出更多指引:”looks like you are accessing a non initialized field in this MonoBehaviour over here, use the inspector to make the field point to something” (看来你在 MonoBehaviour 中试图访问未实例化字段，请在检视窗口使其指向实例)。

2. 第二点稍加复杂。

   当你获取 GameObject 类型的 c# object **[2]，他几乎不包含任何信息。这是因为 Unity 是基于 C/C++ 的引擎。关于此 GameObject 的所有实际信息 (name，component list，HideFlags，等等) 都存活在 C++ 侧。C# object 所有的仅是指向原生对象 (native object) 的指针 (pointer)。我们称这样的对象为“包装对象” (wrapper objects)**。

   这些如 GameObject 的 c++ objects 及其他一切继承自 UnityEngine.Object 的生命周期都被明确的管理。当你加载新场景，或在其上调用 Object.Destroy(myObject); 时，这些 Object 将会被销毁。

   C# object 的生命周期有 C# 的管理方式，其具有垃圾收集器 (garbage collector) **[4]**。这意味着，有可能被包裹的 C++ Object 已经被销毁，但包裹它的 C# 包装对象依然存在。将此对象与 null 比较，UnityEngine 重载的 == 会返回 true，尽管实际上的 C# 变量 (variable) 不为 null。

UnityEngine 自定义的空检测 (null check) 也导致许多缺陷

• 这种自定义十分反直觉
• 对两个 UnityEngine.Object 比较或与 null 比较，会比想象中的要慢
• UnityEngine 重载的 == 是非线程安全 (not thread safe) 的 (这点 Unity 可在后续修复)
• 其与 ?? 操作符的表现不一致，?? 同样进行空检测，但这是纯粹的 C# 空检测，会绕过 UnityEngine.Object 自定义空检测 [5]

回顾所有的这些优缺点，如果从头再构建 API，我们将不会选择自定义空检查，而是创建一个 myObject.destroyed 的属性，访问该属性以检测 object 的生死。让用户接受在空字段调用方法时不再提供更好的错误信息的事实。

我们在思考我们是否应该改变此自定义运算符，我们一直在寻找 “修复，清除原始项目” 与 “不要破坏原始项目” 之间的正确的平衡。在这种情况下，我们想了解其他人的思考。

对于 Unity5，我们一直在研究 Unity 自动更新脚本的能力 (于随后的博客中对此进行了详细介绍)。不幸的是，在本文情况下，我们无法使您的脚本自动升级 (无法准确辨识 “这个旧脚本确实需要旧的 behaviour” 和 “这个新脚本确实需要新的 behaviour” 的区分)。

我们倾向于 “移除自定义 == 运算符”，但还在犹豫，因为这将改变您工程中所有空检查的意义。对于对象不是 “really null” 而是已销毁对象的情况来说，空检查通常返回 true，如果我们修改了它，就会返回 false 了。若想检测变量是否指向被摧毁对象，需要把代码改成 “if (myObject.destroyed) {}”。我们对此有点紧张，无论你有没有读这篇文章，都很容易意识不到这种行为的改变，特别是大多数人根本没有意识到这种自定义空检查的存在。**[3]**

如果我们作修改，应在 Unity5 上。对于非主要发行版，我们允许用户承受的升级痛苦阈值更低。

你希望我们怎么做？以必须更改已有项目中的空检查为代价，提供更整洁的体验，或是保持现状？

再见, Lucas (@lucasmeijer) **[6]

注释

[1] 我们只在编辑器中执行此操作。这就是为什么在调用GetComponent() 查询不存在的组件时，会看到 C# 内存分配产生，因为我们正在新分配的伪空对象中生成自定义警告字符串。在打包的游戏中，这种内存分配不会发生。这就是为什么测试游戏时，应在打包出来的独立端 (standalone 如 Mac, Windows or Linux) 或移动端测试，而不是在编辑器测试，因为我们在编辑器中做了很多额外的 安全/用例检查，以使你的工作更轻松，而牺牲了一些性能。在分析性能和内存分配时，永远不要在编辑器，应始终分析构建出的游戏。

[2] 不仅适用于 GameObject，也适用于继承自 UnityEngine.Object 的所有类。

[3] 有趣的故事: 我在优化GetComponent（）性能时遇到了这个问题，在为 transform 组件做一些缓存实现时，我没有看到任何性能优势。@jonasechterhoff 也研究了此问题，得出了相同的结论。缓存代码如下所示：

1
2
3
4
5
6
7
8
9
10

private Transform m_CachedTransform
public Transform transform
{
  get
  {
    if (m_CachedTransform == null)
      m_CachedTransform = InternalGetTransform();
    return m_CachedTransform;
  }
}

事实证明，我们自己的两位工程师都没有注意到空检查会比想象中更费时。这就是缓存没有带来速度提升的原因，”连我们自己都忘记了它 (Unity 自定义空检测)，会有多少用户会忘记了它？”，这使得我写下了此篇文章 :)

[4] Ryuu: C# 托管对象的回收是 C# 垃圾回收器管理的，不能保证其生命周期和 C++ 侧对象完全一致。

[5] Ryuu: 原文是 “and cannot be bypassed to call our custom null check”(可以绕过自定义空检测) 个人认为是写错了 (也可能是我英语太差，理解错了)，实际情况是，使用 ?? 或 ?. 都会绕过 UnityEngine.Object 的自定义空检测。附上 JetBrains/resharper-unity 的解释页: Possible unintended bypass of lifetime check of underlying Unity engine object

[6] Ryuu: 最后作者真香了，并没有移除自定义的空检查，而是想办法修复其产生的缺陷。

由于大多数程序的算法都是要在一系列元素而非单一元素上执行操作，因此开发者会使用 foreach、for 循环及 while 等结构。通常把某集合用作输入值，然后检视或修改集合本身或其中元素，最后把另一个集合作为输出值返回给调用方。

这样做的问题在于，若针对整个集合中的每个元素执行操作，程序效率很低。因为执行的操作通常不止一个，且需要多次变换才能把源集合元素转换为目标集合元素。在此过程中，需要创建一些集合保存中间结果，且集合有可能较大，必须等整个集合完成了一次变换操作后，才能继续执行下一次变换操作。要执行几次操作，就得把集合遍历几遍，因此，若执行操作较多，那么算法的执行时间会较长。

另一种办法是，在方法中仅遍历一次，将序列中每个元素都处理一遍，并对其进行各种变换，得到结果。这将提高程序的效率，降低内存使用 (不用每执行一步就创建一个集合)。但这样的的代码很难复用，因为开发者复用的不是整套逻辑，而是其中的一小步。

由于 C# 有*迭代器 (iterator)，因此，开发者可用它创建出一种方法来操作序列中的元素，这样的方法只会在调用方法真正请求获取元素是才会处理并返回该元素。这些方法以 IEnumerable 型参数表示源序列，并把要生成的目标序列也设计为 IEnumerable，而且通过 yielld return语句返回序列中的元素，使得开发者无需给整个目标序列中的元素分配空间，而是可以等调用方真正用到序列中的下一个元素时采取向源序列查询相关数据，并以此生成所需元素。将通用的 IEnumerable 或针对某种类型的 IEnumerable 设计成方法的输入及输出参数是一种比较少见的思路，因此，很多开发者都不会这样做，但这种思路能带来许多好处。与传统方法相比，这种延迟执行 (deferred execution，见37条)*机制可以降低算法所需内存空间，使算法各部分能够更灵活的拼接复用 (见40条)。还可把不同操作放在不用的 CPU 内核中执行，进一步的提高程序性能。可创建泛型方法，扩大其使用范围。

如下实例将序列中每种元素输出一次 (重复元素不输出)：

1
2
3
4
5
6
7
8
9
10
11

public static void Unique(IEnumerable<int> nums)
{
    var uniqueSet = new HashSet<int>();

    foreach (int num in nums)
    {
        if (uniqueSet.Contains(num)) continue;
        uniqueSet.Add(num);
        Console.WriteLine(num);
    }
}

此方法虽然简单，但是不能进行复用。

可以考虑改用迭代器方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static IEnumerable<int> UniqueV2(IEnumerable<int> nums)
{
    var uniqueSet = new HashSet<int>();

    foreach (int num in nums)
    {
        if (uniqueSet.Contains(num)) continue;
        uniqueSet.Add(num);
        yield return num;
    }
}

public static void Main(string[] args)
{
    int[] nums = {0, 3, 4, 5, 7, 3, 2, 7, 8, 0, 3, 1};
    foreach (int i in UniqueV2(nums))
        Console.WriteLine(i);
    
    Console.WriteLine(UniqueV2(nums).First());
}

有人认为这样改差不多，没什么好处。加上一些追踪语句，能让你更清楚此方法的运作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public static IEnumerable<int> UniqueV2(IEnumerable<int> nums)
{
    var uniqueSet = new HashSet<int>();
    Console.WriteLine("\tEntering Unique");
    foreach (int num in nums)
    {
        Console.WriteLine($"\tEvaluating {num.ToString()}");
        if (uniqueSet.Contains(num)) continue;
        uniqueSet.Add(num);
        yield return num;
        Console.WriteLine("\tRe-entering after yield return");
    }

    Console.WriteLine("\tExiting Unique");
}

public static void Main(string[] args)
{
    int[] nums = {0, 3, 4, 5, 7, 3, 2, 7, 8, 0, 3, 1};
    
    // Entering Unique
    // Evaluating 0
    // 0
    // Re-entering after yield return
    //     Evaluating 3
    // 3
    // Re-entering after yield return
    //     Evaluating 4
    // 4
    // Re-entering after yield return
    //     Evaluating 5
    // 5
    // Re-entering after yield return
    //     Evaluating 7
    // 7
    // Re-entering after yield return
    //     Evaluating 3
    // Evaluating 2
    // 2
    // Re-entering after yield return
    //     Evaluating 7
    // Evaluating 8
    // 8
    // Re-entering after yield return
    //     Evaluating 0
    // Evaluating 3
    // Evaluating 1
    // 1
    // Re-entering after yield return
    //     Exiting Unique
    foreach (int i in UniqueV2(nums))
        Console.WriteLine(i);

    //        Entering Unique
    //        Evaluating 0
    // 0
    Console.WriteLine(UniqueV2(nums).First()); // Ryuu: 添加一个示例
    
    // foreach (int num in Square(UniqueV2(nums)))
    //     Console.WriteLine($"Number returned from unique square: {num.ToString()}");
}

之所以有这样的效果，关键就在于 yield return 语句。此语句会返回值，并保留信息，记录当前执行的位置及内部迭代逻辑的状态。用此语句写出来的方法，输入输出值都是迭代器，其迭代逻辑可根据早前保留的信息判断当前应读取输入序列的哪一元素，据此生成并返回输出序列中的下一元素。此方法属于可从上次执行位置继续执行的方法 (continuable method)，系统每次运行它时，可根据先前记录的状态信息决定继续执行的位置。

将 Unique() 方法改写成连续方法 (continuation method) 有两个好处：

1. 推迟了每个元素的求值时机，提高程序效率。
2. 此操作可拼接，可灵活复用。

反之，想用包含 foreach 循环的命令式方法进行灵活复用则较为困难。

注意，Unique() 方法还可转换为泛型方法：

1
2
3
4
5
6
7
8
9
10

public static IEnumerable<T> UniqueV3<T>(IEnumerable<T> sequence)
{
    var uniqueSet = new HashSet<T>();
    foreach (T item in sequence)
    {
        if (uniqueSet.Contains(item)) continue;
        uniqueSet.Add(item);
        yield return item;
    }
}

迭代器方法可把多个步骤拼接成一套流程。若要输出是每一种数值的平方，接上一个 Square() 即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static IEnumerable<int> Square(IEnumerable<int> nums)
{
    foreach (int num in nums)
        yield return num * num;
}

public static void Main(string[] args)
{
    int[] nums = {0, 3, 4, 5, 7, 3, 2, 7, 8, 0, 3, 1};
    
    foreach (int num in Square(UniqueV2(nums)))
        Console.WriteLine($"Number returned from unique square: {num.ToString()}");
    
}

无论使用多少个迭代器方法，仅需将源序列迭代一次即可。

将序列用作迭代器的输入参数。并令其输出另一序列是一种很好的思路，这使得开发者能设计更多的用法。若迭代器方法的参数不是一个序列而是两个，可用这样的迭代器方法将两个序列合并起来：

1
2
3
4
5
6
7
8
9
10
11
12
13

public static IEnumerable<string> Zip(IEnumerable<string> first, IEnumerable<string> second)
{
    using (var firstSequence = first.GetEnumerator())
    {
        using (var secondSequence = second.GetEnumerator())
        {
            while (firstSequence.MoveNext() && secondSequence.MoveNext())
            {
                yield return $"{firstSequence.Current}{secondSequence.Current}";
            }
        }
    }
}

Zip() 从两个不同的字符串序列中分别取出一个元素，并连接成为新字符串，输出目标序列。当然，此方法也可设计成泛型方法，只不过稍复杂 (见18条)。

迭代器方法不会修改源序列本身，而是会依次产生目标序列中的元素，这些元素构成一个新序列。若源序列中的元素是引用型，那么迭代器有可能在处理元素时改动该元素内容。

如果能把复杂的算法拆解成多个步骤，并将每个步骤都表示成小型的迭代器方法，那么可将这些方法拼成一条管道，使得程序仅需遍历一次源序列处理，即可对其中元素进行多种小变换。

这条建议可能听起来有些奇怪，因为 lambda 表达式代替方法会重复编写代码。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var allEmployees = FindAllEmployees();

// Find the first employees:
var earlyFolks =
    from e in allEmployees
    where e.Classification == EmployeeType.Salary
    where e.YearsOfService > 20
    where e.MonthlySalary < 4000
    select e;

// Find the newest people:
var newest =
    from e in allEmployees
    where e.Classification == EmployeeType.Salary
    where e.YearsOfService < 20
    where e.MonthlySalary < 4000
    select e;

你可以将这些 where 合并为一条子句，然而这并不会带来太大区别。查询操作之间本就可以拼接 (见31条)，而简单的 where 谓词还会有可能内联 (inline)，因此，这两种写法在性能上是一样的。

看到刚才那段代码，你可能会想把重复的 lambda 表达式提取到方法，以便复用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Factor out method:
private static bool LowPaidSalaried(Employee e) => 
    e.MonthlySalary < 4000 && e.Classification == EmployeeType.Salary;

// else where
var allEmployees = FindAllEmployees();

var earlyFolks =
	from e in allEmployees
	where LowPaidSalaried(e) && e.YearsOfService > 20
	select e;
            
// Find the newest people:
var newest =
	from e in allEmployees
	where e.Classification == EmployeeType.Salary
	where e.YearsOfService < 20
	where e.MonthlySalary < 4000
	select e;

如果将来需要修改员工的类别 (Classification)，或修改筛选底薪员工时所依据的最低月薪 (MonthlySalary)，那么只需要改动 LowPaidSalaried() 里的逻辑即可。

但是这样的重构不能提高其复用性，这与 lambda 表达式求值、解析及执行机制有关：

• LINQ to Objects

  为执行表达式中代码，将 lambda 表达式转化成为委托

• LINQ to SQL

  根据 lambda 表达式创建表达式树，并解析，使其能在其他环境执行

LINQ to Objects 针对本地数据存储 (local data store) 来执行查询，数据通常放在泛型集合。系统根据 lambda 表达式中的逻辑建立匿名委托，并执行相关代码。LINQ to Objects 扩展方法使用 IEnumerable 来表示输入序列。

LINQ to SQL 使用表达式树，根据所写查询逻辑构建表达式树，将其解析为适当的 T-SQL 查询，这种查询是针对数据库执行的，LINQ to SQL 把 T-SQL 形式的查询字符串发送给数据库引擎并执行。这种处理方式要求 LINQ to SQL引擎必须解析表达式树，并把其中每一项操作都替换成等价的 SQL，这意味着所有的方法调用都需要换成 Expression.MethodCall 节点。然而 LINQ to SQL 引擎并不能把每一种方法调用都顺利的转化为 SQL 表达式，无法转换将会引发异常。

如果所写的程序库需要支持任意类型的数据源，必须考虑上述情况。需要分开编写 lambda 表达式，且内联至代码中，以保证程序库正常运行。

这并不是在鼓励一味的复制代码，而是提醒，涉及查询表达式及 lambda 的地方应该用更为合理的方法去创建复用代码块。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static IQueryable<Employee> LowPaidSalariedFilter(this IQueryable<Employee> sequence) =>
    from s in sequence
    where s.Classification == EmployeeType.Salary && s.MonthlySalary < 4000
    select s;

// else where
var allEmployees = FindAllEmployees();

// Find the first employees:
var salaried = allEmployees.LowPaidSalariedFilter();

var earlyFolks = salaried.Where(e => e.YearsOfService > 20);

// Find the newest people:
var newest = salaried.Where(e => e.YearsOfService < 2);

并不是每一种查询都能像这样简单的改写，可能需要沿着调用链寻找，才能发现可供复用的列表处理逻辑 (list-processing logic)，从而提取相同的 lambda 表达式。31条提过，只要当程序真的需要遍历集合的时，enumerator 方法才会得以执行。可利用此特征，将查询操作分成许多小方法来写，这些小方法都能复用某一套 lambda 表达式来执行它所应该完成的那一部分查询工作。这些方法需要将待处理的序列当成输入值，并以 yield return 形式返回处理结果。这些小方法可构成较大的查询模块。避免重复的代码，使得代码结构更合理。

也可按照同样的思路建立表达式树，以此拼接 IQueryable 形式的 enumerator，令查询操作能够远程执行。寻找相关员工所用的那棵表达式树可以先于其他查询拼接，然后执行。IQueryProvider 对象 (LINQ to SQL 引擎的数据源就是这种对象) 可以把全套查询操作一次执行完毕，而不必将其分解成多个部分放到本地执行。

若想在复杂的查询中有效地复用 lambda 表达式，可以考虑针对封闭的泛型类型创建扩展方法。LowPaidSalariedFilter 方法就是这么写的，它接受有待筛选的 Employee 对象序列，输出经过筛选后的 Employee 对象序列。在实际工作中，还应该创建以 IEnumerable 作阐述的重载版本，以便同时支持 LINQ to Objects 及 LINQ to SQL。

你可以把查询操作分成多个小方法，其中一些方法在其内部用 lambda 表达式处理序列，另一些方法以 lambda 表达式作参数。把这些小方法拼接起来，以实现整套操作。这样既可以支持 IEnumerable 与 IQueryable，又能令系统有机会构建出表达式树，以便高效执行查询。

定义查询操作，程序并不会立刻把数据获取并填充至序列，因为定义的实际上只是一套执行步骤，当真正需要遍历结果时，才会执行。每迭代一遍产生一套新结果，这叫做***惰性求值 (lazy evaluation)，反之，若像普通代码一样直接查询某套变量的取值并立即记录，那么就称为及早求值 (eager evaluation)***。

若定义查询操作需多次执行，请考虑采用哪种求值方式。是给数据做一份快照，还是先把逻辑记录下来，以便随时根据该逻辑查询，并将结果置入序列？

惰性求值与一般编写代码时的思路有很大区别，LINQ 查询操作把代码当数据看，用作参数的 lamdba 表达式要等到调用时才执行。此外，如果 provider 使用表达式树 (expression tree) 而不是委托，那么稍后可能还会有新的表达式融入树中。

通过以下示例演示惰性求值与及早求值的区别。生成一个序列，暂停，迭代，暂停，再迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

private static IEnumerable<TResult> Generate<TResult>(int number, Func<TResult> generator)
{
    for (var i = 0; i < number; i++)
        yield return generator();
}

/// <summary>
/// Start time for Test One: 8:37:28 PM
/// Waiting...      Press Return
/// 
/// Iterating...
/// 8:37:30 PM
/// ...
/// 8:37:30 PM
///      Waiting...      Press Return
///
///  Iterating...
///   8:37:39 PM
///   ...
///   8:37:39 PM
/// </summary>
private static void LazyEvaluation()
{
    Console.WriteLine($"Start time for Test One: {DateTime.Now:T}");
    var sequence = Generate(10, () => DateTime.Now);

    Console.WriteLine("Waiting... \tPress Return");
    Console.ReadLine();

    Console.WriteLine("Iterating...");
    foreach (DateTime dateTime in sequence) // warning: Possible multiple enumeration
        Console.WriteLine($"{dateTime:T}");

    Console.WriteLine("Waiting... \tPress Return");
    Console.ReadLine();

    Console.WriteLine("Iterating...");
    foreach (DateTime dateTime in sequence) // warning: Possible multiple enumeration
        Console.WriteLine($"{dateTime:T}");
}

注意观察结果中的时间戳 (time stamp)。由此可知，前后两次迭代所生成的是不同的两个序列，因为 sequence 变量保存的不是创建好的元素，而是创建元素所用的表达式树。(Ryuu：在 Rider 中编写该代码，将出现 Possible multiple enumeration 警告，同样告知，此操作可能导致遍历序列前后不一致。)

由于查询表达式能够惰性求值，因此可以在现有的查询操作后继续拼接其他的操作。

如下示例将 sequence1 序列得到的时间转换成协调世界时：

1
2
3
4
5
6
7

var sequence1 = Generate(10, () => DateTime.Now);
var sequence2 =
    from dateTime in sequence1
    select dateTime.ToUniversalTime();

foreach (DateTime dateTime in sequence2)
    Console.WriteLine($"{dateTime:T}");

sequence1 和 sequence2 两个序列是在功能层面上组合，而不是在数据层面上。系统并不会先把 sequence1 的所有值拿出来，然后全部修改一遍，构成 sequence2。而是执行相关的代码，把 sequence1 的元素生成出来，紧接着执行另一端代码处理该元素，将结果放入sequence2。程序并不会把时间都准备好，并将其转换为协调世界时，而是等待调用时再去生成该序列中被调用的时间。

由于查询表达式可惰性求值，因此，理论上来说，它可以操作无穷序列 (infinite sequence)。如果代码写的较为合理，那么程序仅需检查开头部分即可，因为在完成查询后程序会停止。反之，有些写法令表达式必须把整个序列处理一遍才能得到完整结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/// <summary>
/// 0123456789
/// </summary>
private static void LazyEvaluation3()
{
    var answers = from number in AllNumbers() select number;
    var smallNumbers = answers.Take(10);

    foreach (int num in smallNumbers)
        Console.Write(num);
}

private static IEnumerable<int> AllNumbers()
{
    var number = 0;

    while (number < int.MaxValue)
        yield return number++;
}

此示例不必生成整个序列，而是仅生成十个数 (虽然 AllNumbers() 可以生成至 int.MaxValue)。Take() 方法只需要其中的前 N 个对象。

反之，如果把查询语句改成这样，程序将一直运行，直到 int.MaxValue才停下：

1
2
3
4

var answers = from number in AllNumbers() where number < 10 select number;

foreach (int num in answers)
	Console.Write(num);

查询语句需要逐个判断序列中的每个元素，并根据其是否小于 10 决定要不要生成该元素，该逻辑导致其必须遍历整个元素。

某些查询操作必须把整个序列处理一遍，然后才能得到结果。比如上例的 where，以及 OrderBy、Max、Min。对于可能无限延伸下去的序列来说，尽量不要执行此操作。即使是有限长度，还是应尽量利用过滤机制来缩减待处理的数据，以提高程序效率。

1
2
3
4
5
6
7
8
9
10
11
12
13

// Order before filter.
var sortedProductsSlow =
    from p in products
    orderby p.UnitsInStock descending
    where p.UnitsInStock > 100
    select p;

// Filter before order.
var sortedProductsFast =
    from p in products
    where p.UnitsInStock > 100
    orderby p.UnitsInStock descending
    select p;

第一种方法会将所有产品排序，然后剔除小于等于 100 的产品，而第二种，则是先剔除小于等于 100 的产品，然后再排序，这样的话待排序的数据量可能减小。在编写算法时，请安排合适的执行顺序，这样的算法可能执行很快，反之，则可能极为耗时。

笔者列举了以上理由，建议查询时优先考虑惰性求值，但在个别情况下，可能想要给结果做一份快照，这是可以考虑 ToList() 及 ToArray()，他们都能立刻根据查询结果来生成序列，并保存至容器中。该方法用在以下两个场合：

1. 需要立即执行查询操作
2. 将来还要使用同一套查询结果

与及早求值的方法比，惰性求值能减少程序工作量，且使用起来更灵活。若有需要，可使用 ToList() 及 ToArray() 来保存结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static void main(String[] args) {
    int arraySize = 1 << 15;
    int[] data = new int[arraySize];
    Random rnd = new Random(0);
    for (int c = 0; c < arraySize; ++c)
        data[c] = rnd.nextInt() % 256;
    
    sum(data, arraySize); // 2_506_570_100 ns
    // The next sum runs faster after sort
    Arrays.sort(data);
    sum(data, arraySize);// _768_923_900 ns
}

public static void sum(int[] array, int arraySize) {
    long start = System.nanoTime();
    long sum = 0;

    for (int i = 0; i < arraySize; ++i) {
        for (int j = 0; j < arraySize; ++j) {
            if (array[j] >= 128)
                sum += array[j];
        }
    }
    System.out.println(System.nanoTime() - start + " ns");
    System.out.println("sum : " + sum);
}

以上的示例初始化一个数组，以 256 的模数进行填充，后对其中大于等于 128 的元素求和。

见注释结果，排序后的数组执行求和，比不排序的要快的多。这是在执行 if 语句时，CPU 的分支预测导致的。

通过分支的历史选择记录进行分支预测，若预测命中，则指令能快速的执行；若未命中，则当前执行分支作废，转而执行另一分支 (未命中的预测会损耗性能)：

T : 分支预测命中

F : 分支预测未命中

• 无序数组：

  -248, 7, -14, 241, 15, 112, 88, 246, 152, -200, 31, 180 …

  F F F T F F F T T F F T

• 有序数组：

  127, 127, 127, 127, 127, 127, 128, 128, 128, 128, 128, 128 …

  F F F F F F T T T T T T

无序数组难以保证预测命中率，而有序数组则极好判断。

也可通过位运算优化，消除分支判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * no if statement in this method
 * use shift operators
 * if positive num : num >> 31 == 0
 * if negative num : num >> 31 == -1
 * ~0 = -1 (ffffffff)
 * ~-1 = 0 (0)
 */
public static void sumAvoidBranchPrediction(int[] array, int arraySize) {
    long start = System.nanoTime();
    long sum = 0;

    for (int i = 0; i < arraySize; ++i) {
        for (int j = 0; j < arraySize; ++j) {
            sum += ~((array[j] - 128) >> 31) & array[j];
        }
    }
    System.out.println(System.nanoTime() - start + " ns"); // _606_267_300 ns
    System.out.println("sum : " + sum);
}

原始地址：

【Java深入学习系列】之CPU的分支预测(Branch Prediction)模型

why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array

Show you the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// Variant type parameters could be declared in interfaces or delegates only!

interface ICovariant<out T>
{
}

class Covariant<T> : ICovariant<T>
{
}

interface IContravariant<in T>
{
}

class Contravariant<T> : IContravariant<T>
{
}

interface IInvariant<T>
{
}

class Invariant<T> : IInvariant<T>
{
}

class Program
{
    private static void Covariant( /* out */)
    {
        ICovariant<object> obj = new Covariant<object>();
        ICovariant<string> str = new Covariant<string>();

        // You can assign "Derived" to "Base"
        obj = str;
        str = obj; // error
    }

    private static void Contravariant( /* in */)
    {
        IContravariant<object> obj = new Contravariant<object>();
        IContravariant<string> str = new Contravariant<string>();

        // You can assign "Base" to "Derived"
        str = obj;
        obj = str; // error
    }

    private static void Invariant( /* none */)
    {
        IInvariant<object> obj = new Invariant<object>();
        IInvariant<string> str = new Invariant<string>();

        // You can't do any assign 
        obj = str; // error
        str = obj; // error
    }
}

垃圾收集算法的实现设计大量的程序细节，且各个平台虚拟机操作内存的方法都有差异，本节仅重点介绍分代收集理论，几种算法思想，及其发展过程。若对其中细节感兴趣，推荐阅读 Richard Jones 《垃圾回收算法手册》 第 2 ~ 4 章。

从如何判定对象消亡的角度出发，垃圾收集算法可划分为 “引用记数式垃圾收集” (Reference Counting GC) 和 “追踪式垃圾收集” (Tracing GC) 两大类，这两大类也被称作 “直接垃圾收集” 和 “间接垃圾收集”。由于引用记数式垃圾收集在主流的 Java 虚拟机中均未涉及，故本节主要介绍所有算法属于追踪式垃圾收集的范畴。

分代收集理论

当前商业虚拟机的垃圾收集器，大多遵循了 “分代收集理论” (Generational Collection) 的理论进行设计。其建立在两个分代假说之上：

1. **弱分代假说 (Weak Generational Hypothesis)**：绝大多数对象朝生夕灭。
2. **强分代假说 (Strong Generational Hypothesis)**：熬过越多次 GC 的对象就越难死亡。

这两个分代假说共同奠定了多款常用垃圾收集器的一致设计原则：收集器应将 Java 堆划分出不同的区域，然后将回收对象依据其年龄 (即熬过 GC 的次数) 分配到不同的区域之中存储。如果一个区域中大多数对象都是朝生夕灭，将其集中存储，每次 GC 只关注如何保留存活对象，而不是标记大量要被回收的对象，就能以较低代价回收大量空间；如果一个区域中大多数对象都是难死亡的对象，将其集中存储，虚拟机可以以较低的频率进行回收，这就同时兼顾了垃圾收集的时间开销和内存空间的有效利用。

在 Java 划分出不同的区域后，垃圾收集器才可以每次只回收其中某一个，或者某部分区域 —— 才有了 “Minor GC”、”Major GC”、”Full GC” 这样的回收类型划分；才能针对不用的区域，安排与其存储对象存亡特征相匹配的垃圾收集算法 —— 发展出了 “标记 - 复制算法”、”标记 - 清除算法”、”标记 - 整理算法” 等针对性的垃圾收集算法 (稍后会提到)。

把分代收集理论放到现在的商用 Java 虚拟机中，设计者一般会至少把 Java 划分为新生代 (Young Generation) 和老年代 (Old Generation) 两个区域 (HotSpot 虚拟机的命名，IBM J9 虚拟机对应称其为 婴儿区 (Nursery) 和长存区 (Tenured))。在新生代中，每次都有大量对象死去，而回收后活下来的少量对象会逐步转移至老年代存放。实际上分代收集理论并不是简单的分划内存区域那么简单，存在一个明显的问题：对象间可能存在跨代引用。

假如要对新生代区域的 GC (Minor GC)，但新生代中的对象完全有可能被老年代引用，为了确定该区域中存活的对象，不得不在固定的 GC Roots 之外，在遍历整个老年代中的对象，以确保可达性分析的准确性，反之同理。这虽然在理论上可行，但是会为内存回收带来很大的性能负担，为解决此问题，引入第三个假说：

3. **跨代引用假说 (Intergenerational Reference Hypothesis)**：跨代引用相对于同代引用来说占极少数。

其实这可以通过前两个假说推出：存在互相引用关系的两个对象，应是倾向于同生共死的。若某个新生代的对象被老年代对象引用，由于老年代对象很难死亡，该引用将使得新生代中的对象同样得以存活，进而在年龄增长后晋升到老年代，此时跨代引用也随之解除了。

依据此假说，不应为少量的跨代引用而扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在，及存在哪些跨代引用，仅在新生代上建立一个全局数据结构 (“记忆集” Remember Set)，此结构将老年代划分为若干小块，表示出哪一块会存在跨代引用。当发生 Minor GC 时，只有包含了跨代引用的小块内存中的对象被加入 GC Roots 进行扫描。虽然此方法需要在改变对象引用时更新记忆集记录，将会增加一些执行时的开销，但比起收集器扫描整个老年代来说，仍然是划算的。

• 部分收集 (Partial GC)：不是完整收集整个 Java 堆的垃圾，其中包括：
  • 新生代收集 (Minor / Young GC)：仅回收新生代的垃圾。
  • 老年代收集 (Major / Old GC)：仅回收老年代的垃圾。目前只有 CMS 收集器有此行为。注意，”Major GC” 的说法存在混淆，不同的资料所指不同，可能指老年代收集，也可能指整堆收集。
  • 混合收集 (Mixed GC)：回收新生代的垃圾，及部分老年代的垃圾。目前只有 G1 收集器有此行为。
• 整堆收集 (Full GC)：回收整个 Java 堆和方法去的垃圾

标记 - 清除算法

最早出现，也是最基础的垃圾收集算法是 “标记 - 清除” (Mark - Sweep) 算法，在 1960 年由 Lisp 之父 John McCarthy 提出。算法分为 “标记” 和 “清除” 两个阶段：首先标记出所有需要回收的对象，标记后，统一回收被标记的对象，也可以反过来，标记存活的对象，回收未被标记的对象。

之所以称其为最基础的收集方法，是因为后续的收集算法大都是以标记 - 清除算法为基础，对其缺点进行改进。它主要有两个缺点：

1. 执行效率不稳定。若有大量的对象需要回收，这需要进行大量的标记清除工作。
2. 内存碎片化问题，回收对象后，内存中会产生大量不连续的内存碎片，可能导致在需要为大对象分配空间时，没有足够大的连续内存。因此可能提前触发一次 GC。

标记 - 复制算法

也可简称为复制算法。为解决标记 - 清除算法面对大量可回收对象时执行效率的问题，1969 年 Fenichel 提出了一种称为 “半区复制” (Semispace Copying) 的垃圾收集算法。将内存容量均分两块，每次只使用其中的一块。当一块用完，就把还存活的对象复制到另一块，再将当前的块清理一次。如果内存中大多都是存活的对象，此算法将带来极大的内存复制时间开销，但若大多对象都是可回收的，算法仅需复制极少数对象即可。复制时移动堆指针，按顺序分配即可，这样内存碎片化的问题也解决了。实现简单，运行高效。缺点也是显而易见的，这种算法直接将可利用的内存缩小为了原来的一半，空间的浪费太多了。(Ryuu：相信已经有同志想到了新生代的 GC 了，也确实如此。)

现在的商用 Java 虚拟机大多都优先采用了此算法回收新生代，IBM 公司曾有一项专门研究，对新生代 “朝生夕灭” 的特点做了更量化的诠释 —— 新生代中的对象有 98% 熬不过第一轮收集，因此并不需要按 1：1 的比例划分新生代的内存空间(Ryuu：调优时根据具体情况，这仅是较泛化的诠释)。

在 1989 年，Andrew Appel 针对具备 “朝生夕灭” 特点的对象，提出了以重更优化的半区复制分带策略，现被称为 “Appel 式回收”。HotSpot 虚拟机的 Serial、ParNew 等新生代收集器均采用了这种策略来设计新生代的内存布局。Appel 的具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只使用 Eden 和其中一块 Survivor，发生 GC 时，将 Eden 和 Survivor 中存活的对象复制到另一个 Survivor，然后直接清空 Eden 和上次利用过的 Survivor (Ryuu：这两块 Survivor 也因此被称为 From 和 To，From from-survivor to to-survivor，存活对象从 From 移至 To 后，From 和 To 两者身份互换)。HotSpot 虚拟机默认 Eden 和 Survivor 的比例是 8：1，即每次新生代中可用的内存空间为整个新生代的 90 % (Eden 的 80% 加一个 Survivor 的 10%)，仅有10% 的空间是不能直接使用的。当然，98% 的对象被回收不是一定的，所以 Appel 式回收有一个安全设计：当 Survivor 不能一次容纳所有 GC 后存活的对象时，依赖其他内存区域 (大多情况下是老年代) 进行分配担保 (Handle Promotion)。

标记 - 整理算法

标记 - 复制算法在对象存活率较高时需进行较多的复制操作，效率将会降低。更关键的是，如果不想浪费空间，就需要有额外的空间进行分配担保，以便应对使用的内存中存活的对象过多的问题，所以在老年代一般不直接使用这种算法。

针对老年代的存亡特征，1974 年 Edward Lueders 提出了一种有针对性的 “标记 - 整理” (Mark - Compact) 算法，标记过程与 “标记 - 清除” 法相同，但后续步骤是将存活的对象都向内存空间的一端一移动，然后直接清理掉边界外的空间。

标记 - 清除 和 标记 - 整理算法的本质是，前者是非移动式的回收算法，而后者是移动式的。是否移动存活对象是一项优缺点并存的风险决策：

如果移动存活对象，尤其是在老年代这种每次都有大量对象存活的区域，移动这些对象并更新所有引用这些对象的地方负担极大，这种对于对象的移动操作必须暂停用户应用程序才能进行 (最新的 ZGC 和 Shenandoah 收集器使用读屏障 (Read Barrier) 技术实现了整理过程与用户线程的并发执行)，这就更加让使用者不得权衡其弊端了，这样的停顿被虚拟机的设计者形象的称为 “Stop The World” (通常标记 - 清除算法也是需要停顿用户线程来标记、清理可回收对象的，只是停顿时间相对而言要短)。

但像标记 - 清除算法那样完全不考虑移动和整理存活对象，散在内存中的存活对象导致的空间碎片化问题就只能依赖于更复杂的内存分配器和内存访问器解决。如通过 “分区空闲分配链表” 解决内存分配问题 (计算机硬盘存储大文件就不要求物理连续的磁盘空间，在碎片化的磁盘上存储和访问是通过硬盘分区表实现的)。内存的访问是用户程序最频繁的操作，若在此环节增加额外的负担，势必会直接影响程序的吞吐量。

基于以上两点，是否移动对象都各有其弊端，移动则回收复杂，不移动则分配复杂。从 GC 所需时间看，不移动对象停顿时间更短，甚至不需要停顿，但是从整个程序的吞吐量看，移动对象是正确的选择。此语境中，吞吐量的实质是赋值器 (Mutator，可以理解为使用垃圾收集的用户程序，为便于理解，多数地方用 “用户程序” 或 “用户线程” 代替) 与收集器的效率总和。即使不移动对象使得收集器的效率提升，但因内存分配和访问相比垃圾收集的频率要高得多，这部分的耗时会导致总吞吐量下降。HotSpot 虚拟机中关注吞吐量的 Parallel Old 收集器是基于标记 - 整理算法的，而关注延迟的 CMS 收集器是基于标记 - 清除算法的，这也侧面印证了这点。

另外还有一种解决方案，那就是让虚拟机平时采用标记 - 清除算法，直到内存空间碎片化的程度大到影响对象分配时，采用标记 - 整理算法进行一次 GC，以获得规整的内存空间。这也是前文提及的 CMS 收集器面临碎片过多时的解决方案。

引用计数法

在对象中添加一个引用计数器，每当有一个对他的引用，计数器值加一；引用失效时，计数器减一；任何时刻计数器为 0 的对象都是不可能再被使用的对象。

引用记数算法 (Reference Counting) 虽然占用了一些额外的内存空间来进行记数，但原理简单，判定效率高，大多数情况下都是不错的算法。也有一些著名的应用案例，如微软 COM (Component Object Model) 技术、使用 ActionScript 3 的 FlashPlayer、Python 语言以及在游戏脚本领域得到许多应用的 Squirrel 中都使用了引用记数算法进行内存管理。

但是，在 Java 领域，至少是主流的 Java 虚拟机里都没有选用引用计数算法进行内存管理，这个看似简单的算法有很多例外情况要考虑，必须配合大量额外处理才能保证其正确工作。

请看如下的 testGC()：这两个对象最终都不可被访问 (最后都置 nul)，但是因为他们存在相互引用 (对象 objA 和 objB 都有字段 instance，并利用该字段进行相互引用)，引用记数算法将无法回收他们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class ReferenceCountingGC {
    public Object instance = null;
    private static final int _1MB = 1 << 20;
    private final byte[] bigSize = new byte[_1MB]; // 占点内存以方便得知是否被回收

    public static void testGC() {
        ReferenceCountingGC objA = new ReferenceCountingGC();
        ReferenceCountingGC objB = new ReferenceCountingGC();
        objA.instance = objB;
        objB.instance = objA;

        objA = null;
        objB = null;

        // 建议 gc 进行回收
        System.gc();
    }
}

(Ryuu: 我这里用的是 G1 回收器，gc 日志跟作者的不一样)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

[0.007s][info][gc] Using G1
[0.010s][info][gc,init] Version: 16.0.2+7-67 (release)
[0.010s][info][gc,init] CPUs: 12 total, 12 available
[0.010s][info][gc,init] Memory: 32717M
[0.010s][info][gc,init] Large Page Support: Disabled
[0.010s][info][gc,init] NUMA Support: Disabled
[0.010s][info][gc,init] Compressed Oops: Enabled (Zero based)
[0.010s][info][gc,init] Heap Region Size: 4M
[0.010s][info][gc,init] Heap Min Capacity: 8M
[0.010s][info][gc,init] Heap Initial Capacity: 512M
[0.010s][info][gc,init] Heap Max Capacity: 8180M
[0.010s][info][gc,init] Pre-touch: Disabled
[0.010s][info][gc,init] Parallel Workers: 10
[0.010s][info][gc,init] Concurrent Workers: 3
[0.010s][info][gc,init] Concurrent Refinement Workers: 10
[0.010s][info][gc,init] Periodic GC: Disabled
[0.010s][info][gc,metaspace] CDS archive(s) mapped at: [0x0000000800000000-0x0000000800bb0000-0x0000000800bb0000), size 12255232, SharedBaseAddress: 0x0000000800000000, ArchiveRelocationMode: 0.
[0.010s][info][gc,metaspace] Compressed class space mapped at: 0x0000000800c00000-0x0000000840c00000, reserved size: 1073741824
[0.010s][info][gc,metaspace] Narrow klass base: 0x0000000800000000, Narrow klass shift: 3, Narrow klass range: 0x100000000
[0.088s][info][gc,task     ] GC(0) Using 10 workers of 10 for full compaction
[0.088s][info][gc,start    ] GC(0) Pause Full (System.gc())
[0.088s][info][gc,phases,start] GC(0) Phase 1: Mark live objects
[0.089s][info][gc,phases      ] GC(0) Phase 1: Mark live objects 0.833ms
[0.089s][info][gc,phases,start] GC(0) Phase 2: Prepare for compaction
[0.090s][info][gc,phases      ] GC(0) Phase 2: Prepare for compaction 0.761ms
[0.090s][info][gc,phases,start] GC(0) Phase 3: Adjust pointers
[0.090s][info][gc,phases      ] GC(0) Phase 3: Adjust pointers 0.477ms
[0.090s][info][gc,phases,start] GC(0) Phase 4: Compact heap
[0.091s][info][gc,phases      ] GC(0) Phase 4: Compact heap 0.571ms
[0.092s][info][gc,heap        ] GC(0) Eden regions: 2->0(1)
[0.092s][info][gc,heap        ] GC(0) Survivor regions: 0->0(0)
[0.092s][info][gc,heap        ] GC(0) Old regions: 0->1
[0.092s][info][gc,heap        ] GC(0) Archive regions: 0->0
[0.092s][info][gc,heap        ] GC(0) Humongous regions: 0->0
[0.092s][info][gc,metaspace   ] GC(0) Metaspace: 488K(704K)->488K(704K) NonClass: 462K(576K)->462K(576K) Class: 25K(128K)->25K(128K)
[0.092s][info][gc             ] GC(0) Pause Full (System.gc()) 4M->0M(16M) 4.173ms
[0.093s][info][gc,cpu         ] GC(0) User=0.00s Sys=0.00s Real=0.00s
[0.093s][info][gc,heap,exit   ] Heap
[0.094s][info][gc,heap,exit   ]  garbage-first heap   total 16384K, used 1039K [0x0000000600c00000, 0x0000000800000000)
[0.094s][info][gc,heap,exit   ]   region size 4096K, 1 young (4096K), 0 survivors (0K)
[0.094s][info][gc,heap,exit   ]  Metaspace       used 491K, committed 704K, reserved 1056768K
[0.094s][info][gc,heap,exit   ]   class space    used 25K, committed 128K, reserved 1048576K

gc 日志中可见 “Pause Full (System.gc()) 4M->0M(16M) 4.173ms”，这说明虚拟机并没有因为两个对象存在相互引用就放弃回收他们，也说明了 Java 虚拟机并不是通过引用记数算法进行对象存活判断的。

可达性分析算法

当前主流的商用程序语言 (Java、C#、Lisp) 的内存管理子系统，都是靠通过可达性分析 (Reachability Analysis) 算法来判定对象是否存活。其基本思路是通过一系列 “GC Roots” 的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走的路径被称为 “引用链” (Reference Chain)，如果某个对象到 GC Roots 间没有任何引用相连，用图论的话说，从 GC Roots 到该对象不可达，证明此对象是不可能再被使用的。

在 Java 技术体系中，固定可作为 GC Roots 的对象包括以下几种：

• 虚拟机栈 (栈帧中的本地变量表) 中引用的对象，如当前正在运行的方法所使用的参数、局部变量、临时变量等。
• 方法区中的静态属性引用对象，如 Java 类的引用类型静态变量。
• 方法区中常量引用对象，如字符串常量池 (String Table) 里的引用。
• 本地方法栈中 JNI (通常被称为 Native 方法) 引用的对象。
• Java 虚拟机内部引用，如基本数据类型对应的 Class 对象，一些常驻的异常对象 (如 NullPointException、OutOfMemoryError) 等，还有系统类加载器。
• 所有被同步锁 (synchronized 关键字) 持有的对象。
• 反应 Java 虚拟机内部情况的 JMXBean、JVMTI 中注册的回调、本地代码缓存等。

除了这些固定的 GC Roots 集合外，根据用户所选的垃圾收集器已经当前回收的内存区域不同，还可以有其他对象 “临时性” 地加入，共同构成完整 GC Roots 集合。如后文提到的分代收集和局部回收 (Partial GC)，如果只针对 Java 堆中某一块区域发起垃圾收集时 (如典型的，只针对新生代的垃圾收集)，必须考虑到内存区域只是虚拟机的实现细节，他们不是孤立封闭的，所以某个区域的对象完全有可能被位于堆中其他区域的对象引用，这时就需要将这些关联区域的对象也一并加入 GC Roots 集合中去，才能保证可达性分析的正确性。

目前最新的几款垃圾收集器 (例如 OpenJDK 中的 G1、Shenandoah、ZGC 以及 Azul 的 PGC、C4) 无一例外的都具备局部回收的特征，为了避免 GC Roots 包含过多对象而过度膨胀，它们在实现上也做出了各种优化处理 (见后文)。

关于引用

无论是通过引用计数法判断对象的引用数量，还是通过可达性分析算法判断对象是否引用链可达，判定对象存活都和引用脱不开关系。在 JDK 1.2 版本前，Java 中的引用定义很传统：如果 reference 类型的数据中存储的数值代表的是另外一块内存的起始地址，就称该 reference 数据是代表某块内存、某个对象的引用。但是一个对象不应该只有 “被引用” 和 “未被引用” 两种状态。例如这种情况：当内存空间还足够，就保留在内存中，如果内存空间在完成 GC 后还是十分紧张，就抛弃这些对象 —— 很多系统缓存功能都符合此场景。

在 JDK 1.2 版本后，Java 对引用的概念进行了扩充，将引用分为强引用 (Strongly Reference)、软引用 (Soft Reference)、弱引用 (Weak Reference) 和虚引用 (Phantom Reference) 四种，四种引用强度依次减弱。

1. 强引用 (Strongly Reference)

   “最传统” 的引用定义，指在程序代码中普遍存在的引用赋值，类似 “Object obj = new Object()” 的这种引用关系。无论何种情况，只要强引用还在，垃圾回收器就永远不会回收掉被引用的对象。

2. 软引用 (Soft Reference)

   描述一些还有用，但非必要的对象，系统将要内存溢出前，会把这些对象列入回收范围中进行二次回收，如果回收后内存依然不足，才会抛出内存溢出异常。

3. 弱引用 (Weak Reference)

   非必要的对象，其强度比软引用更弱。其对象只能生存到下一次 GC 发生前。当 GC 发生时，无论内存是否足够，都会回收掉仅被弱引用关联的对象。

4. 虚引用 (Phantom Reference)

   也被称为 “幽灵引用” 或 “幻引用”，是最弱的引用关系。完全不会对其生存时间造成影响。也无法通过该引用获取实例。为一个对象设置虚引用仅是为了能让此对象被回收时受到一个系统通知。

对象死亡判定

即使是在可达性分析算法中判定为不可达对象，也并非 “非死不可”。一个对象真正死亡，最多会经历两次标记，如果在进行可达性分析时没有在 GC Roots 的引用链上，将第一次被标记。之后判断该对象是否有必要执行 finalize()。若对象没有覆盖 finalize()，或者 finalize() 已被虚拟机调用，那么虚拟机将这两种情况都视为 “没有必要执行”。(Ryuu：注意，一个对象的 finalize() 只会被调用一次。)

若有必要执行 finalize()，那么该对象将会被放置在一个名为 F-Queue 的队列中，并在稍后由虚拟机自己建立的，低调度优先级的 Finalizer 线程去执行它们的 finalize()。这里的 “执行” 仅指虚拟机会触发这个的方法开始运行，并不承诺一定等待他们运行结束。这是因为，若 finalize() 执行的太慢，或者极端的发生了死循环，将导致 F-Queue 的其他对象永久处于等待，甚至导致整个内存回收子系统崩溃。finalize() 方法是对象逃脱死亡的最后机会，稍后收集器将对 F-Queue 中的对象进行二次标记，若对象要在 finalize() 中避免死亡 —— 只需重新与引用链上的任何一个对象建立关联即可，例如把 this 赋给某个类变量或者对象成员的成员变量，那么它将会在二次标记时被移除 “即将回收” 的集合；如果它没有这么做，那就真的会被回收了。

如下是对象执行 finalize()，依然存活的示例：(Ryuu：当然，一般情况下没人会在 finalize() 里做除了释放资源以外的事。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// DON'T DO THIS!
public class FinalizeEscapeGC {
    public static FinalizeEscapeGC SAVE_HOOK = null;

    public  void isAlive(){
        System.out.println("alive");
    }

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("finalize method executed!");
        FinalizeEscapeGC.SAVE_HOOK = this;
    }
    
    /**
     * finalize method executed!
     * alive
     * dead
     */
    public static void main(String[] args) throws InterruptedException {
        SAVE_HOOK = new FinalizeEscapeGC();
        SAVE_HOOK = null;
        System.gc();
        // 因为 GC 的优先级低, 先让此线程暂停，以等待 GC
        Thread.sleep(500);
        if(SAVE_HOOK != null){
            SAVE_HOOK.isAlive();
        }else{
            System.out.println("dead");
        }

        SAVE_HOOK = null;
        System.gc();
        Thread.sleep(500);
        if(SAVE_HOOK != null){
            SAVE_HOOK.isAlive();
        }else{
            System.out.println("dead");
        }
    }
}

见以上代码段，SAVE_HOOK 对象的 finalize() 的确被执行，并且成功逃脱回收了。

另外一点是，一个对象的 finalize() 只会被调用一次，所以第二次的自救失败了。

上文的代码不是让读者去用此方法拯救对象。应该尽量避免使用 finalize()，它并不等同于 C 和 C++ 中的析构函数，这是 Java 刚诞生时为了使传统 C、C++ 程序员更容易接受 Java 所做的妥协。其代价是极高的。 finalize() 能做的工作，使用 try-finally 或者其他的方式能够做的更好、更及时。

(Ryuu：finalize() 自 Java 9 被弃用。其运行代价高，可能导致死锁、挂起。即使不在需要 finalize()，finalize() 也无法取消。不同对象的 finalize() 执行顺序没有保证，并且执行完成时间也没有保证。)

方法区回收

有人认为方法区 (如 HotSpot 虚拟机中的元空间或永久代) 是没有垃圾收集的，JLS 中提到，可以不要求虚拟机实现方法区中的垃圾收集，确实也有未实现或未完全实现方法区类型卸载的收集器存在 (如 JDK 11 时期的 ZGC 收集器就不支持类卸载)，方法区垃圾收集的付出/收获比也通常是较低的：在 Java 堆中，尤其是新生代中，对与常规应用进行一次 GC 通常可以回收 70% - 99% 的内存空间，相比之下，方法区回收有着苛刻的判定条件，其垃圾收集效果却往往很低。

方法区的垃圾收集主要回收两种内容：废弃的常量和不再使用的类型。回收废弃常量和回收 Java 堆中对象非常类似。例如字符串 “Java” 进入了常量池，但当前系统没有任何一个字符串对象的值是 “Java” (也就是说 “Java” 没有被任何字符串对象引用)，且虚拟机中也没有其他地方引用此字面量。如果此时发生 GC，若垃圾收集器判断有必要，这个 “Java” 将会被系统清理出常量池，常量池中的其他类 (接口)、方法、字段的符号引用也与此类似。

判定一个类型是否属于 “不再被使用的类” 的条件就比较苛刻了。需同时满足条件：

1. 类所有的实例被回收，Java 堆中不存在该类及其派生子类的实例。
2. 加载该类的类加载器已被回收。(此条件一般很难满足，除非是精心设计的可替换类加载器的场景，如 OSGi、JSP 的重加载等)
3. 该类对应的 java.lang.Class 对象没有在任何地方被引用，无法在任何地方通过反射访问该类方法。

Java 虚拟机被允许对满足以上三个条件的无用类进行回收，仅是 “被允许”，并不是和对象一样，没有了引用就必然会回收。

关于是否要进行类型回收，HotSpot 虚拟机提供了 -Xnoclassgc 参数进行控制，还可以通过 -verbose:class 以及 -XX:+TraceClass-Loading、 -XX:+TraceClassUnLoading 查看类加载和卸载信息，其中 -verbose:class 和 -XX:+TraceClass-Loading 可在 Product 版的虚拟机中使用，-XX:+TraceClassUnLoading 参数需要 FastDebug版虚拟机支持。

在大量使用反射、动态代理、CGLib 等字节码框架，动态生成 JSP 以及 OSGi 这类频繁自定义类加载器的场景中，通常都需要 Java 虚拟机具备类型卸载的能力，以保证不对方法区造成过大的内存压力。