算法之外的优化

[redsea]

关于算法之外的优化, 不少人觉得用处不大,

一般说来, 主要的思路定了之后, 程序的性能大致也定了. 但是, 当前的CPU 潜力很大, 并且 CPU 比内存速度很多, 还是带来很多优化余
地的. 优秀的低级优化是要考虑 memory 访问次数, 顺序访问/随机访问, cpu cache line 大小(例如 64bytes),
甚至考虑到某个地址段的访问, 读和写分别集中起来(内存不但速度慢, 非连续访问的时候, 要等待, 读和写还有切换时间, AMD cpu 内置
memory controller, 内部更加智能地对读写group, 内存性能好), 调整条件判断指令, 以便让分支预测更准确, 等等,
因素很多.

对于基本算法不良的程序, 这种低级优化能够带来的帮助未必很大, 因为它可能有其他严重的性能瓶颈, 例如同步瓶颈, 内存块非常零散, CPU 指
令太多, 或者造成分支预测不准的条件判断太多等不良问题.

但是对于算法良好的程序, 如果程序不是 memory bound 的这种级别的优化, 经常能够提高程序的性能40% 以上, 甚至快几倍.
memory bound 的程序 -- 例如那种执行10万条CPU指令, 就要从1000个不同地址取数据, 数据量还大到cache 放不下;
或者要从一个地址复制5M, 10M 数据到另外一个地址的程序, 这种程序性能被 memory bound 住了, 优化也无用.

intel 的工程师经常帮一起经典的软件, 库进行优化, 优化结果经常是可以快很多, 他们就是结合考虑指令集(SSE之类)优化, 内存访问优
化, 分支预测优化, 可并行(cpu 执行器级别)指令顺序调整等等做的优化.

我现在的水平还很低, 性能 critical 的代码, 主要做的是memory, cache 考虑, 以及用软件对分支预测不准进行分析, 对不
准的点做做调整看看结果(不知道所以然, 所以不知道理论上怎么调整好).

有经验的大大出来指点一下 ?

[oldrev]

Intel 在卖优化过的常用算法库，可以考虑买一个 :)

在 2007-10-24三的 19:13 -0700，redsea写道：

--

Live Long and Prosper
- oldrev

[wang xin]

这个题目太大了，我通常都是把架构和算法选好，剩下的就交给编译器去做优化了
大部分时间下，架构比算法对性能的影响更大

性能critical的代码，有时可能需要考虑lock的粒度，不是说lock的粒度越小越好

在07-10-25，redsea < red...@gmail.com> 写道：

--
Everything is possible and available if we trust ourselves!

[莫华枫]

这么说来，考虑到高性能的情况下，就无法再考虑移植性了。高级的性能优化都是平台特定的。
从这一点上来看，C++既强调性能，又要确保移植性的做法是错误的。与其同时确保两者，还不如确保编译器的可移植性，以便开发者利用不同的编译器针对性地提高性能。如今的情况就是既无法保证一个编译器包打天下，又无法让代码在不同编译期间快速移植，两头没着落。

在07-10-25， redsea <red...@gmail.com> 写道：

longsh...@gmail.com
http://blog.csdn.net/longshanks/

[red...@gmail.com]

我认为 Lock 也是属于算法和设计级别的问题.

还有, 有时候的算法必须依据硬件的特点进行选择, 例如, 我们有一个程序, 每秒
钟收到8万个请求包, 要根据请求包中的一个字符串判断这个请求包后续应该怎么
处理, 请求字符串分布范围非常广, 但是可能有50万个字符串规则; 而这个判断要
在3us 之内确保完成, 这个程序没有架构问题, 没有同步问题(不能进行动态内存
分配, 连这个同步冲突点都没有).

这种情形下面, Intel 销售的优化的算法库也都没有什么用 (实际上这个程序在
os kernel 里面跑), 程序量不大(也不能大).

wang xin 写道:

[red...@gmail.com]

其中 memory 的这个非常重要因素, 倒是各个平台都有的问题, 问题也差不多.

cpu 的 l2 cache line 大小种类也不太多, 32bytes, 64bytes(有没有 128bytes
的 ?), 很多是64bytes, 这样, 一个内存访问, 只要你访问了其中1个字节, 你再
访问64对齐该内存块其他内存就很快了; 由于现在 cpu 执行指令快, 所以
longlong ago 前的传说: byte bool 比起 int bool 速度慢 (cpu 要先执行一个
int 扩展) 现在也不存在了, 反而如果一个结构中, 你将常用的字段都尽量缩小,
并且尽量挤在前面, 那么无论 cpu cache line 多大, 性能多半都有提升.

莫华枫 写道:
> 这么说来，考虑到高性能的情况下，就无法再考虑移植性了。高级的性能优化都
> 是平台特定的。
> 从这一点上来看，C++既强调性能，又要确保移植性的做法是错误的。与其同时
> 确保两者，还不如确保编译器的可移植性，以便开发者利用不同的编译器针对性
> 地提高性能。如今的情况就是既无法保证一个编译器包打天下，又无法让代码在
> 不同编译期间快速移植，两头没着落。
>

[red...@gmail.com]

wang xin 写道:

> 这个题目太大了，我通常都是把架构和算法选好，剩下的就交给编译器去做优化了
> 大部分时间下，架构比算法对性能的影响更大

不过我说得也不准确, 准确地说, 应该, 硬件的这些特性, 对高性能计算的底层算
法选择影响很大.

[wang xin]

精心构造你的字符串规则（也就是选取一个精心构造都数据集）
如：著名的quake中的那个用于求平方根的浮点数

在07-10-25，red...@gmail.com < red...@gmail.com> 写道：

[red...@gmail.com]

还有, 编译器其实是知道后端平台的特点的, 它们也尽力对这些特点进行优化, 例
如安排可平行执行的指令这些东西, 在intel 不同代 cpu 中的做法是不同的..

只是, 最核心的代码, 自己进行分析之后, 调整优化, 可以有机会比编译器干得
好; 并且编译器是不会抱怨你的基础算法不好, 调整一下更好优化的, 人却可以发
现这点.

[red...@gmail.com]

字符串规则倒不是我能够指定的, 因为要和现有的东西兼容.

不过我发现我的题目取错了, 回想起来, 这种优化经常涉及到回头大调或者细调数
据结构. 很有可能 intel 工程师帮别人优化的时候, 也是有这样的调整的.

所以, 不应该叫做算法之外的优化, 应该是从低级分析结果引导的优化.

wang xin 写道:
> 精心构造你的字符串规则（也就是选取一个精心构造都数据集）
> 如：著名的quake中的那个用于求平方根的浮点数

[莫华枫]

如果先抛开算法本身的问题，仅考虑面向平台优化，编译器能多大程度上帮助，或者说代替人工进行的优化呢？是否一个面向特定平台优化的编译器可以完全达到人工的程度？
此外，jit能够起到什么样的作用？

在07-10-25，red...@gmail.com <red...@gmail.com> 写道：

longsh...@gmail.com
http://blog.csdn.net/longshanks/

[wang xin]

我指的也不一定是真的要重新指定字符串规则，只是说你可以选取一个合理的排放到某容器然后用o(1)的算法对它进行访问，anyway，这个东西比较tricky，也不一定可以一下就看到一个直观的结果

嗯，你的这个题目确实很难让人回答；不过那个新的题目，我对它就一窍不通来:D

在07-10-25， red...@gmail.com <red...@gmail.com> 写道：

[wang xin]

99%的程序员做不到比编译器优化的更好的地步

在07-10-25，莫华枫 <longsh...@gmail.com> 写道：

如果先抛开算法本身的问题，仅考虑面向平台优化，编译器能多大程度上帮助，或者说代替人工进行的优化呢？是否一个面向特定平台优化的编译器可以完全达到人工的程度？
此外，jit能够起到什么样的作用？

[red...@gmail.com]

嗯, 确实如此, 就拿最基本的并行指令重新排列, 要做这件事情, pentium 是有两个 uv 不同的执行器, 能力不同, 最新的 core2 有三个整数执行器, 两个浮点执行器, 不同的目标CPU, 做法就不一样.  gcc 的 march 选项就有很多的 cpu 选择. vc 就简单很多.

要能够做好这些事情, 非得要长期做汇编才可以 ---- intel 的工程师可以, photoshop 的程序员中, 说不定也有几个有些研究, 暴雪公司不知道有没有, 但是这样的人, 肯定不多. 但是 gcc 是知道这些事情的, vc 也应该知道.

jit 能够做到什么地步, 我不清楚. 对于编译器而言, 似乎这个地方的优化开销并不是特别大(起码 gcc 开全优化, 编译速度也还能够接受, g++ 那个不谈, 时间花到其他地方了.).


我们现在只是在某些方面, 例如内存访问次数, 条件判断等方面, 在数据结构和C代码的一个级别进行调节和优化. 条件判断这边做的优化我还不知道方向, 只是发现分支预测错误多, 就将条件反向看看结果, 到底应该怎么做呢 ?

wang xin 写道:

99%的程序员做不到比编译器优化的更好的地步

在07-10-25，莫 华枫 <longsh...@gmail.com> 写道：

如 果先抛开算法本身的问题，仅考虑面向平台优化，编译器能多大程度上帮助，或者说代替人工进行的优化呢？是否一个面向特定平台优化的编译器可以完全达到人工 的程度？
此外，jit能够起到什么样的作用？

[Atry]

Boost.Function 在 1.34 做的小缓冲区优化刚好是把 Boost.Function 做成 32 字节，难道也是出于这个考虑？

在07-10-25，red...@gmail.com < red...@gmail.com> 写道：

[wang xin]

其实，这个问题问我几乎就等同于"问道于盲":$
我知道的都是一些基本的理论知识:(
对于jit来说，如果产生的intermediate code（如bytecode或者P-Code）的指令集简单的话，那么jit就可以起到很大的帮助，得到和编译差不多的执行代码
我很怀疑whole-program-optimization应该是可以给性能带来很大的好处，不过没有花时间去测试过

说到编译选项，这个就见仁见智了，gcc的那堆选项，我至今都没有了解1%，还不如vc来得简单点好；反正最终还是可以找专门的人来做一些细调的

在07-10-25，red...@gmail.com <red...@gmail.com> 写道：

嗯, 确实如此, 就拿最基本的并行指令重新排列, 要做这件事情, pentium 是有两个 uv 不同的执行器, 能力不同, 最新的 core2 有三个整数执行器, 两个浮点执行器, 不同的目标CPU, 做法就不一样.  gcc 的 march 选项就有很多的 cpu 选择. vc 就简单很多.

要能够做好这些事情, 非得要长期做汇编才可以 ---- intel 的工程师可以, photoshop 的程序员中, 说不定也有几个有些研究, 暴雪公司不知道有没有, 但是这样的人, 肯定不多. 但是 gcc 是知道这些事情的, vc 也应该知道.

jit 能够做到什么地步, 我不清楚. 对于编译器而言, 似乎这个地方的优化开销并不是特别大(起码 gcc 开全优化, 编译速度也还能够接受, g++ 那个不谈, 时间花到其他地方了.).


我们现在只是在某些方面, 例如内存访问次数, 条件判断等方面, 在数据结构和C代码的一个级别进行调节和优化. 条件判断这边做的优化我还不知道方向, 只是发现分支预测错误多, 就将条件反向看看结果, 到底应该怎么做呢 ?

--

[shark]

gcc做的优化较泛化，主要分三层，想看gimple之前的优化做得如何，可以用svn的gcc加上-fdump-tree-all看看。

[莫华枫]

太恐怖了。:-(

在07-10-25，shark <cplus...@gmail.com> 写道：

--
反者道之动，弱者道之用
m...@seaskysh.com
longsh...@gmail.com
http://blog.csdn.net/longshanks/

[holmescn]

对性能和可移植性的权衡问题，很麻烦啊。
首要的应该是算法的优化，这是非常行之有效的啊。
然后当然应该profile一下，找到20%的地方，再进行可能的算法优化。
最后，在性能仍达不到要求的情况下，考虑底层的优化。

不知道是不是正确，呵呵，见笑了。

[wave]

一些类似SIMD的数据处理，利用GPU计算也能够获得很好的加速效果。

[freefalcon]

程序框架和算法这些关键地方的优化自不用说，汇编级别的优化一般程序也用不到，那除此之外，还有多少地方可以优化？这些优化究竟能带来多大的性能提升，
做过这方面工作的朋友有没有具体数字？我对这方面接触不多，:)

On 10月25日, 上午11时34分, red...@gmail.com wrote:
> 嗯, 确实如此, 就拿最基本的并行指令重新排列, 要做这件事情, pentium 是有两个 uv 不同的执行器, 能力不同, 最新的 core2 有三个整数执行器, 两个浮点执行器, 不同的目标CPU, 做法就不一样. gcc 的 march 选项就有很多的 cpu 选择. vc 就简单很多.
> 要能够做好这些事情, 非得要长期做汇编才可以 ---- intel 的工程师可以, photoshop 的程序员中, 说不定也有几个有些研究, 暴雪公司不知道有没有, 但是这样的人, 肯定不多. 但是 gcc 是知道这些事情的, vc 也应该知道.
> jit 能够做到什么地步, 我不清楚. 对于编译器而言, 似乎这个地方的优化开销并不是特别大(起码 gcc 开全优化, 编译速度也还能够接受, g++ 那个不谈, 时间花到其他地方了.).
> 我们现在只是在某些方面, 例如内存访问次数, 条件判断等方面, 在数据结构和C代码的一个级别进行调节和优化. 条件判断这边做的优化我还不知道方向, 只是发现分支预测错误多, 就将条件反向看看结果, 到底应该怎么做呢 ?

> wang xin 写道:99%的程序员做不到比编译器优化的更好的地步在07-10-25，莫华枫<longsh...@gmail.com> 写道：如果先抛开算法本身的问题，仅考虑面向平台优化，编译器能多大程度上帮助，或者说代替人工进行的优化呢？是否一个面向特定平台优化的编译器可以完全达到人工的程度？
> 此外，jit能够起到什么样的作用？

[freefalcon]

40%的性能提升，这是什么样的程序？优化是在源程序级别还是汇编代码级别？
我个人还是觉得，对于大多数应用程序而言，做到框架与算法级别的优化就足够了，因为我们还要考虑开发效率。而对于计算密集型程序才有必要考虑底层的优
化，IO密集型程序基本上也可以在算法方面进行优化。

On 10月25日, 上午10时13分, redsea <red...@gmail.com> wrote:

[red...@gmail.com]

我自己的程序, 字符串查找分段, 同时变大写, 并且计算 hash code 的几个函数, 在源代码级别优化, 做内存访问优化之后也提高了大概是40% 左右.

后来想进一步优化, 同时减小了内存访问次数和代码行数, 第一次扫描字符串改成跳跃着扫描, 结果是, 比之前的两次从头到尾扫描, 代码行数更长的算法反倒慢了.

freefalcon 写道:

[wang xin]

40%的来源分布是怎么样的？源代码优化贡献了多少？内存访问优化又贡献了多少？有没有具体的数据
有没有试过替换hash func来获取性能的提高？

其实，最好还是可以把source放上来看看（不过这就可能导致了代码的泄露了）:$

在07-10-25， red...@gmail.com <red...@gmail.com> 写道：

我自己的程序, 字符串查找分段, 同时变大写, 并且计算 hash code 的几个函数, 在源代码级别优化, 做内存访问优化之后也提高了大概是40% 左右.

后来想进一步优化, 同时减小了内存访问次数和代码行数, 第一次扫描字符串改成跳跃着扫描, 结果是, 比之前的两次从头到尾扫描, 代码行数更长的算法反倒慢了.

[red...@gmail.com]

我之前没有怎么说清楚, 这个函数应该就是一个, 说几个, 应该是指最初的版本和优化的版本等. 结果是, 最初版本比开始快了40% 多.

由于对性能要求高, 写成多个函数很难完成目标, 所以这是一个函数, 同时完成分段, 变大写, 以及计算各独立段, 连续段的 hashcode 计算 (要计算 3-6 个 hashcode).

利用 TSC 计数器的结果, 先对算法进行小调整(这些小调整, 如果没有TSC 计数器, 也不容易直接判断出效果), 大致获得了 20% 的收益, 然后是调整语句, 以便让内存访写更高效, 又获得了超过20% 的收益.

高深的优化我也不会, 我是设法让读内存的代码集中,连续读, 中间不要写内存(读优化); 几个变量之间赋值的时候, 设法让生成的汇编码连续装载几个变量到寄存器, 然后才从寄存器写出等(写优化), 整个过程都是用调整代码看结果的方法进行尝试.

这种类型的优化, 理由在于, 内存访问首字节延时时间长, 后续连续字节延时时间短 (L2 cache 也有这个特性, L1 不知道, 大概没有), 内存读写切换需要时间(L2 cache 记得也有这个特性)等, 这种特性是不同体系的CPU 中, 都普遍存在的, 所以这些优化结果, 应该不至于使得程序的适应性太差.

当然, 如果程序弄到 33M 的 CPU 上面跑, CPU 执行指令比较慢, 相比之下, 内存等待不是那么长, 有些用更多 CPU指令换取少读内存的优化, 就有反效果. ---- BTW, 我怀疑为当前gHZ 级别 CPU 设计的操作系统, 例如 Vista, Linux 2.6 之类, 里面某些要求性能的地方, 也有类似的优化代码, 这样, 弄到很低频率的CPU上面跑的时候, 有可能由于反效果使得这些 OS 在慢速CPU雪上加霜.


分析过程这样做:
1. 用函数运行前后的 CPU TSC 计数器差值作为标准 (CPU 2.5G, 所以理论最小分辨率 0.4 ns, 但实际最小分辨率大概是5ns这个级别)

2. 测试算法对memory 中的值的计算速度
   方法是, 提供一大堆输入, 给函数调用, 统计 TSC 差值输出; 执行一轮之后, 做大量的内存操作, 使得当前cpu l2 cache 被全部刷新, 然后执行第二轮, 统计多轮之后作为输出.

3. 测试算法对cache 中的值的计算速度
   对每个输入, 连续计算20次, 然后再处理下一个输入.

这样来对程序进行调整观察效果, 进行优化, 根据我们的程序的实际情况, 这 2,3 两个值都要兼顾.

曾经将测试3的每次运行结果都输出, 发现有意思的现象: 对一个输入, 连续运行函数20次, 并不是 cache 被填充之后, 速度就一致了, 大概是:

1. 第一次, cache 没有装载, 慢很多,   例如 调整前后多个版本大概分布 在600-950ns 左右
2. 第二次, cache 已经装载, 好了很多,                      大概分布    75-120ns 左右
3. 第三次, 还能快一些,                                    大概分布    60- 90ns 左右
后面速度就第三次差不多了, 而且方差分布较小.

第三次比第二次还能够提高, 已经不是 cache 的问题, (下面纯属猜测, 概不负责), 可能是执行的代码很局部化, 使得 CPU 分支预测结构有足够存储将分支历史都记住, 从而带来好处. 

从这点看, 密集的循环, 如果循环体里面条件判断较多, 进行低级优化的时候, 可以测试一下, 分成两次循环说不定分支预测程序有机会更好地记住分支历史, 从而速度更快 ---- 前提当然是, 循环体访问的内存量不要太大, 否则第二次循环, 要重新加载cache, 那就糟了. 



wang xin 写道:

[HouS...@gmail.com]

"算法之外的优化" 我经常和这个层级的优化打交道； (这方面我的文章较多，我的blog: http://blog.csdn.net/housisong
)
这几天正在写的一篇blog文章， 高清(1080p)YUV视频格式转换到RGB的优化，可以从普通实现的每秒几十帧优化到几百帧；
对于一些图形图像处理算法，经常需要处理的是一个个的像素，从单个像素的算法复杂度来看，都是O(1),这就y要求必须在"算法之外的优化"处着手。
前面经常提到"算法之外的优化"带来"40%"的优化收益，在我看来远远不止这个数量级，很多时候甚至能够达到快出几倍的地步；

对于编译器的优化能力，VC2005不错(GCC差一些)，如果是同一个实现，我手工写的汇编一般能比VC2005提高10%-20%；(但在不同
CPU上的
适应能力有时没有编译器做得好) (高手应该可以做得更好一些； 什么时候可以不用写汇编就好了) ；
这方面比较佩服Intel的编译器，手工写的汇编很难超过它，但它只对自家的CPU支持比较好，在AMD的CPU上麻烦多多(可能孤陋寡闻)；

[redsea]

细读了条件语句优化的那章, 搞明白了一些事情, 谢谢.
好好学习, 天天向上.

[Linker Lin]

Intel提供的一些特殊指令可以加快一些常用的查找操作,
比如 BSF就可以加快滑动窗口算法.
SSE指令集更是性能优化的关键点,充分利用SSE可以成倍提升ALU运算密集型应用的性能.

linker...@gmail.com