language-features - 使用 bignums 的开销

Question

当涉及数字时，我遇到了关于是否在我的语言中使用 bignums 作为默认数据类型的问题。我自己对此进行了评估，并将其简化为便利和舒适与性能的问题。该问题的答案取决于未得到优化的程序对性能的影响有多大。

在固定数字或整数就足够的地方使用大数字的开销有多小？在最好的实现中它可以有多小？什么样的实现可以达到最小的开销，它们会导致什么样的额外权衡？

如果我将我的语言默认设置为 bignums，我可以期望对整体语言性能产生什么样的影响？

score 4 · Accepted Answer

你或许可以看看 Lisp 是如何做到的。它几乎总是会做完全正确的事情，并在必要时隐式转换类型。它有fixnums（“正常”整数）、bignums、比率（减少的真分数，表示为一组两个整数）和浮点数（不同大小）。只有浮点数有精度误差，并且具有传染性，即一旦计算涉及浮点数，结果也是浮点数。“Practical Common Lisp”很好地描述了这种行为。

score 3 · Accepted Answer

老实说，最好的答案是“试试看”。

显然 bignums 不能像原生类型那样高效，原生类型通常适合单个 CPU 寄存器，但每个应用程序都不同 - 如果您的应用程序不执行整数运算的整个负载，那么开销可以忽略不计。

score 2 · Accepted Answer

想一想……我认为它根本不会对性能产生太大影响。

因为 bignums 本质上会有一个非常大的基数，比如 65536 或更大的基数，这通常是传统固定数和整数的最大可能值。

我不知道你会将 bignum 的基数设置为多大，但如果你将它设置得足够大，以便当它用于代替 fixnums 和/或整数时，它永远不会超过它的第一个 bignum-digit 因此操作将与正常的 fixnums/int 几乎相同。

这为优化提供了机会，对于永远不会超过其第一个大数字的大数字，您可以用超快的大数字操作替换它们。

然后在需要第二个大数位时切换到 n 位算法。

这可以通过位标志和对所有算术运算的验证操作来实现，粗略地认为，您可以使用最高位来表示 bignum，如果数据块的最高位设置为 0，则将它们处理为如果它们是正常的 fixnum/ints 但如果它设置为 1，则将块解析为 bignum 结构并从那里使用 bignum 算法。

这应该避免来自简单循环迭代器变量的性能影响，我认为这是性能影响的第一个可能来源。

这只是我的粗略想法，一个建议，因为你应该比我更了解:-)

ps 抱歉，忘记了 bignum-digit 和 bignum-base 的技术术语是什么

score 0 · Accepted Answer

您的减少是正确的，但选择取决于您的语言的性能特征，我们不可能知道！

一旦你实现了你的语言，你就可以测量性能差异，并可能为程序员提供一个指令来选择默认值

score 0 · Accepted Answer

在您创建自己的基准之前，您永远不会知道实际的性能影响，因为结果会因语言、语言版本和 CPU 的不同而有所不同。除了 32 位整数使用的内存是 16 位整数的两倍这一明显事实外，没有独立于语言的方法来衡量这一点。

score 0 · Accepted Answer

在固定数字或整数就足够的地方使用大数字的开销有多小？显示小可以是最好的实现吗？

坏消息是，即使在最好的软件实现中，BigNum 也将比内置算法慢几个数量级（即从因子 10 到因子 1000）。

我没有确切的数字，但我认为在这种情况下，确切的数字不会有太大帮助：如果您需要大数字，请使用它们。如果没有，不要。如果您的语言默认使用它们（哪种语言使用？一些动态语言使用......），请考虑切换到另一种语言的劣势是否可以通过性能增益得到补偿（这应该很少）。

（大致可以翻译为：有很大的不同，但没关系。如果（且仅当）它很重要，请使用另一种语言，因为即使有最好的实现，这种语言显然也不太适合任务。）

score 0 · Accepted Answer

我完全怀疑它是否值得，除非它是非常特定于领域的。

首先想到的是整个程序中的所有小 for 循环，小迭代器变量都将是 bignums 吗？这太可怕了！

但是，如果您的语言相当实用……那么也许不是。

language-features - 使用 bignums 的开销

7 回答 7

Related

Reference