'Removing mutability without losing speed

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?

performancekotlinimmutability


Solution 1:[1]

Equivalent immutable one-liner is:

fun randomWalk2(numSteps: Int) = 
    (1..numSteps).sumOf { -1 + 2 * Random.nextInt(2) }.absoluteValue

Probably, even more performant would be to replace

enter image description here

with

enter image description here

so that you'll have one multiplication and n additions instead of n multiplications and (2*n-1) additions:

fun randomWalk3(numSteps: Int) = 
    (-numSteps + 2 * (1..numSteps).sumOf { Random.nextInt(2) }).absoluteValue

Update

As @Tenfour04 noted, there is no specific stdlib implementation for IntProgression.sumOf, so it's resolved to Iterable<T>.sumOf, which will add unnecessary overhead for int boxing. So, it's better to use IntArray here instead of IntProgression:

fun randomWalk4(numSteps: Int) = 
    (-numSteps + 2 * IntArray(numSteps).sumOf { Random.nextInt(2) }).absoluteValue

Still encourage you to check this all with JMH

Solution 2:[2]

I think:"Removing mutability without losing speed" is wrong title .because mutability thing comes to deal with the flow that program want to achieve . you are using var inside function.... and 100% this var will not ever change from outside this function and that is mutability concept. if we git rid off from var everywhere why we need it in programming ?

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2

Related Questions