Why kotlin does not provide ArrayDeque implementation?

Language Design
1

A question eerily similar to Why kotlin does not provide LinkedList implementation? - #16 by Wasabi375.

The consideration to not provide a LinkedList implementation is that an ArrayDeque provides the same, but faster. This is true. From the JVM documentation on ArrayDeque:

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

I’d like to abstract sandeep549’s question, because I gather he probably doesn’t really care about LinkedList specifically, but rather an efficient Deque implementation.

ArrayDeque is very similar to ArrayList, but it has a different resizing strategy on the JVM, namely that ArrayDeque roughly increases its capacity by 2x, whereas ArrayList does it by 1.5x.

Granted, these performance gains do not matter in the grand scheme of computational complexity, but do matter in practice. I like the ArrayDeque implementation for my mobile application, because it aligns with power-of-two and uses strictly less array copies, resulting in less GC.

This is might be just an implementation detail, but I use a deque to signal that the code should optimize for sequential writes. I think the multi-platform story improves by adding it to stdlib.

2

We’re introducing an experimental common ArrayDeque implementation in Kotlin 1.3.70 (KT-21327).

However, note that its resizing strategy will be close to the ArrayList’s one, i.e. growing the buffer 1.5 times.

3

Cool!!! Thank you!

Can you tell me why the performance would be close to ArrayList? Wouldn’t Kotlin (at least on the JVM) alias it to Java’s ArrayDeque?

2 Likes
4

The main feature of ArrayDeque (compared to ArrayList) is that it supports cheap adding/deleting at the front of the list (with wraparound). It means that a start index is needed (and wrap support) so most operations are slightly less efficient (more steps in calculating array index). Unfortunately Java architecture makes this a bit harder to implement fast than in C/C++ (but the JVM may have an intrinsic). So in Java I would expect possibly a tiny decrease in speed for operations not (add at start/remove from start)

1 Like