代码之家 › 专栏 › 技术社区 › PhABC

高级语言中的“分支预测”和马尔可夫链

branch-prediction markov-chains matlab performance python

PhABC · 技术社区 · 10 年前

一些函数使用分支预测系统,该系统允许对某些数据结构进行更快的计算,例如,在包含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位整数的概率自动“预分配”一定数量的位可以提高性能。

分支预测就是这样工作的吗?这是否适用于任何计算?

1 回复 | 直到 7 年前

Community CDub 4 年前

关于BigInteger

理论上,如果计算整数乘法实际上是位大小的增加函数,那么这是正确的。也就是说,if整数乘法被实现为带有if语句的循环。然而,32位整数的计算将与当前64位CPU上的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 最后一个实际上利用了马尔可夫预测器,以便根据用户日志来确定要预取到缓存中的页面。在智能数据组织的游戏引擎和运行时实现中,还有许多其他示例,以便击败分支预测,或者干脆跳过它!

太长,读不下去了

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