阅读更多

请注意,本文不是讲解处理器缓存,如果你对cpu cache这个概念不清楚,请先Google一下。
另外,本文主要针对像 C,C++ 这种产生机器码的语言的,对于像 Java,.Net 这样的字节码语言,这里所说的可能无效,至少我没研究过。

首先说说我所说的这些旧有的优化技巧从哪里来的。
原因很简单,如果你像我一样,多年只用 J2ME,或者 Flash 这样的技术开发,你是不太可能会关心处理器缓存的,而是用一些其它的性能技巧,这些技巧遇到处理器缓存问题,就失效了。
再如果你的CPU,汇编,优化知识像我一样仍停留在 80386 时代,你我掌握的优化技巧断然也是过时的。

失效技巧一,使用预先计算好的变量或者查找表

现在来怎么用查找表来计算一个32位整数里位为1的个数。

static const unsigned char BitsSetTable256[256] =
{
// 预先计算好的256个8位数的1的个数
};

int calculateBitsCount(unsigned int n)
{
    unsigned char * p = (unsigned char *)&n;
    return BitsSetTable256[p[0]] +
    BitsSetTable256[p[1]] +
    BitsSetTable256[p[2]] +   
    BitsSetTable256[p[3]];
}
 

很酷,是吧,只用了四次加法运算,我们可以想当然地认为这个算法比那些充满乘除法甚至循环的算法快。
但当有了CPU的数据缓存,情况不一样了。当 calculateBitsCount 第一次取 BitsSetTable256 数据,很有可能导致数据缓存清空重新加载 BitsSetTable256 位置的内存,会导致浪费上百指令周期,而这上百指令周期,足够用普通方法计算位数了。
比如下面这个算法,来自
http://graphics.stanford.edu/~seander/bithacks.html

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}
 

这个算法看似比上面查找表算法多了很多指令,还有循环,但要记住指令成本比数据成本低非常非常多(指令数量很多超出指令缓存的除外),值票价!确实值票价,因为我用这个算法替代查找表以后,确实快了。

失效技巧二,用局部变量来缓存所操作对象的成员变量

 

请注意,这个技巧在大多数情况下是有效的,这里只是说明某些情况下会失效。
比如有这样一个函数,

void func(SomeObject * obj)
{
    int i, k, p;
    int count = obj->getCount();
   
    for(i = 0; i < 100; ++i) {
        for(int k = 0; k < 100; ++k) {
            for(int p = 0; p < count; ++p) {
                // 处理 obj 的数据
            }
        }
    }
}
 

假设 getCount 只是取一个数值。
这看起来很好,很完美,但仔细看却有一个问题。假如所有局部变量都能被放在寄存器,没有问题。但如果 count 不能被放到寄存器里呢?那么每次循环 count 都要从堆栈内存里读取,但同时又要处理 obj 的数据,这两部分极有可能不在一个数据缓存里,这就会导致频繁的数据缓存交换,慢!
如果抛弃 count,而把最内层循环改成

            for(int p = 0; p < obj->getCount(); ++p) {
                // 处理 obj 的数据
            }
 

因为读取的数据都在 obj 范围内,如果都在数据缓存范围里,那就会相当快。

失效技巧三,在一个循环里干所有事

 

我们可能老觉得循环是慢的,因为还要跳转,所以我们宁愿在一个循环里把所有事都做了。

    ObjectA * objA;
    ObjectB * objB;
    for(int i = 0; i < 100; ++i) {
        // 对 objA 做点事
        // 对 objA 做点别的事
        // 对 objB 做点事
    }
 

这有两个问题:
1,一旦循环体里的代码长度超过指令缓存,那么每次循环都要导致指令缓存动荡,无论 CPU 有几级缓存,L1 被清空重新装载,总归比直接命中 L1 缓存慢。
2,更麻烦的事,循环里在两个数据块操作,除非两个对象恰好分配的很近,否则必然导致数据缓存的动荡,慢。
如果把循环切分,

    ObjectA * objA;
    ObjectB * objB;
    for(int i = 0; i < 100; ++i) {
        // 对 objA 做点事
    }
    for(int i = 0; i < 100; ++i) {
        // 对 objA 做点别的事
    }
    for(int i = 0; i < 100; ++i) {
        // 对 objB 做点事
    }
 

则指令缓存和数据缓存都会觉得很高兴,自然也就工作快一点了。

总结:
虽然上面这些技巧会失效,并不意味这些技巧是错的,很多情况下也可能真的有效。而且处理器缓存这东西优化起来不定因素很大,并无不变之规,所以具体做时还要仔细测试,方能知道哪种方法好。

  • 大小: 33.2 KB


相关推荐

  • Java8编程实战

    Java一直作为优秀的编程语言活跃于软件开发行业,掌握Java不仅是一件兴奋的事,更是一把可以帮助你轻松进入软件行业大门的一把金钥匙,本套课程将为读者讲解Java8的所有核心技术知识,一共240集的Java8开发课程,全网独一无二的教学视频资料,你还等什么?赶紧来学吧!官方QQ群:612148723。

  • CSDN规则详解(一)

    CSDN是一个专业的技术社区,不仅可以分享自己的技术经验,还可以向其他行业专业人士学习。在CSDN上写出优秀的博客可以增加自己的曝光率和声誉,但是除了写出好博客,我们还可以认识规则、了解规则、利用规则,来更好地展示自己的专业能力和吸引更多的读者。因此,掌握CSDN的规则是非常重要的,可以帮助我们更好地利用这个平台,实现自己的目标。在本文中,将会介绍一些CSDN的规则和注意事项,帮助读者更好地运用这个平台。

  • CSDN文章教程

    如何创建CSDN文章

  • 实用数据分析:数据分析师从小白到精通

    [入门数据分析的第一堂课]这是一门为数据分析小白量身打造的课程,你从网络或者公众号收集到很多关于数据分析的知识,但是它们零散不成体系,所以第一堂课首要目标是为你介绍:Ø  什么是数据分析-知其然才知其所以然Ø  为什么要学数据分析-有目标才有动力Ø  数据分析的学习路线-有方向走得更快Ø  数据分析的模型-分析之道,快速形成分析思路Ø  应用案例及场景-分析之术,掌握分析方法[哪些同学适合学习这门课程]想要转行做数据分析师的,零基础亦可工作中需要数据分析技能的,例如运营、产品等对数据分析感兴趣,想要更多了解的[你的收获]n  会为你介绍数据分析的基本情况,为你展现数据分析的全貌。让你清楚知道自己该如何在数据分析地图上行走n  会为你介绍数据分析的分析方法和模型。这部分是讲数据分析的道,只有学会底层逻辑,能够在面对问题时有自己的想法,才能够下一步采取行动n  会为你介绍数据分析的数据处理和常用分析方法。这篇是讲数据分析的术,先有道,后而用术来实现你的想法,得出最终的结论。n  会为你介绍数据分析的应用。学到这里,你对数据分析已经有了初步的认识,并通过一些案例为你展现真实的应用。[专享增值服务]1:一对一答疑         关于课程问题可以通过微信直接询问老师,获得老师的一对一答疑2:转行问题解答         在转行的过程中的相关问题都可以询问老师,可获得一对一咨询机会3:打包资料分享         15本数据分析相关的电子书,一次获得终身学习

  • 小白使用CSDN的建议

    小白使用CSDN

  • CSDN常见问题汇总

    通过CSDN平台购买的“VIP会员、余额”,在刚购买后未使用的情况可支持退款;“付费资源、付费专栏、盲盒、魔盒、课程、C认证”等虚拟商品一经购买后,除了特殊原因外,概不支持退款;特殊原因包括:付费资源无法正常使用、课程重复购买、讲师无法继续更新完毕全部课程等;如未使用或者符合特殊原因,请提供账号用户名ID、订单号、退款原因给,以便核实处理;注意:购买的套餐使用后不支持退款,正常退款申请后会在7个工作日内原路返还到支付帐号退款进度:已申请的退款可在“”中查询退款进度。

  • VBA高手进阶课程

    爱好excel 的公式和VBA编程,Access数据库,VB和VB.NET,自己开发有作品《VBA代码宝》、visual studio开发的《大表格工具箱》、发票凑数器、进销存模板表格、出入库、领用单、图书管理系统的模板表格等诸多VBA功能及技巧,熟悉VBA数组、字典、正则,函数公式,SQL、VB等,拥有多年编程经验,实际案例,职场应用,应有尽有,升职加薪不是梦,学会excel函数、VBA、ACCESS数据库等办公技能,能极大地缩短工作时间,达到高效率工作,希望能跟大家一起学习进步!

  • 新手写CSDN的教程

    对于我们新手来说,第一次写像CSDN的博客会有些疑惑,接下来我会总结一些自己的理解。提示:以下是本篇文章正文内容,下面案例可供参考新手第一次写博客,请多多关照。

  • CSDN

    CSDN (China Software Developer Network) is a leading technology community in China for software developers to share, learn and grow their careers. It provides comprehensive resources including code snippets, tutorials, articles, forums, and job opportuniti

  • Java之路

    你了解Java吗?你知道Java能做什么吗?你知道Java该怎么学吗?你知道Java未来的发展趋势、发展状况吗?

  • CSDN原力值解析:功能作用、获取方法、积分对应等级关系详解

    CSDN 原力是衡量一个用户在 CSDN 的贡献和影响力的系统。有数值和等级,等级由低到高 0 到 9 级组成。其作为除积分、博客等级和勋章等外新的指标,不同的级别能反映出不同的技术影响力, 在今后的很长时间内,这个原力系统能稳定地反映用户的贡献与等级的关系。

  • CSDN新手指南

    CSDN(全称为中国软件开发网)是一个致力于服务中国软件开发者的社区平台。

  • CSDN是什么?——我的博客漫漫成长之路

    写这篇文章的目的是过几天要在讲台上和同学们分享CSDN这个网站,希望大家能给个三连支持一下~ 事情是这样的,我们的推荐系统课程要分享自己流量以及各大平台运营的经验,因此我决定向大家介绍CSDN。 一、CSDN是什么 我自己把它当成一个程序员的知乎,以及类似于小猿搜题等APP,如果在计算机方面有不懂的都可以直接查看。 如下: 不懂的问题可以提问,有人会回答。 问题被采纳了还可以有钱赚: 二、运营CSDN有什么意义 【1】可以当成一个电脑端的笔记本,Markdown操作效率高又很方便 【2】方便自己回顾笔

  • Vue知识总结

    文章目录1.概念1.1 对SPA单页面的理解,优缺点是什么?1.2 什么是MVVM?2. 基础知识2.1 v-show 和 v-if 的区别?2.2 computed 和 watch 的区别和运用场景?3.组件3.1 组价中的data为什么是一个函数?3.2 Vue组件间通信的方式?3.3 对keep-alive的理解?4.生命周期4.1谈谈你对 Vue 生命周期的理解?4.2 Vue 的父组件和子组件生命周期钩子函数执行顺序?4.3 父组件可以监听到子组件的生命周期吗?4.4 在哪个生命周期内调用异步请

  • history对象中replaceState详解

    忙呀忙

  • History 对象的pushState()和replaceState()

    history 对象保存了当前窗口访问过的所有页面网址。pushState()、replaceState()、location.href的应用、区别等

  • window history pushState replaceState 跳转原理

    一、pushState 比如,当前打开的界面是:https://developer.mozilla.org/en-US/docs/Web/API/History,如下图所示: 在chrome的console下,执行代码: history.pushState({},'','https://developer.mozilla.org/en-US/docs/Web/API/History_API') 则浏览器中会看到以下三种变化: 1、当前地址栏的url会变成:https://developer.

  • history.pushState() 和 history.replaceState() 方法

    Internet Explorer 10 引入了对 HTML5 草案规范的历史记录界面的支持,该历史记录界面包括用来管理站点的历史记录堆栈和 URL 的方法。 这个控件可以为最终用户提供他们期望从“后退”和“前进”按钮获得的体验,以及在不借助导航或页面加载的情况下提供少量页面更新的性能。HTML5 历史记录的相关定义位于万维网联合会 (W3C) 的 HTML5 规范的第 5.4.2 节。

  • HTML5 History API 项目推荐

    HTML5 History API 项目推荐 HTML5-History-API HTML5 History API expansion for browsers not supporting pushState, replaceState ...

Global site tag (gtag.js) - Google Analytics