c# 数组扫描对于大对象需要更长的时间
c# array scan takes longer for big objects
只是玩弄了一些 C# 代码，发现扫描内存数组所花费的时间取决于对象大小。
让我解释一下，对于两个长度相同但对象大小不同的集合，对于大对象，循环所花费的时间更长。
使用 Linqpad 测试：
- 如果我有一个 20M
SimpleObject 对象的数组，遍历所有对象需要 ~221 毫秒
- 如果我有一个 20M
BigObject 对象的数组，遍历所有对象需要大约 756 毫秒
为什么时间不接近常数？它不应该使用 kind of 指针算法吗？
谢谢
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
}
// Define other methods and classes here
更新：
在这种情况下，@IanMercer 评论和@erisco 为我指出了正确的方式，所以在稍微调整一下对象后，我得到了预期的行为。基本上我所做的是将额外的数据包装到一个对象中。通过这种方式，小型、中型和大型具有或多或少相同的大小，能够容纳 CPU 个缓存。现在测试显示相同的时间。
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
}
public Extra ExtraData;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
}
public Extra ExtraData;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var times = Enumerable
.Range(0, 10)
.Select(r => {
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
// string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
var smalltt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
// string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
var bigtt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
//string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
var mediumtt = sw.ElapsedMilliseconds;
return new {
smalltt,
mediumtt,
bigtt
};
})
.ToArray();
(new {
Small = times.Average(t => t.smalltt),
Medium = times.Average(t => t.mediumtt),
Big = times.Average(t => t.bigtt)
}).Dump();
}
一些有用的链接：
- http://igoro.com/archive/gallery-of-processor-cache-effects/
- https://msdn.microsoft.com/en-us/library/ms973852.aspx
- https://technet.microsoft.com/en-us/sysinternals/cc835722.aspx
谢谢大家！
Should it not be using kind of pointer arithmetic?
虽然 CLR 确实使用 "kind of pointer arithmetic" 来定位内存中的项目，但接下来发生的事情是不同的：一旦您开始访问 JustAnInt0s，CLR 就会开始从这些指针读取数据。
这就是它变得混乱的地方：现代硬件针对缓存进行了大量优化，因此当您请求 JustAnInt0 时，硬件预测 JustAnInt1、JustAnInt2 等是将遵循，因为对于大多数现实生活中的程序都是如此。这称为引用位置。与 JustAnInt0 一起加载的项目数取决于硬件中 缓存行 的大小。当对象较小而缓存行较大时，也可能会加载相邻内存区域中的一两个对象。
似乎当对象很小时，您的程序无意中利用了引用的局部性，因为当您访问 small[c].
时，多个小对象最终进入缓存
此行为也依赖于彼此相邻分配的小对象。如果对 small、medium 和 big 应用随机洗牌，访问时间应该会更接近。
就像其他答案所说的那样，这是因为 CPU 缓存和其他优化。
Smaller arrays: level 1 cache (very fast)
Larger arrays: level 2 cache (fast)
Huge arrays: not cached (normal)
Gigantic arrays: paged to disk (slow)
看到这个simple explanation。
我的回答纯属猜测，但希望它能提供一些可以测试和排除的东西。
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
FakeList 一个接一个分配很多对象，存储在一个数组中。分配器将连续存储所有这些对象。在分代 GC 中，分配是通过指针碰撞完成的（不搜索可用空间）(read here)。
假设一个对象的开销是16 bytes。从那让我们猜测 SmallObject 的大小是 20 字节，MediumObject 是 36 字节，而 BigObject 是 96 字节。
所以，我们有三个连续存储的对象数组。当 CPU 取一个 int，4 个字节时，它还会取一堆与 int 相邻的内存（在 CPU cache and cache lines 上读取）。假设 CPU 一次获取 64 个字节。
一个缓存行可以容纳多少个对象？
0 20 40 60 84
| SmallObject | SmallObject | SmallObject | SmallObject |
0 36 72
| MediumObject | MediumObject |
0 96
| BigObject |
注意：这里我们不考虑 data alignment。
一个缓存行适合 3.2 个 SmallObjects、1.77 个 MediumObjects 和 0.66 个 BigObjects。
我们在循环中自增JustAnInt0，恰好是对象的第一个字段。编译器可能按照您声明它们的相同顺序布置字段（因为它们都是整数，否则可能出于内存对齐目的重新排序）。
考虑到这一点，假设 JustAnInt0 是所有 SmallObject、MediumObject 和 BigObject 中的字节 16 到 20。这意味着我们可以一次从 SmallObjects 获取 3 JustAnInt0，一次从 MediumObject 获取 2 JustAnInt0，而一次只能从 BigObject 获取 1 JustAnInt0。
因此，您可以在 SmallObject 数组上最快递增 JustAnInt0 的原因是因为 CPU 可以将三个 JustAnInt0 加载到其本地缓存中一次。这意味着与 BigObject 相比，需要三分之一的主内存访问。主内存访问比 CPU 高速缓存访问 (read here) 慢一个数量级到两个数量级。主内存访问是您的 CPU 中最慢的指令之一，并且可能占据算法的总时间成本。
同样，这完全是猜测。唯一真正了解的方法是了解您的硬件并进行一些测试。希望这为开始调查提供了一个参考点。
只是玩弄了一些 C# 代码，发现扫描内存数组所花费的时间取决于对象大小。
让我解释一下，对于两个长度相同但对象大小不同的集合，对于大对象，循环所花费的时间更长。
使用 Linqpad 测试：
- 如果我有一个 20M
SimpleObject对象的数组，遍历所有对象需要 ~221 毫秒 - 如果我有一个 20M
BigObject对象的数组，遍历所有对象需要大约 756 毫秒
为什么时间不接近常数？它不应该使用 kind of 指针算法吗？
谢谢
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
}
// Define other methods and classes here
更新：
在这种情况下，@IanMercer 评论和@erisco 为我指出了正确的方式，所以在稍微调整一下对象后，我得到了预期的行为。基本上我所做的是将额外的数据包装到一个对象中。通过这种方式，小型、中型和大型具有或多或少相同的大小，能够容纳 CPU 个缓存。现在测试显示相同的时间。
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
}
public Extra ExtraData;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
}
public Extra ExtraData;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var times = Enumerable
.Range(0, 10)
.Select(r => {
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
// string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
var smalltt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
// string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
var bigtt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
//string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
var mediumtt = sw.ElapsedMilliseconds;
return new {
smalltt,
mediumtt,
bigtt
};
})
.ToArray();
(new {
Small = times.Average(t => t.smalltt),
Medium = times.Average(t => t.mediumtt),
Big = times.Average(t => t.bigtt)
}).Dump();
}
一些有用的链接：
- http://igoro.com/archive/gallery-of-processor-cache-effects/
- https://msdn.microsoft.com/en-us/library/ms973852.aspx
- https://technet.microsoft.com/en-us/sysinternals/cc835722.aspx
谢谢大家！
Should it not be using kind of pointer arithmetic?
虽然 CLR 确实使用 "kind of pointer arithmetic" 来定位内存中的项目，但接下来发生的事情是不同的：一旦您开始访问 JustAnInt0s，CLR 就会开始从这些指针读取数据。
这就是它变得混乱的地方：现代硬件针对缓存进行了大量优化，因此当您请求 JustAnInt0 时，硬件预测 JustAnInt1、JustAnInt2 等是将遵循，因为对于大多数现实生活中的程序都是如此。这称为引用位置。与 JustAnInt0 一起加载的项目数取决于硬件中 缓存行 的大小。当对象较小而缓存行较大时，也可能会加载相邻内存区域中的一两个对象。
似乎当对象很小时，您的程序无意中利用了引用的局部性，因为当您访问 small[c].
此行为也依赖于彼此相邻分配的小对象。如果对 small、medium 和 big 应用随机洗牌，访问时间应该会更接近。
就像其他答案所说的那样，这是因为 CPU 缓存和其他优化。
Smaller arrays: level 1 cache (very fast)
Larger arrays: level 2 cache (fast)
Huge arrays: not cached (normal)
Gigantic arrays: paged to disk (slow)
看到这个simple explanation。
我的回答纯属猜测，但希望它能提供一些可以测试和排除的东西。
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
FakeList 一个接一个分配很多对象，存储在一个数组中。分配器将连续存储所有这些对象。在分代 GC 中，分配是通过指针碰撞完成的（不搜索可用空间）(read here)。
假设一个对象的开销是16 bytes。从那让我们猜测 SmallObject 的大小是 20 字节，MediumObject 是 36 字节，而 BigObject 是 96 字节。
所以，我们有三个连续存储的对象数组。当 CPU 取一个 int，4 个字节时，它还会取一堆与 int 相邻的内存（在 CPU cache and cache lines 上读取）。假设 CPU 一次获取 64 个字节。
一个缓存行可以容纳多少个对象？
0 20 40 60 84
| SmallObject | SmallObject | SmallObject | SmallObject |
0 36 72
| MediumObject | MediumObject |
0 96
| BigObject |
注意：这里我们不考虑 data alignment。
一个缓存行适合 3.2 个 SmallObjects、1.77 个 MediumObjects 和 0.66 个 BigObjects。
我们在循环中自增JustAnInt0，恰好是对象的第一个字段。编译器可能按照您声明它们的相同顺序布置字段（因为它们都是整数，否则可能出于内存对齐目的重新排序）。
考虑到这一点，假设 JustAnInt0 是所有 SmallObject、MediumObject 和 BigObject 中的字节 16 到 20。这意味着我们可以一次从 SmallObjects 获取 3 JustAnInt0，一次从 MediumObject 获取 2 JustAnInt0，而一次只能从 BigObject 获取 1 JustAnInt0。
因此，您可以在 SmallObject 数组上最快递增 JustAnInt0 的原因是因为 CPU 可以将三个 JustAnInt0 加载到其本地缓存中一次。这意味着与 BigObject 相比，需要三分之一的主内存访问。主内存访问比 CPU 高速缓存访问 (read here) 慢一个数量级到两个数量级。主内存访问是您的 CPU 中最慢的指令之一，并且可能占据算法的总时间成本。
同样，这完全是猜测。唯一真正了解的方法是了解您的硬件并进行一些测试。希望这为开始调查提供了一个参考点。