Skip to content

Instantly share code, notes, and snippets.

@louisgv
Last active August 15, 2017 22:04
Show Gist options
  • Save louisgv/7863d5aef9e7cc1641844a161819c151 to your computer and use it in GitHub Desktop.
Save louisgv/7863d5aef9e7cc1641844a161819c151 to your computer and use it in GitHub Desktop.
Benchmarking several way of traversing list in Kotlin
/**
* Created by L on 8/15/17.
*/
import java.util.*
/**
* Iterates provided by [callback] code [ITERATIONS]x[TEST_COUNT] times.
* Performs warming by iterating [ITERATIONS]x[WARM_COUNT] times.
*/
fun simpleMeasureTest(
ITERATIONS: Int = 1000,
TEST_COUNT: Int = 10,
WARM_COUNT: Int = 2,
callback: () -> Unit
) {
val results = ArrayList<Long>()
var totalTime = 0L
var t = 0
println("$PRINT_REFIX -> go")
while (++t <= TEST_COUNT + WARM_COUNT) {
val startTime = System.currentTimeMillis()
var i = 0
while (i++ < ITERATIONS)
callback()
if (t <= WARM_COUNT) {
println("$PRINT_REFIX Warming $t of $WARM_COUNT")
continue
}
val time = System.currentTimeMillis() - startTime
if(shouldPrint)
println(PRINT_REFIX + " " + time.toString() + "ms")
results.add(time)
totalTime += time
}
results.sort()
val average = totalTime / TEST_COUNT
val median = results[results.size / 2]
println("$PRINT_REFIX -> average=${average}ms / median=${median}ms")
}
/**
* Used to filter console messages easily
*/
private val PRINT_REFIX = "[TimeTest]"
val listTest = IntArray(100000) { Random().nextInt() }.asList()
val shouldPrint = !true
fun main(args: Array<String>) {
println("\n\tPLAIN FOR LOOP >>>")
simpleMeasureTest {
var sum = 0
var index = 0
for (value in listTest) {
sum += value* index++
}
if (shouldPrint) println(sum)
}
println("\n\tFOLD INDEXED >>>")
simpleMeasureTest {
var sum = listTest.foldIndexed(0) { i, accumulator, value -> accumulator + value * i }
if (shouldPrint) println(sum)
}
println("\n\tFOREACH INDEXED >>>")
simpleMeasureTest {
var sum: Int = 0
listTest.forEachIndexed { i, value -> sum += value * i }
if (shouldPrint) println(sum)
}
println("\n\tMAP INDEXED >>>")
simpleMeasureTest {
var sum: Int = 0
listTest.mapIndexed { i, value -> sum += value * i }
if (shouldPrint) println(sum)
}
println("\n\tREPEAT >>>")
simpleMeasureTest {
var sum: Int = 0
repeat(listTest.size) { i -> sum += listTest[i] * i }
if (shouldPrint) println(sum)
}
println("\n\tFOLD RIGHT INDEXED >>>")
simpleMeasureTest {
var sum = listTest.foldRightIndexed(0) { i, accumulator, value -> accumulator + value * i }
if (shouldPrint) println(sum)
}
println("\n\tREDUCE INDEXED >>>")
simpleMeasureTest {
var sum = listTest.reduceIndexed { i, accumulator, value -> if (i < 2) value else accumulator + value * i }
if (shouldPrint) println(sum)
}
}
@louisgv
Copy link
Author

louisgv commented Aug 15, 2017

Inconsistent result. Seems like the for loop with 10 test is faster:

	PLAIN FOR LOOP >>>
[TimeTest] -> go
-1973334640
[TimeTest] Warming 1 of 2
-1973334640
[TimeTest] Warming 2 of 2
-1973334640
[TimeTest] 98ms
-1973334640
[TimeTest] 46ms
-1973334640
[TimeTest] 54ms
-1973334640
[TimeTest] 58ms
-1973334640
[TimeTest] 126ms
-1973334640
[TimeTest] 90ms
-1973334640
[TimeTest] 45ms
-1973334640
[TimeTest] 49ms
-1973334640
[TimeTest] 60ms
-1973334640
[TimeTest] 79ms
[TimeTest] -> average=70ms / median=60ms

	FOLD INDEXED >>>
[TimeTest] -> go
-1973334640
[TimeTest] Warming 1 of 2
-1973334640
[TimeTest] Warming 2 of 2
-1973334640
[TimeTest] 132ms
-1973334640
[TimeTest] 124ms
-1973334640
[TimeTest] 231ms
-1973334640
[TimeTest] 91ms
-1973334640
[TimeTest] 52ms
-1973334640
[TimeTest] 55ms
-1973334640
[TimeTest] 75ms
-1973334640
[TimeTest] 80ms
-1973334640
[TimeTest] 69ms
-1973334640
[TimeTest] 88ms
[TimeTest] -> average=99ms / median=88ms

However, it is slower when there are more iteration:
image

@louisgv
Copy link
Author

louisgv commented Aug 15, 2017

When running with this:

        ITERATIONS: Int = 1,
        TEST_COUNT: Int = 10,
        WARM_COUNT: Int = 2,

Plain for loops surpassed fold

But with this:

        ITERATIONS: Int = 1000,
        TEST_COUNT: Int = 10,
        WARM_COUNT: Int = 2,

The output makes plain for loop looks worse:

	PLAIN FOR LOOP >>>
[TimeTest] -> go
[TimeTest] Warming 1 of 2
[TimeTest] Warming 2 of 2
[TimeTest] -> average=9379ms / median=9376ms

	FOLD INDEXED >>>
[TimeTest] -> go
[TimeTest] Warming 1 of 2
[TimeTest] Warming 2 of 2
[TimeTest] -> average=7595ms / median=7516ms

Why is this the case?... The underlying implementation of fold is the exact same for loop?...

@haze
Copy link

haze commented Aug 15, 2017

probably jvm optimizations specific to the bounds of fold.

/**
 * Created by L on 8/15/17.
 */

import java.util.*


/**
 * Iterates provided by [callback] code [ITERATIONS]x[TEST_COUNT] times.
 * Performs warming by iterating [ITERATIONS]x[WARM_COUNT] times.
 */
fun simpleMeasureTest(
        NAME: String = "TimeTest",
        ITERATIONS: Int = 1000,
        TEST_COUNT: Int = 10,
        WARM_COUNT: Int = 2,
        callback: () -> Unit
) {
    val results = ArrayList<Long>()
    var totalTime = 0L
    var t = 0

    println("$NAME -> go")

    while (++t <= TEST_COUNT + WARM_COUNT) {
        val startTime = System.currentTimeMillis()

        var i = 0
        while (i++ < ITERATIONS)
            callback()

        if (t <= WARM_COUNT) {
            println("$NAME Warming $t of $WARM_COUNT")
            continue
        }

        val time = System.currentTimeMillis() - startTime
        println("[$NAME] ${time}ms")

        results.add(time)
        totalTime += time
    }

    results.sort()

    val average = totalTime / TEST_COUNT
    val median = results[results.size / 2]

    println("[$NAME] -> average=${average}ms / median=${median}ms\n")
}

val listTest = IntArray(10000) { Random().nextInt() }.asList()

val shouldPrint = false

fun main(args: Array<String>) {

    simpleMeasureTest("forEachIndexed") {
        var sum = 0
        listTest.forEachIndexed { i, value -> sum += value * i }
        if (shouldPrint) println(sum)
    }

    simpleMeasureTest("mapIndexed") {
        var sum = 0
        listTest.mapIndexed { i, value -> sum += value * i }
        if (shouldPrint) println(sum)
    }

    simpleMeasureTest("repeat") {
        var sum = 0
        repeat(listTest.size) { i -> sum += listTest[i] * i }
        if (shouldPrint) println(sum)
    }

    simpleMeasureTest("foldIndexed") {
        var sum = listTest.foldIndexed(0) { i, accumulator, value -> accumulator + value * i }
        if (shouldPrint) println(sum)
    }

    simpleMeasureTest("fold") {
        var sum = listTest.fold(0, { a, i -> a + i} )
        if (shouldPrint) println(sum)
    }

    simpleMeasureTest("reduceIndexed") {
        var sum = listTest.reduceIndexed { i, accumulator, value -> if (i < 2) value else accumulator + value * i }
        if (shouldPrint) println(sum)
    }
}

I used this, as a little more verbose.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment