[SOLVED] Removing mutability without losing speed

Issue

I have a function like this:

fun randomWalk(numSteps: Int): Int {
    var n = 0
    repeat(numSteps) { n += (-1 + 2 * Random.nextInt(2)) }
    return n.absoluteValue
}

This works fine, except that it uses a mutable variable, and I would like to make everything immutable when possible, for better safety and readability. So I came up with an equivalent version that doesn’t use any mutable variables:

fun randomWalk_seq(numSteps: Int): Int =
    generateSequence(0) { it + (-1 + 2 * Random.nextInt(2)) }
        .elementAt(numSteps)
        .absoluteValue

This also works fine and produces the same results, but it takes 3 times longer.

I used the following way to measure it:

@OptIn(ExperimentalTime::class)
fun main() {
    val numSamples = 100000
    val numSteps = 15708
    repeat(5) {
        val randomWalkSamples: IntArray
        val duration = measureTime {
            randomWalkSamples = IntArray(numSamples) { randomWalk(numSteps) }
        }
        println(duration)
    }
}

I know it’s a bit hacky (I could have used JMH but this is just a quick test – at least I know that measureTime uses a monotonic clock). The results for the iterative (mutable) version:

2.965358406s
2.560777033s
2.554363661s
2.564279403s
2.608323586s

As expected, the first line shows it took a bit longer on the first run due to the warming up of the JIT, but the next 4 lines have fairly small variation.

After replacing randomWalk with randomWalk_seq:

6.636866719s
6.980840906s
6.993998111s
6.994038706s
7.018054467s

Somewhat surprisingly, I don’t see any warmup time – the first line is always lesser duration than the following 4 lines, every time I run this. And also, every time I run it, the duration keeps increasing, with line 5 always being the greatest duration.

Can someone explain the findings, and also is there any way of making this function not use any mutable variables but still have performance that is close to the mutable version?

Solution

Your solution is slower for two main reasons: boxing and the complexity of the iterator used by generateSequence()‘s Sequence implementation.

Boxing happens because a Sequence uses its types generically, so it cannot use primitive 32-bit Ints directly, but must wrap them in classes and unwrap them when retrieving the items.

You can see the complexity of the iterator by Ctrl+clicking the generateSequence function to view the source code.

@Михаил Нафталь’s suggestion is faster because it avoids the complex iterator of the sequence, but it still has boxing.

I tried writing an overload of sumOf that uses IntProgression directly instead of Iterable<T>, so it won’t use boxing, and that resulted in equivalent performance to your imperative code with the var. As you can see, it’s inline and when put together with the { -1 + 2 * Random.nextInt(2) } lambda suggested by @Михаил Нафталь, then the resulting compiled code will be equivalent to your imperative code.

inline fun IntProgression.sumOf(selector: (Int) -> Int): Int {
    var sum: Int = 0.toInt()
    for (element in this) {
        sum += selector(element)
    }
    return sum
}

Ultimately, I don’t think you’re buying yourself much in the way of code clarity by removing a single var in such a small function. I would say the sequence code is arguably harder to read. vars may add to code complexity in complex algorithms, but I don’t think they do in such simple algorithms, especially when there’s only one of them and it’s local to the function.

Answered By – Tenfour04

Answer Checked By – Katrina (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *