Julia的BigInts似乎很慢

Question

我对Julia印象非常深刻,因为它在处理器密集的Euler Project问题上跑得比D快.#303如果有人有兴趣.

奇怪的是Julia的BigInts似乎有多缓慢.奇怪因为我看了他们的表现相当不错.

以下是使用Euler递推公式计算15k分区数的Julia程序.

function eu78()
  lim = 15000
  ps = zeros(BigInt, lim)

  function p(n)  #applies Euler recurrence formula
    if n < 0
      return BigInt(0)
    elseif n == 0
      return BigInt(1)
    elseif ps[n] > 0
      return ps[n]
    end
    s = BigInt(0)
    f = BigInt(-1)
    for k = 1 : n
      f *= -1
      t1 = (k * (3k - 1)) ÷ BigInt(2)
      t2 = (k * (3k + 1)) ÷ 2
      s += f * (p(n - t1) + p(n - t2))
    end
    ps[n] = s
  end

  for i = 1 : lim
    p(i)
  end
  println(ps[lim])
end

eu78()

在高达3分43秒的时间内运行以产生132位数的答案.

与pypy一起运行的等效Python代码仅需8秒.

我究竟做错了什么？

Answer 1

Julia目前BigInts相当缓慢.这是因为每个操作分配一个新的BigInt,而不是Python,其中所有整数都是BigInts,因此他们花了相当多的时间来确保基本操作很快.Python实际上使用混合方法,其中小整数值以内联方式表示,并且仅当值变得太大时才表示为BigInts.在Julia中绝对可以做到这一点,但是还没有人实现这一点 - 部分原因是标准Int值是机器整数,因此BigInts的性能并不重要.BigInt性能的真正提升将来自于将Julia的BigInt类型与GC集成,并允许小的BigInt值被分配堆栈 - 并且存在于寄存器中.然而,我们还没到那里.