Search code examples
kotlinarraylisttolist

I'm curious about the speed difference between Kotlin's toList and IntArray

I was curious to see what Kotlin's toList is returned in, so I tested it.

fun loop(i: Int){
    for(i in 0..i){}
}

fun main() {
    val list: List<Int> = (1..100000).toList()
    val arr =  IntArray(100000) { i -> i}

    println("list : ForLoop Time: " + measureNanoTime {
        for (i in list) { loop(i) }
    })

    println("list : ForEach Time: " + measureNanoTime {
        list.forEach { i -> loop(i) }
    })

    println("Array : ForLoop Time: " + measureNanoTime {
        for (i in arr) { loop(i) }
    })

    println("Array : ForEach Time: " + measureNanoTime {
        arr.forEach { i-> loop(i) }
    })
}

output :

enter image description here

When I looked up, toList was returned in the form of an Array, but I don't know why there is a lot of difference in speed. Is toList returned as a LinkedList?

I wonder.

Solution

  • As Tenfour04 points out, microbenchmarks like this are subject to so many influences from JVM warm-up, dynamic compilation and profiling, system and timing jitter, cache effects, and other confounding factors that they don't tell you very much at all.  Benchmarking small bits of code is notoriously difficult, so far better to use a framework which has done all the hard work for you.

    However, it seems fairly likely that one of the effects you're seeing here is that of boxing.

    An IntArray is an array of (primitive) integers.

    A List<Int> is a list (probably stored as an array) of references to Int objects, each of which holds a primitive integer.

    So the list needs to store not just an array, but also all the individual Int objects; as a result, it'll take much more memory — probably several times more.

    And while the array version does a simple linear scan through its memory (probably benefitting from memory caching), the list version will be accessing all the individual Int objects (which could be at unpredictable places in the heap) as well as scanning through its array of references, probably getting much less benefit from memory caching.

    If you wanted a fairer comparison, you'd probably find that an Array<Int> behaved much more like a List<Int>.  (This is not to recommend using an Array<Int> in general, of course — this question illustrates one good reason why not!)