python - "Branch Predictions"和高级语言中的马尔可夫链

Question

某些函数使用分支预测系统，可以更快地计算某些数据结构，例如在包含 if 语句函数的循环中使用排序数据比处理速度更快，而数据未排序(有关分支预测的更多信息，请参阅以下精彩文章: Why is it faster to process a sorted array than an unsorted array? )。

我的问题相当简单:C、Python、MATLAB、R 等高级编程语言是否使用马尔可夫链预测来提高某些计算的速度？

我不是专家，我刚刚开始学习马尔可夫链，但在我看来，每个代码(主要是包含循环的代码)都具有某种可用于加速计算的时间可预测随机事件。

示例是应用于包含 1 到 200 之间整数的矩阵的函数，其中 90% 的值低于 100，即 2 位数字。似乎根据 x 或 y 位整数的概率自动“预分配”一定数量的位可以提高性能。

这就是分支预测的工作原理吗？这是否扩展到任何计算？

Answer 1

关于 BigInteger

理论上，如果计算整数乘法实际上是位大小的递增函数，那么这是正确的。也就是说，如果整数乘法被实现为带有 if 语句的循环。然而，在当前一代 64 位 CPU 上，32 位整数的计算与 16 位整数或 64 位整数的计算成本“相同”，因为它们将使用在硬件中实现的相同加法器门。更复杂的讨论可以在 Performance 32 bit vs. 64 bit arithmetic 找到。

相反，如果您手动执行此操作，则尝试实际存储这些部分大小的值(例如位字段、位向量)会产生额外开销成本。

假设现在我们正在讨论非常大的整数，想想java.math.BigInteger。那么您正确地说，您可以通过预先分配所述位数而不是从 1 个单位(“数字”)开始并在执行操作时创建新的“数字”来获得性能优势。看看 OpenJDK Implementation of BigInteger.multiply() 。这正是他们在 multiply 方法中所做的事情。这个想法在某些方面也与Pre-allocation performance tip for MATLAB相关。 。当您可以轻松地预分配数组时，不要在 OutOfBounds 上进行不必要的分支。

实践

现在直接回答你的问题，即语言是否利用马尔可夫链，我相信不会。我见过的任何语言源(或引擎，就此而言)都没有维护真正的马尔可夫链。大多数高级语言在其上下文中都是通用的，因此状态预测会给任何类型的计算增加相当大的开销。回到 java.math.BigInteger 示例，仅分配数字总和几乎总是比使用存储状态的预测机制更快。它可能会节省结果中的内存，但会降低性能。 CPU 本身依赖于状态机(可以被认为是马尔可夫链)来执行预测优化，但这是因为它可以负担得起，而不会造成明显的成本损失(请参阅 wiki on branch prediction 或 java hardware array prefetching 中的示例)。

话虽这么说，时间可预测事件的想法是提高总体性能的关键，值得加以利用；它不仅限于分支预测。数据的组织对于性能至关重要。示例包括Generational Garbage Collection in .NET , Efficient Management of Particles in Particle FX和Web Server Predictive Prefetching 。最后一个实际上利用马尔可夫预测器来确定将哪个页面预取到缓存中作为用户日志的函数。在智能数据组织的游戏引擎和运行时实现中可以找到许多其他示例，以便击败分支预测或完全跳过它!

tldr;

在实际开发中，大多数优化依赖于对数据进行简化假设，而不是应用马尔可夫预测器。因此，如果您希望利用分支预测，请了解您的数据并妥善组织它。这要么会改善你的预测，要么让你完全跳过它。使用预测器可能会花费更多的开发和执行时间。如果您仍然认为预测器可能有帮助，请维护一个简单的状态机并将其与简单的解决方案进行基准测试。