I took a look.
I found a few results odd:
|com.github.coderodde.util.IndexedLinkedList.addLast in (ms): 8
java.util.LinkedList.addLast in (ms): 2 java.util.ArrayList.addLast in
(ms): 157 org.apache.commons.collections4.list.TreeList.addLast in (ms): 38|
Basically, ArrayList's performance (which should be O(1) in this case)
is surprising. Looking at the benchmark, it is calling
ArrayList#add(int, E) -- this method is not special cased for adding at
the end of the list (it will do a range check and call System#arrayCopy
in all cases).
|com.github.coderodde.util.IndexedLinkedList.stream() in (ms): 1
java.util.LinkedList.stream() in (ms): 20 java.util.ArrayList.stream()
in (ms): 16 org.apache.commons.collections4.list.TreeList.stream() in
(ms): 15|
This test isn't only measuring streaming (iteration?) but also
re-inserting all elements back into a List
(collect(Collectors.toList()). What I find odd is that the
IndexedLinkedList would perform much better here than ArrayList, given
that the time is probably dominated by the final collect, and not the
iteration itself. Is ArrayList#stream poorly optimized or is something
else going on?
A pure iteration test would be interesting to see.
I also ran the benchmark on my machine. The benchmark on Github doesn't
mention with what parameters it is run, and so when I run it I get quite
different results. The committed version of the benchmark seems to use
collections with a max size of 20 elements. The total time when I run
the benchmark favors TreeList more than any other:
--- Total time elapsed ---
com.github.coderodde.util.IndexedLinkedList in (ms): 207
java.util.LinkedList in (ms): 4248
java.util.ArrayList in (ms): 1799
org.apache.commons.collections4.list.TreeList in (ms): 159
That said, I think there might be a place for a new list implementation
in the JDK. One use case I've had in the past was for a list that is
always sorted but also allows index based access when displaying a
window into the list. A TreeMap satisfies the sorting criteria but
doesn't offer index access, while a plain ArrayList doesn't lend itself
well for doing sorted inserts/removals (locating the correct location is
trivial enough, but the actual insert or removal results in a
potentially large copy). Apache's TreeList is fairly good at this use case.
--John
On 13/06/2022 09:56, Rodion Efremov wrote:
Hello,
I have this List/Deque implementation [1] that (in a versatile benchmark)
runs much faster than ArrayList/LinkedList. Under mild assumptions, it
accesses an element in O(sqrt(N)) time.
Now, if all we want to do is to add at the tail and read via get(int
index), you are better of using java.util.ArrayList. If you wish to iterate
a list removing some elements, the way to go is to use java.util.LinkedList.
However,, if you deal with larger lists via many different operations
(addFirst/addLast/add(int, E)/get(int)/remove(int)/ettc. my
IndexedLinkedLiist will outperform both of them gracefully.
So, what do you think? Does it deserve to become a class candidate for
java.util?
[1]https://github.com/coderodde/IndexedLinkedList
