fwdlist - Rust 中的简单链表。

一个简单的链表，查看API文档。该包也在crates.io上提供。

它是一个链表。它对缓存不友好，从理论上讲，它的速度相对较慢，但它允许在当前光标位置后进行 O(1) 插入...也许你关心这一点。

避免不安全

这里的一个目标是在Rust中玩耍，看看需要多少不安全代码。结果证明，你可以在不使用不安全代码的情况下实现简单链表的基础。

可变迭代器和光标都需要对链表的访问权限，其生命周期与链表本身上的可变引用不同。编译器无法自动推断这一点，需要我们的帮助。

penultimate_link() 性能

有时代码比必要更复杂，只是为了满足借用检查器。一些不安全代码不仅使代码更容易阅读，而且根据我们可能天真地相信的，对机器来说更有效率。

这里最好的例子是 penultimate_link()，它返回对链表最后一个链接的不可变引用。

为了说明此函数返回的内容，让我们假设以下链表

head_link -> node1.next -> node2.next -> node3.next -> nil

在这种情况下，penultimate_link() 将返回对 node2.next 的不可变引用。然后可以很容易地使用简单的 Option.take() 实现代码。

请参阅下面的 penultimate_link() 和 penultimate_link_with_unsafe() 实现。

汇编输出

查看下面的汇编输出（cargo build --release）

• penultimate_link():

0000000000016200 <::only_safe::>:
   16200:	48 8b 4f 08          	mov    0x8(%rdi),%rcx
   16204:	31 c0                	xor    %eax,%eax
   16206:	48 85 c9             	test   %rcx,%rcx
   16209:	74 1f                	je     1622a <::only_safe::+0x2a>
   1620b:	31 c0                	xor    %eax,%eax
   1620d:	0f 1f 00             	nopl   (%rax)
   16210:	48 89 ca             	mov    %rcx,%rdx
   16213:	48 8b 4a 08          	mov    0x8(%rdx),%rcx
   16217:	48 85 c9             	test   %rcx,%rcx
   1621a:	74 0e                	je     1622a <::only_safe::+0x2a>
   1621c:	48 83 79 08 00       	cmpq   $0x0,0x8(%rcx)
   16221:	75 ed                	jne    16210 <::only_safe::+0x10>
   16223:	48 83 c2 08          	add    $0x8,%rdx
   16227:	48 89 d0             	mov    %rdx,%rax
   1622a:	c3                   	retq

• penultimate_link_with_unsafe():

00000000000168a0 <::with_unsafe::>:
   168a0:	31 c0                	xor    %eax,%eax
   168a2:	48 83 7f 08 00       	cmpq   $0x0,0x8(%rdi)
   168a7:	74 18                	je     168c1 <::with_unsafe::+0x21>
   168a9:	48 83 c7 08          	add    $0x8,%rdi
   168ad:	0f 1f 00             	nopl   (%rax)
   168b0:	48 8b 0f             	mov    (%rdi),%rcx
   168b3:	48 83 79 08 00       	cmpq   $0x0,0x8(%rcx)
   168b8:	48 89 f8             	mov    %rdi,%rax
   168bb:	48 8d 79 08          	lea    0x8(%rcx),%rdi
   168bf:	75 ef                	jne    168b0 <::with_unsafe::+0x10>
   168c1:	c3                   	retq

汇编快速分析

首先要注意的是，原始代码是如何从高级Option和Box转换为简单的可空指针的。

• penultimate_link() 是一个包含两个条件分支的循环，它对列表中的每个节点进行两次测试（与Rust代码中的情况完全相同）。在测试next_link之前，它会先进行一次测试，然后再次测试当它成为新链接以处理每个新迭代时。
• penultimate_with_unsafe() 是一个只有一个条件的循环，但与Rust代码类似，它保留了一个“prev_link”指针。

在我对现代CPU架构极其有限的知识下，观察汇编代码，我推断 penultimate_link() 需要两倍的分支预测，并且这两个函数在每个迭代中都进行两次数据读取。

考虑到现代CPU似乎疯狂地进行流水线/预取，两个分支预测的成本应该相当于只有一个。

Callgrind/Cachegrind（valgrind）分析

在添加 #[inline(never)] 到两个 penultimate_link* 函数后，我像这样运行valgrind

$ valgrind --tool=callgrind --dump-instr=yes --trace-jump=yes --cache-sim=yes --branch-sim=yes --collect-atstart=no --toggle-collect=*penultimate_link* target/release/fwdlist... --test one_penultimate

我们基本上得到以下报告

• Ir：指令读取，penultimate_link() 有更多指令，因此读取的指令更多。
• Dr：数据读取。 penultimate_with_unsafe() 执行更多一次循环迭代，读取更多 2 条数据。
• D1mr：L1缓存上的数据读取未命中。两者相似。
• DLmr：最后一级缓存上的数据读取未命中。有趣的是，penultimate_with_unsafe() 有更多未命中。
• Bc：条件分支。确认 penultimate_link() 有两个条件，而另一个有一个。
• Bcm：条件分支未命中。 penultimate_with_unsafe() 多了一次，可能是额外的迭代？

AMD Phenom(tm) II X4 965 Processor
penultimate_safe        ... bench:   3651099 ns/iter (+/- 35924)
penultimate_with_unsafe ... bench:   3687377 ns/iter (+/- 33386)

Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz
penultimate_safe        ... bench:   2333951 ns/iter (+/- 27634)
penultimate_with_unsafe ... bench:   2334611 ns/iter (+/- 43642)

Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz
penultimate_safe        ... bench:   1675111 ns/iter (+/- 106477)
penultimate_with_unsafe ... bench:   2127297 ns/iter (+/- 128966)

Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz
penultimate_safe        ... bench: 2399497518 ns/iter (+/- 357540058)
penultimate_with_unsafe ... bench: 2509462341 ns/iter (+/- 377119880)