Slow array access in ruby?

Question

I would like to present you this small (in this reduced form senseless) snippet of ruby code, which runs awfully slow:

MAX = 28123
M = 7000

abundant = Array.new(M) {|k| k}
checked = Array.new(MAX) {|k| false}

for a in 0..M-1 do
    for b in a..M-1 do
        checked[abundant[a] + abundant[b]] = true if abundant[a] + abundant[b] < MAX
    end
end

It takes about 10 seconds to execute, whereas the equivalent C++ code runs in about 0.2 secs:

int main()
{
    int abundant[M];
    bool checked[MAX];               

    for (int n = 0; n < M; n++)
        abundant[n] = n;
    for (int n = 0; n < MAX; n++)
        checked[n] = false;

    for (int a = 0; a < M; a++)
        for (int b = a; b < M; b++)
            if (abundant[a] + abundant[b] < MAX)
                checked[abundant[a] + abundant[b]] = true;
}

What am I doing wrong in the ruby implementation? I'm new to ruby - do I use any statement which is known to be thaaat slow?

Answer 1

Ruby is definitely a lot slower than C++, so there is not a lot you could do to make your code faster.

I believe the following code has the same behaviour and is a bit faster (±25%):

MAX = 28123
M = 7000

checked = Array.new(MAX) {|k| false}

(0..M - 1).each do |a|
  (a..M - 1).each do |b|
    checked[a + b] = true if a + b < MAX
  end
end

Using #each makes no difference, but making fewer array access does. I believe one of the reasons C++ is so much faster is because it makes no boundary check for array accesses while Ruby has to do it.

Could you change the C++ version to use std::vector and .at() to access the array and then compare with the Ruby version?