[performance] 性能优化策略的最后手段



Answers

建议:

  • 预先计算而不是重新计算 :任何包含具有相对有限输入范围的计算的循环或重复调用都应考虑对包含有效范围内的所有值的计算结果进行查找(数组或字典)投入。 然后在算法中使用简单的查找。
    下方 :如果实际使用的预计算值很少,这可能会使情况变得更糟,而查找可能会占用大量内存。
  • 不要使用库方法 :大多数库需要被编写为在各种场景下正确运行,并对参数执行空检查等。通过重新实现一种方法,您可能会去掉大量的逻辑并不适用于您正在使用它的确切情况。
    下方 :编写额外的代码意味着更多的表面区域的错误。
  • 使用图书馆方法 :与自己相反,语言图书馆是由比你或我更聪明的人编写的; 几率是他们做得更好,更快。 不要自己实现它,除非你真的能够更快地实现它(即:总是测量!)
  • 作弊 :在某些情况下,虽然您的问题可能存在确切的计算方法,但您可能不需要“确切”,有时候可能“足够好”并且交易速度更快。 问问自己,答案是否超出1%真的很重要吗? 5%? 甚至10%?
    下方 :呃......答案并不准确。
Question

这个网站上有很多性能问题,但是我发现几乎所有问题都是针对特定问题的,而且相当狭窄。 几乎所有的重复建议,以避免过早优化。

我们假设:

  • 代码已经正常工作
  • 所选算法对于问题的情况已经是最优的
  • 代码已被测量,并且违规程序已被隔离
  • 所有优化的尝试也将被测量,以确保它们不会让事情变得更糟

我在这里寻找的是一些策略和技巧,当没有其他任何事情可以做但是无论如何需要的时候,在关键算法中挤出最后的几个百分比。

理想情况下,尽量使语言不可知的答案,并在适用的情况下指出建议策略的任何缺点。

我会用我自己的最初建议添加一个回复,并期待社区可以想到的任何其他内容。




If better hardware is an option then definitely go for that. 除此以外

  • Check you are using the best compiler and linker options.
  • If hotspot routine in different library to frequent caller, consider moving or cloning it to the callers module. Eliminates some of the call overhead and may improve cache hits (cf how AIX links strcpy() statically into separately linked shared objects). This could of course decrease cache hits also, which is why one measure.
  • See if there is any possibility of using a specialized version of the hotspot routine. Downside is more than one version to maintain.
  • Look at the assembler. If you think it could be better, consider why the compiler did not figure this out, and how you could help the compiler.
  • Consider: are you really using the best algorithm? Is it the best algorithm for your input size?



Tweak the OS and framework.

It may sound an overkill but think about it like this: Operating Systems and Frameworks are designed to do many things. Your application only does very specific things. If you could get the OS do to exactly what your application needs and have your application understand how the the framework (php,.net,java) works, you could get much better out of your hardware.

Facebook, for example, changed some kernel level thingys in Linux, changed how memcached works (for example they wrote a memcached proxy, and used udp instead of tcp ).

Another example for this is Window2008. Win2K8 has a version were you can install just the basic OS needed to run X applicaions (eg Web-Apps, Server Apps). This reduces much of the overhead that the OS have on running processes and gives you better performance.

Of course, you should always throw in more hardware as the first step...




今天唯一最重要的限制因素是有限的记忆bandwitdh 。 由于带宽在核心之间共享,多核只会让这种情况变得更糟。 而且,专用于实现缓存的有限芯片面积也在内核和线程之间分配,甚至更加恶化了这个问题。 最后,保持不同高速缓存一致性所需的片间信令也随着内核数量的增加而增加。 这也增加了一个惩罚。

这些是你需要管理的效果。 有时通过微观管理你的代码,但有时通过仔细的考虑和重构。

很多评论已经提到了缓存友好的代码。 至少有两种不同的风味:

  • 避免获取存储器延迟。
  • 降低内存总线压力(带宽)。

第一个问题具体与使您的数据访问模式更加规律有关,从而允许硬件预取器高效工作。 避免动态内存分配将数据对象分散到内存中。 使用线性容器而不是链接列表,哈希和树。

第二个问题与改进数据重用有关。 修改算法以处理适合可用缓存的数据子集,并尽可能重用该数据,同时仍保留在缓存中。

将数据打包得更严格并确保在热循环中使用高速缓存行中的所有数据,将有助于避免这些其他影响,并允许在缓存中安装更多有用的数据。




分而治之

如果正在处理的数据集太大,请循环使用它的大块。 如果你已经完成了你的代码,那么实现应该很简单。 如果你有一个单一的程序,现在你知道更好。




Reduce variable sizes (in embedded systems)

If your variable size is larger than the word size on a specific architecture, it can have a significant effect on both code size and speed. For example, if you have a 16 bit system, and use a long int variable very often, and later realize that it can never get outside the range (−32.768 ... 32.767) consider reducing it to short int.

From my personal experience, if a program is ready or almost ready, but we realize it takes up about 110% or 120% of the target hardware's program memory, a quick normalization of variables usually solves the problem more often than not.

By this time, optimizing the algorithms or parts of the code itself can become frustratingly futile:

  • reorganize the whole structure and the program no longer works as intended, or at least you introduce a lot of bugs.
  • do some clever tricks: usually you spend a lot of time optimizing something, and discover no or very small decrease in code size, as the compiler would have optimized it anyway.

Many people make the mistake of having variables which exactly store the numerical value of a unit they use the variable for: for example, their variable time stores the exact number of milliseconds, even if only time steps of say 50 ms are relevant. Maybe if your variable represented 50 ms for each increment of one, you would be able to fit into a variable smaller or equal to the word size. On an 8 bit system, for example, even a simple addition of two 32-bit variables generates a fair amount of code, especially if you are low on registers, while 8 bit additions are both small and fast.




Did you know that a CAT6 cable is capable of 10x better shielding off extrenal inteferences than a default Cat5e UTP cable?

For any non-offline projects, while having best software and best hardware, if your throughoutput is weak, then that thin line is going to squeeze data and give you delays, albeit in milliseconds... but if you are talking about the last drops, that's a some drops gained, 24/7 for any packge sent or received.




更多建议:

  • 避免I / O :任何I / O(磁盘,网络,端口等)总是比执行计算的任何代码都要慢很多,所以要摆脱任何你不需要的I / O。

  • 预先移动I / O :将预先需要的所有数据加载到计算机中,以便在重要算法的核心内不会有重复的I / O等待(也可能是重复的结果磁盘寻求,当加载所有数据在一个命中可能会避免寻求)。

  • 延迟I / O :在计算结束前不要写出结果,将它们存储在数据结构中,然后在完成艰苦工作时一次性转储结果。

  • Threaded I / O :对于那些足够大胆的人来说,将“I / O预先”或“延迟I / O”与实际计算结合起来,将加载移动到并行线程中,以便在加载更多数据时,在对已有数据进行计算时,或者在计算下一批数据时,可以同时写出最后一批的结果。




Not nearly as in depth or complex as previous answers, but here goes: (these are more beginner/intermediate level)

  • obvious: dry
  • run loops backwards so you're always comparing to 0 rather than a variable
  • use bitwise operators whenever you can
  • break repetitive code into modules/functions
  • cache objects
  • local variables have slight performance advantage
  • limit string manipulation as much as possible



Here are some quick and dirty optimization techniques I use. I consider this to be a 'first pass' optimization.

Learn where the time is spent Find out exactly what is taking the time. Is it file IO? Is it CPU time? Is it the network? Is it the Database? It's useless to optimize for IO if that's not the bottleneck.

Know Your Environment Knowing where to optimize typically depends on the development environment. In VB6, for example, passing by reference is slower than passing by value, but in C and C++, by reference is vastly faster. In C, it is reasonable to try something and do something different if a return code indicates a failure, while in Dot Net, catching exceptions are much slower than checking for a valid condition before attempting.

Indexes Build indexes on frequently queried database fields. You can almost always trade space for speed.

Avoid lookups Inside of the loop to be optimized, I avoid having to do any lookups. Find the offset and/or index outside of the loop and reuse the data inside.

Minimize IO try to design in a manner that reduces the number of times you have to read or write especially over a networked connection

Reduce Abstractions The more layers of abstraction the code has to work through, the slower it is. Inside the critical loop, reduce abstractions (eg reveal lower-level methods that avoid extra code)

Spawn Threads for projects with a user interface, spawning a new thread to preform slower tasks makes the application feel more responsive, although isn't.

Pre-process You can generally trade space for speed. If there are calculations or other intense operations, see if you can precompute some of the information before you're in the critical loop.




  • 内联例程(消除呼叫/返回和参数推送)
  • 尝试用表查找消除测试/开关(如果它们更快)
  • 展开循环(Duff的设备)到刚好适合CPU高速缓存的位置
  • 本地化内存访问,以免打击缓存
  • 如果优化器尚未执行相关计算,请进行本地化
  • 如果优化器尚未这样做,则消除循环不变量



尽管我喜欢Mike Dunlavey的回答,但事实上这对于支持性例子来说确实是一个很好的答案,我认为它可以非常简单地表达为:

找出最先花费的时间,并理解原因。

这是时间的识别过程,可以帮助您了解您必须完善算法的位置。 这是我能找到的一个全面涵盖的语言不可知的答案,这个答案已经被认为是完全优化的。 同样假设你想要在速度上追求独立的架构。

所以虽然算法可能会被优化,但它的实现可能不会。 该标识可以让您知道哪个部分是哪个:算法或实现。 因此,无论哪个时间段,大多数人都是您的主要候选人。 但是既然你说你想挤出最后几个百分比,那么你可能还需要检查一些较小的部分,即你最初没有仔细检查过的部分。

最后,通过不同方式实现相同解决方案或可能不同算法的性能数据进行反复试验,可以获得有助于识别浪费时间和节省时间的洞察力。

HPH,asoudmove。




我认为这已经以不同的方式说过了。 但是当你处理一个处理器密集型算法时,你应该简化所有内部循环中的所有内容,而牺牲其他所有内容。

这对某些人来说可能是显而易见的,但无论我使用的语言如何,我都试图关注这些内容。 例如,如果您正在处理嵌套循环,并且您有机会将某些代码降低到某个级别,则可以在某些情况下大幅提高代码速度。 作为另一个例子,有些事情需要考虑,比如尽可能地使用整数而不是浮点变量,并且尽可能使用乘法而不是分割。 再次,这些是你最内在循环应该考虑的事情。

有时候你可能会发现在内部循环内的一个整数上执行数学运算的好处,然后将它缩小到一个浮点变量,之后你可以使用它。 这是在一个部分中牺牲速度以提高另一部分速度的一个例子,但在某些情况下,回报可能非常值得。




我大部分时间都在这个地方度过。 广泛的笔触是运行你的分析器并记录下来:

  • 缓存未命中 。 数据缓存是大多数程序中排名第一的来源。 通过重组违规数据结构来提高缓存命中率以获得更好的局部性; 打包结构和数字类型以消除浪费的字节(并因此浪费高速缓存提取); 尽可能预取数据以减少失速。
  • 加载打击商店 。 关于指针混叠的编译器假设,以及数据通过内存在已断开连接的寄存器集之间移动的情况可能导致某种病态行为,导致整个CPU管道在加载操作中清除。 寻找漂浮物,矢量和整数投入彼此并消除它们的地方。 宽松地使用__restrict来承诺编译器关于别名。
  • 微码操作 。 大多数处理器有一些不能流水线的操作,但是运行一个存储在ROM中的微小子程序。 PowerPC上的例子是整数乘法,除法和逐变量。 问题是整个管道在这个操作执行时停止。 尽量消除这些操作的使用,或者至少将它们分解为组成流水线的操作,这样您就可以在程序的其余部分执行时获得超标量调度的好处。
  • 分支错误预测 。 这些也会清空管道。 查找CPU在分支后花费大量时间重新填充管道的情况,并使用分支提示(如果可用)使其更频繁地正确预测。 或者更好的是,尽可能用条件移动替换分支, 特别是在浮点操作之后,因为它们的管道通常较深,并且在fcmp之后读取条件标志可导致失速。
  • 顺序浮点操作 。 制作这些SIMD。

还有一件事我喜欢做:

  • 设置您的编译器输出汇编列表,并查看它为代码中的热点函数发出的内容。 所有那些“一个好的编译器应该能够自动为你做的”巧妙的优化? 机会是你的实际编译器不会这样做。 我见过GCC发布真正的WTF代码。



Very difficult to give a generic answer to this question. It really depends on your problem domain and technical implementation. A general technique that is fairly language neutral: Identify code hotspots that cannot be eliminated, and hand-optimize assembler code.




Related