Hello World
Spiga

浅谈代码的执行效率(3):缓存与局部性

2010-01-12 00:03 by 老赵, 9546 visits

在前两篇文章里,我们讨论了程序性能的两个方面,一是算法(广义的算法,即解决问题的方法),二是编译器。通过这两个方面,我想表达的意思是,一段程序的执行效率,是很难从表面现象得出结论的,至少从一些简单的层面,如代码的长度是几乎难以说明任何问题——因此一定要进行Profiling才能做到有效的优化。而现在,我们假设两段程序算法基本相同,编译器也只是进行简单的“翻译”,那么……我们能从“表面”看出性能高下吗?

那么就从一个最简单的例子看起吧。假设DoSomethingA和DoSomethingB里做的事情是固定的,那么您认为下面两种写法的哪个性能更好?

for (int i = 0; i < 100; i++)
{
    DoSomethingA();
    DoSomethingB();
}
for (int i = 0; i < 100; i++)
    DoSomethingA();

for (int i = 0; i < 100; i++)
    DoSomethingB();

这两段逻辑的算法基本上完全相同,如果编译器只是进行直接“翻译”而不进行优化,那么第一种做法对于i的累加和条件跳转比较少,因此您可能会得出结论:“很明显”第一段代码的执行效率比较高。只可惜事实并非那么简单,因为影响程序性能的另一个关键因素是:缓存。

“缓存”无处不在。在CPU中,性能最快的存储设备当属“寄存器”,不过众所周知寄存器的数量是极其有限的。因此,CPU都会有L1 Cache和L2 Cache的多级缓存机制。其中,L2 Cache的性能比L1 Cache和寄存器都要慢,但还是比内存要快许多。当某个Core需要从内存中获取数据的时候,便会从L1 Cache获取数据,如果L1 Cache没有那么就会从多个核共用的L2 Cache拿,再没有便会从内存拿——由于操作系统的虚拟内存机制,可能还要从磁盘的交换页中获取数据,此时性能自然相当差了。

虽然寄存器只使用一个字长(如4字节)的数据,但是L1 Cache从L2 Cache拿数据时总是“一块一块”拿的——这么一块往往就是连续的64个字节。换句话说,在CPU读取的一个地址的数据之后,读取其他一些地址上的数据便会比另一些特别快,因为它们都已经在L1 Cache中了。如果一个程序能够利用起CPU的这个特性,那它的性能往往便可以更好一些(自然还有很多其他影响性能的因素)。

局部性(Locality),便是用来描述程序是否能利用好缓存的名词。我们说一个程序的局部性比较好,那么就表示它能够较好地利用起CPU的缓存机制。局部性分“空间局部性”和“时间局部性”两方面,前者是指“加载一个地址的数据之后,继续加载它附近的数据”,后者表示“在加载一个地址的数据之后,短时间内重新加载这块数据”。无论是哪一方面,目的都是希望从较快的缓存中加载“热”的数据。为什么冷启动总是很慢?为什么有人说系统从开机后会越跑越快?其实道理都差不多。

那么现在,您还能判断上面两种做法的效率孰高孰低?虽然第一种做法减少了i的累加次数和条件跳转的次数,但是它在一次循环中做了两件事情,可能在执行DoSomethingB方法的时候,DoSomethingA方法中刚刚进入缓存的数据便冷却了,于是在下次执行DoSomethingA时又要重新从较慢的存储设备中加载数据。而在第二种做法中,我们“密集”地执行完100次DoSomethingA或DoSomethingB的调用,而此间大量的数据访问都是集中在L1 Cache上,性能优势不言而喻。

我以前的文章《计算机体系结构与程序性能》在第一部分里也讨论了局部性对程序性能的影响,讲的更为具体一些,您也可以参考其中的内容。

由于程序指令不是执行效率的唯一因素,因此从代码长短上判断程序性能也是非常不靠谱的事情。当然,从任何独立的角度来判断性能可能都不合适。例如在那篇文章里提到,出于程序性能的考虑应该使用全局变量——当然作者也认为这不是好的设计,事实上在我们刚才的例子中,在一个循环中做多件事情可能也值得重构。如果您使用全局变量,它的确省下了push,pop等指令的开销,但是这么一个全局变量——例如是一个静态变量,它存储在堆的某一个地方,访问它并非是一个局部性方面的优秀实践。与之相反,由于L1 Cache的作用,在调用栈上访问“参数”或“局部变量”并不会比访问寄存器慢多少,此时push,pop几个指令的开销可能就不算什么了。更何况,如果编译器/运行时内联了这个方法,这样连push,pop等指令也不会出现了。

记得前一段时间在有某些朋友在我的博客上发布一些较为“激进”的说法,例如“学底层只是对写.NET程序没有帮助,因为就算你知道了这些,C#也没有办法内嵌汇编”。我不同意这个说法,因为即便是.NET程序,它也是在符合计算机体系结构的规律下运行的,我们完全可以在一定程度上了解一段代码在执行时的表现。

就拿目前谈到的“局部性”来说,我们便可以把握很多东西。比如,我们知道每个线程的调用栈在默认情况下是1兆大小,因此两个线程调用栈上的数据几乎不可能出现在同一个Cache条目中。再比如,由于“时间局部性”,最近使用的数据最有可能出现在缓存中,因此在.NET 4.0的并行库在调度“私有队列”的任务时会倾向于执行最新创建的任务。再比如,您是使用两个int数组来表示一系列坐标的x值和y值,还是构造一个struct Point数组来保存它们呢?虽然使用两个int数组更节省内存,但是从局部性考虑问题的话,您会发现同一个坐标的x值和y值存放在一起可能更为合适。

我的这几篇文章,其实也都在强调从代码表面判断程序性能的“不确定性”。同样道理,即便是把它们的汇编代码(片断)放在您面前,您也可能很难“看出”性能区别。这也从侧面说明了Profiling的重要性:阅读代码是静态的,而程序执行和Profiling都是动态的。之前有朋友对我说“你最近迷上Profiler啦?”其实我这里的Profiling泛指“一种探索程序性能的方式”,并不是指某个特定的手段,更不是某个具体的工具——不过无论是使用VS的Profiler也好,还是自己搞一个CodeTimer,都比“读代码”来的可靠。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

70 条回复

  1. 老赵
    admin
    链接

    老赵 2010-01-12 00:03:00

    还是打算把最后一篇拆开写了。

  2. 李胜攀
    *.*.*.*
    链接

    李胜攀 2010-01-12 00:10:00

    占个板凳先

  3. Anders Cui
    *.*.*.*
    链接

    Anders Cui 2010-01-12 00:31:00

    原来代码的背后还有这么多微妙的事情

  4. JosephLiu
    *.*.*.*
    链接

    JosephLiu 2010-01-12 00:50:00

    第一发现能这么靠前,必须回了。第一次回帖。。。献给你了。。。

  5. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-12 08:30:00

    老赵,你似乎没有仔细分析两段程序的差别,是否指变量"i"两次申请内存空间和申请一次的区别呢?

  6. 邢少
    *.*.*.*
    链接

    邢少 2010-01-12 08:57:00

    貌似明白,但是没有看到什么实质的东西。缓存确实在一定程度上提高了系统的性能,但是在实际的开发中,应该遵循那些特定的习惯呢?就好比上文提到的 dosomethinga和dosomethingb,到底两个循环那个更高效,它决定于dosomething的内容吧。赵老师如果可以整理一些提高性能的缓存使用、利用的“习惯”这些会更有意义的。

  7. zeus2
    *.*.*.*
    链接

    zeus2 2010-01-12 08:57:00

    靠前沙发。楼上第一个是执行A,执行B100次。
    第二个是执行A100次,再执行b100次

  8. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2010-01-12 09:03:00

    老赵的意思是说在循环里做多个事情效率可能会比多个循环做多个事情效率高是吗,例如你上面的例子

  9. 小火
    *.*.*.*
    链接

    小火 2010-01-12 09:05:00

    哈哈,不错受教,指明了一个大概方向
    要是能再讲深入点更好。比如举例.Net中,哪些类库方法用了缓存局部性的思想,操作系统在读L1 Cache或L2 Cache的机制。为什么一次读64Byte呢

  10. mythzz
    *.*.*.*
    链接

    mythzz 2010-01-12 09:06:00

    邢少:貌似明白,但是没有看到什么实质的东西。缓存确实在一定程度上提高了系统的性能,但是在实际的开发中,应该遵循那些特定的习惯呢?就好比上文提到的 dosomethinga和dosomethingb,到底两个循环那个更高效,它决定于dosomething的内容吧。赵老师如果可以整理一些提高性能的缓存使用、利用的“习惯”这些会更有意义的。


    同感

  11. 天天不在
    *.*.*.*
    链接

    天天不在 2010-01-12 09:09:00

    今天长见识了.老以为是第一个的性能高.以前也那样做的.以后看样子要先用工具测试一下.

  12. Kain
    *.*.*.*
    链接

    Kain 2010-01-12 09:24:00

    感觉是不是有点过了,难道非得揪出个回字有几种写法么?
    绝大多数人的绝大多数用第一种写法,毕竟在可读性和效率上要占绝对优势。

    顺便说个:老赵研究这些个极端的执行效率目的何在?感觉老赵以前研究那些个MVC的东东更实在一点。

  13. 红泥
    *.*.*.*
    链接

    红泥 2010-01-12 09:28:00

    @Kain
    您应该没有看文章吧-_-!

  14. _龙猫
    *.*.*.*
    链接

    _龙猫 2010-01-12 09:36:00

    LS有几位还真是一点钻牛角尖精神都没有呢.你们直接拿着XX宝典看就完事了,反正不在乎。

    文中提到的,以前确实没有考虑到。Framework的过度纵然,已经让人很少考虑更底层的东西了,唉~

  15. 四有青年
    *.*.*.*
    链接

    四有青年 2010-01-12 09:36:00

    楼主的文章真是滴水不漏啊,继续支持。

  16. 红泥
    *.*.*.*
    链接

    红泥 2010-01-12 09:41:00

    详情请看CSAPP第六章@_@

  17. 极品拖拉机
    *.*.*.*
    链接

    极品拖拉机 2010-01-12 09:48:00

    最近经常看见locality这个词
    老赵貌似比较懒了,评论回复没以前勤快了

  18. alby
    *.*.*.*
    链接

    alby 2010-01-12 10:14:00

    追究各种效率以及它们的平衡点是程序员的基本道德,
    老赵比我们有道德

  19. csfeng
    *.*.*.*
    链接

    csfeng 2010-01-12 10:25:00

    这个例子举得不是很好,很容易让人混淆。那段代码是什么语言,LZ好像也没有说清楚,可能默认指的是C#。如果是C#,两个for循环中的i变量的作用域是在各自的循环体内,可以当做两个完全不同的变量,.NET编译器若没有优化的话,程序运行时会申请两个不同的内存地址。这样的话,LZ的缓存例子便是错误的。
    如果是C++语法,按照旧的C++语法,上面那段代码是错误的,第二循环的i变量不可以再定义其数据类型。若是新的C99语法,则代码无语法错误,这时候的情况与C#相似。要取决于编译器的原理。
    其实这里的性能已经涉及到了编译器和硬件层次,相同结构的代码,不同的编译器编译出来的机器指令会不尽相同,即使相同指令的程序结构,在不同的CPU下(比如单核、多核)的运行速度也会不同。楼主所说的缓存是指硬件缓存,从硬件上考虑代码的运行速度,这个选择点本来就不是很正确。再烂的代码拿到大型机上也可能比个人机快。

  20. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-12 10:59:00

    我想老赵的意思其实很简单,就是说执行效率会受到很多因素的影响,我们几乎不可能从代码的区别观察出他们之间执行效率的区别。唯一的手段只能是Profiling。


    但其实我觉得执行效率这个东西,更多的时候不应该单独拿出来讨论。我们不应当将效率作为评价代码质量的唯一指标,更不能没事就拿这个东西出来当借口。

    代码的执行效率固然重要,但更多的时候我们需要去权衡各个方面,找出一个平衡点,维护效率很多时候比执行效率重要的多。

  21. 说不得
    *.*.*.*
    链接

    说不得 2010-01-12 11:02:00

    代码说话,字符串拼接和替换,这个差异太小可,可以忽略不计。
    执行结果:

    两个方法在同一个循环执行 100000 次耗时 6.9025738 秒
    方法循环执行 100000 次耗时 3.541913 秒
    方法循环执行 100000 次耗时 3.22663 秒
    两方法分别执行 100000 次共耗时 6.768543 秒
    差异 -1.94175106103175 %



    private const int Count = 100000;
    
    public static void Main()
    {
    	Stopwatch stopWatch = new Stopwatch();
    	
    	stopWatch.Start();
    	for(int i = 0; i < Count; ++i)
    	{
    		DoSomethingA();
    		DoSomethingB();
    	}
    	stopWatch.Stop();
    	double c = stopWatch.Elapsed.TotalMilliseconds/1000;
    	Console.WriteLine("两个方法在同一个循环执行 {0} 次耗时 {1} 秒",Count, c);
    	
    	stopWatch.Reset();
    	stopWatch.Start();
    	for(int i = 0; i < Count; ++i)
    	{
    		DoSomethingA();
    	}
    	stopWatch.Stop();
    	double a = stopWatch.Elapsed.TotalMilliseconds/1000;
    	Console.WriteLine("A方法循环执行 {0} 次耗时 {1} 秒",Count, a);
    	
    	stopWatch.Reset();
    	stopWatch.Start();
    	for(int i = 0; i < Count; ++i)
    	{
    		DoSomethingB();
    	}
    	stopWatch.Stop();
    	double b = stopWatch.Elapsed.TotalMilliseconds/1000;
    	Console.WriteLine("B方法循环执行 {0} 次耗时 {1} 秒",Count, b);
    	
    	Console.WriteLine("两方法分别执行 {0} 次共耗时 {1} 秒", Count, a+b);
    	
    	Console.WriteLine("差异 {0} %", (a+b-c)/c*100);
    }
    
    private static void DoSomethingA()
    {
    	string str = "defg";
    	for(int i = 0; i < 10; ++i)
    	{
    		str += str;
    	}
    	str = str.Replace('f', 't');
    }
    
    private static void DoSomethingB()
    {
    	string str = "defg";
    	for(int i = 0; i < 10; ++i)
    	{
    		str += str;
    	}
    	str = str.Replace('f', 't');
    }
    
    /*private static void DoSomethingB()
    {
    	string str = "abcd";
    	for(int i = 0; i < 10; ++i)
    	{
    		str += str;
    	}
    	str = str.Replace('a', 's');
    }*/
    
    

  22. 说不得
    *.*.*.*
    链接

    说不得 2010-01-12 11:04:00

    在多说一句,执行结果的差异有正有负,我还没搞明白是怎么回事。

  23. JimLiu
    *.*.*.*
    链接

    JimLiu 2010-01-12 11:16:00

    第一个例子那种情况,可以用高阶函数来优化吧
    我一开始以为Linq写法会让程序变慢,因为我多次执行Where的话会多造成多次遍历,后来才直到高阶函数这个东西,还有yield的巧妙利用之处。

  24. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-12 11:17:00

    Jeffrey Zhao:
    再比如,您是使用两个int数组来表示一系列坐标的x值和y值,还是构造一个struct Point数组来保存它们呢?虽然使用两个int数组更节省内存,但是从局部性考虑问题的话,您会发现同一个坐标的x值和y值存放在一起可能更为合适。


    那个……为什么用两个int数组更省内存的?

  25. DiggingDeeply
    *.*.*.*
    链接

    DiggingDeeply 2010-01-12 11:29:00

    其实我觉得应该多引用一些intel的开发白皮书可能更有说服力。
    文里所说“C#没有办法内嵌汇编”,其实C#可以内嵌IL,足够了。

  26. 过路的[未注册用户]
    *.*.*.*
    链接

    过路的[未注册用户] 2010-01-12 12:27:00

    理论上是正确的,在实际环境中,执行得最频繁的代码,必然是操作系统的各种中断处理,线程切换一类的代码,L1,L2能不能装下这些代码段都是个问题。

  27. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-12 12:55:00

    说不得:
    代码说话,字符串拼接和替换,这个差异太小可,可以忽略不计。
    执行结果:

    两个方法在同一个循环执行 100000 次耗时 6.9025738 秒
    方法循环执行 100000 次耗时 3.541913 秒
    方法循环执行 100000 次耗时 3.22663 秒
    两方法分别执行 100000 次共耗时 6.768543 秒
    差异 -1.94175106103175 %



    [code=csharp]
    private const int Count = 100000;

    public static void Main()
    {
    Stopwatch stopWat...


    老兄 你确定你的计时能准确到CPU和寄存器么

  28. ubunoon
    *.*.*.*
    链接

    ubunoon 2010-01-12 12:57:00

    @说不得

    你那个例子很明显,如果相差极大的话,也就不会有那么底层了。Lache1与内存直接的差别,本来就在很微弱的差别(尤其是用ms来表示的时候),如果用指令执行时间来区别,可能就很大了。

  29. 说不得
    *.*.*.*
    链接

    说不得 2010-01-12 13:19:00

    Leon Weng:

    说不得:
    代码说话,字符串拼接和替换,这个差异太小可,可以忽略不计。
    执行结果:

    两个方法在同一个循环执行 100000 次耗时 6.9025738 秒
    方法循环执行 100000 次耗时 3.541913 秒
    方法循环执行 100000 次耗时 3.22663 秒
    两方法分别执行 100000 次共耗时 6.768543 秒
    差异 -1.94175106103175 %



    [code=csharp]
    private const int Count = 100000;

    public static void Main()
    {
    Stopwatch stopWat...


    老兄 你确定你的计时能准确到CPU和寄存器么



    不能,所以一共执行了十万次计算总时间。

  30. virus
    *.*.*.*
    链接

    virus 2010-01-12 14:09:00

    老赵
    你目前不会是失业中吧
    为什么你的职位用中划线标注呢

  31. 老赵
    admin
    链接

    老赵 2010-01-12 14:24:00

    Leon Weng:老赵,你似乎没有仔细分析两段程序的差别,是否指变量"i"两次申请内存空间和申请一次的区别呢?


    不是“申请”,是“计算”和“跳转”的次数。

  32. minus[未注册用户]
    *.*.*.*
    链接

    minus[未注册用户] 2010-01-12 14:26:00

    老赵给的例子中有一定局限性,DoSomethingA();和DoSomethingB();刚好是完全独立,互不干涉的两个方法,且不带参数,之间没有逻辑关联的方法.而在平时的程序中这样的例子颇少.
    如果是
    string tmp = null;
    for (int i = 0; i < 100; i++)
    {
    tmp = DoSomethingA(i); // i作为参数,输出tmp
    DoSomethingB(tmp); // tmp作为DoSomethingB的参数
    }

    那么上面的假设也就没有可比之处.
    再者如果DoSomethingA()和DoSomethingB()共用相同的参数,则把他们放在同一for语句执行,效率会更好,如:

    string tmp = null;
    for (int i = 0; i < 100; i++)
    {
    tmp = GetParameter(i); // i作为参数,获取中间变量
    DoSomethingA(tmp); // tmp作为DoSomethingB的参数
    DoSomethingB(tmp); // tmp作为DoSomethingB的参数
    }
    与下面相比:

    string tmp = null;
    for (int i = 0; i < 100; i++)
    {
    tmp = GetParameter(i); // i作为参数,获取中间变量
    DoSomethingA(tmp); // tmp作为DoSomethingB的参数
    }
    for (int i = 0; i < 100; i++)
    {
    tmp = GetParameter(i); // i作为参数,获取中间变量
    DoSomethingB(tmp); // tmp作为DoSomethingB的参数
    }

  33. 老赵
    admin
    链接

    老赵 2010-01-12 14:26:00

    邢少:貌似明白,但是没有看到什么实质的东西。缓存确实在一定程度上提高了系统的性能,但是在实际的开发中,应该遵循那些特定的习惯呢?就好比上文提到的 dosomethinga和dosomethingb,到底两个循环那个更高效,它决定于dosomething的内容吧。赵老师如果可以整理一些提高性能的缓存使用、利用的“习惯”这些会更有意义的。


    没法有意义到这种程度,因为文章里写了,这两种情况哪个快需要根据A和B到底做了什么,如何确定?3种方法
    1、静态分析
    2、Profiling
    3、Profiling
    哦,忘了,应该还有一种,就是Profiling

  34. 老赵
    admin
    链接

    老赵 2010-01-12 14:27:00

    温景良(Jason):老赵的意思是说在循环里做多个事情效率可能会比多个循环做多个事情效率高是吗,例如你上面的例子


    你好像不是第一次没看文章内容了,呵呵……

  35. 老赵
    admin
    链接

    老赵 2010-01-12 14:29:00

    Kain:
    感觉是不是有点过了,难道非得揪出个回字有几种写法么?
    绝大多数人的绝大多数用第一种写法,毕竟在可读性和效率上要占绝对优势。

    顺便说个:老赵研究这些个极端的执行效率目的何在?感觉老赵以前研究那些个MVC的东东更实在一点。


    在你眼中真是无处不“回”啊。
    第一种写法在可读性和效率上要占绝对优势吗?
    看来你真的没有看文章啊……可读性和性能都被我指出问题来了……

    还有就是,我不是说应该极端追求执行效率,但是你必须知道这些内容。
    MVC的东西,其实不用我多说,你完全可以自己看自己分析出来啊。
    分析不出来?我现在差不多知道你为什么分析不出来了,你意识到问题了吗?

  36. 老赵
    admin
    链接

    老赵 2010-01-12 14:30:00

    Ivony...:
    我想老赵的意思其实很简单,就是说执行效率会受到很多因素的影响,我们几乎不可能从代码的区别观察出他们之间执行效率的区别。唯一的手段只能是Profiling。

    代码的执行效率固然重要,但更多的时候我们需要去权衡各个方面,找出一个平衡点,维护效率很多时候比执行效率重要的多。


    是的,这个我举五肢赞同。

  37. 老赵
    admin
    链接

    老赵 2010-01-12 14:37:00

    ubunoon:
    @说不得

    你那个例子很明显,如果相差极大的话,也就不会有那么底层了。Lache1与内存直接的差别,本来就在很微弱的差别(尤其是用ms来表示的时候),如果用指令执行时间来区别,可能就很大了。


    你错了,内存和L1 Cache的性能差距有很大区别:
    L1 Cache的性能很高,不比寄存器慢多少。
    L1 Miss,从L2 Cache读,可能就有40-50个时钟周期了。
    L2 Miss,从RAM读,就有600以上的时钟周期了。
    如果两个程序真正写出差距来的话,性能应该有很大差距,看到我之前的文章《计算机体系结构与程序性能》里的例子了吗?
    他这里测试出来区别不大,只是因为它的例子并不能在这方面产生差距。
    我文章里两种做法性能孰高孰低,都是不确定的,不同情况下都不同。

  38. 老赵
    admin
    链接

    老赵 2010-01-12 14:38:00

    DiggingDeeply:
    其实我觉得应该多引用一些intel的开发白皮书可能更有说服力。
    文里所说“C#没有办法内嵌汇编”,其实C#可以内嵌IL,足够了。


    IL和汇编还是有很大区别的,IL太高级了,算不得汇编……

  39. 老赵
    admin
    链接

    老赵 2010-01-12 14:40:00

    RednaxelaFX:

    Jeffrey Zhao:
    再比如,您是使用两个int数组来表示一系列坐标的x值和y值,还是构造一个struct Point数组来保存它们呢?虽然使用两个int数组更节省内存,但是从局部性考虑问题的话,您会发现同一个坐标的x值和y值存放在一起可能更为合适。


    那个……为什么用两个int数组更省内存的?


    因为……假设32位平台。
    一个Point struct要3个int,n个Point要3n。
    如果是两个int数组,就是2n。
    算上数组的一些边角,Point struct要多占一些吧。
    struct到底怎么样的忘了,具体也没有探索过,说错了不要怪我……

  40. 老赵
    admin
    链接

    老赵 2010-01-12 14:41:00

    virus:
    老赵
    你目前不会是失业中吧
    为什么你的职位用中划线标注呢


    你才意识到啊

  41. 老赵
    admin
    链接

    老赵 2010-01-12 14:42:00

    说不得:在多说一句,执行结果的差异有正有负,我还没搞明白是怎么回事。


    说明你的代码受L1 Cache的影响有限,体会不到我文章里说的差距,呵呵。

  42. 老赵
    admin
    链接

    老赵 2010-01-12 14:45:00

    csfeng:
    这个例子举得不是很好,很容易让人混淆。那段代码是什么语言,LZ好像也没有说清楚,可能默认指的是C#。如果是C#,两个for循环中的i变量的作用域是在各自的循环体内,可以当做两个完全不同的变量,.NET编译器若没有优化的话,程序运行时会申请两个不同的内存地址。这样的话,LZ的缓存例子便是错误的。
    如果是C++语法,按照旧的C++语法,上面那段代码是错误的,第二循环的i变量不可以再定义其数据类型。若是新的C99语法,则代码无语法错误,这时候的情况与C#相似。要取决于编译器的原理。
    其实这里的性能已经涉及到了编译器和硬件层次,相同结构的代码,不同的编译器编译出来的机器指令会不尽相同,即使相同指令的程序结构,在不同的CPU下(比如单核、多核)的运行速度也会不同。楼主所说的缓存是指硬件缓存,从硬件上考虑代码的运行速度,这个选择点本来就不是很正确。再烂的代码拿到大型机上也可能比个人机快。


    你确定看清楚我文章的内容了么……
    就算是C#,我这个例子就不行了么,我这里是在说i的内存分配问题么……
    就算大型机肯定比个人机快,我这里会受这一点影响么……

  43. 老赵
    admin
    链接

    老赵 2010-01-12 14:48:00

    minus:
    老赵给的例子中有一定局限性,DoSomethingA();和DoSomethingB();刚好是完全独立,互不干涉的两个方法,且不带参数,之间没有逻辑关联的方法.而在平时的程序中这样的例子颇少.


    这也说不准,你确定int temp = GetParameters(i)少执行一次的效率,就一定能弥补Locality的不足吗?真是说不定的,所以要Profiling。
    当然,我文章的例子只是说明问题,事实上就那个例子而言,高低也是不确定的,都可以设计出对应的实现。

  44. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2010-01-12 14:57:00

    Jeffrey Zhao:

    温景良(Jason):老赵的意思是说在循环里做多个事情效率可能会比多个循环做多个事情效率高是吗,例如你上面的例子


    你好像不是第一次没看文章内容了,呵呵……


    呵呵,弄反了,其实我看了,是多个循环做多个事情比在循环里做多个事情的效率高,是这意思吗

  45. 老赵
    admin
    链接

    老赵 2010-01-12 15:05:00

    @温景良(Jason)
    你还是没看清……我文章从头至尾在这方面没有给出过确定的结论。

  46. Jerry Chou
    *.*.*.*
    链接

    Jerry Chou 2010-01-12 15:11:00

    老赵真不容易,
    怪不得在推上叫累呢。

    印象中第一次看见Locality在大学的《软件工程》这本书中,光记这个结论是“已证实”的,跟只要用“顺序,选择,循环”就可以完成所有程序逻辑的完备性一样。

    所以呢,当下流行的“有些话不能说太细”就比较有意思了。
    比如老赵总结时可以这样说:
    了解基本的计算机基础可以影响我们写程序时的思路,Cache和Locality会影响程序的运行性能,但针对具体案例请Profiling,Profiling,Profiling。

    或许这样可以省些口水,哈哈哈~

  47. ZelluX[未注册用户]
    *.*.*.*
    链接

    ZelluX[未注册用户] 2010-01-12 15:14:00

    其实作下限制可能更容易理解,比如说明DoSomethingA和DoSomethingB都是对某个数组的顺序操作。否则很难让人联想到locality上去啊,呵呵。locality的例子还是那个矩阵乘法的最经典,一些GPGPU文档都拿它做内存优化的例子。

  48. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2010-01-12 15:17:00

    决定多看3遍

  49. 张荣华
    *.*.*.*
    链接

    张荣华 2010-01-12 15:19:00

    老赵的这系列文章不错。 凡事要经过实践才好得出结果,没有profile,只看代码,基本上猜不出很准确的结果来。

  50. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-12 15:30:00

    Jeffrey Zhao:

    RednaxelaFX:

    Jeffrey Zhao:
    再比如,您是使用两个int数组来表示一系列坐标的x值和y值,还是构造一个struct Point数组来保存它们呢?虽然使用两个int数组更节省内存,但是从局部性考虑问题的话,您会发现同一个坐标的x值和y值存放在一起可能更为合适。


    那个……为什么用两个int数组更省内存的?


    因为……假设32位平台。
    一个Point struct要3个int,n个Point要3n。
    如果是两个int数组,就是2n。
    算上数组的一些边角,Point struct要多占一些吧。
    struct到底怎么样的忘了,具体也没有探索过,说错了不要怪我……


    为什么一个Point struct要3n?.NET的值类型被装箱过之后才会带有对象头(包括有些很隐蔽的装箱场景,例如调用值类型上的虚方法、将值类型赋值给接口类型的变量等),一般使用中未经装箱的值类型都是“裸”的;在值类型数组里保存的也都是裸的……算上数组的头,两个int[]占的空间比一个Point[]多吧?

  51. 老赵
    admin
    链接

    老赵 2010-01-12 15:32:00

    @RednaxelaFX
    骚嘎,原来如此,我错了……

  52. Asharp
    *.*.*.*
    链接

    Asharp 2010-01-12 15:45:00

    学习啦

  53. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-12 15:58:00

    Jeffrey Zhao:
    比如,我们知道每个线程的调用栈在默认情况下是1兆大小,因此两个线程调用栈上的数据几乎不可能出现在同一个Cache条目中。


    然后这个……这个是为什么?老赵的意思是因为栈隔得比较远,所以它们不容易被映射到同一条cache line上么?

    另外,继续发扬跑题的光荣传统,关于cache我想起这个:http://www.networkworld.com/community/node/39825?t51hb

  54. 老赵
    admin
    链接

    老赵 2010-01-12 16:05:00

    @ZelluX
    大牛好呀

  55. 老赵
    admin
    链接

    老赵 2010-01-12 16:06:00

    @RednaxelaFX
    嗯,我就这个意思,这个说法有问题吗?

  56. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-12 16:13:00

    @Jeffrey Zhao
    因为不是针对具体的CPU来讨论,在不确定cache映射算法的情况下这个也是说不定的。如果是不到1M的L1 cache跟G一级的地址空间做映射,隔得远也可能撞到一起。那句描述或许不是个好例子。

  57. 老赵
    admin
    链接

    老赵 2010-01-12 16:26:00

    @RednaxelaFX
    没听懂……我的意思是相距距离远的地址,不会“同时出现”在同一条cache line上,不是说cpu映射不会把它们映射到L1 Cache的同一个cache line上。
    还是你的意思是说,cpu读取地址x的数据之后,x + 1024 * 1024上的数据也可能被同时加载到同一个cache line上?

  58. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-12 16:42:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    还是你的意思是说,cpu读取地址x的数据之后,x + 1024 * 1024上的数据也可能被同时加载到同一个cache line上?


    不……我只是在想隔得远的东西也可能造成cache冲突而迫使前面的被flush掉。

  59. 老赵
    admin
    链接

    老赵 2010-01-12 16:50:00

    @RednaxelaFX
    嗯嗯,这个理解,L1 Cache就这么大,一复用就可能被flush掉了,呵呵。
    且根据抽屉原理,相隔1M而被flush是一定会出现的……

  60. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2010-01-12 20:07:00

    现在CPU的L2/L3非常大而且延迟很低,栈上所有东西都可以放到缓存里去,内存带宽也逐渐变得充裕了。所以我觉得优化就应该抓大放小,呵呵。

  61. 老赵
    admin
    链接

    老赵 2010-01-12 20:15:00

    @装配脑袋
    啥叫抓大放小啊?

  62. KevinDai[未注册用户]
    *.*.*.*
    链接

    KevinDai[未注册用户] 2010-01-13 14:37:00

    老赵和RednaxelaFX的讨论真是好看,下次我也来。担心的是有点不入流呢……

  63. 金色海洋(jyk)
    *.*.*.*
    链接

    金色海洋(jyk) 2010-01-15 23:00:00

    果然可以用IE6回复了,哈。

  64. 金色海洋(jyk)
    *.*.*.*
    链接

    金色海洋(jyk) 2010-01-15 23:00:00

    回复测试
    这是IE6。

  65. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-24 21:25:00

    看了复旦软件学院的视频后对缓存还真有了新的理解。

  66. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-29 23:56:00

    阅毕,这篇帖子的内容其实比上次写的那个讲二级缓存命中率的帖子少。

    以下为引用v

    避免内存的连续分配
    .NET 内存分配器确实隐藏了内存布局的许多细节,但我们通常也能够猜出该布局的特定属性,甚至确切知道它们的某些信息。我们假设下列事实成立:

    * 同一类实例中的两个实例字段在内存位置中非常接近。
    * 同一类型的两个静态字段在内存中非常接近。
    * 数组中具有相邻索引的两个元素在内存中也是相邻的。
    * 连续分配的对象在内存中很可能也是邻近的,并且可能会随着时间的推移而更加接近。
    * 在闭包中同时使用的局部变量很可能在实例字段中被捕获,并且根据上面的第一条注释,它们很可能在内存中也是相邻的。

    在其他情况下,我们知道两个内存位置可能是相距很远的。例如,不同线程所分配的对象很可能在内存中相隔很远。
    如果某个线程分配一个对象,然后分配很多中型或大型对象,最后分配另一个对象,则第一个和最后一个对象之间的距离很可能等于分布其间的各对象彼此之间的距离和。此行为并不确定,不过在实际中经常出现。(但是,如果中间对象过大,它们可能会在不同的堆中终止,此时第一个和最后一个对象在内存中可能会很接近。)
    如果两个对象添加了总大小至少等于缓存行大小的未用字段,则这两个对象不会在同一缓存行结束。所添加的字段在内存中应最后出现。如果我们知道了对象在内存中的出现顺序,则可以只填充首先出现的字段。
    根据这些假设,我们可以设计出一个并行应用程序,并最大程度减少需要调试的错误共享问题的数量。


    http://msdn.microsoft.com/zh-cn/magazine/cc872851.aspx

  67. Dbger
    *.*.*.*
    链接

    Dbger 2010-02-28 22:36:00

    我觉得老赵已经把局部性的原理讲的比较明白了。补充两点吧:

    >>后者(时间局部性)表示“在加载一个地址的数据之后,短时间内重新加载这块数据”
    不是短时间内重新加载,而是将其暂时保存起来,重新加载的话就没起到利用时间局部性的作用。

    >>为什么冷启动总是很慢?
    补充一下,热启动快于冷启动的原因在于操作系统做了cache,把该进程上一次运行的workingset中的数据暂存于系统的standby page list中,当程序第二次启动时多数数据将直接从内存中获得。算是利用了程序的时间局部性原理吧。

  68. 老赵
    admin
    链接

    老赵 2010-03-01 11:23:00

    Dbger:
    >>后者(时间局部性)表示“在加载一个地址的数据之后,短时间内重新加载这块数据”
    不是短时间内重新加载,而是将其暂时保存起来,重新加载的话就没起到利用时间局部性的作用。


    我觉得我说的没错,这里不能用你的方法理解,呵呵。

  69. 链接

    gaobanana 2010-04-10 13:21:27

    greate!so much to learn.

  70. cxvision
    58.247.204.*
    链接

    cxvision 2010-05-17 17:14:21

    多核时代的优化是个大学问 GPU DUCORE 优化...调试更是xxx

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我