Ryuu 的个人博客

一个计算机初学者

这条建议可能听起来有些奇怪,因为 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 之外,在遍历整个老年代中的对象,以确保可达性分析的准确性,反之同理。这虽然在理论上可行,但是会为内存回收带来很大的性能负担,为解决此问题,引入第三个假说:

  1. **跨代引用假说 (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 虚拟机具备类型卸载的能力,以保证不对方法区造成过大的内存压力。

刚接触事件的人可能觉得触发事件是很容易的,只需将事件定义好,并在需要触发时调用相关的事件处理程序就可以了,底层的多播委托将会依次执行这些处理程序。实际上触发事件并不是如此简单。若根本没有事件对应的处理程序会怎样?若多个线程都要检测并调用事件处理程序,而线程之间互相争夺,会怎样?C# 6.0 引入的 null 条件运算符 (null-conditional operator,又称 null 传播运算符 (null-propagation operator)) 可用更加清晰的写法来解决这些问题。

1
2
3
4
5
6
7
8
9
10
11
public class EventSource
{
private int counter;
private EventHandler<int> Updated;

public void RaiseUpdates()
{
counter++;
Updated(this, counter);
}
}

这种旧写法有个明显的问题:如在对象上出发 Updated 事件是并没有事件处理程序与之相关,将会发生 NullReferenceException,因为 C# 用 null 值表示这种没有处理程序与之相关的情况。于是,触发事件前,必须先判断事件处理程序是否为 null。

1
2
3
4
5
6
public void RaiseUpdates()
{
counter++;
if(Updated != null)
Updated(this, counter);
}

但这种写法依然有 bug。当程序线程执行完 if 判断了 Updated 不为 null 后,可能会有另一个线程打断该线程,并解除订阅,这样的话依然会引发 NullReferenceException,虽然这种情况很少见。

这个 bug 很难诊断,也很难修复。想重现该错误,必须按照上述线程的执行顺序执行。一些开发老手在此问题上吃过亏,他们知道其危险,改用另一个种写法:

1
2
3
4
5
6
7
public void RaiseUpdates()
{
counter++;
var handler = Updated;
if(handler != null)
handler(this, counter);
}

此方法是可行的,线程是安全的。但是从阅读的角度来看,看代码的人不太明白为何这样改后就能确保线程安全。

var handler = Updated; 这是对赋值号的右侧做 *浅拷贝 (shallow copy)*,也就是创建一个新的引用,指向其事件处理程序。因此,即使是 Updated 被其他线程注销,变为 null。也不会影响 handler,handler 依然保存了原先记录的事件订阅者。这段代码实际上是通过浅拷贝为事件订阅这做了份快照,触发事件时通过快照来触发事件处理程序。

触发事件是一项简单的任务,不该用这么冗长且费解的方式去完成。

有了 null 条件运算符,可以用更清晰的写法来实现:

1
2
3
4
5
public void RaiseUpdates()
{
counter++;
Updated?.Invoke(this, counter);
}

采用了 null 条件运算符 (也就是 ?.) 安全地调用事件处理程序。该运算符首先对左侧内容进行 null 判断,若非 null 执行右侧内容。若为 null 则跳过此语句。

从语义上来说这和 if 类似。但区别在于 ?. 运算符左侧的内容只会计算一次。

由于 C# 不许 ?. 运算符右侧直接出现一对括号,因此必须用 Invoke() 去触发事件。每定义一种委托或事件,编译器都会为此生成类型安全的 Invoke(),这意味着,通过 Invoke 方法触发事件,使得代码篇幅更小,且线程安全。

有了这种简单且清晰的写法后,原来的写法需要改一改了。以后触发事件都应采用此写法。

成员访问运算符和表达式 - C# 参考

Java 用起来如此舒适的一个因素在于,它是一门安全的语言 (safe language)。这意味着,它对于缓冲区溢出、数组越界、非法指针以及其他的内存破坏错误都自动免疫,而这些错误却困扰着诸如 C 和 C++ 这样的不安全语言。在一门安全语言中,在设计类时,无论系统的其他部分发生什么问题,类的约束都可以保持为真。对于那些 “把所有内存当作一个巨大的数组来对待” 的语言来说,这是不可能的。

即使在安全的语言中,如果不采取一点措施,还是无法与其它的类隔离开来。建设类的客户端会尽其所能来破坏这个类的约束条件,因此你必须保护性地设计程序。实际上,只有当有人试图破坏系统的安全性时,才可能发生这种情况;更有可能的是,对你的 API 产生误解的程序员,所导致的各种不可预期的行为,只好由类来处理。无论是何种情况,编写面对客户端的不良行为仍保持健壮性的类,这是非常值得投入时间去做的事情。

如果没有对象的帮助,另一个类不可能修改对象的内部状态,但是对象很容易在无意识的情况下提供帮助。例如 下面的类表示一段不可变的时间周期:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Broken "immutable" time period class
public class Period {
private final Date start;
private final Date end;

public Period(Date start, Date end) {
if (start.compareTo(end) > 0)
throw new IllegalArgumentException(start + " after " + end);
this.start = start;
this.end = end;
}

public Date start() {
return start;
}

public Date end() {
return end;
}
}

乍看之下,此类似乎是不可变的,并且加了周期的起始时间 (start) 不能在结束时间 (end) 之后。然而,因为 Date 类本身是可变的,因此很容易违反这个约束条件:

1
2
3
4
5
// Attack the internals of a Period instance
Date start = new Date();
Date end = new Date();
Period p = new Period(start, end);
end.setYear(78); // Modifies internals of p!

从 Java 8 开始,修正这个问题最明显的方式是使用 Instant (或 LocalDateTime,或者 ZonedDateTime) 代替 Date,因为 Instant (以及另一个 java.time 类) 是不可变类 (见17条)。Date 已经过时了,不应该在新代码中使用

为了保护 Period 实例的内部信息,避免受到此攻击,对于构造器的每个可变参数进行保护性拷贝 (defensive copy) 是必要的,并且使用备份对象作为 Period 实例的组件,而不使用原始的对象:

1
2
3
4
5
6
7
// Repaired constructor - makes defensive copies of parameters
public Period(Date start, Date end) {
this.start = new Date(start.getTime());
this.end = new Date(end.getTime());
if (this.start.compareTo(this.end) > 0)
throw new IllegalArgumentException(this.start + " after " + this.end);
}

用了新的构造器之后,上述的攻击对于 Period 实例不再有效。注意,保护性拷贝是在检查参数的有效性 (见第38条) 之前进行的,并且有效性检查是针对拷贝之后的对象,而不是针对原始的对象。虽然这样做看起来有点不太自然,却是必要的。这样做可以避免在 “危险阶段” 期间从另一个线程改变类的参数,这里的危险阶段是指从检査参数开始,直到拷贝参数之间的时间段。在计算机安全社区中,这被称作Time-Of-Check / Time-Of-Use 或者 TOCTOU 攻击 [ViegaO1]。

同时也请注意,没有用 Date 的 clone 方法来进行保护性拷贝。因为 Date 是非 final 的, 不能保证 clone 方法一定返回类为 java.util.Date 的对象:有可能返回专门出于恶意的目的而设计的不可信子类实例。例如,子类可以在每个实例被创建的时候,把指向该实例的引用记录到一个私有的静态列表中,并且允许攻击者访问这个列表。这将使得攻击者可以 自由地控制所有的实例。为了阻止这种攻击,对于参数类型可以被不可信任方子类化的参数,不使用 clone 方法进行保护性拷贝

虽然替换构造器就可以成功地避免上述的攻击,但是改变 Period 实例仍然是有可能的,因为它的访问方法提供了对其可变内部成员的访问能力:**(Ryuu:原始方法返回的是其成员的视图,这样会导致 Period 可被修改)**

1
2
3
4
5
6
7
8
// Repaired accessors - make defensive copies of internal fields
public Date start() {
return new Date(start.getTime());
}

public Date end() {
return new Date(end.getTime());
}

采用了新的构造器和新的访问方法之后,Period 真正是不可变的了。不管程序员是多么恶意,或者多么不合格,都绝对不会违反 “周期的起始时间不能落后于结束时间” 的约束条件。因为除了 Period 类自身之外,其他任何类都无法访问 Period实例中的任何一个可变域。这些域被真正封装在对象的内部。

访问方法与构造器不同,它们在进行保护性拷贝的时候允许使用 clone 方法。之所以如此, 是因为我们知道,Period 内部的 Date 对象的类是 java.util.Date,而不可能是其他某个潜在的不可信子类。也就是说,基于第11条中所阐述的原因,一般情况下,最好使用构造器或者静态工厂。

参数的保护性拷贝并不仅仅针对不可变类。每当编写方法或者构造器时,如果它要允许客户提供的对象进入到内部数据结构中,则有必要考虑,客户提供的对象是否有可能是可变的。如果是,就考虑你的类是否能够容忍对象进入数据结构之后发生变化。如果答案是否定的,就必须对该对象进行保护性拷贝,并且让拷贝之后的对象,而不是原始对象进入到数据结构中。例如,如果你正在考虑使用由客户提供的对象引用作为内部 Set 实例的元素,或者 作为内部Map实例的键 (key),就应该意识到,如果这个对象在插入之后再被修改,Set 或者 Map 的约束条件就会遭到破坏。

在内部组件被返回给客户端之前,对它们进行保护性拷贝也是同样的道理。不管类是否为不可变的,在把一个指向内部可变组件的引用返回给客户端之前,也应该加倍认真地考虑。 解决方案是,应该返回保护性拷贝。记住长度非零的数组总是可变的。因此,在把内部数组返回给客户端之前,应该总要进行保护性拷贝。另一种解决方案是,给客户端返回该数组的不可变视图(immutableview)。这两种方法在第13条中都已经演示过了。

可以肯定地说,只要有可能,都应该使用不可变的对象作为对象内部的组件,这样就不必再为保护性拷贝(见第15条)操心。在前面的 Period 例子中,有经验的程序员通常使用 Date.getTime() 返回的 long 基本类型作为内部的时间表示法, 而不是使用 Date 对象引用。他们之所以这样做,主要因为 Date 是可变的。

保护性拷贝可能会带来相关的性能损失,这种说法并不总是正确的。如果类信任它的调用者不会修改内部的组件,可能因为类及其客户端都是同一个包的双方,那么不进行保护性拷贝也是可以的。在这种情况下,类的文档中就必须淸楚地说明,调用者绝不能修改可受影响的参数或者返回值

即使跨越包的作用范围,也并不总是适合在将可变参数整合到对象中之前,对它进行保护性拷贝。有一些方法和构造器的调用,要求参数所引用的对象必须有个显式的交接过程。当客户端调用这样的方法时,它承诺以后不再直接修改该对象。如果方法或者构造器 期望接管一个由客户端提供的可变对象,它就必须在文档中明确地指明这一点。

如果类所包含的方法或者构造器的调用需要移交对象的控制权,这个类就无法让自身抵御恶意的客户端。只有当类和它的客户端之间有着互相的信任,或者破坏类的约束条件不会伤害到除了客户端之外的其他对象时,这种类才是可以接受的。后一种情形的例子是包装类模式 (wrapper class pattern) (见第18条)。根据包装类的本质特征,客户端只需在对象被包装 之后直接访问它,就可以破坏包装类的约束条件,但是,这么做往往只会伤害到客户端自己。

总结:如果类具有从客户端得到或者返回到客户端的可变组件,类就必须保护性地拷贝这些组件。如果拷贝的成本受到限制,并且类信任它的客户端不会不恰当地修改组件,就可以在文档中指明客户端的职责是不得修改受到影响的组件,以此来代替保护性拷贝。

自从有了编程这门职业,开发者需要把计算机中板寸的信息转换成更便于人阅读的格式。C# 语言中的相关 API 可以追溯到几十年前诞生的 C 语言,但是这些旧习惯应该改变,C# 6.0 提供了内插字符串 (Interpolated String) 这项新功能可以更好的用来设置字符串格式。

与旧习惯相比,这项功能有很多好处。开发者可用他们写出可读性更高的代码,编译器也可以用它实现更为完备的静态类型检查机制,降低程序出错概率。此外,它还可以提供更加丰富的语法,令你可以用更为合适的表达式来生成自己想要的字符串的格式。

String.Format() 虽然可使用,但是会导致一些问题。

  1. 开发者必须对生成的字符串进行测试及验证。所有的替换操作都是根据格式字符串中的序号来完成的,而编译器不会验证格式字符串后的参数个数与有待替换的序号数是否相等。如果两者不相等,那么程序在运行时将抛出异常。
  2. 格式字符串中的序号与 params 数组中的位置必须对应。而阅读代码的人不太容易看出数组中的字符串是不是按照正确顺序排列。必须允许代码,并检查生成的字符串,才能确认这一点。

不妨用 C# 提供的新特性简化代码编写工作,这项新特性就是内插字符串,这种语法糖 (syntactic sugar),的功能是极其强大的。

内插字符串以 $ 开头,不像传统的格式字符串把序号放在一对花括号,并用其指代的 params 数组中的对应元素,而是直接在花括号中编写 C# 表达式。

  1. 开发者能直接在字符串中看到待替换的内容,代码可读性高
  2. 表达式在字符串内,每一个有待替换的部分都能与替换部分的表达式对应

花括号中的内容叫作表达式而不是泛称为语句,其不能使用 if / else 或 while 等控制流语句来做替换。若需要控制流语句做替换,那么必须把这些逻辑写成方法,在内插字符串里嵌入该方法的调用结果。

字符串内插机制是通过库代码完成的,那些代码与当前的 string.Format() 类似 (至于如何实现国际化,见第五条)。内插字符串会在必要的时候把变量从其他类型转换为 string 类型:

1
Console.WriteLine($"The value of pi is {Math.PI}");

由字符串内插操作生成的代码会调用一个参数为 params 对象数组的格式化方法。 Math.PI 是 double 类型,而 double 类型是值类型,因此,必须将其自动转换为 Object 才行。此转换需装箱,**若此代码运行很频繁,或需要在短小的循环中反复执行,那么会严重影响性能 (见第9条)**。该情况下,开发者应自己去做字符串转换,这样就不需要给表达式中的数值装箱了:

1
Console.WriteLine($"The value of pi is {Math.PI.ToString()}");

如果 ToString() 直接返回的文本不符合你的要求,那么可以修改其他参数,创造你想要的文本:

1
Console.WriteLine($"The value of pi is {Math.PI.ToString("F2")}")

可使用标准格式说明符 (C# 语言内建说明符) 来调整字符串格式。我们有可能需要对字符串做一些处理,或是把表达式返回的对象格式化,只需要在大括号中的表达式后面加上冒号,并将格式说明符写在右侧。

1
Console.WriteLine($"The value of pi is {Math.PI:F2}");

由于条件表达式也使用冒号,因此,如果在内插字符串中用冒号,那么 C# 可能会把他理解成格式说明符的前导符,而不将其视为条件表达式的一部分,这行代码是无法编译的:

1
Console.WriteLine($"The value of pi is {round ? Math.PI.ToString(): Math.PI.ToString("F2")}");

可以用小括号将整个内容括起,编译器就不会再把冒号是为格式字符串的前导符了。

1
Console.WriteLine($"The value of pi is {(round ? Math.PI.ToString() : Math.PI.ToString("F2"))}");

可以通过 null 合并运算符 (null-coalescing operator) 与 null 条件运算符 (null-conditional operator,也称为 null-propagation operator (null 传播运算符)) 更清晰的处理那些可能缺失的值:

1
Console.WriteLine($"The customer's name is {c?.name ?? "Name is missing"}");

通过示例可以看出,花括号中还可以嵌入字符串,凡是位于 { 和 } 之间的字符,就都会被当作此表达式中的 C# 代码,并加以解析 (冒号除外,他是用来表示右侧的内容是格式说明符)。

内插字符串可以嵌套。合理利用此方法,可以极大的简化编程工作量。

1
2
3
4
5
Console.WriteLine(
$@"Record is {(
records.TryGetValue(index, out string result) ? result : $"No record found at index {index}"
)}"
);

如果查找的记录不存在,那么就会执行条件表达式的 false 部分,从而令嵌套的内插字符串生效,该字符串会返回一条消息,指出要查找位置的记录不存在。

可以使用 LINQ 查询操作来创建内容,其本身也支持利用内插字符串调整查询结果格式

1
2
3
4
5
6
7
8
9
var output = $@"The First five items are: {
src.Take(
5
).Select(
n => $@"Item: {n.ToString()}"
).Aggregate(
(c, a) => $@"{Environment.NewLine}{a}"
)
}";

上面的这种写法可能不太会出现在正式的产品代码中,但可以看出,内插字符串和 C# 之间结合的相当密切。ASP.NET MVC 框架中的 Razor View 引擎也支持内插字符串,使得开发者在编写 Web 应用程序时能够更便捷地以 HTML 的形式来输出信息。默认的 MVC 应用程序本身就演示了怎样在 Razor View 中使用内插字符串,以下示例节选自 controller 部分,它可以显示当前登入的用户名:

1
<a asp-controller="Message" asp-action="Index" title="Manage"> Hello@User.GetUserName()!</a>

构建应用程序中的其他 HTML 页面时,也可以采用这个技巧,更为精确地表达你想输出的内容。

上述实例展示了内插字符串的强大功能,虽然这些功能可用传统格式化字符串实现,但是比较麻烦。值得注意的地方在于,内插字符串本身也会解析称为一条普通的字符串 (将其中的填充部分解析填充后,其与普通字符串无差别)。使用内插字符串创建 SQL 命令是极其危险的:内插字符串不会创建参数化的 SQL 查询 (parameterized SQL query),只会形成一个普通的 string 对象,参数已经全部被写入至该 string 中了。不只是 SQL 命令,凡是需要留到运行时去解析的信息都有此风险,开发者需要特别小心。

在每个覆盖了 equals 方法的类中,都必须覆盖 hashCode 方法。如果不这样做,就会违反 hashCode 的通用约定,从而导致该类无法结合所有基于散列的集合一起正常运作,这类集合包括 HashMap 和 HashSet。下面是约定的内容,摘自 Object 规范:

  • 在应用程序的执行期间,只要对象的 equals 方法的比较操作所用到的信息没有被修改,那么对同一个对象的多次调用,hashCode 方法都必须始终返回同一个值。在一个应用程序与另一个程序的执行过程中,执行 hashCode 方法所返回的值可以不一致。
  • 如果两个对象根据 equals(Object) 方法比较相等,调用这两个对象中的 hashCode 方法都必须产生同样的整数结果。
  • 如果两个对象根据 equals(Object) 方法比较不相等,调用这两个对象中的 hashCode 方法,则不一定要求 hashCode 方法必须产生不同的结果 (哈希碰撞)。但是程序员应该知道,给不相等的对象产生截然不同的整数结果,有可能提高散列表(hash table)的性能。

因没有覆盖 hashCode 而违反的关键约定是第二条:相等的对象必须具有相等的散列码 (hash code)。根据类的 equals 方法,两个截然不同的实例在逻辑上有可能是相等的,但是根据 Object 类的 hashCode 方法,它们仅仅是两个没有任何共同之处的对象。因此,对象的 hashCode 方法返回两个看起来是随机的整数,而不是根据第二个约定所要求的那样,返回两个相等的整数。

假设在 HashMap 中用第10条中出现过的 PhoneNumber 类的实例作为键:

1
2
HashMap<PhoneNumber, String> m = new HashMap<>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");

你可能期望 m.get(new PhoneNumber(707, 867, 5309)) 会返回 “Jenny”,但它实际上返回的是 null。注意,这里涉及两个 PhoneNumber 实例:第一个被插入 HashMap 中,第二个实例与第一个相等,用于从 Map 中根据 PhoneNumber 去获取用户名字。由于 PhoneNumber 类没有覆盖 hashCode 方法,从而导致两个相等的实例具有不相等的散列码,违反了 hashCode 的约定。因此,put 方法把电话号码对象存放在一个散列桶 (hash bucket)中,get 方法却在另一个散列桶中查找这个电话号码。即使这两个实例正好被放到同一个散列桶中,get 方法也必定会返回 null,因为 HashMap 有一项优化,可以将与每个项相关联的散列码缓存起来,如果散列码不匹配,也就不再去检验对象的等同性。

修正这个问题非常简单,只需为PhoneNumber类提供一个适当的 hashCode 方法即可。那么,hashCode 方法应该是什么样的呢?编写一个合法但并不好用的 hashCode 方法没有任何价值。例如,下面这个方法总是合法的,但是它永远都不应该被正式使用

1
2
3
4
5
// The worst possible legal hashCode implementation -never use!
@Override
public int hashCode() {
return 42;
}

上面这个 hashCode 方法是合法的,因为它确保了相等的对象总是具有同样的散列码。但它也极为恶劣,因为它使得每个对象都具有同样的散列码。因此,每个对象都被映射到同一个散列桶中,使散列表退化为链表 (linked list)。它使得本该线性时间运行的程序变成了以平方级时间在运行。对于规模很大的散列表而言,这会关系到散列表能否正常工作。

一个好的散列函数通常倾向于 “为不相等的对象产生不相等的散列码”。这正是hashCode约定中第三条的含义。理想情况下,散列函数应该把集合中不相等的实例均匀地分布到所有可能的int值上。要想完全达到这种理想的情形是非常困难的。幸运的是,相对接近这种理想情形则并不太困难。下面给出一种简单的解决办法:

  1. 声明一个 int 变量并命名为 result,将它初始化为对象中第一个关键域的散列码 c,如步骤 2.1 中计算所示 (如第10条所述,关键域是指影响 equals 比较的域)。

  2. 对象中剩下的每一个关键域 f 都完成以下步骤:

    1. 为该域计算 int 类型的散列码 c :

      1. 若该域是基本类型,则计算 Type.hashCode(f)。这里的 Type 是装箱基本类型的类,与 f 的类型相对应。

      2. 若该域是一个对象引用,并且该类的 equals 方法通过递归地调用 equals 的方式来比较这个域,则同样为这个域递归地调用 hashCode。

        若需要更复杂的比较,则为这个域计算一个 “范式” (canonical representation),然后针对这个范式调用 hashCode。

        若这个域的值为 null,则返回 0 (或者其他某个常数,但通常是0)。

      3. 如果该域是一个数组,则要把每一个元素当作单独的域来处理。

      递归地应用上述规则,对每个重要的元素计算一个散列码,然后根据步骤 2.2 中的做法把这些散列值组合起来。

      若数组域中没有重要的元素,可以使用一个常量,但最好不要用 0。

      若数组域中的所有元素都很重要,可以使用 Arrays.hashCode 方法。

    2. 按照下面的公式,把步骤 2.1 中计算得到的散列码 c 合并到 result 中:

      1
      result = 31 * result + c;
  3. 返回 result 。

    (Ryuu:附上 java 源码的实现,你会发现这就是作者提供的解决方案。这并不奇怪,本书作者 Joshua Bloch,曾任职 Sun 公司 进行 Java 的开发)

    1
    2
    3
    4
    // java.util.Objects
    public static int hash(Object... values) {
    return Arrays.hashCode(values);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // java.util.Arrays
    public static int hashCode(Object a[]) {
    if (a == null)
    return 0;

    int result = 1;

    for (Object element : a)
    result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
    }

    写完了 hashCode 方法之后,问问自己相等的实例是否都具有相等的散列码。要编写单元测试来验证你的推断 (除非利用 AutoValue 生成 equals 和 hashCode 方法,这样你就可以放心地省略这些测试)。如果相等的实例有着不相等的散列码,则要找出原因,并修正错误。

0%