我有一个包含 500000 个随机生成的 Tuple<long,long,string>
对象的列表,我正在对这些对象执行简单的“介于”搜索:
var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
当我生成随机数组并搜索 100 个随机生成的 x
值时,搜索在大约四秒内完成。然而,知道了 great wonders that sorting does to searching,我决定在运行 100 次搜索之前对我的数据进行排序 - 首先按 Item1
,然后按 Item2
,最后按 Item3
。由于分支预测,我希望排序后的版本执行得更快一些:我的想法是,一旦我们到达 Item1 == x
的点,所有对 t.Item1 <= x
的进一步检查都会正确地预测分支为“不接受”,加速搜索的尾部。令我惊讶的是,排序数组的搜索时间是原来的两倍!
我尝试改变运行实验的顺序,并为随机数生成器使用不同的种子,但效果是一样的:在未排序数组中的搜索运行速度几乎是在同一数组中搜索的两倍,但是排序!
有人对这种奇怪的效果有很好的解释吗?我的测试源代码如下;我正在使用 .NET 4.0。
private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
var data = new byte[8];
r.NextBytes(data);
return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
var res = x.Item1.CompareTo(y.Item1);
if (res != 0) return res;
res = x.Item2.CompareTo(y.Item2);
return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
}
}
static void Test(bool doSort) {
var data = new List<Tuple<long,long,string>>(TotalCount);
var random = new Random(1000000007);
var sw = new Stopwatch();
sw.Start();
for (var i = 0 ; i != TotalCount ; i++) {
var a = NextLong(random);
var b = NextLong(random);
if (a > b) {
var tmp = a;
a = b;
b = tmp;
}
var s = string.Format("{0}-{1}", a, b);
data.Add(Tuple.Create(a, b, s));
}
sw.Stop();
if (doSort) {
data.Sort(new TupleComparer());
}
Console.WriteLine("Populated in {0}", sw.Elapsed);
sw.Reset();
var total = 0L;
sw.Start();
for (var i = 0 ; i != TotalQueries ; i++) {
var x = NextLong(random);
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
total += cnt;
}
sw.Stop();
Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
Test(false);
Test(true);
Test(false);
Test(true);
}
Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)
Item1 == x
的位置,对 t.Item1 <= x
的所有进一步检查都会正确地将分支预测为“不接受”,从而加快搜索的尾部。显然,这种思路已经被残酷的现实证明是错误的:)
当您使用未排序列表时,所有元组都按内存顺序访问。它们已在 RAM 中连续分配。 CPU 喜欢顺序访问内存,因为它们可以推测性地请求下一个高速缓存行,因此它总是在需要时出现。
当您对列表进行排序时,您会将其按随机顺序排列,因为您的排序键是随机生成的。这意味着对元组成员的内存访问是不可预测的。 CPU 无法预取内存,几乎每次访问元组都是缓存未命中。
这是 GC 内存管理的特定优势的一个很好的例子:一起分配并一起使用的数据结构执行得非常好。他们有很好的参考地方。
在这种情况下,缓存未命中的惩罚超过了保存的分支预测惩罚。
尝试切换到 struct
元组。这将恢复性能,因为在运行时不需要指针取消引用来访问元组成员。
Chris Sinclair 在评论中指出“对于大约 10,000 或更少的 TotalCount,排序后的版本确实执行得更快”。这是因为一个小列表完全适合 CPU 缓存。内存访问可能无法预测,但目标始终在缓存中。我相信仍然会有一个小的惩罚,因为即使从缓存加载也需要一些周期。但这似乎不是问题,因为 CPU 可以处理多个未完成的负载,从而提高吞吐量。每当 CPU 遇到内存等待时,它仍然会在指令流中加速以尽可能多地排队内存操作。该技术用于隐藏延迟。
这种行为表明在现代 CPU 上预测性能是多么困难。从顺序访问到随机访问时,我们只慢了 2 倍这一事实告诉我,隐藏内存延迟的背后到底发生了多少事情。一次内存访问会使 CPU 停顿 50-200 个周期。鉴于第一个可能期望程序在引入随机内存访问时会变慢 10 倍以上。
LINQ 不知道您的列表是否已排序。
由于带有谓词参数的 Count 是所有 IEnumerables 的扩展方法,所以我认为它甚至不知道它是否以有效的随机访问在集合上运行。因此,它只检查每个元素,然后 Usr 解释了性能下降的原因。
要利用排序数组的性能优势(例如二进制搜索),您必须进行更多编码。
Count
或 Where
会“以某种方式”接受我的数据已排序的想法,并运行二进制搜索而不是简单的“检查所有内容”搜索。由于更好的分支预测,我所希望的只是一些改进(请参阅我的问题中的链接),但事实证明,参考的局部性在很大程度上胜过分支预测。
不定期副业成功案例分享
new List<Tuple<long,long,string>>(500000)
中来确认此行为。在这种情况下,已排序的测试与未排序的测试一样快,这与此答案的推理相匹配。Tuple
结构,程序开始按照我预测的方式运行:排序后的版本要快一点。而且,未排序的版本变得快了一倍!所以带有struct
的数字是 2s 未排序的,而 1.9s 是排序的。std::vector
的性能几乎总是优于std::list
。std::vector
与std::list
就是一个很好的例子。