优化代码速度/因素优化
因素优化与复杂度优化相反：它们不会改变算法的整体复杂度，而是通过一定的因素使算法运行更快。举一个极端（但并不那么不切实际）的例子，我可以将程序运行时间的公式从 5 秒乘以 N^2（其中 N 是输入的长度）增加到 1 秒乘以 N^2。可以看出，我们通过一定的因素提高了优化，但仍然没有处理潜在的可扩展性问题。
因素优化值得你的时间吗？有些人似乎不这么认为。例如，埃里克·雷蒙德在《Unix 编程艺术》中谈到 这一点
其中一个是摩尔定律的指数效应——收集性能增益最聪明、最便宜，而且通常也是最快的途径，就是等待几个月，让目标硬件变得更强大。考虑到硬件和程序员时间之间的成本比率，几乎总是有比优化一个正在运行的系统更好的事情可做。
我们可以从数学上具体说明这一点。几乎永远不值得进行仅将资源使用降低一个常数因子的优化；更明智的做法是集中精力处理可以将平均运行时间或空间使用从 O(n^2) 降低到 O(n) 或 O(n log n)[112] 或类似地从更高阶降低到更低阶的情况。线性性能增益往往会被摩尔定律迅速吞噬[113]。
兰德尔·海德在 他的 OnLAMP.com 特色文章“为什么学习汇编语言仍然是一个好主意” 中提出了相反的观点
大多数情况下，你可以通过简单地改进现有算法的实现来实现非常好的性能提升。计算机科学家可能会争辩说，性能的常数改进不如将算法从 O(n^2) 性能提升到 O(n lg n) 性能那么好，但事实是，大多数情况下，在整个软件中应用的二三倍的常数因子改进，可以决定一个实际应用和一个运行速度过慢而无法舒适使用的应用之间的区别。而正是这种类型的优化，大多数现代程序员都没有什么经验。
那么，哪种观点是正确的？我倾向于认为雷蒙德是错的，而海德是对的。程序运行的因素仍然很重要，可以产生天壤之别。一些因素优化可能会带来巨大的收益，并将使你和你的用户更快乐。
雷蒙德也误以为，人们不能指望他们的最终用户升级他们的机器。此外，似乎我们已经 触及了基于半导体的 CPU 线性 CPU 速度增长的终点，我们不能指望线性代码随着新硬件而变得更快。高度并行化的代码可能会变得更快，但并行化并不总是可能的，或者不可取。
另一个说明性的故事 讲述了为什么不依赖摩尔定律来加速你的代码是一个好主意，是由吉尔博阿·达瓦拉发布到 Linux-IL 邮件列表中的。摘录自那里，同时为了连贯性而进行编辑
几年前，我在一家医疗软件开发公司工作。我在数据库开发方面工作。（我们有自己的专有面向对象的数据库）
我们的数据库非常酷；它可以在一台双奔腾 Pro 机器上处理医院级别的负载。（这与当时使用的大多数大型机相去甚远。）
我们的医疗软件方面使用 PowerBuilder（后来是 VB）来开发医疗应用程序。毫不夸张地说，医疗应用程序本身比它构建的医疗数据库慢得多，也重得多。当 50 个客户端可以在一台奔腾 I 90 MHz 带 32MB 内存的机器上轻松运行时，医疗应用程序在一台奔腾 I 166 MHz 带 64MB 内存的机器上运行非常缓慢！
而且每次我们把这个异常情况指出来时，医疗团队都声称，“新的机器即将推出，新的 CPU；到我们推出的时候，CPU 性能就不是问题了。”
你知道吗，现在，那个医疗软件在一台顶级奔腾 3/奔腾 4/AMD 芯片机器上运行比一条死狗还慢……什么也没改变。
我们是否应该投入时间去进行只为我们节省 5 秒（或更少）的优化？速度提高 5% 是否可取？有些人可能会对这些问题回答“不”，但答案并非那么简单。例如，比尔·雷蒙德写了一个 FreeCell 求解器，据说 在一台 733 MHz 的计算机上每小时可以求解 10,000,000 个牌局，并且他 证实了
我通过无数次 1% 的减少来实现我的快速运行时间。
根据我对 我自己求解器（它是开源的，并且有一个公开的版本控制库）的经验，我能够 随着时间的推移逐渐减少某个基准测试的运行时间，从 224 秒降至 94 秒（提高了 138%），仅仅是每次削减几秒，并进行许多不同的优化。在 一篇博文中，我进一步解释了我是如何通过应用许多小的优化来使“文件查找对象”Perl 5 模块的性能提升了四倍。
因此，不应排除即使是“小”优化也是微不足道的，也不应追求它们。只需四次 20% 的速度提升，就能将程序的速度提高一倍，虽然每次小的优化的收益并不十分显著，但这种提升会很快累积起来，并最终产生很大影响。另一方面，如果你不应用任何小的优化到你的代码中，而是等待彩虹尽头的宝藏，那么你的代码很可能只会像现在一样快（或者一样慢）。
如果我们有一个包含许多 C/C++ 结构体（包含可能具有不同数据类型的相邻数量元素的结构体）的集合，那么交换两个这样的结构体（例如为了重新排序或排序）将需要大量的内存访问。另一方面，如果我们管理指向这些结构体的指针，并且这些指针具有永久地址，那么交换两个 32 位或 64 位指针将相对便宜。
FreeCell Solver 的第一个 ANSI C 版本（0.2.0）分配了一个直接的大型 C 结构体数组，然后对其进行排序并进行二分搜索。在 0.4.0 版本中，实现了指向单独 malloc() 的结构体的指针数组，这带来了巨大的速度提升。这让我上了宝贵的一课，了解如何使用指针作为优化工具。
应用程序或其各个元素消耗的内存越多，缓存未命中次数就越多，页面交换次数就越多，数据需要不止一个缓存行的可能性就越大。因此，减小程序的大小通常会导致速度优势。
正如 在 Linux-IL 上的一篇文章中记录的那样，当 FreeCell Solver 从将卡片表示为 32 位值转换为使用 8 位八位字节表示卡片时，它变得快了很多。这很可能是由于交换次数减少、缓存未命中次数减少，以及更多卡片可以放入奔腾的 32 字节缓存行中。
LWN.net 上的“内联函数的代价”文章 也具有说明性。当 Linux 内核中的一个函数被取消内联时，内核的速度有所提升。原因是它所有内联实例在每个实例中占据了（相对）大量的内存，因此内核更大，并且出现了更多缓存未命中。
在阅读了这里的内容之后，你可能会认为这与常见的内存-速度权衡“真理”相矛盾。内存/速度权衡起源于理论计算机科学，在那里表明对于某些任务，可以通过增加所使用的内存的渐进数量来降低运行时间的渐进复杂度（反之亦然）。例如，我们有时可以通过将内存从 O(1) 增加到 O(N) 来将渐进运行时间从 O(N^2) 降低到 O(N)。
这很好，而且是正确的，但它并不与以下事实相矛盾：鉴于当代计算机硬件和操作系统的体系结构，程序使用的内存越少（只要算法的逻辑保持不变）——它运行的速度可能越快。这不是一个渐进的权衡，而是一个双赢的局面。
通过 并行化 任务，可以将其拆分为多个执行行（进程、线程、集群中不同计算机上的任务等），每个执行行将并行运行。结果，整个任务本身有望更快完成。并行化的一个好例子是对大量输入执行相同的耗时操作。如果我们为不同的进程分配输入的子集，那么它们很可能更快地完成它。
最近，由于多核 CPU 的发展，并行化在使代码运行得更快方面变得特别有吸引力。但是，应该注意的是，并行化仍然受到一些因素的限制，例如锁定、进程间数据的序列化和反序列化、上下文切换、CPU 和操作系统限制，以及任务数量往往超过可用处理器数量的事实。最重要的是，阿姆达尔定律 规定任务的串行部分（根据定义）不能并行化，因此限制了并行化的收益量。
在 Linux 内核中，struct 成员的顺序被排序，以便最重要的成员适合 Pentium 架构的 32 字节缓存行大小。这样，对 struct 的访问速度总体上会加快，因为它的所有成员大部分时间都保留在缓存行中，并且可以更快地访问。
另一种有用的优化被称为 写时复制。一个很好的例子是，当为编程语言实现虚拟机时，以及当我们将一个变量分配给另一个变量时。虽然我们可以在每次操作时复制变量的内容，但只需增加引用计数，并在其中一个变量发生变化之前等待它们分离，这样做会更便宜。
如果副本的内容很重要，那么写时复制可以节省大量的时间。
如果我们执行了许多代价高昂的查询，那么将常见发出的查询及其结果缓存到内存中很可能会提高程序的整体性能。缓存是在各种软件中实现的——从将最近访问的文件系统条目保存在缓存中的操作系统内核，到保存对它们发出的各种查询阶段的缓存的数据库服务器。
缓存有一个变体叫做 记忆化，在这种情况下，我们永远不会释放结果。可以证明，通过记忆化朴素的（树递归的）斐波那契数计算，实际上可以将它的复杂度从指数复杂度降低到线性复杂度。
应该注意的是，在许多情况下无法进行缓存或记忆化，例如，如果查询具有大多数类型的副作用。
这篇文章来自 Hackers-IL 阐述了为了提高性能而避免不必要地复制对象的理由。过度调用复制构造函数可能会对性能产生负面影响，而将调用次数降至最低限度可以提高性能。仅仅在内存中复制一个大型的连续区域多次，可能会对性能产生负面影响，消除它也可能会证明是有益的。
尽管之前提到了，但在减少内存消耗的背景下，在 C 或 C++ 等语言中内联函数通常会对性能产生积极影响。函数调用是代价高昂的操作，并且有很多开销，通过在每次使用函数时将代码插入到适当位置来避免函数调用，可以提高性能。内联函数的长度越短，它们带来的益处就越大，并且如果内联调用占用的内存小于不内联时使用的内存。
如果你不确定内联某个函数是会产生积极影响还是消极影响，那么就进行基准测试并观察结果。
Schwartzian 变换 是一种优化某些类型的基于比较的排序操作的方法。如果我们要比较的函数的键需要很长时间来计算（例如，如果它们需要访问硬盘），那么我们可以首先准备一个等效的数组，其中包含输入及其键的配对，然后根据键对配对进行排序，最后只从配对中过滤出原始输入。
应该注意的是，Schwartzian 变换实际上将计算键的次数的复杂度从 O(N*log(N)) 降低到 O(N)。但是，排序的总体复杂度仍然是 O(N*log(N))。
我认为，将所有已知的优化集中在一个地方，类似于 重构目录 和 波特兰模式库，是一个好主意。这将是一个列表，人们可以完整地阅读它，了解他们的代码可以在哪些地方进行改进，以及为了一般启发和促进交流。
截至撰写本文时，我不知道有类似的努力，这将非常有用。本节只涵盖了可能的优化策略的一小部分，只是为了让大家有所了解，并不旨在面面俱到。