2

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

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

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

4

7 回答 7

4

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

于 2008-11-06T21:45:05.783 回答
3

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

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

于 2008-11-06T21:39:25.623 回答
2

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

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

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

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

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

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

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

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

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

于 2008-11-06T22:00:12.583 回答
0

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

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

于 2008-11-06T21:37:58.010 回答
0

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

于 2008-11-06T21:40:13.733 回答
0

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

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

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

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

于 2008-11-06T21:41:45.337 回答
0

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

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

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

于 2008-11-06T21:50:25.570 回答