[Very fast List/Deque to java.util?]

[Rodion Efremov]

ti 14.6.2022 klo 18.49 Rodion Efremov <coderodd3 at gmail.com> kirjoitti:

> Hi community,
>
> > 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.
>
> I suppose you are talking about an order statistic tree. If that is the
> case, I have one [1].
>
> Best regards,
> rodde
>
> [1] https://github.com/coderodde/OrderStatisticTree
>
>
> ma 13.6.2022 klo 15.00 John Hendrikx <john.hendrikx at gmail.com> kirjoitti:
>
>> 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
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20220614/a9e50ac3/attachment.htm>