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




optimization language-agnostic (20)

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.

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

我们假设:

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

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

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

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


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.


分而治之

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


缓存! 一个便宜的方法(在编程人员的努力下)让几乎所有东西都变得更快,就是将缓存抽象层添加到程序的任何数据移动区域。 无论是I / O还是传递/创建对象或结构。 通常很容易将缓存添加到工厂类和读者/作者。

Sometimes the cache will not gain you much, but it's an easy method to just add caching all over and then disable it where it doesn't help. I've often found this to gain huge performance without having to micro-analyse the code.


I've spent some time working on optimising client/server business systems operating over low-bandwidth and long-latency networks (eg satellite, remote, offshore), and been able to achieve some dramatic performance improvements with a fairly repeatable process.

  • Measure : Start by understanding the network's underlying capacity and topology. Talking to the relevant networking people in the business, and make use of basic tools such as ping and traceroute to establish (at a minimum) the network latency from each client location, during typical operational periods. Next, take accurate time measurements of specific end user functions that display the problematic symptoms. Record all of these measurements, along with their locations, dates and times. Consider building end-user "network performance testing" functionality into your client application, allowing your power users to participate in the process of improvement; empowering them like this can have a huge psychological impact when you're dealing with users frustrated by a poorly performing system.

  • Analyze : Using any and all logging methods available to establish exactly what data is being transmitted and received during the execution of the affected operations. Ideally, your application can capture data transmitted and received by both the client and the server. If these include timestamps as well, even better. If sufficient logging isn't available (eg closed system, or inability to deploy modifications into a production environment), use a network sniffer and make sure you really understand what's going on at the network level.

  • Cache : Look for cases where static or infrequently changed data is being transmitted repetitively and consider an appropriate caching strategy. Typical examples include "pick list" values or other "reference entities", which can be surprisingly large in some business applications. In many cases, users can accept that they must restart or refresh the application to update infrequently updated data, especially if it can shave significant time from the display of commonly used user interface elements. Make sure you understand the real behaviour of the caching elements already deployed - many common caching methods (eg HTTP ETag) still require a network round-trip to ensure consistency, and where network latency is expensive, you may be able to avoid it altogether with a different caching approach.

  • Parallelise : Look for sequential transactions that don't logically need to be issued strictly sequentially, and rework the system to issue them in parallel. I dealt with one case where an end-to-end request had an inherent network delay of ~2s, which was not a problem for a single transaction, but when 6 sequential 2s round trips were required before the user regained control of the client application, it became a huge source of frustration. Discovering that these transactions were in fact independent allowed them to be executed in parallel, reducing the end-user delay to very close to the cost of a single round trip.

  • Combine : Where sequential requests must be executed sequentially, look for opportunities to combine them into a single more comprehensive request. Typical examples include creation of new entities, followed by requests to relate those entities to other existing entities.

  • Compress : Look for opportunities to leverage compression of the payload, either by replacing a textual form with a binary one, or using actual compression technology. Many modern (ie within a decade) technology stacks support this almost transparently, so make sure it's configured. I have often been surprised by the significant impact of compression where it seemed clear that the problem was fundamentally latency rather than bandwidth, discovering after the fact that it allowed the transaction to fit within a single packet or otherwise avoid packet loss and therefore have an outsize impact on performance.

  • Repeat : Go back to the beginning and re-measure your operations (at the same locations and times) with the improvements in place, record and report your results. As with all optimisation, some problems may have been solved exposing others that now dominate.

In the steps above, I focus on the application related optimisation process, but of course you must ensure the underlying network itself is configured in the most efficient manner to support your application too. Engage the networking specialists in the business and determine if they're able to apply capacity improvements, QoS, network compression, or other techniques to address the problem. Usually, they will not understand your application's needs, so it's important that you're equipped (after the Analyse step) to discuss it with them, and also to make the business case for any costs you're going to be asking them to incur. I've encountered cases where erroneous network configuration caused the applications data to be transmitted over a slow satellite link rather than an overland link, simply because it was using a TCP port that was not "well known" by the networking specialists; obviously rectifying a problem like this can have a dramatic impact on performance, with no software code or configuration changes necessary at all.


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?

Last few % is a very CPU and application dependent thing....

  • cache architectures differ, some chips have on-chip RAM you can map directly, ARM's (sometimes) have a vector unit, SH4's a useful matrix opcode. Is there a GPU - maybe a shader is the way to go. TMS320 's are very sensitive to branches within loops (so separate loops and move conditions outside if possible).

The list goes on.... But these sorts of things really are the last resort...

Build for x86, and run Valgrind /Cachegrind against the code for proper performance profiling. Or Texas Instruments' CCStudio has a sweet profiler. Then you'll really know where to focus...


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

The google way is one option "Cache it.. Whenever possible don't touch the disk"


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.


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

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

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

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

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

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

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


好的,你正在将问题定义为看起来没有太大改进空间的地方。 根据我的经验,这是相当罕见的。 我在1993年11月的一篇Dr. Dobbs的文章中试图解释这一点,从一个没有明显浪费的传统精心设计的非平凡程序开始,并通过一系列的优化,直到它的挂钟时间从48秒到1.1秒,源代码大小减少了4倍。我的诊断工具是这样的 。 变化的顺序是这样的:

  • 发现的第一个问题是使用了列表集群(现在称为“迭代器”和“容器类”)占了一半以上的时间。 这些被相当简单的代码所取代,时间缩短到20秒。

  • 现在最大的接受者是更多的名单建设。 作为一个百分比,之前并没有那么大,但现在是因为更大的问题被删除了。 我找到了一种加快速度的方法,时间下降到17秒。

  • 现在很难找到明显的罪魁祸首,但是我可以做一些小事情,时间下降到13秒。

现在我似乎碰壁了。 样品告诉我它到底在做什么,但我似乎无法找到任何可以改进的地方。 然后,我会回顾一下程序的基本设计,以及它的交易驱动结构,并询问它所做的所有列表搜索是否实际上是由问题的要求来确定的。

然后我重新进行了一次重新设计,其中程序代码实际上是通过一组较小的源代码生成的(通过预处理器宏),并且程序员并不是经常搞清楚程序员知道的事情是否可预测。 换句话说,不要“解释”要做的事情的顺序,“编译”它。

  • 重新设计完成后,将源代码缩小4倍,时间缩短为10秒。

现在,因为它变得如此之快,所以很难抽样,所以我给它做了10倍的工作,但以下时间是基于原始工作量的。

  • 更多的诊断表明它花费时间在队列管理上。 内嵌这些将时间缩短到7秒。

  • 现在一个很大的接受者是我一直在做的诊断印刷。 冲洗 - 4秒。

  • 现在最大的接受者是对malloc的 免费调用。 回收对象 - 2.6秒。

  • 继续抽样,我仍然发现并非严格需要的操作--1.1秒。

总加速因数:43.6

现在没有两个程序是相同的,但在非玩具软件中,我总是看到这样的进展。 首先你得到简单的东西,然后更难,直到你达到收益递减点。 然后,您获得的洞察力很可能会导致重新设计,开始新一轮加速,直到您再次获得收益递减。 现在,这个问题可能会让人怀疑++ii++for(;;)while(1)是否更快:我经常在SO上看到的问题类型。

PS可能会奇怪为什么我没有使用分析器。 答案是几乎每个这些“问题”都是一个函数调用站点,这些堆栈示例是精确定位的。 即使在今天,Profiler也只是几乎没有想到声明和调用指令比定位更重要,并且比整个函数更容易修复。 实际上,我建立了一个分析器来做到这一点,但是对于代码正在做的一个真正的肮脏亲密来说,没有任何东西可以替代你的手指。 这不是一个问题,因为样本数量很少,因为没有发现的问题太小而容易漏掉。

补充:jerryjvl请求了一些例子。 这是第一个问题。 它由少量单独的代码行组成,共占用一半以上的时间:

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

这些使用列表集群ILST(类似于列表类)。 它们以通常的方式实施,“信息隐藏”意味着班级的用户不应该在乎他们如何实施。 当写这些行(大约800行代码)时,没有想到这些可能是一个“瓶颈”(我讨厌这个词)。 他们只是推荐的做事方式。 事后很容易说这些应该是可以避免的,但根据我的经验, 所有的性能问题都是这样的。 一般来说,尽量避免造成性能问题是件好事。 即使它们“应该被避免”(事后看来),找到并修复所创建的更好。 我希望能给出一点风味。

这是第二个问题,分为两行:

 /* ADD TASK TO TASK LIST */ 
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

这些是通过将项目附加到它们的末端来建立列表。 (修复的目的是收集数组中的项目,并一次构建所有的列表)。有趣的是,这些语句只花费了原始时间的3/48(即在调用堆栈上),所以它们不在事实上在一开始就是一个大问题。 然而,在消除第一个问题后,他们花费了3/20的时间,所以现在是“更大的鱼”。 总的来说,就是这样。

我可能会补充说这个项目是从我帮助过的一个真实项目中提炼出来的。 在那个项目中,性能问题更加剧烈(如同加速),例如在内部循环中调用数据库访问例程以查看任务是否完成。

增加参考文献:原始和重新设计的源代码可在www.ddj.com上找到,文件为9311.zip,文件为slug.asc和slug.zip。

编辑2011/11/26:现在有一个sourceforge项目包含了Visual C ++中的源代码,并详细介绍了它是如何调整的。 它仅经过上述情景的前半部分,并且不遵循完全相同的顺序,但仍然得到2-3个数量级的加速。


建议:

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

当你无法再提高性能时 - 看看你是否能改善感知性能。

您可能无法更快地制作fooCalc算法,但通常有多种方法可以让您的应用程序看起来更能响应用户。

几个例子:

  • 预测用户将要求什么,然后开始工作
  • 在他们进来时显示结果,而不是一次结束
  • 准确的进度表

这些不会让你的程序更快,但它可能会让你的用户更快乐。


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

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

还有一件事我喜欢做:

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

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

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

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


更多建议:

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

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

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

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


由于许多性能问题涉及数据库问题,因此在调整查询和存储过程时,我会给你一些具体的东西。

避免在大多数数据库中使用游标。 避免循环。 大多数情况下,数据访问应该基于设置,而不是记录处理记录。 这包括当您想要一次插入1,000,000条记录时不重复使用单个记录存储过程。

切勿使用select *,只返回实际需要的字段。 如果连接字段将重复发生,并且因此会在服务器和网络上造成不必要的负载,那么这是尤其如此。

避免使用相关的子查询。 使用连接(尽可能包括对派生表的连接)(我知道Microsoft SQL Server的确如此,但在使用不同的后端时测试建议)。

指数,指数,指数。 如果适用于您的数据库,请更新这些统计信息。

使查询sargable 。 意思是避免使用索引无法使用的东西,例如在连接的like子句或函数的第一个字符中使用通配符,或者作为where语句的左侧部分。

使用正确的数据类型。 在日期字段上进行日期数学比在必须尝试将字符串数据类型转换为日期数据类型后执行计算要快。

切勿将任何类型的回路放入触发器!

大多数数据库都有办法检查查询执行的方式。 在Microsoft SQL Server中,这被称为执行计划。 首先检查那些问题区域在哪里。

考虑查询的运行频率以及运行需要多长时间才能确定需要优化的内容。 有时,您可以通过对每天运行数百万次的查询进行轻微调整来获得更多的性能,而不是从每月只运行一次的long_running查询中清除时间。

使用某种分析器工具来查明真正发送到数据库和从数据库发送的内容。 我可以记得过去的一次,我们无法弄清楚当存储过程很快时,为什么页面加载非常缓慢,并通过分析发现网页要求查询很多次而不是一次。

分析器还将帮助您查找谁阻止了谁。 由于来自其他查询的锁定,一些单独运行时快速执行的查询可能会变得非常慢。


  • 你在运行什么硬件? 你可以使用平台特定的优化(如矢量化)吗?
  • 你能得到一个更好的编译器吗? 从GCC切换到英特尔?
  • 你可以让你的算法并行运行吗?
  • 您可以通过重新组织数据来减少缓存遗漏吗?
  • 你可以禁用断言?
  • 针对您的编译器和平台进行微型优化。 以“在一个if / else中”的风格,首先提出最常见的陈述“

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




language-agnostic