对于大对象,c#array scan需要更长的时间

Question

只是玩一些C#代码,发现扫描内存数组所需的时间取决于对象的大小.

让我解释一下,对于两个长度相同但对象大小不同的集合,循环所需的时间对于大对象来说更大.

使用Linqpad进行测试:

• 如果我有一个20M SimpleObject对象的数组循环所有需要~221 ms
• 如果我有一个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

谢谢你们!

Answer 1

它不应该使用指针算法吗？

虽然CLR确实使用"种类指针算法"来定位内存中的项目,但接下来发生的事情是不同的:一旦开始访问JustAnInt0s,CLR就开始从这些指针中读取数据.

这是它就会变得混乱:现代化的硬件在很大程度上缓存优化,所以当你要求JustAnInt0,硬件预测JustAnInt1,JustAnInt2等,要遵循,因为它最真实的生活计划.这称为参考局部.随之加载的项目数JustAnInt0取决于硬件中缓存行的大小.当对象很小并且高速缓存行很大时,也可以加载相邻存储器区域中的一个或两个对象.

当对象很小时,程序似乎无意中利用了引用的局部性,因为当您访问时,多个小对象最终会进入缓存small[c].

此行为依赖于彼此相邻分配的小对象.如果你将随机shuffle应用于small,medium和big,访问时间应该更加接近.