Learning Kotlin Programming

Speed up algorithm using Kotlin Channel Parallelize Computation

Get up to 7.5X speed up when compare to single thread processing

Here, I’m experimenting with Channel Fan-Out and Fan-In, parallelize the process to see what improvement gain I can get.

The simple computation algorithm I use

In order to experiment with the speed up, I execute a simple algorithm to ensure a set of randomly generated numbers are evenly distributed.

This can be achieved by I average out the random numbers generated for a random value between 0 and 1. If it generated 0.5, then the randomized value is evenly distributed.

The more iteration I get, the final result should be closer to 0.5.

The normal sequential process

For this I’m doing is accumulating many random numbers between 0 and 1, and average them out, to ensure the result is 0.5.

I repeat them REPEAT x REPEAT times as shown in the diagram above in a single process, with REPEAT = 5,000 till REPEAT = 100,000 times.

For REPEAT = 5,000, I get the value of 0.500150, and for the REPEAT = 100,000 times, I get the value of 0.500004. You can see the more iteration the closer it gets to 0.5.

In term of time used, I got between 0.4 seconds till 133 seconds for them respectively.

fun main() {
    val time = measureTimeMillis {
        var result = 0.0
        repeat(REPEAT) {
            result += accumulate()
        }

        result /= REPEAT
        println("Result $result")
    }
    println("Time Used sequential with $REPEAT : $time")
}

fun accumulate(): Double {
    var x = 0.0
    repeat(REPEAT) {
        x += (1..REPEAT).random()/REPEAT.toDouble()
    }
    return x / REPEAT
}

133 seconds is quite long. What if I parallelize it using Kotlin Channels… how much time I save?

Using Kotlin Channel Fan-Out and Fan-In

In reference to Kotlin Channel’s documentation, we can fan-out to multiple channels, and fan-in to collect the result from all the fan-outs.

To improve performance, I fan-outs to different threads and fan-in to another thread as below.

Here you can see that I fan-out and fan-in the processes with channels, using different thread.

I only do a REPEAT loop within the fan-out channels, and generate REPEAT channels to parallel processing them (instead of looping through them again REPEAT time)

fun parallel() = runBlocking<Unit> {
    val time = measureTimeMillis {
        val consumer = Channel<Double>()
        repeat(REPEAT) { accumulateProducer(consumer) } // FAN-OUT  
        accumulateConsumer(consumer).join()             // FAN-IN
    }
    println("Time Used parallel with $REPEAT : $time")
}

The FAN-OUT Channels code

fun CoroutineScope.accumulateProducer(consumer: Channel<Double>) =
    produce<Double>(Dispatchers.Default) {
        var x = 0.0
        repeat(REPEAT) {
            x += (1..REPEAT).random()/REPEAT.toDouble()
        }
        consumer.send(x / REPEAT)
    }

The FAN-IN Channel Code

fun CoroutineScope.accumulateConsumer(consumer: Channel<Double>) =
    launch(Dispatchers.Default) {
        var x = 0.0
        repeat(REPEAT) {
            x += consumer.receive()
        }
        consumer.close()

        val result = x / REPEAT
        println("Result $result")
    }

I also experiment this with REPEAT = 5,000 till REPEAT = 100,000 times.

For REPEAT = 5,000, I get the value of 0.500175, and for the REPEAT = 100,000 times, I get the value of 0.500006. You can see the more iteration the closer it gets to 0.5.

In term of time used, I got between 0.2 seconds till 17.9 seconds for them respectively.

Below is the graph result comparison between Sequential and Parallel (using Kotlin Channel), where for REPEAT = 100,000 iteration, I get 133 seconds for sequential process, and 17.9 seconds for parallel process. A total of about 7.5x faster!

In short, if we know how to parallelize some of the computational process, we can get pretty decent speed up for our execution, by just parallelize the similar processes one execute.