大量输入的时间很长

Question

(SBCL 2.2.0)

在玩 time 函数时，我偶然发现 dotimes 发生了无法解释的事情：在一定的限制之后，它需要永远循环。

例如：

对于 100000：（勉强注册）

(time (dotimes (i 100000)
    (1+ 1)))

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  139,293 processor cycles
  0 bytes consed

对于 10000000:

(time (dotimes (i 10000000)
    (1+ 1)))
Evaluation took:
  0.010 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  0.00% CPU
  10,130,013 processor cycles
  0 bytes consed

对于 100000000（请注意，它不是之前值的 10 倍，而是 ~5 倍）

(time (dotimes (i 100000000)
    (1+ 1)))
Evaluation took:
  0.050 seconds of real time
  0.031250 seconds of total run time (0.031250 user, 0.000000 system)
  62.00% CPU
  84,139,662 processor cycles
  0 bytes consed

对于 1000000000：

(time (dotimes (i 1000000000)
    (1+ 1)))
Evaluation took:
  0.404 seconds of real time
  0.328125 seconds of total run time (0.328125 user, 0.000000 system)
  81.19% CPU
  942,942,189 processor cycles
  0 bytes consed

对于 10000000000：爆炸

(time (dotimes (i 10000000000)
    (1+ 1)))
Evaluation took:
  153.227 seconds of real time
  129.781250 seconds of total run time (128.781250 user, 1.000000 system)
  [ Run times consist of 11.651 seconds GC time, and 118.131 seconds non-GC time. ]
  84.70% CPU
  1 form interpreted
  370,698,869,379 processor cycles
  109,232,098,992 bytes consed
  
  before it was aborted by a non-local transfer of control.

二进制搜索数字，我发现交叉点是4294967295，之后循环永远不会结束。为什么会这么突然？

Answer 1

one-word-but-slightly-wrong 答案是 'bignums'。我假设您使用的是 32 位 SBCL，而 2^32 是 4294967296。对于大于该值的整数，实现必须自己进行算术运算，而不是使用机器来进行运算。更糟糕的是，这么大的整数不是机器整数，因此通常需要 heap-allocated，这反过来意味着 GC 现在有工作要做。

more-correct 的答案是，事实上，2^32-1 几乎肯定会大于最正的 fixnum（您可以通过查看 most-positive-fixnum 来检查这是什么）一个 32 位 SBCL，但 SBCL 在某些情况下支持使用裸机器整数，这可能是一个。

大量输入的时间很长

dotimes taking very long for large inputs

common-lisp

sbcl