"Branch Predictions" 和高级语言中的马尔可夫链
"Branch Predictions" and Markov Chain in High-Level Languages
一些函数使用分支预测系统，可以更快地计算某些数据结构，例如在包含 if 语句函数的循环中使用排序数据比处理数据更快，而数据是未排序的（有关分支预测的更多信息，请参见以下奇妙的 post：Why is it faster to process a sorted array than an unsorted array?）。
我的问题很简单：C、Python、MATLAB、R 等高级编程语言是否使用马尔可夫链预测来提高某些计算的速度？
我不是专家，我才刚刚开始了解马尔可夫链，但在我看来，每个代码（主要是包含循环的代码）都有某种时间上可预测的随机事件，可用于加速计算。
示例 将是一个应用于矩阵的函数，该矩阵包含 1 到 200 之间的整数，其中 90% 的值小于 100，即 2 位数字。似乎自动 "pre-allocating" 基于具有 x 或 y 数字整数的概率的一定数量的位可以提高性能。
分支预测就是这样工作的吗？这会扩展到任何计算吗？
关于大整数
理论上，如果计算整数乘法实际上是位大小的递增函数，那是正确的。也就是说，如果整数乘法被实现为带有 if 语句的循环。然而，32 位整数的计算将是 'same' 成本作为当前 gen 64 位 CPU 上的 16 位整数或 64 位整数，因为它们将使用在硬件中实现的相同加法器门。在 Performance 32 bit vs. 64 bit arithmetic
可以找到更复杂的讨论
相反，如果您手动存储那些部分大小的值（例如位域、位向量），您将产生 额外的 间接费用。
假设现在我们讨论的是非常大的整数，想想 java.math.BigInteger。那么你说得对，你可以通过预先分配所述位数而不是从 1 个单元 ('digit') 开始并在执行操作时创建新的 'digits' 来获得性能优势。看看 OpenJDK Implementation of BigInteger.multiply(). That is exactly what they do in their multiply method. This idea is also, in some ways, related to the Pre-allocation performance tip for MATLAB 就知道了。当您可以轻松地预分配数组时，请不要在 OutOfBounds 上进行不必要的分支。
实践中
现在直接回答你的问题，语言是否利用了马尔可夫链，我相信不会。我见过的任何语言源（或引擎，就此而言）都没有维护真正的马尔可夫链。大多数高级语言在其上下文中都是通用的，因此状态预测会为任何类型的计算增加相当大的开销。回到 java.math.BigInteger 示例，仅分配数字总和几乎总是比使用存储状态的预测机制更快。它可能会在结果中节省内存，但不利于性能。 CPU 本身依赖于状态机（可以被认为是马尔可夫链）来执行预测优化，但这是因为它可以负担得起而不会造成明显的成本损失（参见 wiki on branch prediction or an example in java hardware array prefetching）。
话虽这么说，时间上可预测的事件 的想法是总体上提高性能的关键，应该加以利用；它不仅限于分支预测。数据组织对性能至关重要。示例包括 Generational Garbage Collection in .NET, Efficient Management of Particles in Particle FX and Web Server Predictive Prefetching。最后一个实际上利用马尔可夫预测器来确定将哪个页面预取到缓存中作为用户日志的函数。在智能数据组织的游戏引擎和运行时实现中可以找到许多其他示例，以击败分支预测或完全跳过它！
tldr;
在实际开发中，大多数优化依赖于对数据进行简化假设，而不是应用马尔可夫预测器。因此，如果您希望利用分支预测，请了解您的数据并妥善组织。这将改善您的预测，或者让您完全跳过它。使用预测器可能会花费您更多的开发和执行时间。如果您仍然觉得预测器可能有帮助，请维护一个简单的状态机并将其与原始解决方案进行基准测试。
一些函数使用分支预测系统，可以更快地计算某些数据结构，例如在包含 if 语句函数的循环中使用排序数据比处理数据更快，而数据是未排序的（有关分支预测的更多信息，请参见以下奇妙的 post：Why is it faster to process a sorted array than an unsorted array?）。
我的问题很简单：C、Python、MATLAB、R 等高级编程语言是否使用马尔可夫链预测来提高某些计算的速度？
我不是专家，我才刚刚开始了解马尔可夫链，但在我看来，每个代码（主要是包含循环的代码）都有某种时间上可预测的随机事件，可用于加速计算。
示例 将是一个应用于矩阵的函数，该矩阵包含 1 到 200 之间的整数，其中 90% 的值小于 100，即 2 位数字。似乎自动 "pre-allocating" 基于具有 x 或 y 数字整数的概率的一定数量的位可以提高性能。
分支预测就是这样工作的吗？这会扩展到任何计算吗？
关于大整数
理论上，如果计算整数乘法实际上是位大小的递增函数，那是正确的。也就是说，如果整数乘法被实现为带有 if 语句的循环。然而，32 位整数的计算将是 'same' 成本作为当前 gen 64 位 CPU 上的 16 位整数或 64 位整数，因为它们将使用在硬件中实现的相同加法器门。在 Performance 32 bit vs. 64 bit arithmetic
可以找到更复杂的讨论相反，如果您手动存储那些部分大小的值（例如位域、位向量），您将产生 额外的 间接费用。
假设现在我们讨论的是非常大的整数，想想 java.math.BigInteger。那么你说得对，你可以通过预先分配所述位数而不是从 1 个单元 ('digit') 开始并在执行操作时创建新的 'digits' 来获得性能优势。看看 OpenJDK Implementation of BigInteger.multiply(). That is exactly what they do in their multiply method. This idea is also, in some ways, related to the Pre-allocation performance tip for MATLAB 就知道了。当您可以轻松地预分配数组时，请不要在 OutOfBounds 上进行不必要的分支。
实践中
现在直接回答你的问题，语言是否利用了马尔可夫链，我相信不会。我见过的任何语言源（或引擎，就此而言）都没有维护真正的马尔可夫链。大多数高级语言在其上下文中都是通用的，因此状态预测会为任何类型的计算增加相当大的开销。回到 java.math.BigInteger 示例，仅分配数字总和几乎总是比使用存储状态的预测机制更快。它可能会在结果中节省内存，但不利于性能。 CPU 本身依赖于状态机（可以被认为是马尔可夫链）来执行预测优化，但这是因为它可以负担得起而不会造成明显的成本损失（参见 wiki on branch prediction or an example in java hardware array prefetching）。
话虽这么说，时间上可预测的事件 的想法是总体上提高性能的关键，应该加以利用；它不仅限于分支预测。数据组织对性能至关重要。示例包括 Generational Garbage Collection in .NET, Efficient Management of Particles in Particle FX and Web Server Predictive Prefetching。最后一个实际上利用马尔可夫预测器来确定将哪个页面预取到缓存中作为用户日志的函数。在智能数据组织的游戏引擎和运行时实现中可以找到许多其他示例，以击败分支预测或完全跳过它！
tldr;
在实际开发中，大多数优化依赖于对数据进行简化假设，而不是应用马尔可夫预测器。因此，如果您希望利用分支预测，请了解您的数据并妥善组织。这将改善您的预测，或者让您完全跳过它。使用预测器可能会花费您更多的开发和执行时间。如果您仍然觉得预测器可能有帮助，请维护一个简单的状态机并将其与原始解决方案进行基准测试。