社区应用 最新帖子 精华区 社区服务 会员列表 统计排行 银行

  • 14728阅读
  • 26回复

C++性能优化要点

级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 20楼 发表于: 2012-12-24
比memcpy更快的内存拷贝
这个不是本人写的,转载过来的。稍微看了下。


感觉比ARM库中的memcpy 函数的实现弱爆了。
如果同样的总线宽度、时钟、那么ARM我想会完胜。


有兴趣和环境的实验比较一下下。


下面这个是ARM 库memcpy函数的实现(部分)。


ldm     r1!,{r3-r8,r12,r14}
            20|                                                                                              
   SR:052678FC|E2422020            sub     r2,r2,#0x20
            21|                                                                                              
   SR:05267900|E3520080            cmp     r2,#0x80
            22|                                                                                              
   SR:05267904|E8A051F8____________stm_____r0!,{r3-r8,r12,r14}





转载文章开始


偶然间看到一个叫xmemcpy的工具,用做内存拷贝。号称在拷贝120字节以内时,比glibc提供的memcpy快10倍,并且有实验数据。


这让人感觉很诧异。一直以来都觉得memcpy是很高效的。相比于strcpy等函数的逐字节拷贝,memcpy是按照机器字长逐字进行拷贝的,一个字等于4(32位机)或8(64位机)个字节。CPU存取一个字节和存取一个字一样,都是在一条指令、一个内存周期内完成的。显然,按字拷贝效率更高。


那么,这个xmemcpy是靠什么来实现比memcpy“快10倍”的呢?
看了一下xmemcpy的实现,原来它速度快的根据是:“小内存的拷贝,使用等号直接赋值比memcpy快得多”。
这下就更纳闷了,内存拷贝不就是把一块内存一部分一部分地拷贝到另一块内存去吗?难道逐字拷贝还有性能提升的空间?


写了一段代码:


#include <stdio.h>
#define TESTSIZE        128
struct node {
char buf[TESTSIZE];
};
void main()
{
char src[TESTSIZE] = {0};
char dst[TESTSIZE];
*(struct node*)dst = *(struct node*)src;
}
然后反汇编:


......
00000000004004a8 <main>:
4004a8:       55                      push   %rbp
4004a9:       48 89 e5                mov    %rsp,%rbp
4004ac:       48 81 ec 00 01 00 00    sub    $0x100,%rsp
4004b3:       48 8d 7d 80             lea    0xffffffffffffff80(%rbp),%rdi
4004b7:       ba 80 00 00 00          mov    $0x80,%edx
4004bc:       be 00 00 00 00          mov    $0x0,%esi
4004c1:       e8 1a ff ff ff          callq 4003e0 <>
4004c6:       48 8b 45 80             mov    0xffffffffffffff80(%rbp),%rax
4004ca:       48 89 85 00 ff ff ff    mov    %rax,0xffffffffffffff00(%rbp)
4004d1:       48 8b 45 88             mov    0xffffffffffffff88(%rbp),%rax
......
400564:       48 89 85 70 ff ff ff    mov    %rax,0xffffffffffffff70(%rbp)
40056b:       48 8b 45 f8             mov    0xfffffffffffffff8(%rbp),%rax
40056f:       48 89 85 78 ff ff ff    mov    %rax,0xffffffffffffff78(%rbp)
400576:       c9                      leaveq
400577:       c3                      retq  
400578:       90                      nop    
......


再将libc反汇编,并找到memcpy的实现,以作比较:


......
0006b400 <memcpy>:
6b400:       8b 4c 24 0c             mov    0xc(%esp),%ecx
6b404:       89 f8                   mov    %edi,%eax
6b406:       8b 7c 24 04             mov    0x4(%esp),%edi
6b40a:       89 f2                   mov    %esi,%edx
6b40c:       8b 74 24 08             mov    0x8(%esp),%esi
6b410:       fc                      cld    
6b411:       d1 e9                   shr    %ecx
6b413:       73 01                   jae    6b416 <memcpy+0x16>
6b415:       a4                      movsb %ds:(%esi),%es:(%edi)
6b416:       d1 e9                   shr    %ecx
6b418:       73 02                   jae    6b41c <memcpy+0x1c>
6b41a:       66 a5                   movsw %ds:(%esi),%es:(%edi)
6b41c:       f3 a5                   repz movsl %ds:(%esi),%es:(%edi)
6b41e:       89 c7                   mov    %eax,%edi
6b420:       89 d6                   mov    %edx,%esi
6b422:       8b 44 24 04             mov    0x4(%esp),%eax
6b426:       c3                      ret    
6b427:       90                      nop    
......


原来两者都是通过逐字拷贝来实现的。但是“等号赋值”被编译器翻译成一连串的MOV指令,而memcpy则是一个循环。“等号赋值”比memcpy快,并不是快在拷贝方式上,而是快在程序流程上。
(另外,测试发现,“等号赋值”的长度必须小于等于128,并且是机器字长的倍数,才会被编译成连续MOV形式,否则会被编译成调用memcpy。当然,具体怎么做是编译器决定的。)


而为什么同样是按机器字长拷贝,连续的MOV指令就要比循环MOV快呢?
在循环方式下,每一次MOV过后,需要:1、判断是否拷贝完成;2、跳转以便继续拷贝。
每拷贝一个字长,CPU就需要多执行以上两个动作。


循环除了增加了判断和跳转指令以外,对于CPU处理流水产生的影响也是不可不计的。CPU将指令的执行分为若干个阶段,组成一条指令处理流水线,这样就能实现在一个CPU时钟周期完成一条指令,使得CPU的运算速度得以提升。
指令流水只能按照单一的指令路径来执行,如果出现分支(判断+跳转),流水就没法处理了。
为了缓解分支对于流水的影响,CPU可能会采取一定的分支预测策略。但是分支预测不一定就能成功,如果失败,其损失比不预测还大。


所以,循环还是比较浪费的。如果效率要求很高,很多情况下,我们需要把循环展开(比如在本例中,每次循环拷贝N个字节),以避免判断与跳转占用大量的CPU时间。这算是一种以空间换时间的做法。GCC就有自动将循环展开的编译选项(如:-funroll-loops)。
但是,循环展开也是应该有个度的,并不是越展开越好(即使不考虑对空间的浪费)。因为CPU的快速执行很依赖于cache,如果cache不命中,CPU将浪费不少的时钟周期在等待内存上(内存的速度一般比CPU低一个数量级)。而小段循环结构就比较有利于cache命中,因为重复执行的一段代码很容易被硬件放在cache中,这就是代码局部性带来的好处。而过度的循环展开就打破了代码的局部性,所以xmemcpy一开始就提到拷贝120字节以内。如果要拷贝的字节更多,则全部展开成连续的MOV指令的做法未必会很高效。


综上所述,“等号赋值”之所以比memcpy快,就是因为它省略了CPU对于判断与跳转的处理,消除了分支对CPU流水的影响。而这一切都是通过适度展开内存拷贝的循环来实现的。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 21楼 发表于: 2012-12-28
影响系统性能的20个瓶颈
在   Zen And The Art Of Scaling - A Koan And Epigram Approach 一文中 ,  Russell Sullivan 提出一个很有趣的设想:一共有20种经典的瓶颈。这听起来就像只有20种基本的故事情节(20 basic story plots)那样让人怀疑。不过基于每个人不同的分类方式,这个说法或许是对的,但是在现实中,众所周知,瓶颈是无穷无尽的而且涉及方方面面。


roger37
翻译于 3天前
0人顶
顶 翻译的不错哦!
一天, 来自 Terracotta 的 Aurelien Broszniowski 给我电邮了一份他心中的瓶颈列表,我们同时把我们的邮件抄送给了Russell, 他也给出了他的列表。而我也有我自己的想法。 所以,下面就是这几碗水煮成的一锅石头汤( http://en.wikipedia.org/wiki/Stone_soup, stone soup典故)


鉴客
翻译于 2天前
0人顶
顶 翻译的不错哦!
Russell 说要是年轻的时候就知道这些该多好啊,而对我来说则可以提供更多的思路。你的经验越多,处理过不同类型的项目,你就可以给这个列表增加更多的内容。因此当你在阅读这个列表时,或者是在整理自己的列表时,多年的丰富经验的积累以及遇到的一些小挫折,每一个故事都值得进行总结。


红薯
翻译于 2天前
1人顶
顶 翻译的不错哦!
数据库:
工作中数据大小超过可用内存 RAM
长短查询混合
写-写 冲突
大的联合查询占光内存
虚拟化:
共享 HDD 存储,磁盘寻道挂起
云平台中的网络 I/O 波动


铂金小鸟
翻译于 昨天(18:15)
4人顶
顶 翻译的不错哦!
编程:
线程:死锁、相对于事件驱动来说过于重量级、调试、线程数与性能比非线性
事件驱动编程:回调的复杂性、函数调用中如何保存状态(how-to-store-state-in-function-calls)
缺少profile工具、缺少trace工具、缺少日志工具
单点故障、横向不可扩展
有状态的应用
搓设计:一台机器上能跑,几个用户也能跑,几个月后,几年后,尼玛,发现扛不住了,整个架构需要重写。
算法复杂度
依赖于诸如DNS查找等比较搞人的外部组件
栈空间


YiseNet
翻译于 8天前
0人顶
顶 翻译的不错哦!
磁盘:
本地磁盘存取
随机磁盘读写 -> 磁盘寻道
磁盘碎片化
写入超过SSD容量的数据导致SSD硬盘性能降低
操作系统:
内核缓冲刷入磁盘,填充linux缓冲区缓存
TCP缓冲区过小
文件描述符限制
功率分配


铂金小鸟
翻译于 昨天(14:53)
0人顶
顶 翻译的不错哦!
缓存:
不使用memcached
HTTP中,header,etags,不压缩(headers, etags, not gzipping)
没有充分使用浏览器缓存功能
字节码缓存(如PHP)
L1/L2缓存. 这是个很大的瓶颈. 把频繁使用的数据保持在L1/L2中. 设计到的方面很多:网络数据压缩后再发送,基于列压缩的DB中不解压直接计算等等。有TLB友好的算法。最重要的是牢固掌握以下基础知识:多核CPU、L1/L2,共享L3,NUMA内存,CPU、内存之间的数据传输带宽延迟,磁盘页缓存,脏页,TCP从CPU到DRAM到网卡的流程。


八木
翻译于 昨天(15:54)
0人顶
顶 翻译的不错哦!
CPU:
CPU 过载
上下文切换 -> 一个内核上跑了太多的线程,linux调度对于应用来说很不友好, 太多的系统调用, 等等...
IO 等待 -> 所有的CPU都挂起等待比较慢的IO
CPU 缓存: 缓存数据是一个为了平衡不同实例有不同的值和繁重的同步缓存数据保持一致,而精心设计的一个进程。
背板吞吐量


铂金小鸟
翻译于 昨天(14:51)
0人顶
顶 翻译的不错哦!
网络:
网卡的最大输出带宽,IRQ达到饱和状态,软件中断占用了100%的CPU
DNS查找
丢包
网络路由瞎指挥
网络磁盘访问
共享SAN(Storage Area Network)
服务器失败 -> 服务器无响应


红薯
翻译于 2天前
0人顶
顶 翻译的不错哦!
过程:
测试时间 Testing time
开发时间 Development time
团队人数 Team size
预算 Budget
代码缺陷 Code debt


红薯
翻译于 2天前
0人顶
顶 翻译的不错哦!
内存:
内存溢出 -> 杀进程,进入 swap ,越来越慢
内存溢出导致磁盘频繁读写(swap相关)
内存库开销
内存碎片
Java 需要垃圾收集导致程序暂停
C 语言的 malloc 无法分配


红薯
翻译于 2天前
1人顶
顶 翻译的不错哦!
如果你有更多的瓶颈要添加或者建议修复,请加入。感谢 Aurelien 和 Russel。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 22楼 发表于: 2013-01-10
专访赵开勇:传统的CPU架构将不再是高性能计算唯一选择
摘要:社区之星第9期采访的嘉宾是香港浸会大学计算机在读博士、浪潮高性能计算顾问赵开勇。此次他为我们揭开了高性能计算的神秘面纱,为读者讲解自己的经验心得。并且他认为基于移动设备的高性能计算将会成为未来潮流,低功耗、高性能也将成为一个重要指标。


赵开勇:基于移动设备的高性能计算将会成为未来潮流
赵开勇,香港浸会大学计算机在读博士,长期从事高性能计算领域研究,在CPU、GPU异构计算方面有多年的研究经验。浪潮高性能计算顾问,组织参与国内多个科研单位和高性能用户的高性能项目开发。
众核、内存计算是高性能发展未来
CSDN:过去几年,并行计算的技术演变、应用的拓展,以及未来发展分别是什么?
赵开勇:传统的并行计算机更多的是中型机和大型机,或者专门制造的特需机器,那个时候并行计算离大众还很远。并行计算的算法基本是在上世纪六、七十年代的时候开始,当时有很多研究文章,而且研究得很透彻。但在那时候,并行计算、高性能计算,离大众还比较远。
从2000年左右开始,计算芯片、存储、网络的发展使得之前昂贵的计算机变得廉价。由于像Google这类公司的算法的演变,使得廉价的PC架构的机器构建出的服务器集群就可以完成高性能计算。当然我们这里讨论的并行计算,其实只是高性能计算的一种方法而已,并行计算通常是指许多指令一起执行,是针对串行计算而言的。
现在的高性能计算,既有并行计算,也有串行计算,概念更加的广泛,而不局限于传统的并行计算。从2000年左右开始,有科研者采用GPU作为通用计算。到2006年,Nvidia推出通用计算的GPU,打破了传统基于CPU(或者专用协处理器)的高性能计算,让民众更接近高性能计算(并行计算),并且可以采用廉价的芯片达到高性能计算的目的。
在传统CPU芯片方面,也通过增加CPU的核心来提高计算性能,从以前的单核、双核到多核,再到Intel前不久推出的MIC架构的众核芯片,都标明了计算芯片再向多核心方向发展。另一个方面,基于AMD的APU架构芯片,兼备CPU和GPU,让CPU和GPU可以通过更便捷的方式共享内存,达到协作处理的目的。
此外,内存的价格越来越低,基于内存的存储会在将来的高性能发展中起到重要的地位。我们在高性能计算中常常会遇到IO的瓶颈,很难真正发挥所有计算芯片的能力,内存等存储的廉价也会在这些问题上得到一些解决。随着网络传输的发展,性能的提高,也会在将来的高性能计算中起到决定的因素。
x86不再是唯一选择
CSDN:你如何看待未来的芯片格局?
赵开勇:传统的CPU会长期存在,但是高性能计算的地位会下降,会有GPU、CPU(不同类别的CPU,x86体系结构,基于ARM的CPU)都会逐步跟上。Intel的高性能计算的地位有所动摇,Nvidia的GPU和ARM64架构的芯片会埋头追赶,AMD的APU和基于ARM64的芯片也同样如此。同时基于移动设备的CPU、GPU也会具有高性能计算的能力。
在过几年,Intel的x86的CPU、MIC;Nvidia的GPU(还有ARM64架构的芯片,可能是CPU也可能是GPU,也可能是CPU和GPU的合体);AMD的CPU、GPU、APU,以及基于ARM的芯片,都会在高性能计算里面各争天下。基于移动设备的高性能计算,也会成为一个潮流
还有一个重点是低功耗、高性能,会在将来的高性能计算中会成为一个重要的指标
而国产的高性能计算芯片会在中国未来几年的舞台上发挥重要的作用,包括专业级的高性能计算中心,也包括民用级别的高性能计算机,都会国产的设备初露头角。
未来的元计算中心和高性能计算中心,基本上会成为一个实体、两个概念或是融合一起。硬件层次上不会有太多的区别,更多的是跑在服务器上的算法和应用。
其中,高性能计算的发展硬件只是一个方面,而且硬件的变革很快,这几年基本上是一年到一年半就有一个变化。所以在堆砌硬件的同时,一定要注意软件的开发、软件算法、框架的设计,做到发挥现有集群性能的同时,向后兼容。现在很多云计算中心,或者高性能中心,计算量达不到饱和,一年维护的费用和电费等超过了本身发挥的价值。软件是高性能计算现在的短板,需要在高性能计算的软件上开展更多的工作。
CSDN:ARM+Hadoop在高性能计算领域的应用领域是什么?瓶颈是什么?
赵开勇:Hadoop在高性能计算中已经应用很广,基于ARM架构的Hadoop部署现在还比较少。ARM的优势是低功耗、高性能,但是其处于瓶颈,基于ARM的高性能计算核心还没有大规模的量产,或者说在业界还没有真正得到认可。基于ARM架构的高性能计算芯片,或许会在接下来的几年中大放异彩。
CSDN:你认为GPU与CPU的融合,最大的挑战在哪里?
赵开勇:GPU现在还是作为CPU的协作处理器存在,通过PCIE传输数据,这就是很严重的瓶颈。也许再过几年,CPU和GPU可以共享内存以后,传输的瓶颈会得到解决。
高性能计算是一个不断迭代的优化过程
CSDN:对并行计算从业者而言,请推荐几个好的开源框架和一定要去读的几本书,以及分享下你学习的好经验、好方法。
赵开勇:个人感觉,高性能计算有硬件和软件部分,对于一个整体系统,既要对系统的硬件,包括计算核心、存储和网络传输分布等都要有了解。这些方面可以看Intel、NVidia和AMD等厂商的技术手册,都可以看到一些计算核心的资料。
同时要了解高性能计算的应用层面,任何的高性能计算都不能大包大揽,用一个方案解决所有的问题。需要在对应的行业里面学习相关的知识,了解问题的根本,从问题的根本入手,从算法层面优化问题,不要套用固定的模型或框架。需具体问题具体分析,再抽象出来,看已有的框架是否可以解决,然后再优化设计。高性能计算是一个不断迭代的优化过程,找到分析问题、问题的热点、解决问题、优化问题、再找新的热点,然后重复迭代的过程。高性能计算的领域不同,解决问题的方法也不一定相同,需要融汇各种方法和理论。
我个人推荐的书籍有陈国良院士的《并行计算系列丛书》、《并行算法导论/艾克萨威尔》等一些算法的书籍,对高性能计算(并行计算)有一些算法的了解,学会用并行计算的思维思考问题,解决问题。编程相关的就可以了解一下OpenMP、MPI、CUDA等编程方法。还有现在比较流行的并行计算框架、hadoop等,此类文档都可以再上网搜索。
既要了解最根本的算法,有算法的思想,同时深入了解问题的本质,然后再在编程实践中去解决问题,既有理论,也有实践,结合起来才最重要的原则。空谈误事,实干兴业
CSDN帮我提升自身价值
CSDN:你曾是CSDN社区版主,在那段时间里对你的工作和学习有何帮助?你留下了什么深刻的回忆可分享?
赵开勇:通过解答网友的问题,可以更清楚的认识问题。有些问题自己一开始也不清楚,但是在回答问题的过程中需要查阅资料,也就把问题攻克了。同时,还可以跟很多业界的朋友进行沟通和交流,分享自己研究成果的时候,帮助大家的时候,其实也是在帮助自己。我最大的收获是在分享这些成果的时候,得到了大家的认可。最深刻的影响是通过CSDN的博客分享、技术交流,让业界的各个高性能公司了解了我,包括Nvidia、AMD、浪潮、联想、曙光,以及Intel等。这些收获是在帮助别人的时候并没有考虑到的,后来回想这些收获,最重要的一点在于帮助别人,其实就是帮助自己。
CSDN:你对CSDN有何建议,你认为未来的社区有何期待?
赵开勇:在CSDN有大概有十年的感情,在这里认识了不少朋友,也希望可以成为技术交流的圈子,希望成为华人核心技术社区,成为国际品牌,而不止局限于国内,希望能走出国门,让更多的华人参与到这里面来。

QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 23楼 发表于: 2013-02-05
软件开发性能调优秘诀
关于性能优化这是一个比较大的话题,在《由12306.cn谈谈网站性能技术》中我从业务和设计上说过一些可用的技术以及那些技术的优缺点,今天,想从一些技术细节上谈谈性能优化,主要是一些代码级别的技术和方法。本文的东西是我的一些经验和知识,并不一定全对,希望大家指正和补充。


在开始这篇文章之前,大家可以移步去看一下酷壳以前发表的《代码优化概要》,这篇文章基本上告诉你——要进行优化,先得找到性能瓶颈! 但是在讲如何定位系统性能瓶劲之前,请让我讲一下系统性能的定义和测试,因为没有这两件事,后面的定位和优化无从谈起。


一、系统性能定义


让我们先来说说如何什么是系统性能。这个定义非常关键,如果我们不清楚什么是系统性能,那么我们将无法定位之。我见过很多朋友会觉得这很容易,但是仔细一问,其实他们并没有一个比较系统的方法,所以,在这里我想告诉大家如何系统地来定位性能。 总体来说,系统性能就是两个事:


Throughput ,吞吐量。也就是每秒钟可以处理的请求数,任务数。
Latency, 系统延迟。也就是系统在处理一个请求或一个任务时的延迟。
一般来说,一个系统的性能受到这两个条件的约束,缺一不可。比如,我的系统可以顶得住一百万的并发,但是系统的延迟是2分钟以上,那么,这个一百万的负载毫无意义。系统延迟很短,但是吞吐量很低,同样没有意义。所以,一个好的系统的性能测试必然受到这两个条件的同时作用。 有经验的朋友一定知道,这两个东西的一些关系:


Throughput越大,Latency会越差。因为请求量过大,系统太繁忙,所以响应速度自然会低。
Latency越好,能支持的Throughput就会越高。因为Latency短说明处理速度快,于是就可以处理更多的请求。
二、系统性能测试


经过上述的说明,我们知道要测试系统的性能,需要我们收集系统的Throughput和Latency这两个值。




首先,需要定义Latency这个值,比如说,对于网站系统响应时间必需是5秒以内(对于某些实时系统可能需要定义的更短,比如5ms以内,这个更根据不同的业务来定义)
其次,开发性能测试工具,一个工具用来制造高强度的Throughput,另一个工具用来测量Latency。对于第一个工具,你可以参考一下“十个免费的Web压力测试工具”,关于如何测量Latency,你可以在代码中测量,但是这样会影响程序的执行,而且只能测试到程序内部的Latency,真正的Latency是整个系统都算上,包括操作系统和网络的延时,你可以使用Wireshark来抓网络包来测量。这两个工具具体怎么做,这个还请大家自己思考去了。
最后,开始性能测试。你需要不断地提升测试的Throughput,然后观察系统的负载情况,如果系统顶得住,那就观察Latency的值。这样,你就可以找到系统的最大负载,并且你可以知道系统的响应延时是多少。
再多说一些,


关于Latency,如果吞吐量很少,这个值估计会非常稳定,当吞吐量越来越大时,系统的Latency会出现非常剧烈的抖动,所以,我们在测量Latency的时候,我们需要注意到Latency的分布,也就是说,有百分之几的在我们允许的范围,有百分之几的超出了,有百分之几的完全不可接受。也许,平均下来的Latency达标了,但是其中仅有50%的达到了我们可接受的范围。那也没有意义。
关于性能测试,我们还需要定义一个时间段。比如:在某个吞吐量上持续15分钟。因为当负载到达的时候,系统会变得不稳定,当过了一两分钟后,系统才会稳定。另外,也有可能是,你的系统在这个负载下前几分钟还表现正常,然后就不稳定了,甚至垮了。所以,需要这么一段时间。这个值,我们叫做峰值极限。
性能测试还需要做Soak Test,也就是在某个吞吐量下,系统可以持续跑一周甚至更长。这个值,我们叫做系统的正常运行的负载极限。
性能测试有很多很复要的东西,比如:burst test等。 这里不能一一详述,这里只说了一些和性能调优相关的东西。总之,性能测试是一细活和累活。


三、定位性能瓶颈


有了上面的铺垫,我们就可以测试到到系统的性能了,再调优之前,我们先来说说如何找到性能的瓶颈。我见过很多朋友会觉得这很容易,但是仔细一问,其实他们并没有一个比较系统的方法。


3.1)查看操作系统负载
首先,当我们系统有问题的时候,我们不要急于去调查我们代码,这个毫无意义。我们首要需要看的是操作系统的报告。看看操作系统的CPU利用率,看看内存使用率,看看操作系统的IO,还有网络的IO,网络链接数,等等。Windows下的perfmon是一个很不错的工具,Linux下也有很多相关的命令和工具,比如:SystemTap,LatencyTOP,vmstat, sar, iostat, top, tcpdump等等 。通过观察这些数据,我们就可以知道我们的软件的性能基本上出在哪里。比如:


1)先看CPU利用率,如果CPU利用率不高,但是系统的Throughput和Latency上不去了,这说明我们的程序并没有忙于计算,而是忙于别的一些事,比如IO。(另外,CPU的利用率还要看内核态的和用户态的,内核态的一上去了,整个系统的性能就下来了。而对于多核CPU来说,CPU 0 是相当关键的,如果CPU 0的负载高,那么会影响其它核的性能,因为CPU各核间是需要有调度的,这靠CPU0完成)


2)然后,我们可以看一下IO大不大,IO和CPU一般是反着来的,CPU利用率高则IO不大,IO大则CPU就小。关于IO,我们要看三个事,一个是磁盘文件IO,一个是驱动程序的IO(如:网卡),一个是内存换页率。这三个事都会影响系统性能。


3)然后,查看一下网络带宽使用情况,在Linux下,你可以使用iftop, iptraf, ntop, tcpdump这些命令来查看。或是用Wireshark来查看。


4)如果CPU不高,IO不高,内存使用不高,网络带宽使用不高。但是系统的性能上不去。这说明你的程序有问题,比如,你的程序被阻塞了。可能是因为等那个锁,可能是因为等某个资源,或者是在切换上下文。


通过了解操作系统的性能,我们才知道性能的问题,比如:带宽不够,内存不够,TCP缓冲区不够,等等,很多时候,不需要调整程序的,只需要调整一下硬件或操作系统的配置就可以了。


3.2)使用Profiler测试
接下来,我们需要使用性能检测工具,也就是使用某个Profiler来差看一下我们程序的运行性能。如:Java的JProfiler/TPTP/CodePro Profiler,GNU的gprof,IBM的PurifyPlus,Intel的VTune,AMD的CodeAnalyst,还有Linux下的OProfile/perf,后面两个可以让你对你的代码优化到CPU的微指令级别,如果你关心CPU的L1/L2的缓存调优,那么你需要考虑一下使用VTune。 使用这些Profiler工具,可以让你程序中各个模块函数甚至指令的很多东西,如:运行的时间 ,调用的次数,CPU的利用率,等等。这些东西对我们来说非常有用。


我们重点观察运行时间最多,调用次数最多的那些函数和指令。这里注意一下,对于调用次数多但是时间很短的函数,你可能只需要轻微优化一下,你的性能就上去了(比如:某函数一秒种被调用100万次,你想想如果你让这个函数提高0.01毫秒的时间 ,这会给你带来多大的性能)


使用Profiler有个问题我们需要注意一下,因为Profiler会让你的程序运行的性能变低,像PurifyPlus这样的工具会在你的代码中插入很多代码,会导致你的程序运行效率变低,从而没发测试出在高吞吐量下的系统的性能,对此,一般有两个方法来定位系统瓶颈:


1)在你的代码中自己做统计,使用微秒级的计时器和函数调用计算器,每隔10秒把统计log到文件中。


2)分段注释你的代码块,让一些函数空转,做Hard Code的Mock,然后再测试一下系统的Throughput和Latency是否有质的变化,如果有,那么被注释的函数就是性能瓶颈,再在这个函数体内注释代码,直到找到最耗性能的语句。


最后再说一点,对于性能测试,不同的Throughput会出现不同的测试结果,不同的测试数据也会有不同的测试结果。所以,用于性能测试的数据非常重要,性能测试中,我们需要观测试不同Throughput的结果。


四、常见的系统瓶颈


下面这些东西是我所经历过的一些问题,也许并不全,也许并不对,大家可以补充指正,我纯属抛砖引玉。关于系统架构方面的性能调优,大家可移步看一下《由12306.cn谈谈网站性能技术》,关于Web方面的一些性能调优的东西,大家可以看看《Web开发中需要了解的东西》一文中的性能一章。我在这里就不再说设计和架构上的东西了。


一般来说,性能优化也就是下面的几个策略:


用空间换时间。各种cache如CPU L1/L2/RAM到硬盘,都是用空间来换时间的策略。这样策略基本上是把计算的过程一步一步的保存或缓存下来,这样就不用每次用的时候都要再计算一遍,比如数据缓冲,CDN,等。这样的策略还表现为冗余数据,比如数据镜象,负载均衡什么的。
用时间换空间。有时候,少量的空间可能性能会更好,比如网络传输,如果有一些压缩数据的算法(如前些天说的“Huffman 编码压缩算法” 和 “rsync 的核心算法”),这样的算法其实很耗时,但是因为瓶颈在网络传输,所以用时间来换空间反而能省时间。
简化代码。最高效的程序就是不执行任何代码的程序,所以,代码越少性能就越高。关于代码级优化的技术大学里的教科书有很多示例了。如:减少循环的层数,减少递归,在循环中少声明变量,少做分配和释放内存的操作,尽量把循环体内的表达式抽到循环外,条件表达的中的多个条件判断的次序,尽量在程序启动时把一些东西准备好,注意函数调用的开销(栈上开销),注意面向对象语言中临时对象的开销,小心使用异常(不要用异常来检查一些可接受可忽略并经常发生的错误),…… 等等,等等,这连东西需要我们非常了解编程语言和常用的库。
并行处理。如果CPU只有一个核,你要玩多进程,多线程,对于计算密集型的软件会反而更慢(因为操作系统调度和切换开销很大),CPU的核多了才能真正体现出多进程多线程的优势。并行处理需要我们的程序有Scalability,不能水平或垂直扩展的程序无法进行并行处理。从架构上来说,这表再为——是否可以做到不改代码只是加加机器就可以完成性能提升?
总之,根据2:8原则来说,20%的代码耗了你80%的性能,找到那20%的代码,你就可以优化那80%的性能。 下面的一些东西都是我的一些经验,我只例举了一些最有价值的性能调优的的方法,供你参考,也欢迎补充。


4.1)算法调优。算法非常重要,好的算法会有更好的性能。举几个我经历过的项目的例子,大家可以感觉一下。


一个是过滤算法,系统需要对收到的请求做过滤,我们把可以被filter in/out的东西配置在了一个文件中,原有的过滤算法是遍历过滤配置,后来,我们找到了一种方法可以对这个过滤配置进行排序,这样就可以用二分折半的方法来过滤,系统性能增加了50%。
一个是哈希算法。计算哈希算法的函数并不高效,一方面是计算太费时,另一方面是碰撞太高,碰撞高了就跟单向链表一个性能(可参看Hash Collision DoS 问题)。我们知道,算法都是和需要处理的数据很有关系的,就算是被大家所嘲笑的“冒泡排序”在某些情况下(大多数数据是排好序的)其效率会高于所有的排序算法。哈希算法也一样,广为人知的哈希算法都是用英文字典做测试,但是我们的业务在数据有其特殊性,所以,对于还需要根据自己的数据来挑选适合的哈希算法。对于我以前的一个项目,公司内某牛人给我发来了一个哈希算法,结果让我们的系统性能上升了150%。(关于各种哈希算法,你一定要看看StackExchange上的这篇关于各种hash算法的文章 )
分而治之和预处理。以前有一个程序为了生成月报表,每次都需要计算很长的时间,有时候需要花将近一整天的时间。于是我们把我们找到了一种方法可以把这个算法发成增量式的,也就是说我每天都把当天的数据计算好了后和前一天的报表合并,这样可以大大的节省计算时间,每天的数据计算量只需要20分钟,但是如果我要算整个月的,系统则需要10个小时以上(SQL语句在大数据量面前性能成级数性下降)。这种分而治之的思路在大数据面前对性能有很帮助,就像merge排序一样。SQL语句和数据库的性能优化也是这一策略,如:使用嵌套式的Select而不是笛卡尔积的Select,使用视图,等等。
4.2)代码调优。从我的经验上来说,代码上的调优有下面这几点:


字符串操作。这是最费系统性能的事了,无论是strcpy, strcat还是strlen,最需要注意的是字符串子串匹配。所以,能用整型最好用整型。举几个例子,第一个例子是N年前做银行的时候,我的同事喜欢把日期存成字符串(如:2012-05-29 08:30:02),我勒个去,一个select  where between语句相当耗时。另一个例子是,我以前有个同事把一些状态码用字符串来处理,他的理由是,这样可以在界面上直接显示,后来性能调优的时候,我把这些状态码全改成整型,然后用位操作查状态,因为有一个每秒钟被调用了150K次的函数里面有三处需要检查状态,经过改善以后,整个系统的性能上升了30%左右。还有一个例子是,我以前从事的某个产品编程规范中有一条是要在每个函数中把函数名定义出来,如:const char fname[]=”functionName()”, 这是为了好打日志,但是为什么不声明成 static类型的呢?
多线程调优。有人说,thread is evil,这个对于系统性能在某些时候是个问题。因为多线程瓶颈就在于互斥和同步的锁上,以及线程上下文切换的成本,怎么样的少用锁或不用锁是根本(比如:多版本并发控制(MVCC)在分布式系统中的应用 中说的乐观锁可以解决性能问题),此外,还有读写锁也可以解决大多数是读操作的并发的性能问题。这里多说一点在C++中,我们可能会使用线程安全的智能指针AutoPtr或是别的一些容器,只要是线程安全的,其不管三七二十一都要上锁,上锁是个成本很高的操作,使用AutoPtr会让我们的系统性能下降得很快,如果你可以保证不会有线程并发问题,那么你应该不要用AutoPtr。我记得我上次我们同事去掉智能指针的引用计数,让系统性能提升了50%以上。对于Java对象的引用计数,如果我猜的没错的话,到处都是锁,所以,Java的性能问题一直是个问题。另外,线程不是越多越好,线程间的调度和上下文切换也是很夸张的事,尽可能的在一个线程里干,尽可能的不要同步线程。这会让你有很多的性能。
内存分配。不要小看程序的内存分配。malloc/realloc/calloc这样的系统调非常耗时,尤其是当内存出现碎片的时候。我以前的公司出过这样一个问题——在用户的站点上,我们的程序有一天不响应了,用GDB跟进去一看,系统hang在了malloc操作上,20秒都没有返回,重启一些系统就好了。这就是内存碎片的问题。这就是为什么很多人抱怨STL有严重的内存碎片的问题,因为太多的小内存的分配释放了。有很多人会以为用内存池可以解决这个问题,但是实际上他们只是重新发明了Runtime-C或操作系统的内存管理机制,完全于事无补。当然解决内存碎片的问题还是通过内存池,具体来说是一系列不同尺寸的内存池(这个留给大家自己去思考)。当然,少进行动态内存分配是最好的。说到内存池就需要说一下池化技术。比如线程池,连接池等。池化技术对于一些短作业来说(如http服务) 相当相当的有效。这项技术可以减少链接建立,线程创建的开销,从而提高性能。
异步操作。我们知道Unix下的文件操作是有block和non-block的方式的,像有些系统调用也是block式的,如:Socket下的select,Windows下的WaitforObject之类的,如果我们的程序是同步操作,那么会非常影响性能,我们可以改成异步的,但是改成异步的方式会让你的程序变复杂。异步方式一般要通过队列,要注间队列的性能问题,另外,异步下的状态通知通常是个问题,比如消息事件通知方式,有callback方式,等,这些方式同样可能会影响你的性能。但是通常来说,异步操作会让性能的吞吐率有很大提升(Throughput),但是会牺牲系统的响应时间(latency)。这需要业务上支持。
语言和代码库。我们要熟悉语言以及所使用的函数库或类库的性能。比如:STL中的很多容器分配了内存后,那怕你删除元素,内存也不会回收,其会造成内存泄露的假像,并可能造成内存碎片问题。再如,STL某些容器的size()==0  和 empty()是不一样的,因为,size()是O(n)复杂度,empty()是O(1)的复杂度,这个要小心。Java中的JVM调优需要使用的这些参数:-Xms -Xmx -Xmn -XX:SurvivorRatio -XX:MaxTenuringThreshold,还需要注意JVM的GC,GC的霸气大家都知道,尤其是full GC(还整理内存碎片),他就像“恐龙特级克赛号”一样,他运行的时候,整个世界的时间都停止了。
4.3)网络调优


关于网络调优,尤其是TCP Tuning(你可以以这两个关键词在网上找到很多文章),这里面有很多很多东西可以说。看看Linux下TCP/IP的那么多参数就知道了(顺便说一下,你也许不喜欢Linux,但是你不能否认Linux给我们了很多可以进行内核调优的权力)。强烈建议大家看看《TCP/IP 详解 卷1:协议》这本书。我在这里只讲一些概念上的东西。


A) TCP调优


我们知道TCP链接是有很多开销的,一个是会占用文件描述符,另一个是会开缓存,一般来说一个系统可以支持的TCP链接数是有限的,我们需要清楚地认识到TCP链接对系统的开销是很大的。正是因为TCP是耗资源的,所以,很多攻击都是让你系统上出现大量的TCP链接,把你的系统资源耗尽。比如著名的SYNC Flood攻击。


所以,我们要注意配置KeepAlive参数,这个参数的意思是定义一个时间,如果链接上没有数据传输,系统会在这个时间发一个包,如果没有收到回应,那么TCP就认为链接断了,然后就会把链接关闭,这样可以回收系统资源开销。(注:HTTP层上也有KeepAlive参数)对于像HTTP这样的短链接,设置一个1-2分钟的keepalive非常重要。这可以在一定程度上防止DoS攻击。有下面几个参数(下面这些参数的值仅供参考):


1
2
3
net.ipv4.tcp_keepalive_probes = 5
net.ipv4.tcp_keepalive_intvl = 20
net.ipv4.tcp_fin_timeout = 30
对于TCP的TIME_WAIT这个状态,主动关闭的一方进入TIME_WAIT状态,TIME_WAIT状态将持续2个MSL(Max Segment Lifetime),默认为4分钟,TIME_WAIT状态下的资源不能回收。有大量的TIME_WAIT链接的情况一般是在HTTP服务器上。对此,有两个参数需要注意,


1
2
net.ipv4.tcp_tw_reuse=1
net.ipv4.tcp_tw_recycle=1
前者表示重用TIME_WAIT,后者表示回收TIME_WAIT的资源。


TCP还有一个重要的概念叫RWIN(TCP Receive Window Size),这个东西的意思是,我一个TCP链接在没有向Sender发出ack时可以接收到的最大的数据包。为什么这个很重要?因为如果Sender没有收到Receiver发过来ack,Sender就会停止发送数据并会等一段时间,如果超时,那么就会重传。这就是为什么TCP链接是可靠链接的原因。重传还不是最严重的,如果有丢包发生的话,TCP的带宽使用率会马上受到影响(会盲目减半),再丢包,再减半,然后如果不丢包了,就逐步恢复。相关参数如下:


1
2
3
4
net.core.wmem_default = 8388608
net.core.rmem_default = 8388608
net.core.rmem_max = 16777216
net.core.wmem_max = 16777216
一般来说,理论上的RWIN应该设置成:吞吐量  * 回路时间。Sender端的buffer应该和RWIN有一样的大小,因为Sender端发送完数据后要等Receiver端确认,如果网络延时很大,buffer过小了,确认的次数就会多,于是性能就不高,对网络的利用率也就不高了。也就是说,对于延迟大的网络,我们需要大的buffer,这样可以少一点ack,多一些数据,对于响应快一点的网络,可以少一些buffer。因为,如果有丢包(没有收到ack),buffer过大可能会有问题,因为这会让TCP重传所有的数据,反而影响网络性能。(当然,网络差的情况下,就别玩什么高性能了) 所以,高性能的网络重要的是要让网络丢包率非常非常地小(基本上是用在LAN里),如果网络基本是可信的,这样用大一点的buffer会有更好的网络传输性能(来来回回太多太影响性能了)。


另外,我们想一想,如果网络质量非常好,基本不丢包,而业务上我们不怕偶尔丢几个包,如果是这样的话,那么,我们为什么不用速度更快的UDP呢?你想过这个问题了吗?


B)UDP调优


说到UDP的调优,有一些事我想重点说一样,那就是MTU——最大传输单元(其实这对TCP也一样,因为这是链路层上的东西)。所谓最大传输单元,你可以想像成是公路上的公交车,假设一个公交车可以最多坐70人,带宽就像是公路的车道数一样,如果一条路上最多可以容下100辆公交车,那意味着我最多可以运送7000人,但是如果公交车坐不满,比如平均每辆车只有20人,那么我只运送了2000人,于是我公路资源(带宽资源)就被浪费了。 所以,我们对于一个UDP的包,我们要尽量地让他大到MTU的最大尺寸再往网络上传,这样可以最大化带宽利用率。对于这个MTU,以太网是1500字节,光纤是4352字节,802.11无线网是7981。但是,当我们用TCP/UDP发包的时候,我们的有效负载Payload要低于这个值,因为IP协议会加上20个字节,UDP会加上8个字节(TCP加的更多),所以,一般来说,你的一个UDP包的最大应该是1500-8-20=1472,这是你的数据的大小。当然,如果你用光纤的话, 这个值就可以更大一些。(顺便说一下,对于某些NB的千光以态网网卡来说,在网卡上,网卡硬件如果发现你的包的大小超过了MTU,其会帮你做fragment,到了目标端又会帮你做重组,这就不需要你在程序中处理了)


再多说一下,使用Socket编程的时候,你可以使用setsockopt() 设置 SO_SNDBUF/SO_RCVBUF 的大小,TTL和KeepAlive这些关键的设置,当然,还有很多,具体你可以查看一下Socket的手册。


最后说一点,UDP还有一个最大的好处是multi-cast多播,这个技术对于你需要在内网里通知多台结点时非常方便和高效。而且,多播这种技术对于机会的水平扩展(需要增加机器来侦听多播信息)也很有利。


C)网卡调优


对于网卡,我们也是可以调优的,这对于千兆以及网网卡非常必要,在Linux下,我们可以用ifconfig查看网上的统计信息,如果我们看到overrun上有数据,我们就可能需要调整一下txqueuelen的尺寸(一般默认为1000),我们可以调大一些,如:ifconfig eth0 txqueuelen 5000。Linux下还有一个命令叫:ethtool可以用于设置网卡的缓冲区大小。在Windows下,我们可以在网卡适配器中的高级选项卡中调整相关的参数(如:Receive Buffers, Transmit Buffer等,不同的网卡有不同的参数)。把Buffer调大对于需要大数据量的网络传输非常有效。


D)其它网络性能


关于多路复用技术,也就是用一个线程来管理所有的TCP链接,有三个系统调用要重点注意:一个是select,这个系统调用只支持上限1024个链接,第二个是poll,其可以突破1024的限制,但是select和poll本质上是使用的轮询机制,轮询机制在链接多的时候性能很差,因主是O(n)的算法,所以,epoll出现了,epoll是操作系统内核支持的,仅当在链接活跃时,操作系统才会callback,这是由操作系统通知触发的,但其只有Linux Kernel 2.6以后才支持(准确说是2.5.44中引入的),当然,如果所有的链接都是活跃的,过多的使用epoll_ctl可能会比轮询的方式还影响性能,不过影响的不大。


另外,关于一些和DNS Lookup的系统调用要小心,比如:gethostbyaddr/gethostbyname,这个函数可能会相当的费时,因为其要到网络上去找域名,因为DNS的递归查询,会导致严重超时,而又不能通过设置什么参数来设置time out,对此你可以通过配置hosts文件来加快速度,或是自己在内存中管理对应表,在程序启动时查好,而不要在运行时每次都查。另外,在多线程下面,gethostbyname会一个更严重的问题,就是如果有一个线程的gethostbyname发生阻塞,其它线程都会在gethostbyname处发生阻塞,这个比较变态,要小心。(你可以试试GNU的gethostbyname_r(),这个的性能要好一些) 这种到网上找信息的东西很多,比如,如果你的Linux使用了NIS,或是NFS,某些用户或文件相关的系统调用就很慢,所以要小心。


4.4)系统调优


A)I/O模型


前面说到过select/poll/epoll这三个系统调用,我们都知道,Unix/Linux下把所有的设备都当成文件来进行I/O,所以,那三个操作更应该算是I/O相关的系统调用。说到  I/O模型,这对于我们的I/O性能相当重要,我们知道,Unix/Linux经典的I/O方式是(关于Linux下的I/O模型,大家可以读一下这篇文章《使用异步I/O大大提高性能》):


第一种,同步阻塞式I/O,这个不说了。


第二种,同步无阻塞方式。其通过fctnl设置 O_NONBLOCK 来完成。


第三种,对于select/poll/epoll这三个是I/O不阻塞,但是在事件上阻塞,算是:I/O异步,事件同步的调用。


第四种,AIO方式。这种I/O 模型是一种处理与 I/O 并行的模型。I/O请求会立即返回,说明请求已经成功发起了。在后台完成I/O操作时,向应用程序发起通知,通知有两种方式:一种是产生一个信号,另一种是执行一个基于线程的回调函数来完成这次 I/O 处理过程。


第四种因为没有任何的阻塞,无论是I/O上,还是事件通知上,所以,其可以让你充分地利用CPU,比起第二种同步无阻塞好处就是,第二种要你一遍一遍地去轮询。Nginx之所所以高效,是其使用了epoll和AIO的方式来进行I/O的。


再说一下Windows下的I/O模型,


a)一个是WriteFile系统调用,这个系统调用可以是同步阻塞的,也可以是同步无阻塞的,关于看文件是不是以Overlapped打开的。关于同步无阻塞,需要设置其最后一个参数Overlapped,微软叫Overlapped I/O,你需要WaitForSingleObject才能知道有没有写完成。这个系统调用的性能可想而知。


b)另一个叫WriteFileEx的系统调用,其可以实现异步I/O,并可以让你传入一个callback函数,等I/O结束后回调之, 但是这个回调的过程Windows是把callback函数放到了APC(Asynchronous Procedure Calls)的队列中,然后,只用当应用程序当前线程成为可被通知状态(Alterable)时,才会被回调。只有当你的线程使用了这几个函数时WaitForSingleObjectEx, WaitForMultipleObjectsEx, MsgWaitForMultipleObjectsEx, SignalObjectAndWait 和 SleepEx,线程才会成为Alterable状态。可见,这个模型,还是有wait,所以性能也不高。


c)然后是IOCP – IO Completion Port,IOCP会把I/O的结果放在一个队列中,但是,侦听这个队列的不是主线程,而是专门来干这个事的一个或多个线程去干(老的平台要你自己创建线程,新的平台是你可以创建一个线程池)。IOCP是一个线程池模型。这个和Linux下的AIO模型比较相似,但是实现方式和使用方式完全不一样。


当然,真正提高I/O性能方式是把和外设的I/O的次数降到最低,最好没有,所以,对于读来说,内存cache通常可以从质上提升性能,因为内存比外设快太多了。对于写来说,cache住要写的数据,少写几次,但是cache带来的问题就是实时性的问题,也就是latency会变大,我们需要在写的次数上和相应上做权衡。


B)多核CPU调优


关于CPU的多核技术,我们知道,CPU0是很关键的,如果0号CPU被用得过狠的话,别的CPU性能也会下降,因为CPU0是有调整功能的,所以,我们不能任由操作系统负载均衡,因为我们自己更了解自己的程序,所以,我们可以手动地为其分配CPU核,而不会过多地占用CPU0,或是让我们关键进程和一堆别的进程挤在一起。


对于Windows来说,我们可以通过“任务管理器”中的“进程”而中右键菜单中的“设置相关性……”(Set Affinity…)来设置并限制这个进程能被运行在哪些核上。
对于Linux来说,可以使用taskset命令来设置(你可以通过安装schedutils来安装这个命令:apt-get install schedutils)
多核CPU还有一个技术叫NUMA技术(Non-Uniform Memory Access)。传统的多核运算是使用SMP(Symmetric Multi-Processor )模式,多个处理器共享一个集中的存储器和I/O总线。于是就会出现一致存储器访问的问题,一致性通常意味着性能问题。NUMA模式下,处理器被划分成多个node, 每个node有自己的本地存储器空间。关于NUMA的一些技术细节,你可以查看一下这篇文章《Linux 的 NUMA 技术》,在Linux下,对NUMA调优的命令是:numactl 。如下面的命令:(指定命令“myprogram arg1 arg2”运行在node 0 上,其内存分配在node 0 和 1上)


1
numactl --cpubind=0 --membind=0,1 myprogram arg1 arg2
当然,上面这个命令并不好,因为内存跨越了两个node,这非常不好。最好的方式是只让程序访问和自己运行一样的node,如:


1
$ numactl --membind 1 --cpunodebind 1 --localalloc myapplication
C)文件系统调优


关于文件系统,因为文件系统也是有cache的,所以,为了让文件系统有最大的性能。首要的事情就是分配足够大的内存,这个非常关键,在Linux下可以使用free命令来查看 free/used/buffers/cached,理想来说,buffers和cached应该有40%左右。然后是一个快速的硬盘控制器,SCSI会好很多。最快的是Intel SSD 固态硬盘,速度超快,但是写次数有限。


接下来,我们就可以调优文件系统配置了,对于Linux的Ext3/4来说,几乎在所有情况下都有所帮助的一个参数是关闭文件系统访问时间,在/etc/fstab下看看你的文件系统 有没有noatime参数(一般来说应该有),还有一个是dealloc,它可以让系统在最后时刻决定写入文件发生时使用哪个块,可优化这个写入程序。还要注间一下三种日志模式:data=journal、data=ordered和data=writeback。默认设置data=ordered提供性能和防护之间的最佳平衡。


当然,对于这些来说,ext4的默认设置基本上是最佳优化了。


这里介绍一个Linux下的查看I/O的命令—— iotop,可以让你看到各进程的磁盘读写的负载情况。


其它还有一些关于NFS、XFS的调优,大家可以上google搜索一些相关优化的文章看看。关于各文件系统,大家可以看一下这篇文章——《Linux日志文件系统及性能分析》


4.5)数据库调优


数据库调优并不是我的强项,我就仅用我非常有限的知识说上一些吧。注意,下面的这些东西并不一定正确,因为在不同的业务场景,不同的数据库设计下可能会得到完全相反的结论,所以,我仅在这里做一些一般性的说明,具体问题还要具体分析。


A)数据库引擎调优


我对数据库引擎不是熟,但是有几个事情我觉得是一定要去了解的。


数据库的锁的方式。这个非常非常地重要。并发情况下,锁是非常非常影响性能的。各种隔离级别,行锁,表锁,页锁,读写锁,事务锁,以及各种写优先还是读优先机制。性能最高的是不要锁,所以,分库分表,冗余数据,减少一致性事务处理,可以有效地提高性能。NoSQL就是牺牲了一致性和事务处理,并冗余数据,从而达到了分布式和高性能。
数据库的存储机制。不但要搞清楚各种类型字段是怎么存储的,更重要的是数据库的数据存储方式,是怎么分区的,是怎么管理的,比如Oracle的数据文件,表空间,段,等等。了解清楚这个机制可以减轻很多的I/O负载。比如:MySQL下使用show engines;可以看到各种存储引擎的支持。不同的存储引擎有不同的侧重点,针对不同的业务或数据库设计会让你有不同的性能。
数据库的分布式策略。最简单的就是复制或镜像,需要了解分布式的一致性算法,或是主主同步,主从同步。通过了解这种技术的机理可以做到数据库级别的水平扩展。
B)SQL语句优化


关于SQL语句的优化,首先也是要使用工具,比如:MySQL SQL Query Analyzer,Oracle SQL Performance Analyzer,或是微软SQL Query Analyzer,基本上来说,所有的RMDB都会有这样的工具,来让你查看你的应用中的SQL的性能问题。 还可以使用explain来看看SQL语句最终Execution Plan会是什么样的。


还有一点很重要,数据库的各种操作需要大量的内存,所以服务器的内存要够,优其应对那些多表查询的SQL语句,那是相当的耗内存。


下面我根据我有限的数据库SQL的知识说几个会有性能问题的SQL:


全表检索。比如:select * from user where lastname = “xxxx”,这样的SQL语句基本上是全表查找,线性复杂度O(n),记录数越多,性能也越差(如:100条记录的查找要50ms,一百万条记录需要5分钟)。对于这种情况,我们可以有两种方法提高性能:一种方法是分表,把记录数降下来,另一种方法是建索引(为lastname建索引)。索引就像是key-value的数据结构一样,key就是where后面的字段,value就是物理行号,对索引的搜索复杂度是基本上是O(log(n)) ——用B-Tree实现索引(如:100条记录的查找要50ms,一百万条记录需要100ms)。
索引。对于索引字段,最好不要在字段上做计算、类型转换、函数、空值判断、字段连接操作,这些操作都会破坏索引原本的性能。当然,索引一般都出现在Where或是Order by字句中,所以对Where和Order by子句中的子段最好不要进行计算操作,或是加上什么NOT之类的,或是使用什么函数。
多表查询。关系型数据库最多的操作就是多表查询,多表查询主要有三个关键字,EXISTS,IN和JOIN(关于各种join,可以参看图解SQL的Join一文)。基本来说,现代的数据引擎对SQL语句优化得都挺好的,JOIN和IN/EXISTS在结果上有些不同,但性能基本上都差不多。有人说,EXISTS的性能要好于IN,IN的性能要好于JOIN,我各人觉得,这个还要看你的数据、schema和SQL语句的复杂度,对于一般的简单的情况来说,都差不多,所以千万不要使用过多的嵌套,千万不要让你的SQL太复杂,宁可使用几个简单的SQL也不要使用一个巨大无比的嵌套N级的SQL。还有人说,如果两个表的数据量差不多,Exists的性能可能会高于In,In可能会高于Join,如果这两个表一大一小,那么子查询中,Exists用大表,In则用小表。这个,我没有验证过,放在这里让大家讨论吧。另,有一篇关于SQL Server的文章大家可以看看《IN vs JOIN vs EXISTS》
JOIN操作。有人说,Join表的顺序会影响性能,只要Join的结果集是一样,性能和join的次序无关。因为后台的数据库引擎会帮我们优化的。Join有三种实现算法,嵌套循环,排序归并,和Hash式的Join。(MySQL只支持第一种)
嵌套循环,就好像是我们常见的多重嵌套循环。注意,前面的索引说过,数据库的索引查找算法用的是B-Tree,这是O(log(n))的算法,所以,整个算法复法度应该是O(log(n)) * O(log(m)) 这样的。
Hash式的Join,主要解决嵌套循环的O(log(n))的复杂,使用一个临时的hash表来标记。
排序归并,意思是两个表按照查询字段排好序,然后再合并。当然,索引字段一般是排好序的。
还是那句话,具体要看什么样的数据,什么样的SQL语句,你才知道用哪种方法是最好的。


部分结果集。我们知道MySQL里的Limit关键字,Oracle里的rownum,SQL Server里的Top都是在限制前几条的返回结果。这给了我们数据库引擎很多可以调优的空间。一般来说,返回top n的记录数据需要我们使用order by,注意在这里我们需要为order by的字段建立索引。有了被建索引的order by后,会让我们的select语句的性能不会被记录数的所影响。使用这个技术,一般来说我们前台会以分页方式来显现数据,Mysql用的是OFFSET,SQL Server用的是FETCH NEXT,这种Fetch的方式其实并不好是线性复杂度,所以,如果我们能够知道order by字段的第二页的起始值,我们就可以在where语句里直接使用>=的表达式来select,这种技术叫seek,而不是fetch,seek的性能比fetch要高很多。
字符串。正如我前面所说的,字符串操作对性能上有非常大的恶梦,所以,能用数据的情况就用数字,比如:时间,工号,等。
全文检索。千万不要用Like之类的东西来做全文检索,如果要玩全文检索,可以尝试使用Sphinx。
其它。
不要select *,而是明确指出各个字段,如果有多个表,一定要在字段名前加上表名,不要让引擎去算。
不要用Having,因为其要遍历所有的记录。性能差得不能再差。
尽可能地使用UNION ALL  取代  UNION。
索引过多,insert和delete就会越慢。而update如果update多数索引,也会慢,但是如果只update一个,则只会影响一个索引表。
等等。
关于SQL语句的优化,网上有很多文章, 不同的数据库引擎有不同的优化技巧,正如本站以前转发的《MySQL性能优化的最佳20+条经验》


先写这么多吧,欢迎大家指正补充。


注:这篇文章的确是个大杂烩。其实其中的说到的很多技术在网上都有很多很多的技术文章,google一下就能找到一堆有很多细节的文章,所以我也就不写了。这篇性能调优的文章写作的动机是之前看到 @淘宝褚霸 强推的highscalability.com上的这篇文章:Big List Of 20 Common Bottlenecks,觉得这篇文章泛泛而谈,觉得自己能写得比它好,所以就产生了动机。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 24楼 发表于: 2013-06-30
开发者不懂硬件运行的方式怎么可以
摘要:对比理解像Hibernate这样复杂的框架,弄清程序赖以运行的硬件工作模式实在是太简单了。单一的去追求编程的技巧而不去弄清硬件的工作方式,无异于舍本逐末!
精彩的算法,优秀的编程技巧一直广受开发者的喜爱。然而开发者不懂系统赖以运行的硬件工作方式怎么可以?基于业内一直充斥着新型硬件已经复杂到难以理解的流言,高性能计算专家Martin Thompson发表了主题为《Mythbusting Modern Hardware to Gain "Mechanical Sympathy"》的演讲。他认为如果你可以理解像Hibernate这样复杂的框架,去弄清程序赖以运行的硬件工作模式实在是太简单了。


以下为译文:


Martin Thompson是位高性能计算专家,一直从事帮助开发者弄清新型计算系统的内部构造。他在Cache、Buffer、Memory Controller、Processor Architectures、Cache line等领域发表过多次讲话和教程。


Thompson认为当下开发者在系统运行的理解上并没有投入应有的精力,大家往往被有趣的和时尚的技术所吸引。他还认为与其传授开发者编程策略,何不让其具备自己发掘的能力。他认为当下的形势非常诡异:程序员花很多的时间去理解像Hibernate这样复杂的框架,而不是花很少一点努力去弄清程序赖以运行的硬件是如何工作的。






点击查看视频(YouTube)
“通过实践观察,而不是盲目发言”一直是Martin倡导的思想之一,所以给自己的演讲《Mythbusting Modern Hardware to Gain "Mechanical Sympathy"》选择一个MythBuster(流言终结者)的角色并不奇怪。在演讲中Martin抨击了“新型硬件复杂度已经让普通开发者无法理解”这个论调,并从CPU、内存、网络、存储I/O等多个方面剖析了新型硬件架构。期间他阐述了赛车手Jackie Stewart提出的"Mechanical Sympathy"这个术语:赛车手想获得更好的成绩,那么必须对汽车的运作有一个很好的了解,驾驶员必须与赛车配合的足够默契才能获得赛车的最佳性能。Martin将这个观点延伸到了开发领域,认为开发者需要清楚硬件的工作模式,才能更好的奴驾基础设施性能。如果你可以搞清楚Hibernate,就可以搞清楚任何事情。


讲话中最精彩的部分就是有些我们一直认为做随机访问的设备,比如内存、硬盘、SSD在特定的情况下会转换成串行设备。比如说磁盘,其实就是一个又大又快的磁带,其实它并不是真正意义上的随机访问。


流言1:CPU并没有变的更快


根本原因在于CPU不能更加赖热,而不是不能变快。我们让CPU计算的更快,他们就会变的更热,并且这种局部散热是非常困难的。
时钟速度不代表一切。举个例子,给Alice和Wonderland两个文档做word split,Intel Core 2 Duo,2008,2.40GHz处理器可以达到每秒1434次操作。Intel Core,2011,2.20GHz处理器可以达到每秒2674次操作;我们看到虽然时钟速度变慢了,但是速度几乎是提升了两倍,并且这个趋势在继续发展。
取代继续变快,Sandy/Ivy Bridge平台的CPU内部使用了并行处理。比如使用3 ALU及6 Port的CPU用来加载和存储数据,我们就需要更多的Port来供给ALU,这样就可以达到每个周期并行处理6条指令的效果。
当然这里还存在多分支和多步解决的问题。多分枝或者拥有除法的代码肯定没有使用简单连接词“+、-、*”来的快。
CPU拥有计数器,这样一来,我们就可以更直观的观察其性能。在Linux上使用pref stat访问计数器。
在Alice和Wonderland测试中使用Nehalem 2.8GHz运行pref stat,我们发现CPU空闲时间将达到1/3,这样的话更快的CPU其实并没有什么帮助。
而当使用Sandy Bridge 2.4GHz时,CPU的空闲时间也达到了1/4。实验证明快不在时钟速度上,而在指令被传送到CPU的速度。
流言2:内存提供的是随机读取


1. 这个问题我们考虑的根本其实是成本问题。因为主储存器非常昂贵,我们又想尽可能快的给CPU传送指令。那么我们该如何做?我们需要让数据尽可能的靠近CPU,然而新时代的寄存器到寄存器复制模式将没有任何开销,因为这里做的是重映射,甚至没有任何移动。


2. 缓存层。缓存是越大越缓慢,所以这是速度与成本的对抗,但是功率同样很重要。访问磁盘的功率永远要比访问L1缓存大得多。新型处理器已经着手将数据从网卡直接传输到缓存,这样跳过了内存,通过不涉及CPU来降低温度。


3. 在内存访问排序、缓存结构以及连贯性上有很多细节可谈。重点是内存的不同层以及CPU之间有非常复杂的环路。如果你不可以让内存的子系统、缓存、存储器总线足够的快,就无法足够快的给CPU传输数据,这也是CPU无法变快的原因。


4. 这就意味着软件必须以一个非常友好的方式访问内存,否则将会出现CPU饥饿的状况。在Sandy Bridge平台下了连续遍历内存需要在L1上花费3 clocks,L2上花费11 clocks,L3上花费14 clocks以及内存上的6ns。页内随机则分别是3 clocks,11 clocks,18 clocks以及22ns。全随机存储访问则是3 clocks,11 clocks,38 clocks以及65.8 ns。


5. 这是高效的内存连续遍历时间,所以我们如何访问内存将是非常、非常的重要。


6. 编写多分支代码将造成更多的指令丢失,因为这里有太多的数据需要跟踪。


7. 鉴于你不可能连续的遍历内存,你需要降低耦合以及增加连贯性好的耦合,良好的连贯性可以让这些变得非常高效。如果你的代码存在太多分支,并且都是运行在堆上,那么运行的速度将会相当的缓慢。


流言3:HDD提供的随机访问


在磁盘内圈和外圈写入时性能有着很大的区别,更多的扇区被分布在磁盘的外圈,这样可以得到非常高的密度。将更多的扇区放到外圈,从而获得更高的密度。对于旋转的磁盘来说,这样可以获得更高的吞吐量。
在1万转的磁盘上,外圈的连续读取速度可以达到220MB/S,而内圈的只可以达到140MB/S。
最快的磁盘转速只有1.5万,并且已在这个数字上停滞好多年了。
当光头移动到某个扇区时,磁盘会对这个扇区上数据进行预读取及重排序。为了能获取更多的数据,当下磁盘一个扇区的大小为4K,也就是说你在磁盘上写入或者读取1字节的数据,整个工作量会达到4K。
操作由什么组成:
指令处理——亚秒
寻道时间——服务器0-6毫秒,笔记本0-15毫秒
旋转延迟——对于一个1万转的硬盘,旋转一圈需要6ms的时间,那么平均的旋转时间大约为3ms。
数据传输——100-200MB/S
随机访问一个4K的块,延时时间是10ms或者是100IOPS。随机吞吐量每秒不会超过1MB,非常智能的硬件也不会超过2MB。这样再说磁盘是随机访问显然不切实际,如果你看到一些异常的数据,那只能说这些数据并没有真正的使用磁盘。
磁盘就是个非常大的磁带,显然不是真正意义上的随机访问。
流言4:SSD提供了随机访问


1. SSD里一个块通常的大小为2MB,由大量的单元组成。SLC(Single Level Cell)——单层单元,每个单元可以存储1个字节(1、0)。MLC(Multiple Level Cell)——每个单元可以存储2或3个字节。


2. 单个单元的操作开销是巨大的,所以你可以针对行进行操作。这里被称为页,一页的大小通常为4K或者8K。以页的大小进行读或者写是相当快的,因为这里通常没有移动的过程。


3. 删除最小单位是块。SSD工作的方式是针对每个单元进行写入,当你向某个单元中写入数据并删除旧字节时,会发生这样的情况:删除一个字节是容易的,因为只需要关闭这个单元,然而当你打开一个单元时,你必须要同时打开这个单元附近的单元,这样你就不可以准确的去操作某个单元,所以你必须同时删除整个块。介于SSD中每个块的写入和读取次数是有限的,并且你的要求并不是删除整个块,所以这里只是将这个字节标注为删除。总而言之,数据被标记为删除,然后向新的块写入数据。这是有开销的,同时介于每个块读写次数都有着上限,所以直到这块SSD彻底报废,需要不停的做垃圾回收及块压缩。


4. 举个例子,SSD的读写和可以达到200M/S。当你做删除时,其读性能依然能得到保证,但是写入的速度明显下降,这就是因为SSD的垃圾回收机制。如果某块SSD的写入性能下降太多,你就必须为其重新格式化,同样还存在小的写入引起一连串的复制事件。


5. SSD在连续和随机读取上有着相当不俗的表现,如果你只做append-only write的话,性能也会一直不错。


6. 在4K随机读写,40K IOPS的情况下,平均操作次数将达到100-300ms,将花去长达半秒的垃圾回收时间。


7. 局部的异变可能会导致极低的性能。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 25楼 发表于: 2013-09-11
使用 C++ 的 StringBuilder 提升 4350% 的性能
介绍
经常出现客户端打电话抱怨说:你们的程序慢如蜗牛。你开始检查可能的疑点:文件IO,数据库访问速度,甚至查看web服务。 但是这些可能的疑点都很正常,一点问题都没有。
你使用最顺手的性能分析工具分析,发现瓶颈在于一个小函数,这个函数的作用是将一个长的字符串链表写到一文件中。
你对这个函数做了如下优化:将所有的小字符串连接成一个长的字符串,执行一次文件写入操作,避免成千上万次的小字符串写文件操作。
这个优化只做对了一半。
你先测试大字符串写文件的速度,发现快如闪电。然后你再测试所有字符串拼接的速度。
好几年。
怎么回事?你会怎么克服这个问题呢?
你或许知道.net程序员可以使用StringBuilder来解决此问题。这也是本文的起点。
monkee
monkee
翻译于 4天前
0人顶
顶 翻译的不错哦!
背景


如果google一下“C++ StringBuilder”,你会得到不少答案。有些会建议(你)使用std::accumulate,这可以完成几乎所有你要实现的:
01
#include <iostream>// for std::cout, std::endl
02
#include <string>  // for std::string
03
#include <vector>  // for std::vector
04
#include <numeric> // for std::accumulate
05
int main()
06
{
07
    using namespace std;
08
    vector<string> vec = { "hello", " ", "world" };
09
    string s = accumulate(vec.begin(), vec.end(), s);
10
    cout << s << endl; // prints 'hello world' to standard output.
11
    return 0;
12
}
目前为止一切都好:当你有超过几个字符串连接时,问题就出现了,并且内存再分配也开始积累。
std::string在函数reserver()中为解决方案提供基础。这也正是我们的意图所在:一次分配,随意连接。
字符串连接可能会因为繁重、迟钝的工具而严重影响性能。由于上次存在的隐患,这个特殊的怪胎给我制造麻烦,我便放弃了Indigo(我想尝试一些C++11里的令人耳目一新的特性),并写了一个StringBuilder类的部分实现:
001
// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx
002
template <typename chr>
003
class StringBuilder {
004
    typedef std::basic_string<chr> string_t;
005
    typedef std::list<string_t> container_t; // Reasons not to use vector below.
006
    typedef typename string_t::size_type size_type; // Reuse the size type in the string.
007
    container_t m_Data;
008
    size_type m_totalSize;
009
    void append(const string_t &src) {
010
        m_Data.push_back(src);
011
        m_totalSize += src.size();
012
    }
013
    // No copy constructor, no assignement.
014
    StringBuilder(const StringBuilder &);
015
    StringBuilder & operator = (const StringBuilder &);
016
public:
017
    StringBuilder(const string_t &src) {
018
        if (!src.empty()) {
019
            m_Data.push_back(src);
020
        }
021
        m_totalSize = src.size();
022
    }
023
    StringBuilder() {
024
        m_totalSize = 0;
025
    }
026
    // TODO: Constructor that takes an array of strings.
027

028

029
    StringBuilder & Append(const string_t &src) {
030
        append(src);
031
        return *this; // allow chaining.
032
    }
033
        // This one lets you add any STL container to the string builder.
034
    template<class inputIterator>
035
    StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) {
036
        // std::for_each and a lambda look like overkill here.
037
                // <b>Not</b> using std::copy, since we want to update m_totalSize too.
038
        for (inputIterator f = first; f != afterLast; ++f) {
039
            append(*f);
040
        }
041
        return *this; // allow chaining.
042
    }
043
    StringBuilder & AppendLine(const string_t &src) {
044
        static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love!
045
        m_Data.push_back(src + lineFeed);
046
        m_totalSize += 1 + src.size();
047
        return *this; // allow chaining.
048
    }
049
    StringBuilder & AppendLine() {
050
        static chr lineFeed[] { 10, 0 };
051
        m_Data.push_back(lineFeed);
052
        ++m_totalSize;
053
        return *this; // allow chaining.
054
    }
055

056
    // TODO: AppendFormat implementation. Not relevant for the article.
057

058
    // Like C# StringBuilder.ToString()
059
    // Note the use of reserve() to avoid reallocations.
060
    string_t ToString() const {
061
        string_t result;
062
        // The whole point of the exercise!
063
        // If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll,
064
        // both in performance and chances of failure.
065
        // I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=.
066
        result.reserve(m_totalSize + 1);
067
    //  result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve'
068
        for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) {
069
            result += *iter;
070
        }
071
        return result;
072
    }
073

074
    // like javascript Array.join()
075
    string_t Join(const string_t &delim) const {
076
        if (delim.empty()) {
077
            return ToString();
078
        }
079
        string_t result;
080
        if (m_Data.empty()) {
081
            return result;
082
        }
083
        // Hope we don't overflow the size type.
084
        size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;
085
        result.reserve(st);
086
                // If you need reasons to love C++11, here is one.
087
        struct adder {
088
            string_t m_Joiner;
089
            adder(const string_t &s): m_Joiner(s) {
090
                // This constructor is NOT empty.
091
            }
092
                        // This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory.
093
            string_t operator()(string_t &l, const string_t &r) {
094
                l += m_Joiner;
095
                l += r;
096
                return l;
097
            }
098
        } adr(delim);
099
        auto iter = m_Data.begin();
100
                // Skip the delimiter before the first element in the container.
101
        result += *iter;
102
        return std::accumulate(++iter, m_Data.end(), result, adr);
103
    }
104

105
}; // class StringBuilder
jimmyjmh
jimmyjmh
翻译于 2天前
0人顶
顶 翻译的不错哦!
有趣的部分


函数ToString()使用std::string::reserve()来实现最小化再分配。下面你可以看到一个性能测试的结果。
函数join()使用std::accumulate(),和一个已经为首个操作数预留内存的自定义函数。
你可能会问,为什么StringBuilder::m_Data用std::list而不是std::vector?除非你有一个用其他容器的好理由,通常都是使用std::vector。
好吧,我(这样做)有两个原因:
1. 字符串总是会附加到一个容器的末尾。std::list允许在不需要内存再分配的情况下这样做;因为vector是使用一个连续的内存块实现的,每用一个就可能导致内存再分配。
2. std::list对顺序存取相当有利,而且在m_Data上所做的唯一存取操作也是顺序的。
你可以建议同时测试这两种实现的性能和内存占用情况,然后选择其中一个。
jimmyjmh
jimmyjmh
翻译于 2天前
0人顶
顶 翻译的不错哦!
性能评估


为了测试性能,我从Wikipedia获取一个网页,并将其中一部分内容写死到一个string的vector中。
随后,我编写两个测试函数,第一个在两个循环中使用标准函数clock()并调用std::accumulate()和StringBuilder::ToString(),然后打印结果。
01
void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
02
    const int loops = 500;
03
    clock_t start = clock(); // Give up some accuracy in exchange for platform independence.
04
    for (int i = 0; i < loops; ++i) {
05
        std::wstring accumulator;
06
        std::accumulate(tested2.begin(), tested2.end(), accumulator);
07
    }
08
    double secsAccumulate = (double) (clock() - start) / CLOCKS_PER_SEC;
09

10
    start = clock();
11
    for (int i = 0; i < loops; ++i) {
12
        std::wstring result2 = tested.ToString();
13
    }
14
    double secsBuilder = (double) (clock() - start) / CLOCKS_PER_SEC;
15
    using std::cout;
16
    using std::endl;
17
    cout << "Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds."
18
            << " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%"
19
            << endl;
20
}
第二个则使用更精确的Posix函数clock_gettime(),并测试StringBuilder::Join()。
01
#ifdef __USE_POSIX199309
02

03
// Thanks to <a href="http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/">Guy Rutenberg</a>.
04
timespec diff(timespec start, timespec end)
05
{
06
    timespec temp;
07
    if ((end.tv_nsec-start.tv_nsec)<0) {
08
        temp.tv_sec = end.tv_sec-start.tv_sec-1;
09
        temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
10
    } else {
11
        temp.tv_sec = end.tv_sec-start.tv_sec;
12
        temp.tv_nsec = end.tv_nsec-start.tv_nsec;
13
    }
14
    return temp;
15
}
16

17
void AccurateTestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
18
    const int loops = 500;
19
    timespec time1, time2;
20
    // Don't forget to add -lrt to the g++ linker command line.
21
    ////////////////
22
    // Test std::accumulate()
23
    ////////////////
24
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
25
    for (int i = 0; i < loops; ++i) {
26
        std::wstring accumulator;
27
        std::accumulate(tested2.begin(), tested2.end(), accumulator);
28
    }
29
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
30
    using std::cout;
31
    using std::endl;
32
    timespec tsAccumulate =diff(time1,time2);
33
    cout << tsAccumulate.tv_sec << ":" <<  tsAccumulate.tv_nsec << endl;
34
    ////////////////
35
    // Test ToString()
36
    ////////////////
37
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
38
    for (int i = 0; i < loops; ++i) {
39
        std::wstring result2 = tested.ToString();
40
    }
41
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
42
    timespec tsToString =diff(time1,time2);
43
    cout << tsToString.tv_sec << ":" << tsToString.tv_nsec << endl;
44
    ////////////////
45
    // Test join()
46
    ////////////////
47
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
48
    for (int i = 0; i < loops; ++i) {
49
        std::wstring result3 = tested.Join(L",");
50
    }
51
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
52
    timespec tsJoin =diff(time1,time2);
53
    cout << tsJoin.tv_sec << ":" << tsJoin.tv_nsec << endl;
54

55
    ////////////////
56
    // Show results
57
    ////////////////
58
    double secsAccumulate = tsAccumulate.tv_sec + tsAccumulate.tv_nsec / 1000000000.0;
59
    double secsBuilder = tsToString.tv_sec + tsToString.tv_nsec / 1000000000.0;
60
        double secsJoin = tsJoin.tv_sec + tsJoin.tv_nsec / 1000000000.0;
61
    cout << "Accurate performance test:" << endl << "    Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." << endl
62
            << "    The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" << endl <<
63
             "     Join took " << secsJoin << " seconds."
64
            << endl;
65
}
66
#endif // def __USE_POSIX199309
最后,通过一个main函数调用以上实现的两个函数,将结果显示在控制台,然后执行性能测试:一个用于调试配置。
Debug version screenshot另一个用于发行版本:
Release version screenshot看到这百分比没?垃圾邮件的发送量都不能达到这个级别!
jimmyjmh
jimmyjmh
翻译于 2天前
0人顶
顶 翻译的不错哦!
代码使用


在使用这段代码前, 考虑使用ostring流。正如你在下面看到Jeff先生评论的一样,它比这篇文章中的代码更快些。
你可能想使用这段代码,如果:
你正在编写由具有C#经验的程序员维护的代码,并且你想提供一个他们所熟悉接口的代码。
你正在编写将来会转换成.net的、你想指出一个可能路径的代码。
由于某些原因,你不想包含<sstream>。几年之后,一些流的IO实现变得很繁琐,而且现在的代码仍然不能完全摆脱他们的干扰。
要使用这段代码,只有按照main函数实现的那样就可以了:创建一个StringBuilder的实例,用Append()、AppendLine()和Add()给它赋值,然后调用ToString函数检索结果。
就像下面这样:
01
int main() {
02
    ////////////////////////////////////
03
    // 8-bit characters (ANSI)
04
    ////////////////////////////////////
05
    StringBuilder<char> ansi;
06
    ansi.Append("Hello").Append(" ").AppendLine("World");
07
    std::cout << ansi.ToString();
08

09
    ////////////////////////////////////
10
    // Wide characters (Unicode)
11
    ////////////////////////////////////
12
    // http://en.wikipedia.org/wiki/Cargo_cult
13
    std::vector<std::wstring> cargoCult
14
    {
15
        L"A", L" cargo", L" cult", L" is", L" a", L" kind", L" of", L" Melanesian", L" millenarian", L" movement",
16
// many more lines here...
17
L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.\n"
18
    };
19
    StringBuilder<wchar_t> wide;
20
    wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();
21
        // use ToString(), just like .net
22
    std::wcout << wide.ToString() << std::endl;
23
    // javascript-like join.
24
    std::wcout << wide.Join(L" _\n") << std::endl;
25

26
    ////////////////////////////////////
27
    // Performance tests
28
    ////////////////////////////////////
29
    TestPerformance(wide, cargoCult);
30
#ifdef __USE_POSIX199309
31
    AccurateTestPerformance(wide, cargoCult);
32
#endif // def __USE_POSIX199309
33
    return 0;
34
}
任何情况下,当连接超过几个字符串时,当心std::accumulate函数。
jimmyjmh
jimmyjmh
翻译于 2天前
0人顶
顶 翻译的不错哦!
现在稍等一下!


你可能会问:你是在试着说服我们提前优化吗?
不是的。我赞同提前优化是糟糕的。这种优化并不是提前的:是及时的。这是基于经验的优化:我发现自己过去一直在和这种特殊的怪胎搏斗。基于经验的优化(不在同一个地方摔倒两次)并不是提前优化。
当我们优化性能时,“惯犯”会包括磁盘I-O操作、网络访问(数据库、web服务)和内层循环;对于这些,我们应该添加内存分配和性能糟糕的 Keyser Söze。
鸣谢


首先,我要为这段代码在Linux系统上做的精准分析感谢Rutenberg。
多亏了Wikipedia,让“在指尖的信息”的梦想得以实现。
最后,感谢你花时间阅读这篇文章。希望你喜欢它:不论如何,请分享您的意见。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 26楼 发表于: 2015-12-27
memory prefetch浅析
最近在用vtune分析程序性能瓶颈时,发现一些内存访问的地方竟然成了cpu热点。经过仔细分析,发现这些热点主要是对大数组非连续位置的访问的引起的。比较消耗cpu的原因应该是cache不命中。因为像这样局部性很差的内存访问逻辑,对cache是很不友好的。于是想到了prefetch……


x86(以及其他很多体系结构)的CPU提供了prefetch系列指令,用于将指定地址的内存预取到cache。如”prefetcht0 (%rax)”将以$rax所保存的值为地址的内存所在的cache line(大小一般是64byte)载入每一级cache。
在适当位置加了prefetch之后,程序里相应的cpu热点果然得以消除,程序性能得到提升。
现象
在此也写一段测试程序,体验一下prefetch的功效,并做一些简单的分析。(注,分析硬件的行为实在是一件痛苦的事情。对于软件来说,源代码摆在那里,一是一、二是二,很多问题都是确定的。而硬件不仅看不到它的具体实现,也鲜有文档。并且相比操作系统为软件提供的虚拟而单纯的运行环境,硬件环境复杂多变,有时候实在让人难以琢磨。所以以下分析实在难免存在谬误。不妥之处还请包涵。)
#include <xmmintrin.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <math.h>


void usage()
{
    printf("usage: BIN file step prefetch\n");
    exit(1);
}


inline int calcu(int input)
{
#ifdef EMPTYCALC
    return input;
#endif
    int val = (input % 99) * (input / 98);
    val = val ? val : 1;
#ifdef HEAVYCALC
    double d = (double)input / (double)val;
    return (int)pow(d, 1999.9);
#endif
    double n = sqrt(sqrt((double)(unsigned)input * 1.3));
    double m = sqrt(sqrt((double)(unsigned)val * 0.9));
    return (int)((double)input * (double)val * m / (n ? n : 1.1));
}


int run_withprefetch(const int *array, int size, int step, int prefetch)
{
    int result = 0;
    printf("run with prefetch(%d)...\n", prefetch);
    for (int i = 0; i < step; i++) {
        for (int j = i; j < size; j += step) {
            int k = j + step * prefetch;
            if (k  < size) {
                _mm_prefetch(&array[k], _MM_HINT_T0);
                //const int *addr = &array[k];
                //__asm__ __volatile__ ("mov (%0), %%eax"::"r"(addr):"eax");
                //__asm__ __volatile__ ("mov %0, %%eax"::"r"(k):"eax");
            }
            result += calcu(array[j]);
        }
    }
    return result;
}


int run(const int *array, int size, int step)
{
    int result = 0;
    printf("run...\n");
    for (int i = 0; i < step; i++) {
        for (int j = i; j < size; j += step) {
            //asm volatile("lfence");
            result += calcu(array[j]);
        }
    }
    return result;
}


int main(int argc, const char *argv[])
{
    if (argc != 4) {
        usage();
    }


    int step = atoi(argv[2]);
    int prefetch = atoi(argv[3]);
    int fd = open(argv[1], O_RDONLY);
    if (fd == -1) {
        usage();
    }
    struct stat st;
    int ret = fstat(fd, &st);
    if (ret != 0) {
        usage();
    }


    int array_size = st.st_size / sizeof(int);
    printf("array size: %d, step: %d. ", array_size, step);


    const int *array = (const int *)mmap(NULL, st.st_size, PROT_READ, MAP_POPULATE|MAP_SHARED, fd, 0);
    if (array == MAP_FAILED) {
        usage();
    }


    struct timeval tv1, tv2;
    gettimeofday(&tv1, NULL);


    int result = 0;
    if (prefetch == 0) {
        result = run(array, array_size, step);
    }
    else if (prefetch > 0) {
        result = run_withprefetch(array, array_size, step, prefetch);
    }


    gettimeofday(&tv2, NULL);
    tv2.tv_sec -= tv1.tv_sec;
    tv2.tv_usec -= tv1.tv_usec;
    if (tv2.tv_usec < 0) {
        tv2.tv_usec += 1000000;
        tv2.tv_sec--;
    }
    printf("time cost: %d.%06d, ", tv2.tv_sec, tv2.tv_usec);
    printf("result: %d\n", result);
    return result;
}
程序mmap一个大文件(由file参数指定)作为大数组,对数组中的每一个元素进行一定的变换逻辑(calc函数,通过宏定义选择三种不同复杂度的逻辑)、然后加和。
对于数组元素的访问支持顺序访问和跳跃访问(step参数,跳跃间隙)、支持预取(prefetch参数,预取提前量)。
(注意,程序最终产生的result的值只跟选择的计算逻辑和输入文件的内容相关,跟读内存的顺序无关。所以,后续不管给程序加了什么稀奇古怪的读内存逻辑,最终的result都是一致的。这就确保了我们所加的各种读内存逻辑没有引入BUG。)
一些测试结果:
$ ll -h test.tar.gz
-rw-rw-r-- 1 xiangy xiangy 1.8G Jun 27 09:37 test.tar.gz
$ g++ -O2 prefetch.cpp -DHEAVYCALC -o prefetch.heavy
$ g++ -O2 prefetch.cpp -DEMPTYCALC -o prefetch.empty
$ g++ -O2 prefetch.cpp -o prefetch.normal
$ ./prefetch.normal
usage: BIN file step prefetch
(选择不同复杂度的计算逻辑,编译成以不同后缀命名的可执行文件。)


[case-1]$ ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 23.980005, result: 692002678
(空计算+跳读内存。预期内存访问基本上都是cache miss,而计算逻辑基本上又不花时间,所以最终花费的时间主要就是读内存时间。记住这个值,下面的case经常需要参考它。)


[case-2]$ ./prefetch.normal test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 22.846302, result: 1309150882
[case-3]$ ./prefetch.normal test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 66.041256, result: 1309150882
[case-4]$ ./prefetch.normal test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.247350, result: 1309150882
(以上是普通计算的运行情况。case-2顺序读内存预期基本上都是cache hit的,最终花费的时间主要是执行计算逻辑的时间;case-3跳读内存时间花费大量增加;case-4加了预取之后,时间花费基本上恢复到case-2的水平。)


[case-5]$ ./prefetch.heavy test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 47.386533, result: 1625037789
[case-6]$ ./prefetch.heavy test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 107.783801, result: 1625037789
[case-7]$ ./prefetch.heavy test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 51.492479, result: 1625037789
(以上是复杂计算的运行情况。跟前面的表现基本一致,跳读带来了大量的时间增长,而预取又基本恢复到顺序读时的水平。)


如果读内存开销很小、或者计算开销很小,prefetch也有用么?
[case-8]$ ./prefetch.empty test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 24.253892, result: 692002678
(空计算+跳读内存,预取效果跟不加预取时差不多。)


[case-9]$ ./prefetch.normal test.tar.gz 1 4
array size: 468787200, step: 1. run with prefetch(4)...
time cost: 22.896790, result: 1309150882
(普通计算+顺序读内存+预取,效果跟不加预取时也差不多。)


可见当读内存存在一定开销、且开销小于或相当于计算开销时,通过适当的prefetch能够将跳读内存开销隐藏掉,基本上达到顺序读内存的效果。
反过来如果计算开销不大、或者读内存本身没什么开销,单纯想通过prefetch来提升读内存的速度,效果并不明显。
prefetch原理
为什么prefetch能达到这样的效果呢?简单来说,prefetch将原本串行工作的计算过程和读内存过程并行化了。如:
load-1                            load-1
calc-1                   =>       calc-1    load-2
          load-2                            calc-2    load-3
          calc-2                                      calc-3
但是实际上却又并非如此简单。


在一个程序中,组成程序本身的指令虽然是有顺序的,但是CPU在执行指令的时候并不一定按部就班一条一条的去执行,指令之间有很多并行性可以去挖掘。(这就是所谓的ILP,Instruction Level Parallelism,指令级并行。)
两条指令想要并行执行需要满足三个条件:
1、指令之间没有数据依赖
如:a = b * 3; c = d + 5;, 就没有依赖;
如:a = b * 3; c = a + 5; ,“写后读”依赖。第二条指令需要a的值作为输入,而a的值依赖于第一条指令的计算结果;
如:a = b * 3; a = d + 5; ,“写后写”依赖。不过虽然第二条指令一定要在第一条指令修改a的值之后才能修改a的值(确保最终a的值是d + 5的结果),但是其实两条指令是可以并行执行的,最后将结果commit到a的时候再串行就OK了;
如:a = b * 3; b = d + 5;, “读后写”依赖。同样,虽然第二条指令一定不能在第一条指令读取b的值之前就将b的值修改(确保第一条指令读到的是旧值),但是只要确保第一条指令先拿到b的旧值、或者直接跟生成b的旧值的那条指令关联上,之后两条指令还是可以并行执行的;
2、CPU功能部件充足
CPU中用来执行具体操作的功能部件是有限的,假设CPU只有一个乘法器。
如:a = b * 3; c = d + 5; ,一个使用乘法器、另一个使用加法器,互不影响就可以并行;
如:a = b * 3; c = d * 5; ,两条指令都需要使用这个仅有的乘法器,就只能串行了(当然也未必是第一条指令先占用乘法器,因为可能它所依赖的b的值尚未ready、而第二条指令所需要的d已经OK);
3、CPU已经看到这两条指令
程序执行的指令序列可能无穷无尽(考虑到有循环),CPU为了挖掘并行性不可能一下子分析所有指令,一定会有个限度。在经典的流水线算法--tomasulo算法--中,这个限度就是RS(reservation station,保留站)的数目。CPU取指部件按指令顺序将指令放入RS,并设置它们的依赖关系(RS提供了这样的支持)。存在于RS中的指令当输入已经ready、且需要的功能部件有空余时,便会开始执行。
遇到分支指令时指令序列如何确定呢?分支指令在执行完成之前根本就不知道程序要往哪里走。解决办法就是分支预测,根据一些统计信息猜测程序的走向。然后无视这些分支,就跟没有分支时一样去执行。如果分支预测错了,再回滚回来,按正确的序列重新执行。
回到我们的例子,每个loop有一个load过程+一个calc过程,calc过程依赖于load过程。但是下一次loop的load并不依赖于上一loop的calc过程,并且load和calc使用不同的CPU功能部件,所以这两个过程是可以并行的。(for循环在经历很多次loop之后才会退出,每次分支的走向都是一样的,可以近似认为分支预测一定成功。)
prefetch加与不加,前两个并行条件都是不会变的:prefetch既不会改变指令之间的依赖关系、也不会多占用或少占用CPU功能部件。但是为什么加上prefetch会有效果呢?
区别只在于第三个并行条件。试想当程序执行到第N次loop时(loop-N),由于calc过程复杂,指令很多,RS一直被占满。直到计算进入尾声,loop-(N+1)的指令才进入RS,这时CPU才知道要去load loop-(N+1)的input。而这些input在cache中不能命中,需要经历漫长的读内存过程,导致loop-(N+1)的calc指令卡在RS中得不到执行。相当于load和calc过程被串行化了。
加了prefetch之后呢?loop-(N+X)的prefetch指令排在loop-N的计算指令之前,早早的就能进入RS。这些load指令是计算的源头,其本身并没有依赖别的数据,所以一旦内存通道空闲下来prefetch就可以开始工作了。于是load与calc才正真并行起来。
如下面示意:
case-2,顺序读内存,cache全命中:
calc-11
calc-12
calc-13    calc-21
           calc-22
           calc-23    calc-31
                      calc-32
                      calc-33    calc-41
                                 calc-42
                                 calc-43    calc-51
                                            calc-52
                                            calc-53
(每个loop约花费2个单位时间。)


case-3,跳读内存,cache全不命中:
load-11
load-12
calc-11
calc-12
calc-13    load-21
           load-22
           calc-21
           calc-22
           calc-23    load-31
                      load-32
                      calc-31
                      calc-32
                      calc-33
(每个loop约花费4个单位时间。注,假设CPU执行到calc-N3的时候才看到有load-(N+1)1。)


case-4,跳读内存,加预取:
load-11
load-12
calc-11    prefetch-21
calc-12    prefetch-22
calc-13    calc-21    prefetch-31
           calc-22    prefetch-32
           calc-23    calc-31    prefetch-41
                      calc-32    prefetch-42
                      calc-33    calc-41    prefetch-51
                                 calc-42    prefetch-52
                                 calc-43    calc-51
                                            calc-52
                                            calc-53
(每个loop约花费2个单位时间。注,在calc-N1之前prefetch-(N+X)1就已经发起了。)


通过prefetch,使这些既耗时又被后续指令依赖的load指令提前进入CPU的视野,让CPU可以利用可能空闲的内存带宽,提前完成读操作。另一方面,使用prefetch预取内存之后,跟依赖于它的那些计算指令拉开了距离,使得计算指令不必等到马上就得使用load的输入时才临时抱佛脚。拉开相关依赖指令的距离正是编译器优化代码的一种常用手段,通常通过指令重排调整无关指令的顺序来实现。
到这里prefetch的大致逻辑已经理清楚了,但是仔细想一下其实问题还很多……
例子引出的问题
第一个问题,为什么case-3(读内存+普通计算)的执行时间(66.041256)要比case-1(单纯的读内存)时间(23.980005)+case-2(单纯的计算)时间(22.846302)更长呢?按理说,就算load指令和calc指令完全串行,case-3的执行时间最多也就等于1、2之合吧。
这个问题应该可以用内存多通道来解释。现在CPU访问内存的通道一般会有两个或以上。在case-1中,单纯的读内存其实并不代表串行的读内存。多个内存通道是可以让多个load指令并行工作的,以充分利用内存带宽。而在case-3中,由于引入了一堆计算指令,导致RS被装满,CPU无法同时看到当前loop和下一个loop的load请求,也就无法将两次load并行化。所以,更准确来说,case-3耗时这么长的原因并不是load与calc无法并行,而是load与load无法并行。loop-N的calc过程跟loop-(N+1)的load过程是并行的,但是在loop-(N+1) load完成并进行calc之前,loop-(N+2)的load指令还未进入CPU的视野,所以无法与loop-(N+1)的load并行。
如何证实这一点呢?
我们在case-1中加一个lfence指令试试看。lfence是x86提供的内存屏障指令,作用是确保load操作的顺序:lfence之前的load操作必须先于lfence之后的load操作。如此便打破了load的并行性(如果真如刚才所说,并行性存在的话)。
修改run函数如下:
int run(const int *array, int size, int step)
{
    int result = 0;
    printf("run...\n");
    for (int i = 0; i < step; i++) {
        for (int j = i; j < size; j += step) {
            asm volatile("lfence");
            result += calcu(array[j]);
        }
    }
    return result;
}
再次运行case-1:


[case-1.1]$ g++ -O2 prefetch.cpp -DEMPTYCALC
[case-1.1]$ ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 63.999864, result: 692002678
(强制让load不能并行之后,case-1.1的耗时直接变成了case-3的水平。说明在原本的case-1中load是存在很大的并行度的。)


再以加lfence的代码运行一下case-6(未加prefetch、复杂计算)看看,如果在复杂计算+跳读内存的情况下,读内存的并行性已经很少的话,加了lfence之后的耗时应该跟加之前差不多:
[case-6.1]$ g++ -O2 prefetch.cpp -DHEAVYCALC
[case-6.1]$ ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 114.787379, result: 1625037789
(果然如此。)


还可以同时运行两个程序来看看是什么情况。两个程序同时运行时,由于kernel load balance的作用,它们会尽量运行在不同的CPU上、且尽量不共享cache。那么,如果两个进程都总是能cache hit,则运行时间应该跟单个进程运行时差不多;反之如果总是cache miss,则两个进程会争抢内存带宽,运行时间会有所增加。
[case-2.2]$ ./prefetch.normal test.tar.gz 1 0 | ./prefetch.normal test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 22.964594, result: 1309150882
(两个顺序读内存的普通计算一起运行,因为总是cache hit,所以跟单个运行的时间差不多。)


[case-1.2]$ ./a.out test.tar.gz 1024 0 | ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 63.973557, result: 692002678
(两个加了lfence的进程一起运行,由于进程内的内存访问已经串行化了,两个进程可以各自使用一个内存通道,所以运行时间跟单个进程运行时差不多。)


[case-1.3]$ ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 24.083044, result: 692002678
[case-1.4]$ ./prefetch.empty test.tar.gz 1024 0 | ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 37.948864, result: 692002678
(而用之前没加过lfence的程序再试一下,两个进程同时运行时,由于争抢内存带宽,运行时间就会受影响。)


prefetch提前量
还有一个问题也可以用内存多通道来解释,即prefetch提前量问题。先就之前的程序继续看几个case:
$ for x in 1 2 4 8 16 32; do ./prefetch.normal test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run with prefetch(1)...
time cost: 36.262511, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(2)...
time cost: 29.902517, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.052798, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(8)...
time cost: 26.040215, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(16)...
time cost: 26.198825, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(32)...
time cost: 25.910506, result: 1309150882
prefetch提前量从1增大到32。从结果看,当提前量小的时候,prefetch效果不明显。为什么呢?


假设提前量为1,那么loop-N会为loop-(N+1)进行预取。但是从前面普通计算的数据可以看出,就一个loop而言,load的时间是多于calc时间的(从总量上说,load并行之后才与calc时间相当,那么单独的load就应该比calc耗时长)。所以当执行到loop-(N+1)的时候,prefetch应该尚未完成。
再假设提前量为4,loop-N会为loop-(N+4)做预取,loop-(N+1)为loop-(N+5)预取。而在进入loop-(N+1)时,loop-(N+4)的预取尚未完成,而此时发起的loop-(N+5)的预取就能与之并行。可见增大提前量能更好的利用内存带宽。(虽然说以N为提前量就可以充分利用N个内存通道,但是机器上还有kernel和其他进程也在使用内存,未必就能让你独占内存带宽。所以使用大于N的提前量更能充分利用空余的内存带宽。)
当然提前量肯定不能太大,否则等真正用到数据的时候,预取好的数据可能已经被从cache中挤出去了。
用mov代替prefetch?
prefetch指令可以用来预取,难道不用prefetch就不行了么?
我们将之前的run_withprefetch函数修改一下,把prefetch替换成简单的load操作:
int run_withprefetch(const int *array, int size, int step, int prefetch)
{
    int result = 0;
    printf("run with prefetch(%d)...\n", prefetch);
    for (int i = 0; i < step; i++) {
        for (int j = i; j < size; j += step) {
            int k = j + step * prefetch;
            if (k  < size) {
                const int *addr = &array[k];
                asm volatile("mov (%0), %%eax"::"r"(addr):"eax");
            }
            result += calcu(array[j]);
        }
    }
    return result;
}
重跑case-4:


[case-4.1]$ g++ -O2 prefetch.cpp
[case-4.1]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 37.312423, result: 1309150882
确实比不加prefetch的情况case-3(66.041256)要好很多,但还是比不上原来的case-4(28.247350)。


那么prefetch比直接movload好在哪里呢?
1、使用mov也同样能达到让load操作提前进入CPU视野的目的
2、使用mov访问过的内存同样会被cache住
3、仅仅是因为mov操作多占用了一个寄存器么?把代码改成这样看看(使用原来的prefetch但是多占用一个寄存器):
    if (k  < size) {
        _mm_prefetch(&array[k], _MM_HINT_T0);
        __asm__ __volatile__ ("mov %0, %%eax"::"r"(k):"eax");
    }
[case-4.2]$ g++ -O2 prefetch.cpp
[case-4.2]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.051848, result: 1309150882
可见仅仅多占用一个寄存器,貌似并没有什么影响。(在tomasulo算法中,这里实际上并没有多占用寄存器,而是多占用了RS。)


前面提到了tomasulo算法,提到了RS,这里面还有个东西叫ROB(reorder buffer,指令重排缓存)。前面还提到过对于“写后写”依赖指令,在执行过程中是可以并行的,只要保证最后写回的顺序不变就行了。ROB就能完成这个功能。
CPU取指令之后除了将其放入RS(让其可以乱序执行),还要按顺序将其放入ROB。执行完成后的指令最终在ROB中排队,然后按顺序提交(将结果写回寄存器或内存)。ROB还有另一个很重要的作用,就是分支预测失败时的回滚。分支指令也跟其他指令一样要在ROB中排队。如果分支指令执行完以后发现分支预测错了,则将ROB里排在这条分支之后的指令及其结果都清理掉就行了。因为ROB是按指令顺序排队的,由于分支预测出错而被错误执行的那些指令一定都排在分支指令之后。
回到我们的例子,”mov (addr), %eax”这条指令会一直占着ROB,直到load完成。这将导致后续的指令结果一直得不到提交,尚未被CPU取走的指令又会因为无法获得ROB而不能被取走。这又回到了类似于case-3(未加prefetch)的情形,指令无法大量进入CPU的视野,以致于内存访问无法占满内存带宽。只不过因为ROB的资源没有RS那么紧张,所以阻塞的情况没有case-3那么严重。
基于以上说明,我们改造case-6(未加prefetch、复杂计算)看看。对于复杂计算,calc过程的指令更多,按理说,阻塞的情况会更严重,直接load应该效果更差。
[case-6.2]$ g++ -O2 prefetch.cpp -DHEAVYCALC
[case-6.2]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 100.910547, result: 1625037789
果然,这个结果比起原本的case-6(107.783801)已经没有优势了。


那么为什么prefetch不会受ROB的大小限制呢?因为prefetch是一个特殊指令,没有输出,对程序上下文也没有影响,甚至于分支预测失败时也不需要回滚。那么CPU完全没必要让prefetch指令进ROB(当然RS还是要进的,因为prefetch可能依赖于前面指令的结果)。
其他问题
关于硬件prefetch
虽然CPU提供了显式prefetch指令,其实它自己暗中也会进行一些prefetch,可以称之为硬件prefetch。
硬件prefetch有这么几个要点:
1、CPU在经历连续一定次数的cache miss后触发。偶尔发生的一次cache miss是很正常的,比如访问一个不常使用的全局变量;
2、CPU有一定的模式匹配策略,能够识别顺序访问和一些固定step的跳跃访问;
3、最重要的一点,硬件prefetch不会跨page进行。因为内存是按page管理的,跨page意味着可能触发page fault,这是CPU自己所无法handle的,得由kernel来解决。CPU暗中的prefetch动作对软件来说本来是透明的,不能让kernel去handle可能本不应发生的page fault,甚至于这样的page fault可能导致segment fault(相反,软件prefetch是软件自己发起的,有什么后果自己承担);
基于第3点,CPU一般不会试图去识别步长高于512字节的跳跃访问。因为要经历三次cache miss,CPU才能发现跳读内存的步长是相同的(pos2 – pos1 == pos3 – pos2),而后如果触发硬件prefetch的话,大于512字节的步长可能使得访存操作很快跨跃page边界,触发prefetch意义已经不大了。
我们可以继续用前面的程序来观察一下硬件prefetch的表现。将step从1到1024递增,不使用软件prefetch:
$ for x in 1 2 4 8 16 32 64 128 256 512 1024; do ./prefetch.normal test.tar.gz $x 0; done
array size: 468787200, step: 1. run...
time cost: 22.863716, result: 1309150882
array size: 468787200, step: 2. run...
time cost: 23.438035, result: 1309150882
array size: 468787200, step: 4. run...
time cost: 23.846166, result: 1309150882
array size: 468787200, step: 8. run...
time cost: 24.171723, result: 1309150882
array size: 468787200, step: 16. run...
time cost: 25.502980, result: 1309150882
array size: 468787200, step: 32. run...
time cost: 37.461018, result: 1309150882
array size: 468787200, step: 64. run...
time cost: 39.829086, result: 1309150882
array size: 468787200, step: 128. run...
time cost: 44.291904, result: 1309150882
array size: 468787200, step: 256. run...
time cost: 65.332225, result: 1309150882
array size: 468787200, step: 512. run...
time cost: 64.764071, result: 1309150882
array size: 468787200, step: 1024. run...
time cost: 65.952260, result: 1309150882
随着step的逐步增大,可以看出时间消耗分为三个档次:


step 1~16,cost 22~25,因为16个int是64byte,正好在一个cache line中。这么小的step再加上硬件预取基本上都能cache hit了;
step 32~128,cost 37~44,这个区间的cost跨度较大。在这些step下,单个page内读取值的个数分是32、16、8,硬件prefetch尚有一定的余地被触发、并发挥作用。然后随着可预取数目的减少,cost也不段增加;
step 256~,cost 64~65,步长超过了1024byte,硬件prefetch已经不会被触发;
关于TLB cache miss
应用程序中使用地址的都是虚拟地址,访问内存时存在虚拟地址到物理地址的转换过程。转换规则(即页表)是放在内存中的,并由TLB来cache。地址转换需要跳多级页表、多次读内存,所以如果TLB cache miss,代价是很大的。
不过在我的环境中貌似并不存在TLB cache miss的问题。继续改造程序验证一下:
int run(const int *array, int size, int step, int blocksize)
{
    int result = 0;
    blocksize *= 4096;
    if (blocksize == 0) {
        blocksize = size;
    }
    printf("run... (block=%d pages)\n", blocksize/4096);
    int start = 0;
    int nsize = blocksize;
    while (nsize == blocksize) {
        if (start + blocksize > size)
            nsize = size - start;
        for (int i = 0; i < step; i+=32) {
            for (int j = i; j < nsize; j += step) {
                int thissize = j + 32 < nsize ? j + 32 : nsize;
                for (int k = j; k < thissize; k++) {
                    result += calcu(array[start+k]);
                }
            }
        }
        start += nsize;
    }
    return result;
}
改造run函数把整个文件按blocksize划分成若干个块,每个块单独完成跳读逻辑。


于是,当块比较小时块内跳读时所涉及的page比较少,TLB应该能将相关的页表都cache住;而当块比较大,可能就会出现TLB cache miss。
这里面还存在另一个问题,按之前的做法,每个int跳一次。如果块比较小,第一轮跳读时可能整个块都被cache了,后续的跳读都将cache hit。而块大时又无法cache整个块,后续的跳读又将继续cache miss。这就对观察TLB cache miss产生很大影响。所以程序改成每32个int跳读一次(按前面的结果,跳读32以后性能就不好了),以忽略cache hit所带来的影响。
修改main函数,用第4个参数来传递blocksize(0值表示不分block):
$ for x in 128 256 512 1024 0; do ./a.out test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run... (block=128 pages)
time cost: 22.501363, result: 1309150882
array size: 468787200, step: 1024. run... (block=256 pages)
time cost: 22.627935, result: 1309150882
array size: 468787200, step: 1024. run... (block=512 pages)
time cost: 25.064514, result: 1309150882
array size: 468787200, step: 1024. run... (block=1024 pages)
time cost: 24.976720, result: 1309150882
array size: 468787200, step: 1024. run... (block=114450 pages)
time cost: 24.900870, result: 1309150882
看起来TLB cache miss所带来的影响不大。


关于L1 cache
前面一直在讲cache,并没有细分是第几级的cache。其实前面的例子对内存的使用并没有那么精细,主要利用的cache还是L2 cache。
继续用前面分块的例子来看看,因为要考查cache,所以把连读32个int的逻辑去掉。run函数改造如下:
int run(const int *array, int size, int step, int blocksize)
{
    int result = 0;
    blocksize *= 4096;
    if (blocksize == 0) {
        blocksize = size;
    }
    printf("run... (block=%d pages)\n", blocksize/4096);
    int start = 0;
    int nsize = blocksize;
    while (nsize == blocksize) {
        if (start + blocksize > size)
            nsize = size - start;
        for (int i = 0; i < step; i++) {
            for (int j = i; j < nsize; j += step) {
                result += calcu(array[start+j]);
            }
        }
        start += nsize;
    }
    return result;
}
在一个块内反复跳读,如果以块的大小刚好能被cache住,则程序运行时间会很短;否则又得经历漫长的读内存过程。


$ for x in 1 2 4 8 16 32 64 128 256 512 1024; do ./a.out test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run... (block=1 pages)
time cost: 1.614654, result: 692002678
array size: 468787200, step: 1024. run... (block=2 pages)
time cost: 1.554286, result: 692002678
array size: 468787200, step: 1024. run... (block=4 pages)
time cost: 1.625566, result: 692002678
array size: 468787200, step: 1024. run... (block=8 pages)
time cost: 2.621453, result: 692002678
array size: 468787200, step: 1024. run... (block=16 pages)
time cost: 2.697908, result: 692002678
array size: 468787200, step: 1024. run... (block=32 pages)
time cost: 2.724401, result: 692002678
array size: 468787200, step: 1024. run... (block=64 pages)
time cost: 2.710056, result: 692002678
array size: 468787200, step: 1024. run... (block=128 pages)
time cost: 3.864916, result: 692002678
array size: 468787200, step: 1024. run... (block=256 pages)
time cost: 4.241000, result: 692002678
array size: 468787200, step: 1024. run... (block=512 pages)
time cost: 20.216653, result: 692002678
array size: 468787200, step: 1024. run... (block=1024 pages)
time cost: 24.361176, result: 692002678
随着block size的逐渐增大,程序运行时间显现出三个层次。分别代表着L1 cache hit(1〜4)、L2 cache hit(8〜256)、cache miss(512〜)三种状态。看起来L1 cache在本例中影响并不大。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
描述
快速回复

您目前还是游客,请 登录注册
如果您在写长篇帖子又不马上发表,建议存为草稿