CPU 高效算法？
CPU efficient algorithms?
我相当涉足以性能为中心的编程。通常，我所学和了解的大多数技术都与节省 RAM 有关。
话虽如此，我最近在这里解决了这个问题
我被告知的地方：
it is usually the CPU that runs out of speed before memory is exhausted
我们做了一些测试，似乎 packing/unpacking 确实节省了 RAM，但肯定会降低性能。
但正如我所说，我所见过的大多数典型性能 'rules' 都与节省 RAM 有关。
例如，程序速度的主要主题之一是动态内存分配，它也关注 RAM 保护。
我想知道的是：是什么让代码 CPU 高效？像 C 这样的低级语言在 CPU 效率方面是否具有更大的灵活性？如果是，why/how?
为了简单起见，让我们排除对汇编语言的讨论，因为它们超出了这个问题的范围。
是什么让代码 CPU 高效？
代码中更少的指令、更少的分支和最少的变量使用导致更少的 cpu 资源使用。所有这些都可以通过为您的逻辑应用高效的算法并减少不必要的代码来有效地实现。尝试从需要更多时间访问的内存中减少更多 I/O。
像 C 这样的低级语言在 CPU 效率方面是否具有更大的灵活性？
CPU的工作只是执行指令，您只能在您的软件中控制以最小化指令。 CPU 效率与指令数量成正比。
C 旨在使用相对简单的编译器进行编译，提供对内存的低级访问，提供有效映射到机器指令的语言结构，并需要最少的 运行 时间支持。因此，C 对于以前使用汇编语言编写的许多应用程序非常有用，例如系统编程。
一般性问题需要一般性回答：
All optimization is an exercise in caching.
特别是在当今的多级缓存架构上。
当心愚蠢的想法，你需要做的就是将代码塞入一级指令缓存，并将所有数据塞入一级数据缓存，以便有效地计算 O(N2) 算法，因为随之而来的是一位天才，他通过在大型 table.
中使用 O(1) 查找进行繁重的工作来生活和呼吸练习
换句话说，RAM 和磁盘 space 很便宜。充分利用它们。
探查器
首先，当您超越明显的算法效率低下时，您希望自己找到一个不错的分析器。分析器有几个好处：
- 向您显示精确的测量值（时间花在哪里、缓存未命中、分支预测错误等）。
- 追寻最热门的热点往往会迅速加速您的学习过程和对微观层面瓶颈原因的直觉（例如：内存层次结构和分支）。
- 将使您成为更好的优先级排序者。它还会告诉您哪些代码不需要优化，这意味着您可以专注于其他指标，例如生产力（可维护性、安全性等）。
对我来说#2 实际上是一个很大的。在我手头有一个分析器之前，我并没有真正开始非常快速地学习很多这些东西。这有点像你可以通过从事一个实际的、规模庞大的项目并查找中间出现的东西来学习大量编程。同样地，当你追逐一个又一个热点并研究它存在的原因时，如果手头有分析器，学习微观效率和计算机体系结构往往会更容易。
内存优化
除此之外，算法复杂性之外的第一件事（这是关于可伸缩性而不是某种绝对的性能）可能是内存效率。
Caveat: this is going to be somewhat oversimplified and doesn't go into compiler design topics like register allocation and stack spills or even a very detailed description of the memory hierarchy.
机器和操作系统的工作方式建立在内存的分层形式中，从绝对最快但最小的内存（寄存器）到绝对最慢但最大的内存（磁盘）。
访问内存时，系统会将其从较慢的内存以较大的对齐块加载到较快的内存中。例如，操作系统可能会将辅助存储设备的内存以 4 KB 块的形式分页到物理内存 (DRAM)。
[4 kilobyte chunk][*4 kilobyte chunk][4 kilobyte chunk][...]
// '*' indicates the chunk that's loaded in.
当您请求访问对齐的 4 KB 块周围的任何虚拟内存时，系统将在该块中分页到 DRAM。然而我们还没有完成。通常，在我们可以做任何事情之前，我们必须从 DRAM 加载到 CPU 缓存中，它本身分为一个层次结构。在这些情况下，内存可能会加载到 64 字节对齐的缓存行块中，如下所示：
[64-byte chunk][64-byte chunk][*64-byte chunk][...]
...所以内存访问最终会以这种方式从 DRAM 加载到 CPU 缓存中。当您请求围绕这些 64 字节块之一访问 DRAM 中的内存时，整个 64 字节块将加载到 CPU 缓存中。
然后 CPU 缓存本身被划分为一个层次结构（尽管通常都使用相同的缓存行大小），并且内存向下移动到更快但更小的 CPU 缓存（最快为 L1)。最后但并非最不重要的一点是，在执行算术之类的操作之前，L1 缓存中的内存被加载到一个寄存器中，对于通用 CPU 寄存器，该寄存器的大小可能是 64 位。在那种情况下，我们最终将我们的 CPU 缓存内存布置在一个 64 字节的缓存行中：
[64 bits][64 bits][64 bits][*64 bits][64 bits][...]
因此，最终在找到最小和最快的内存之后，我们在寄存器上执行一些算术指令，然后通常将结果移回层次结构。
现在这有点过于简单化了，我以后可能会为此感到尴尬。然而要记住的是 CPU 从较慢、较大的区域获取内存到对齐块中较快、较小的区域。它通过连续的少数抓住记忆。这样做的希望是您最终会多次访问该内存块（spatial/temporal 局部性），然后它最终会被逐出。
内存优化
牢记这一点，要从代码中获得最大性能，通常需要先确定内存布局和访问的优先级（当然，除了算法和数据结构之外）。如果没有高效的内存访问，最快的算术指令也无济于事。
这里值得牢记的一件事是连续数组。连续排列并按顺序访问的数据非常适合这种内存层次结构。这是因为计算机可能会占用一大块旧的内存（页面、缓存行），然后我们依次遍历它并访问整个块，同时它在驱逐之前处于更快的内存形式。
在逐出之前使用数据
最坏的情况是当你最终加载一大块旧内存时只使用其中的一小部分，然后让系统在我们使用它的其余部分之前驱逐它。这种情况可以出现在链表和树之类的链接结构中（缺少内存分配器来为它们提供更连续的表示），我们可能最终会为节点周围的内存区域加载一大块内存，而只能访问节点内部的一个节点然后驱逐它。
另一种情况出现在托管语言中，其中每个用户定义的类型都必须单独分配（例如：通过垃圾收集器）但聚合到基于数组的列表结构中。在那种情况下，即使我们正在存储这些对象的数组，每个对象实际上都是通过指向内存中其他地方的引用（如指针）来表示的。
这可能是使用 C 或 C++ 等语言的最令人信服的理由之一。它们允许用户定义的类型被连续聚合以及在堆栈上分配（具有大量的时间局部性）。
TL;DR
如果您想了解有关这些主题的更多信息，我建议您调查参考地点。这篇文章也是必看的：http://lwn.net/Articles/250967/
最后但同样重要的是，如果允许我无耻地插入我花了很多时间回答的赏金问题：What is the most efficient way to represent small values in a struct?。
但无论如何，首先要做的是获取分析器并开始追踪热点。这是最快的学习方式，也是最高效的优化方式。
更新
Jenz 的精彩回答中的智慧建议也让我产生了加入免责声明的冲动，因为算法效率仍然是首要考虑的事情。我曾与那些整天谈论缓存效率和多线程的类型一起工作，同时处理最次优的算法，这是无效的优先级排序。作为一个明显的例子，微优化或并行化一百万个元素的冒泡排序远非有效。
在那些别无选择只能触及每个元素（无法低于线性复杂度）的顺序情况下，许多内存优化技术往往会立即提供帮助。例如，需要处理每个粒子的粒子模拟器，必须影响每个像素的图像处理算法，涉及大量矩阵的矩阵乘法。在这些情况下，无法通过算法跳过大部分工作并仍然获得相同的结果，因为我们必须处理每个元素。在那些时候，内存优化技术可以变得比并行化更有效，并为您提供更多的并行化。
然而，数据结构和算法的核心也存在内存效率问题。纯粹由于内存效率，数组的快速排序在实际场景中仍然倾向于击败合并排序。甚至在某些情况下，线性算法可能会击败线性算法，前提是前者的内存效率要高得多。
内存分配器
我之前提到过链接结构（如树和链接列表）的缓存不友好性，但这是假设每个节点都是针对通用分配器分配的（并且可能不是一次全部分配）。可以开始真正使像单链表这样的结构更适用的事情之一是使用内存分配器，它可以将其节点返回它们通常会缺乏的空间局部性。因此，有一些方法可以挖掘您的数据结构并利用内存分配器，并以这种方式提高它们的效率，而无需实际使用全新的分配器。
还有像展开列表这样的数据结构经常被忽视，因为它们在算法上没有链表的优势。然而，从内存效率的角度来看，它们提供了更大的好处，并且在我们有两个具有相似算法复杂性但内存布局截然不同的数据结构的场景中，赢家往往是内存布局和访问模式更高效的那个。展开的列表将元素数组而不是单个元素链接在一起，而且，空间局部性再次强烈支持基于连续数组的表示。
然而，几乎任何微优化都会降低代码的直接性和可维护性。因此，优化的关键通常是确定优先级，而这正是探查器至少可以在一定程度上帮助您进行检查的地方（从生产力的角度来看，探查器具有巨大的好处，可以向您展示不是 进行优化，否则您可能会想尝试）。
只要一种语言有相当不错的编译器，它生成的代码应该与其他语言大致相同。
不同语言的问题是它们会诱使您做一些花费额外时间的事情。
就像 C++ 诱惑你使用 new 因为它太简单了，
并且有各种各样的容器 类 可以很容易地做一些花哨的事情。
如果您使用 C 语言工作，那么做一些花哨的事情会更麻烦，所以猜猜看 - 您不这样做（除非您真的必须这样做）并且您不会为性能付出代价。
人们很容易认为高级语言的所有优秀功能都是免费的，或者至多可以忽略不计，
但实际上它们可以相互相乘，如this example shows。
您仍然可以使用高级语言，但如果您知道如何进行性能调优，则无需为您不需要的东西付费就可以从它们的高级功能中获益。
我相当涉足以性能为中心的编程。通常，我所学和了解的大多数技术都与节省 RAM 有关。
话虽如此，我最近在这里解决了这个问题
我被告知的地方：
it is usually the CPU that runs out of speed before memory is exhausted
我们做了一些测试，似乎 packing/unpacking 确实节省了 RAM，但肯定会降低性能。
但正如我所说，我所见过的大多数典型性能 'rules' 都与节省 RAM 有关。
例如，程序速度的主要主题之一是动态内存分配，它也关注 RAM 保护。
我想知道的是：是什么让代码 CPU 高效？像 C 这样的低级语言在 CPU 效率方面是否具有更大的灵活性？如果是，why/how?
为了简单起见，让我们排除对汇编语言的讨论，因为它们超出了这个问题的范围。
是什么让代码 CPU 高效？
代码中更少的指令、更少的分支和最少的变量使用导致更少的 cpu 资源使用。所有这些都可以通过为您的逻辑应用高效的算法并减少不必要的代码来有效地实现。尝试从需要更多时间访问的内存中减少更多 I/O。
像 C 这样的低级语言在 CPU 效率方面是否具有更大的灵活性？
CPU的工作只是执行指令，您只能在您的软件中控制以最小化指令。 CPU 效率与指令数量成正比。 C 旨在使用相对简单的编译器进行编译，提供对内存的低级访问，提供有效映射到机器指令的语言结构，并需要最少的 运行 时间支持。因此，C 对于以前使用汇编语言编写的许多应用程序非常有用，例如系统编程。
一般性问题需要一般性回答：
All optimization is an exercise in caching.
特别是在当今的多级缓存架构上。
当心愚蠢的想法，你需要做的就是将代码塞入一级指令缓存，并将所有数据塞入一级数据缓存，以便有效地计算 O(N2) 算法，因为随之而来的是一位天才，他通过在大型 table.
中使用 O(1) 查找进行繁重的工作来生活和呼吸练习换句话说，RAM 和磁盘 space 很便宜。充分利用它们。
探查器
首先，当您超越明显的算法效率低下时，您希望自己找到一个不错的分析器。分析器有几个好处：
- 向您显示精确的测量值（时间花在哪里、缓存未命中、分支预测错误等）。
- 追寻最热门的热点往往会迅速加速您的学习过程和对微观层面瓶颈原因的直觉（例如：内存层次结构和分支）。
- 将使您成为更好的优先级排序者。它还会告诉您哪些代码不需要优化，这意味着您可以专注于其他指标，例如生产力（可维护性、安全性等）。
对我来说#2 实际上是一个很大的。在我手头有一个分析器之前，我并没有真正开始非常快速地学习很多这些东西。这有点像你可以通过从事一个实际的、规模庞大的项目并查找中间出现的东西来学习大量编程。同样地，当你追逐一个又一个热点并研究它存在的原因时，如果手头有分析器，学习微观效率和计算机体系结构往往会更容易。
内存优化
除此之外，算法复杂性之外的第一件事（这是关于可伸缩性而不是某种绝对的性能）可能是内存效率。
Caveat: this is going to be somewhat oversimplified and doesn't go into compiler design topics like register allocation and stack spills or even a very detailed description of the memory hierarchy.
机器和操作系统的工作方式建立在内存的分层形式中，从绝对最快但最小的内存（寄存器）到绝对最慢但最大的内存（磁盘）。
访问内存时，系统会将其从较慢的内存以较大的对齐块加载到较快的内存中。例如，操作系统可能会将辅助存储设备的内存以 4 KB 块的形式分页到物理内存 (DRAM)。
[4 kilobyte chunk][*4 kilobyte chunk][4 kilobyte chunk][...]
// '*' indicates the chunk that's loaded in.
当您请求访问对齐的 4 KB 块周围的任何虚拟内存时，系统将在该块中分页到 DRAM。然而我们还没有完成。通常，在我们可以做任何事情之前，我们必须从 DRAM 加载到 CPU 缓存中，它本身分为一个层次结构。在这些情况下，内存可能会加载到 64 字节对齐的缓存行块中，如下所示：
[64-byte chunk][64-byte chunk][*64-byte chunk][...]
...所以内存访问最终会以这种方式从 DRAM 加载到 CPU 缓存中。当您请求围绕这些 64 字节块之一访问 DRAM 中的内存时，整个 64 字节块将加载到 CPU 缓存中。
然后 CPU 缓存本身被划分为一个层次结构（尽管通常都使用相同的缓存行大小），并且内存向下移动到更快但更小的 CPU 缓存（最快为 L1)。最后但并非最不重要的一点是，在执行算术之类的操作之前，L1 缓存中的内存被加载到一个寄存器中，对于通用 CPU 寄存器，该寄存器的大小可能是 64 位。在那种情况下，我们最终将我们的 CPU 缓存内存布置在一个 64 字节的缓存行中：
[64 bits][64 bits][64 bits][*64 bits][64 bits][...]
因此，最终在找到最小和最快的内存之后，我们在寄存器上执行一些算术指令，然后通常将结果移回层次结构。
现在这有点过于简单化了，我以后可能会为此感到尴尬。然而要记住的是 CPU 从较慢、较大的区域获取内存到对齐块中较快、较小的区域。它通过连续的少数抓住记忆。这样做的希望是您最终会多次访问该内存块（spatial/temporal 局部性），然后它最终会被逐出。
内存优化
牢记这一点，要从代码中获得最大性能，通常需要先确定内存布局和访问的优先级（当然，除了算法和数据结构之外）。如果没有高效的内存访问，最快的算术指令也无济于事。
这里值得牢记的一件事是连续数组。连续排列并按顺序访问的数据非常适合这种内存层次结构。这是因为计算机可能会占用一大块旧的内存（页面、缓存行），然后我们依次遍历它并访问整个块，同时它在驱逐之前处于更快的内存形式。
在逐出之前使用数据
最坏的情况是当你最终加载一大块旧内存时只使用其中的一小部分，然后让系统在我们使用它的其余部分之前驱逐它。这种情况可以出现在链表和树之类的链接结构中（缺少内存分配器来为它们提供更连续的表示），我们可能最终会为节点周围的内存区域加载一大块内存，而只能访问节点内部的一个节点然后驱逐它。
另一种情况出现在托管语言中，其中每个用户定义的类型都必须单独分配（例如：通过垃圾收集器）但聚合到基于数组的列表结构中。在那种情况下，即使我们正在存储这些对象的数组，每个对象实际上都是通过指向内存中其他地方的引用（如指针）来表示的。
这可能是使用 C 或 C++ 等语言的最令人信服的理由之一。它们允许用户定义的类型被连续聚合以及在堆栈上分配（具有大量的时间局部性）。
TL;DR
如果您想了解有关这些主题的更多信息，我建议您调查参考地点。这篇文章也是必看的：http://lwn.net/Articles/250967/
最后但同样重要的是，如果允许我无耻地插入我花了很多时间回答的赏金问题：What is the most efficient way to represent small values in a struct?。
但无论如何，首先要做的是获取分析器并开始追踪热点。这是最快的学习方式，也是最高效的优化方式。
更新
Jenz 的精彩回答中的智慧建议也让我产生了加入免责声明的冲动，因为算法效率仍然是首要考虑的事情。我曾与那些整天谈论缓存效率和多线程的类型一起工作，同时处理最次优的算法，这是无效的优先级排序。作为一个明显的例子，微优化或并行化一百万个元素的冒泡排序远非有效。
在那些别无选择只能触及每个元素（无法低于线性复杂度）的顺序情况下，许多内存优化技术往往会立即提供帮助。例如，需要处理每个粒子的粒子模拟器，必须影响每个像素的图像处理算法，涉及大量矩阵的矩阵乘法。在这些情况下，无法通过算法跳过大部分工作并仍然获得相同的结果，因为我们必须处理每个元素。在那些时候，内存优化技术可以变得比并行化更有效，并为您提供更多的并行化。
然而，数据结构和算法的核心也存在内存效率问题。纯粹由于内存效率，数组的快速排序在实际场景中仍然倾向于击败合并排序。甚至在某些情况下，线性算法可能会击败线性算法，前提是前者的内存效率要高得多。
内存分配器
我之前提到过链接结构（如树和链接列表）的缓存不友好性，但这是假设每个节点都是针对通用分配器分配的（并且可能不是一次全部分配）。可以开始真正使像单链表这样的结构更适用的事情之一是使用内存分配器，它可以将其节点返回它们通常会缺乏的空间局部性。因此，有一些方法可以挖掘您的数据结构并利用内存分配器，并以这种方式提高它们的效率，而无需实际使用全新的分配器。
还有像展开列表这样的数据结构经常被忽视，因为它们在算法上没有链表的优势。然而，从内存效率的角度来看，它们提供了更大的好处，并且在我们有两个具有相似算法复杂性但内存布局截然不同的数据结构的场景中，赢家往往是内存布局和访问模式更高效的那个。展开的列表将元素数组而不是单个元素链接在一起，而且，空间局部性再次强烈支持基于连续数组的表示。
然而，几乎任何微优化都会降低代码的直接性和可维护性。因此，优化的关键通常是确定优先级，而这正是探查器至少可以在一定程度上帮助您进行检查的地方（从生产力的角度来看，探查器具有巨大的好处，可以向您展示不是 进行优化，否则您可能会想尝试）。
只要一种语言有相当不错的编译器，它生成的代码应该与其他语言大致相同。
不同语言的问题是它们会诱使您做一些花费额外时间的事情。
就像 C++ 诱惑你使用 new 因为它太简单了，
并且有各种各样的容器 类 可以很容易地做一些花哨的事情。
如果您使用 C 语言工作，那么做一些花哨的事情会更麻烦，所以猜猜看 - 您不这样做（除非您真的必须这样做）并且您不会为性能付出代价。
人们很容易认为高级语言的所有优秀功能都是免费的，或者至多可以忽略不计， 但实际上它们可以相互相乘，如this example shows。 您仍然可以使用高级语言，但如果您知道如何进行性能调优，则无需为您不需要的东西付费就可以从它们的高级功能中获益。