GlueList – Fast New Java List Implementation | Hacker News Reader

GlueList – Fast New Java List Implementation

github.com

44 pointsertucetin35 comments

Iteration will be slower than Arraylist.

Just like LinkedList (which is even worse), there will be cache misses on jumps to new nodes.

Random access lookup will be (very slightly) slower as you determine which node to look inside.

This is hardly a new datastructure. Just one that's been thought of before and not standardized due to lack of compelling performance differentiation.

Curious if there are numbers showing how much slower.

Worrying about cache misses seems premature without value types in Java. The list elements are not physically embedded in the list, and accessing each one could easily result in a cache miss.

A second cache miss. That the language almost (1) forces the language implementation to be inefficient doesn't give those writing programs in the language to ignore further inefficiencies.

(1) A sufficiently smart compiler could, in some cases, convert a data structure that logically uses reference types into one that uses value types in the compiled code (I think that's highly hypothetical in this case, as it almost isn't worth spending time on for compiler writers, given that it will be possible very rarely)

I'm scepctical if I just read "fastest X". Fastest at what? Here it seems it is way faster at adding elements. But what about moving elements, sorting, searching, deleting? In most optimizations you get faster in one operation and slower in some others.

And if you decide to optimize one operation over the others some usecases for that would be great as well. The most expensive things I needed to do with lists were sorting. Having a list type that improves this operation over the others would be most reasonable for me.

Last but not least I think the List is such an old and often used data structure, it is very unlikely one can develop something a lot faster.

Seems like a java implementation of std::deque http://en.cppreference.com/w/cpp/container/deque

Yeah that seems like exactly what it is. I kinda feel bad because it seems like this person came up with the data structure and thought they were super smart for "inventing" it even though most people (should) already know about it...

Is this a unrolled linked list implementation? https://en.wikipedia.org/wiki/Unrolled_linked_list

It looks that way from looking at the README and skimming the code; I'd be interested to know if it differs somehow.

"Unrolled linked list, In this model, the maximum number of elements is 4 for each node." - wiki

According to the README, it only uses 36 nodes for 10 Million records, so I guess it is like Unrolled linked lists but with a higher limit of elements per node?

It's just a constant.

List starts with array which has 10 elements(default just like ArrayList) unless you say otherwise(new GlueList(capacity)).

You can say 'allocate me 10million elements' and there will be 1 node :)

There's nothing requiring that an unrolled linked list has a fixed number of elements per node. It's just easier to reason about the performance results by fixing the number. This looks like an unrolled linked list with variable elements per node, which allows it to do things like allocate a single node for an entire bulk add operation.

This is fine and dandy, until your list becomes heavily fragmented. Suddenly traversing your list becomes a series of expensive cache misses.

So it's not 'faster', it depends very much on the use case - like any data structure.

Does it actually matter that much in Java? In Java, a collection of objects is already a collection of pointers, so wouldn't we get a fair number of cache misses anyway? Or does the JVM have some cool mechanism to minimize those?

Some JVM implementations convert objects into value types if they are final POJOs e.g. Point with X/Y accessors, Azul does this I think, but most likely it won't work for list like structures.

With Java, and any other VM that doesn't specify an exact GC algorithm, it always depends.

IIRC the train algorithm used in some JVMs improves locality. Most GCs use a pointer-bump scheme anyways, leading to pretty good locality for objects that have been created together.

So yes, the JVM _may_ have some pretty cool mechanisms to minimize those. I would be also interested in G1s behavior and whether or not it improves locality somehow.

some thoughts:

remove and add worst case complexity is O(mn) ! that is terrible, linked list should be able to do inserts and removes in O(1).

the test of appending is faster. but is it? I would offer that it's likely java doing some more datatype and bounds checking in their implementations, which is inline with the marginal speedup and relatively linear growth complexity. furthermore there are resize effects that will happen periodically as big malloc+move events.

worse case complexity seems incorrect for worse case search and access. assuming bins, you'd have to traverse the bin as well, so access should be O(m+n) .

but what about a remove test, or an actual search test? this looks somewhat like a b-tree.

> linked list should be able to do inserts and removes in O(1).

That assumes you have a reference to the node, which isn't true in Java's LinkedList, as the nodes are encapsulated. The remove() operation in List either takes the object you want to remove (by equality) or an index. Both require an O(n) scan to find the node, then it can be removed in O(1).

You probably forgot that it's possible to remove current element via Iterator, which indeed gives us O(1) for LinkedList in best case. Removal from ArrayList is more expensive except the case when you remove the last element.

my thoughts exactly. removing where you need random access to elements to me always = array list. Things i iterate through and manipulate = linked list, otherwise every get() is an O(n).

You can always swap the current element with the last element and then delete the last element in an unordered list.

java.util.List is ordered by definition (first sentence in Javadoc, if you want to verify).

As cristaloleg pointed out [0], it's an unrolled linked list with variable node sizing. B-tree is, in some sense, an unrolled binary search tree, so that's why it looks familiar.

[0] https://news.ycombinator.com/item?id=12274657

What's old is new again:

http://javolution.org/

This library has been around forever, and extends the same concept to other collection types.

It seems this may have been done already: have you looked at Clojure data structures implementations? Most, e.g vector, use a 32-branching factor with constant access/upate time. Clojure data types are all accessible from Java. Check it out: http://clojure.org/reference/data_structures#Vectors

Bad title. Datastructures always come with trade offs. In this case Insertion Speed and memory efficiency vs iteration and random access Speed.

Why is everything in the root namespace? Have you used this library for any real-life project?

Try something like sort for a benchmark.

In addition to what everyone else has said, ArrayList may get faster with a Java update.

This makes me wish I could downvote things on HN. This is not new, nor is there any significant evidence that it's "fastest" (a term that doesn't really mean much without context anyway).

The benchmarks do not use caliper or jmh. This is _very_ important - microbenchmarks on the JVM rarely do what you think they do without extra work.

Using sun.misc.Unsafe to access array elements would make it much faster. Also ArrayList with preset size is faster for inserting elements.

Using sun.misc.Unsafe to access array elements would make it much faster.

sun.misc.Unsafe should not make any difference to performance here. OK, you skip bounds checks, but modern VMs are very good at optimising those away anyway.

Also ArrayList with preset size is faster for inserting elements.

Exactly what I was thinking. The only case this is really going to help is where you don't have an idea of what the size is going to be.

Decompression on byte[] is 3x faster with unsafe. I think modern JVMs are far from optimal.

Yes, that may be true for byte[], but there's no primitive types in play here. Java collections hold object types only.

Reply on news.ycombinator.com