Problem Solving with Algorithms and Data Structures using Kotlin The Interactive Edition

The designers of Kotlin’s lists had many choices to make when they implemented them. Each of these choices could have an impact on how fast list operations perform. To help them make the right choices they looked at the ways that people would most commonly use a list, and they optimized their implementation of a list so that the most common operations were very fast. Of course they also tried to make the less common operations fast, but when a trade-off had to be made the performance of a less common operation was often sacrificed in favor of the more common operation.

Because different people might have different needs, Kotlin provides multiple list implementations, each of which offers somewhat different advantages. Kotlin also makes the distinction between a List which is immutable (unchangeable), as well as a MutableList, which can be modified. To keep the discussion here focused, we will be talking about the list implementation that you automatically get when you the mutableListOf or MutableList functions to create it. Internally, Kotlin refers to this mutable list as an ArrayList, because it is implemented inside using something called an array. It should be understood for the remainder of this section that when we talk about performance for a Kotlin list, we are talking about performance for this implementation in particular

¹

As of the time of this writing, Kotlin directly provides two implementations of mutable lists. The first, and the default, is the ArrayList. The second implementation is the ArrayDeque. The ArrayDeque is designed to have similar performance to an ArrayList, but allows for fast insertions and removals at either end. Additional implementations, such as LinkedList, can be imported from Java.

.

Two common operations for a list are indexing and assigning to an index position. Both of these operations in Kotlin take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list, it is \(O(1)\text{.}\)

Another very common programming task is to grow a list by using the add method. In Kotlin, this operation is \(O(n)\text{,}\) but in a very special way that we will examine later.

Here is a table of common lists operations and their Big O efficiency in Kotlin:

Let’s examine the remove method a bit more closely. The \(O(n)\) is a worst-case number. When we remove the first element in an list, all the remaining elements have to be moved left one position. If we remove the last element in a list, that is a best-case situation, and is \(O(1)\text{,}\) as no elements need to be moved.

Here’s the results of a program that removes the first item from a list 1000 times and compares that time to the time required to remove the last item 1000 times.

400000 items
Remove first time:  58.523178ms
Remove last time:   2.014451ms

200000 items
Remove first time:  32.113901ms
Remove last time:   2.012129ms

100000 items
Remove first time:  16.178345ms
Remove last time:   2.008027ms

As you see, the worst case time is proportional to the size of the list; the best case time is relatively unchanged.

Listing 2.6.2 is the program that we used, and there are some important things to note:

In line 13, we will run each test 25 times and average only the last 5 (in line 25), giving the cache time to stabilize as we saw in Listing 2.2.3.

We allocate the list once before the trials, in line 12, initializing each value to be the same as its index (so location 0 has a 0 in it, location 1 has a 1 in it, and so on). We need to reinitialize the list at every trial, because each trial removes 1000 items.

Line 13 introduces a very important concept. When Kotlin allocates and re-allocates memory, it is possible to have an area of memory that is no longer referred to. The runtime environment periodically goes through memory and collects these unused areas so they can be re-used. This process is called garbage collection, and it can take a fair amount of time. We don’t want this to happen while we are in our timing loop, so we call System.gc() to explicitly invoke garbage collection. This is not a sure-fire cure; the documentation for gc says: “There is no guarantee that this effort will recycle any particular number of unused objects, reclaim any particular amount of space, or complete at any particular time, if at all, before the method returns or ever.” Nonetheless, calling System.gc() is our best effort to avoid garbage collection at inopportune times.

Finally, because the inner loop repeats a thousand times, it is also important to point out that the list is decreasing in size by one each time through the loop. But even in the shortest list of 100,000 elements, this only reduces the overall size by \(1\%\) (and only \(0.25\%\) in the case of the 400,000 element list).