dotimes taking very long for large inputs

(SBCL 2.2.0)

Playing around with the time function, I chanced upon an unexplainable happening with dotimes: after a certain limit, it takes forever to loop.

For example:

For 100000: (it barely registers)

(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

For 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

For 100000000 (note that it does not go 10x the previous value, rather ~5x)

(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

For 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

For 10000000000: explodes

(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.

Binary searching around the numbers, I found that the crossing over point is 4294967295, after which the loop never ends. Why does this happen so suddenly?

Solution

The one-word-but-slightly-wrong answer is 'bignums'. You are using a 32-bit SBCL I assume and 2^32 is 4294967296. For integers larger than that the implementation has to do arithmetic itself rather than using the machine to do it. Worse, integers this large are not machine integers and so, generally, need to be heap-allocated which in turn means the GC now has work to do.

The more-correct answer is that, in fact, 2^32-1 will almost certainly be larger than the most positive fixnum (you can check what this is by looking at most-positive-fixnum) in a 32-bit SBCL, but SBCL has support for using naked machine integers in some cases, and this is probably one.