[JMH results for IndexedLinkedList]

Jens Lideström jens at lidestrom.se
Mon Jul 11 15:10:43 UTC 2022


I think you are coming at this in the wrong way, Rodion. I am not a JDK contributor, but these are my thoughts on how this works.

The people that are responsible for the Java collections framework are well aware of the existence of alternative data structures such as finger trees. There are also a lot of various implementations of them available on the internet.

The code for these data structures is not the reason that they have not been added to Java. The reason is that adding more data structures makes the  standard library harder to learn for users and increases the maintenance burden for JDK developers. The benefits of the new data structure must outweigh these costs.

If you want to move forward with this I think you should create a JEP-style document with the following content:

* A description of the problem you think should be solved and why the current collection framework does not solve it.
* A list of concrete use cases for your contribution.
* An overview of the existing collection framework where you demonstrate how your collection would fill a hole.
* An overview of alternative data structures and implementations, where you argue that your collection solves the problem in the best way.

Adding a new data structure the the collections framework is a major change. There is a very small change that it will be done and it will not be done without careful evaluation. The code and the benchmarks is only a small part of that work.

BR,
Jens Lideström

On 2022-06-21 13:20, Rodion Efremov wrote:
> Hi,
> 
> Data structure: IndexedLinkedList <https://github.com/coderodde/IndexedLinkedList>
> Benchmark: IndexedLinkedListBenchmark <https://github.com/coderodde/IndexedLinkedListBenchmark>
> 
> Benchmark output: https://github.com/coderodde/indexedLinkedList/#benchmark-output <https://github.com/coderodde/indexedLinkedList/#benchmark-output>
> 
>  From the benchmark output, we can judge that IndexedLinkedList outperforms both java.util.LinkedList and the Apache Commons Collections TreeList. It, however, does not seem to supersede the java.util.ArrayList.
> 
> Basically, I would expect the IndexedLinkedList to beat the ArrayList where we have a lot of following operations:
> 
>   * addFirst(E)
>   * add(int, E)
>   * remove(int)
> 
> So, what do you think? I am getting anywhere with that?
> 
> Best regards,
> rodde


More information about the core-libs-dev mailing list