A loop with many iterations makes execution incredibly slow

Question

Execution time for this code is around 1 second:

start_time = Time.now

prev = 1
(1..1000).each do |i|
  (1..10000).each do |j|
    result = j * prev
    result = result + prev
    result = result - prev
    result = result / prev
    prev = j
  end
end

end_time = Time.now
printf('%f sec', end_time - start_time)

But when I use one loop with 10000000 iterations (instead of 2 loops, 1000 and 10000 iterations as written above), it becames much slower (around 4.5 seconds):

start_time = Time.now

prev = 1
(1..10000000).each do |j|
  result = j * prev
  result = result + prev
  result = result - prev
  result = result / prev
  prev = j
end

end_time = Time.now
printf('%f sec', end_time - start_time)

Why is it happening? The total iterations number is still the same.

Try to investigate values of `result` in each case. I think `10_000_000 * 9_999_999` is greater than `10_000 * 9_999`. — Sergii K, May 31 '16 at 09:16
I have 1.35sec for the first, and 1.24sec for the second code. The variable `result` do not grow excessively, because it is resetted each time. — T. Claverie, May 31 '16 at 09:17
So basically, iteration of the first code is 1.35 seconds and 1.24 seconds for the second? Odd. Try logging execution at smaller chunks, every 20% of the total for instance. The overall load should increase equally with a simple check, so it shouldn't visibly affect the test. — Sava Glodic, May 31 '16 at 09:22
Cannot reproduce: The first is `1.288465 sec`, the second `1.219005 sec` on my computer. What do you try to achieve with this examples? — spickermann, May 31 '16 at 09:29
@spickermann I just run these scripts in the console :) Ruby 2.3 x64, Windows 10 x64. Maybe the operating system causes the problem? — ozahorulia, May 31 '16 at 09:38
Second loop it's faster in my computer, MacBook Pro i7 SSD. with El Capitan — Trouner, May 31 '16 at 09:51
First taking 0.900022 sec and second one taking 0.873427 time om machine — Thorin, May 31 '16 at 10:06
Interesting, I can reproduce this as well on my Windows 7 (64 bit) using Ruby 2.1.5 but not on my Linux machine using the same version. The first script only takes 0.8 seconds as opposed to 3.8 for the second. — Nabeel, May 31 '16 at 10:20
Ah, after placing the answer I noticed you actually use a 64-bit version of ruby and OS. Still, could you try to determine the max integer number using [this answer](http://stackoverflow.com/a/535763/1544012) on your particular ruby/win combination? — Matouš Borák, May 31 '16 at 10:51
``machine_bytes => 8`` ``machine_bits => 64`` ``machine_max_signed => 9223372036854775807`` ``machine_max_unsigned => 18446744073709551615`` on both Linux/Windows. — Nabeel, May 31 '16 at 11:30
@BoraMa Here they are: machine_bytes: 8 machine_bits: 64 machine_max_signed: 9223372036854775807 machine_max_unsigned: 18446744073709551615 FIXNUM_MAX: 1073741823 FIXNUM_MIN: -1073741824 — ozahorulia, May 31 '16 at 11:50
@Hast then it means that while you have a 64-bit OS, the ruby itself still limits Fixnum numbers to 4 bytes (it is 8 bytes on my Linux system) and my answer is I believe actually correct. Please check my updated answer. — Matouš Borák, May 31 '16 at 14:14

score 2 · Accepted Answer · edited May 23 '17 at 11:44

The second example processes much larger numbers than the first one (as @Sergii K commented above). It is possible that the second sample code reaches the maximum Fixnum limit on your system. On a 32-bit system, the maximum signed integer is 2**(32-1) - 1 = 2147483647 which is much less than the maximum product j * prev in the second example (as opposed to max products in the first example). In a situation like this ruby has to convert the Fixnums to Bignums internally which is why the second sample code may be slower than the first one.

On a 64-bit system I would expect both samples to run approximately the same time because the biggest integers will never reach the Fixnum limit. That is why perhaps most other commenters did not see a big difference in the timings.

Update: if the max Fixnum number is only 1073741823, as commented by the OP above, then it must mean that while the OS itself is 64-bits and perhaps the installed ruby is also a 64-bit ruby, it still uses only 4 bytes to store Fixnum numbers (instead of 8 in truly 64-bit rubies). The max integer value is much less then needed in the second example so it indeed has to convert the higher numbers to Bignums and that is where the slowness of the second sample comes from.

You can check this yourself if you compare:

(2**(0.size * 8 -2) -1).class      # => Fixnum vs:
(2**(0.size * 8 -2) -1 + 1).class  # => should be Bignum

A loop with many iterations makes execution incredibly slow

1 Answers1