使用bignums的开销

Question

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

在fixnum或integer已经足够的地方使用bignums的开销有多小？它最多只能是多小的实现？什么样的实现可以达到最小的开销，以及它们会导致什么样的额外权衡？

如果我将我的语言默认放在bignums上，我可以期望在整体语言性能上得到什么样的结果？

Answer 1

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

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

Answer 2

您也许可以看看Lisp是如何做到这一点的。它几乎总是做完全正确的事情，并在必要时隐式地转换类型。它有固定数(“正常”整数)、大数、比率(表示为两个整数的集合)和浮点数(不同大小的浮点数)。只有浮点型才有精度误差，而且它们具有传染性，即一旦计算涉及浮点型，结果也是浮点型。“实用的通用Lisp”很好地描述了这种行为。

Answer 3

仔细想想..。我认为它根本不会有太多的性能冲击。

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

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

这为优化打开了一个机会，对于永远不会超过第一个bignum数字的bignum，您可以将其替换为超快的一bignum数字操作。

然后当需要第二个双数字时切换到n位算法。

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

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

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

附注：对不起，我忘了bignum-digit和bignum-base的术语是什么了