Ruby's Power Range

Once in the evening I ran a couple of basic lines of code in the irb and received the results I couldn’t believe! But then I realized… 😏

Boring Intro

Back in the days, when I wasn't familiar with Ruby but did climb the learning curve, I'd already heard, that programs which were written in this language usually took more time to execute comparing with any popular compiled language that had been taught in the university I studied. Moreover, the pragmatism of the language was being killed by academical tasks, solutions of which contained loops not necessarily coming from 0 to the end of an array, that made me end up with something like:

  (1..x.length - 2).times { |i| ... }
Thus, the only reason to use it for such tasks was the desire of learning the language (not the best way, I agree).

That time one company successfully adopted Ruby and started actively evangelizing it. Somehow, I appeared on their lectures and witnessed something unexplainable. One of the listeners joked about the performance and activated the Search & Destroy mode of the lector:

"What? Wait... stop... you're saying that Ruby is slow? That's bullshit! The only bottleneck is IO, other operations have the same performance as C"

Seems that I'll never understand the meaning of this phrase, no worries, but since I've been triggered by this already hazy recollection, why not just try it out and compare?

What about summing a range?

I opened irb, entered first lines of code I had in my head. What about calculating the sum of a range?

  (0..10000000000).sum
  => 50000000005000000000 # immediately!
Damn!

I've received the result instantly!!1 Shock content! Excuse me not even placing a disclaimer with a warning!

But a few seconds later I added a couple more zeros to the number and realized that practically constant time needed to sum up a range.

The first thought I had: ah, cool, seems like Range class has this optimized method defined. However, turned out that it's just an if in the Enumberable#sum yeah booooy

It doesn't matter as long as it does precisely what we expect it to do:

1. Check if the object is a range
if (RTEST(rb_range_values(obj, &beg, &end, &excl))) {
    if (!memo.block_given && !memo.float_value &&
            (FIXNUM_P(beg) || RB_TYPE_P(beg, T_BIGNUM)) &&
            (FIXNUM_P(end) || RB_TYPE_P(end, T_BIGNUM))) {
        return int_range_sum(beg, end, excl, memo.v);
    }
}
2. Use the formula that we all remember from school
int_range_sum(VALUE beg, VALUE end, int excl, VALUE init)
{
    if (excl) {
        if (FIXNUM_P(end))
            end = LONG2FIX(FIX2LONG(end) - 1);
        else
            end = rb_big_minus(end, LONG2FIX(1));
    }

    if (rb_int_ge(end, beg)) {
        VALUE a;
        a = rb_int_plus(rb_int_minus(end, beg), LONG2FIX(1));
        a = rb_int_mul(a, rb_int_plus(end, beg));
        a = rb_int_idiv(a, LONG2FIX(2));
        return rb_int_plus(init, a);
    }

    return init;
}
3. Profit


Previously I said that practically constant time is needed, but obviously, it takes more trivial operations to apply the formula of arithmetic progression to a bigger number. But it's nothing near as resource-intensive as iterating over a range with hundreds of billions of elements, as reduce(:+) would do.

Dig a little deeper

Nevertheless, a bunch of methods that exists in Enumerable have its optimized definition in Range:

But the most tricky part is that some methods doesn’t:

count

There is optimized Range#size as an alternative.

Range#count is going to bubble up to Enumerable#count and iterate the whole range, the rest is history. But count → int and count(item) → int callings could be optimized and count { |obj| block } → int case could fallback to Enumerable#count.

For instance, Range#last has a similar implementation with fallback to Array#last (but could avoid it as Range#first does).

minmax

Yea, there are Range#min and Range#max, but Range#minmax is going to call the Enumerable#minmax implementation.


Conclusion

Sure, there is a reason why a particular part of a library is implemented one way, but not another one. Following the logic above, plenty of methods, such as drop, sort, and uniq, could have an optimized counterpart in the Range class. But most of them either useless for a range or can be replaced by a composition of other methods with a small overhead. Therefore, such optimizations provide little or no benefit at the cost of a complication of the Standard Library.

But it's just useful to know the difference. For example, between Range#size, which executes instantaneously, and Range(Enumerable)#count, which will take forever to finish on a ridiculously large range 😅.