Musings on Kotlin Ranges

Here are a few interesting aspects of Kotlin ranges, some of which I've found to be less-than-intuitive.

Ranging on Empty

Pop quiz: What does the following code output?

(1..3).forEach(System.out::print)
(3..1).forEach(System.out::print)

If you think the answer is 123321, guess again. It only prints out 123.

That's because IntRange is defined by its minimum start and its maximum endInclusive values. In other words, when endInclusive < start, the range is empty.

The solution is to use a progression instead. A progression can be any arithmetic sequence, so it can go up or down. Here are two ways to make a decrementing progression:

(3 downTo 1).forEach(System.out::print)
(1..3).reversed().forEach(System.out::print)

Home on the Range

You can use ranges to easily determine inclusion:

fun inRange(target: Int) = target in 0..100

What's really neat is how the Kotlin compiler optimizes the above code. Instead of allocating an IntRange then using IntRange.contains(), it actually compiles to a simple if-statement. Here's how it looks in Java:

boolean inRange(int target) {
  return 0 <= target && target <= 100;
}

Pretty awesome!

This optimization extends to any conditional statement. Check out this awesome code a coworker wrote recently:

fun bestSizeMatch(target: Int) = when (target) {
  in 0..256 -> urlThumb
  in 256..800 -> urlSmall
  in 800..2048 -> urlRegular
  else -> urlRaw
}

Again, the above compiles to a series of simple conditionals. No allocations necessary!

Range Against The Machine

Given that the compiler can optimize ranges, which of the following range-based for-loops do you think is the most efficient?

// Option 1
for (i in 1..3) {
  System.out.print(i)
}

// Option 2
for (i in 1..3 step 1) {
  System.out.print(i)
}

// Option 3
(1..3).forEach(System.out::print)

Here's what happens for each:

Option 1 compiles down to a normal loop. It allocates a couple primitives and has a couple if-checks, but is otherwise fairly simple. The same compilation behavior is seen for simple decrementing progressions as well (e.g. 3 downTo 1).

Option 2 would seem to be just as good as option 1, but adding the step parameter makes Kotlin use a more complex set of logic that can handle any step value you might throw at it. It requires one extra object allocation and additional if-checks.

Option 3 has to create an IntRange, then get its Iterator and use that to while-loop over the numbers. That's two object allocations and a lot of function calls. It's the least efficient by far.

So: Option 1 is the most efficient.

It's important to realize that the Kotlin compiler can take advantage of certain situations and make optimizations, but you won't really know about it unless you use the bytecode viewer and/or decompile to Java to see what's really going on underneath the hood.

In case you're curious, here's what those three loops look like in Java. I've cleaned it up from what you would view in the decompiled bytecode, but they're essentially the same:

// Option 1
int i = 1;
byte end = 3;
if (i <= end) {
  while (true) {
    System.out.print(i);
    if (i == end) {
      break;
    }

    ++i;
  }
}

// Option 2
IntProgression progression = RangesKt.step((new IntRange(1, 3)), 1);
int i = progression.getFirst();
int last = progression.getLast();
int step = progression.getStep();
if (step > 0) {
  if (i > last) {
    return;
  }
} else if (i < last) {
  return;
}

while (true) {
  System.out.print(i);
  if (i == last) {
    return;
  }

  i += step;
}

// Option 3
Iterable range = new IntRange(1, 3);
IntIterator iterator = (IntIterator) range.iterator();
while (iterator.hasNext()) {
  int element = iterator.nextInt();
  System.out.print(element);
}