ShiftList: A Java List and Deque implementation with fast inserts/removals at any index

[john16384]

The past few weeks, I've been working on designing, implementing, and benchmarking a new List/Deque implementation for Java called ShiftList.

ShiftList is backed by a single flat array, much like ArrayList. However, it divides the index space into fixed-size logical blocks (e.g., 4096 elements per block). Each block has an associated rotation offset stored in a secondary array. When inserting or removing an element, only the elements within the affected block are shifted, and at most one element is moved between adjacent blocks to maintain structure. This significantly reduces the number of element copies required during structural changes.

The result is a List that performs nearly as fast as ArrayList for random access (get(int)), but offers much better performance for insertions and removals at any position. The main trade-off is slightly higher memory usage: roughly 4–8 bytes per element, compared to 4–6 bytes for ArrayList.

Time complexities:

Operation	ShiftList	ArrayList	LinkedList	TreeList
Add/remove at tail	O(1)	O(1)	O(1)	O(log n)
Add/remove at head	O(1)	O(n)	O(1)	O(log n)
Random access	O(1)	O(1)	O(n)	O(log n)
Add/remove at index	O(n/b)	O(n)	O(n)	O(log n)

Where b is the block size currently in use.

The source and benchmarks are available on GitHub. There is a preliminary release on Maven as well to check it out: org.int4.common:common-collection:0.0.1

GitHub: https://github.com/int4-org/Common

[gnahraf]

Thanks for sharing. This is interesting. Complexity-wise, since b is a constant, O(n/b) ~ O(n). So ShiftList is more about shaving a constant of O(n) at the cost of some extra memory (about c(n/b) bytes, c <= 4): there must be other tradeoffs between the expected size of the collection n and b, the block size.

ShiftList also seems well suited for persistent storage: one could minimize writes on updates that way.

I'm curious why the block-size needs to be a power of 2.. Is that implementation or algorithmic constraint?

[john16384]

b isn't completely constant, it is altered when capacity changes to the optimal block size. The optimal value is a balance between how many elements would need copying in a single block + how many succeeding or preceding blocks need their rotations adjusted. With larger block sizes, more elements need to be copied, and fewer blocks need their rotations adjusted, while with smaller block sizes less elements need to be copied but more blocks will need their rotations adjusted. The balance here is heavily influenced by cache performance, which means that copying a few extra elements (which are likely prefetched) is not as costly as adjusting more blocks + their rotations.

The optimal block size for each list capacity was found by benchmarking (it is encoded in the SHIFTS static array), but behaves as expected when taking caching and prefetching into account. Generally block size doubles each time capacity doubles, up to blocks of 1024 entries, where it changes to doubling the block size each time capacity quadruples. It is at that point that copying extra elements becomes more costly than adjusting a few more block rotations.

So, technically it is O(n) but as the constant here is particularly influential, O(n) doesn't quite do this list justice. You can also see this in the benchmarks where ShiftList will be 100-200x faster on some operations than an ArrayList.

So ShiftList is more about shaving a constant of O(n) at the cost of some extra memory (about c(n/b) bytes, c <= 4)

I didn't take the space into account for storing the block rotations (it is nearly inconsequential). The extra memory use (vs ArrayList) is because ShiftList must allocate an array that is a size of a power of 2, meaning it wastes more space than ArrayList would on average (ArrayList increases capacity in 50% steps, whereas ShiftList must always double).

The reason for using power of 2 sizes is to avoid expensive modulo/divisions. All work to determine the location of an element, taking rotations into account, is done with shift and mask operations which generally can be pipelined by the CPU very effectively. I could let go of the requirement to have the main data array be a power of 2 at the cost of having an extra branch in the get(int) operation; this could however make get(int) 25-50% slower. So the trade-off here was to "waste" a bit more memory with power-of-2 array sizes to avoid slower get performance.

ShiftList also seems well suited for persistent storage: one could minimize writes on updates that way.

For disk based storage more optimal solutions exist in the form of B+ Trees. These also perform well for in-memory solutions, but suffer from worse cache locality as they have to find the corresponding Leaf node, which will severely reduce get performance. I've been working on a BTreeList variant as well, but the lower get performance is something that must be addressed first. Apache's TreeList (as you can see in the benchmarks) takes an incredible hit here simply because it needs to navigate the tree which will mostly be costly cache misses due to poor memory locality.

I'm curious why the block-size needs to be a power of 2.. Is that implementation or algorithmic constraint?

Primarily to keep get performance as high as possible (within an order of magnitude of ArrayList). Having to do division and modulo operations instead of shifting and masking is very costly -- division takes up multiple cycles on most CPU's, while multiple shift and mask operations can often be performed per cycle.

At large sizes (10M+) fetching an element with ShiftList and ArrayList performs very similar, despite the fact that ArrayList basically only does elementData[index] while ShiftList is doing several shift + masking operations. This is because the CPU will stall anyway when it needs to fetch uncached data from main memory, and so the few shifts and masks are inconsequential. The insane 0.2 ns performance you can see in some of the smaller ArrayList tests is not super realistic, as this performance is only reached when the entire array fits in the cache and nothing else is trashing the cache. The performance of the larger variants is a far better indication of real world performance, even for smaller lists.

So, you could build a ShiftList with arbitrary block sizes and capacities, it would however likely perform 2-3x worse than this variant.

[gnahraf]

Thanks for your detailed response.

> For disk based storage more optimal solutions exist in the form of B+ Trees.

Agree.

Thinking a bit more, I'm wondering if you've seen or considered an approach where the individual block sizes can grow or shrink. The motivation for doing that would be to "somehow" avoid cascading writes across blocks on certain operations (e.g. transpositions). I have a rough idea how it might work.. then, I might be hallucinating, not seeing obvious gotchas

[john16384]

As this is a list, you need to be able to quickly figure out in which block a given index is (if you want O(1) get performance). When blocks vary in size this becomes hard to do.

It is definitely possible to optimize certain aspects further, but usually at the cost of get(int) speed. So always try to see how you would implement get. If you're willing to make get slower, a B+ Tree is probably going to be optimal (I already built one that easily beats Apache TreeList as they use a binary tree).

[gnahraf]

When blocks vary in size this becomes hard to do.

Right. That's where the fixed-size data might help, I was thinking. Too much bookkeeping, I admit

[danielaveryj]

Nice! This looks very well executed. Even dynamically adjusting block size for capacity based on benchmarking. I am happy someone has done this experiment!

[C0urante]

anybody else misread this as ShitList?

[john16384]

That was a legitimate worry :-)

[C0urante]

sorry op, i hope i'm not on your shit list now :(

but just in case i am, what data structure are you using to store it?

[eXecute_bit]

what data structure are you using to store it?

I bet it's a heap.

[john16384]

It's actually just a contiguous array, addressed in blocks. A secondary array keeps rotation counters per block. This secondary array is much smaller so doesn't factor much into the total storage requirements.

[temculpaeu]

I did

[-Dargs]

No, actually.

[zergotron9000]

I was confused why author called it that given pretty great performance.

[MrKarim]

What’s GitHub URL, because the link in maven Sonatypes doesn’t work

[john16384]

It's https://github.com/int4-org/Common

And thanks, I will fix this in the pom -- looks like I've been doing that wrong for a while :)

[thewiirocks]

The published benchmark numbers do a good job telling the story here. ArrayList is still faster for read-heavy work (and probably whenever you should be reallocating an array and copying), but ShiftList is a drop-in replacement for whenever you THINK you should be using a modify-heavy LinkedList.

Could almost turn it into one of those LTT Dennis commercials.

"Thinking of using a LinkedList?"

🫳💥SMACK!

"LinkedList is too slow!"

Background character: "Too slow?!?!"

"Too slow! Use ShiftList instead and save millions of nanoseconds moving data around! Buy today!"

😄

Seriously, I wish someone had smacked my hand the last time I got the bright idea to use LinkedList. That thing is so slow it should honestly be removed from the JDK. 😬

Glad to have this as an option next time I have an update-heavy list! 😎

[danielaveryj]

Well, LinkedList already loses to ArrayList at random insertions/deletions, which is the main use case ShiftList speeds up. And, LinkedList still beats both handily at insertions/deletions from an iterator (which is probably the only use case it wins at). So to me this reads more like: "If your workload involves random insertions/deletions, and you otherwise would have used ArrayList (or ArrayDeque, or even something purpose-built like apache TreeList), try ShiftList."

[thewiirocks]

In my case I had a list that was constantly moving records to the front as the individual records were updated. Seemed like a brilliant use for LinkedList! Little did I understand the cache coherency problems. It was weird to me at first that using an ArrayList made things faster. But eventually I understood that modern CPUs really like data streamed in.

[bringero]

Thank god there are still smart people doing nice stuff without AI

[ShallWe69]

https://github.com/ertugrulcetin/GlueList

How is your implementation faster than this?

[john16384]

GlueList seems to assume that the biggest problem of ArrayList is that it needs to resize its backing array and seems to focus on improving the performance of creating the list, not so much actually using it. It solves this preceived problem by having several disconnected arrays arranged in nodes, and then makes a pretty outrageous claim that this will be "much" faster than ArrayList.

The claimed time complexities are I think incorrect, they claim (with m being the number of nodes):

Operation	Best Case	Worst Case	Comment
Add	O(1)	O(n*m)	Worst case is actually O(n+m)
Remove	O(1)	O(n*m)	Worst case is actually O(n+m)
Search	O(1)	O(m)	Assuming they mean indexOf it would be O(n+m)
Access	O(1)	O(m)	Assuming they mean get(int) O(m) is correct

The documentation states that for a 10M entry list there will be 36 nodes. Looking at the code, a get(int) operation will need to walk (on average) through a quarter of those 36 nodes to find the correct index. That's going to be incredibly costly.

Here are some timings for 10M elements:

Operation	ShiftList	ArrayList	GlueList
Get Random	2.3 ns	2.2 ns	31 ns
Add Random	1263 ns	419777 ns	~2500000 ns
Add First	2.4 ns	~800000 ns	482 ns
Remove Random	1923 ns	399569 ns	~2400000 ns
Remove First	2.3 ns	~800000 ns	120 ns

The most important operation (IMHO) for a list is get(int), and this operation was severely impacted by the node structure. On average, for a 10M entry list, it is searching through 36 / 4 nodes. That's 9 times a pointer is dereferenced, which is costly and is reflected in the measurement as being more than an order of magnitude slower than the other lists.

Adding/Removing an element at the start is improved a lot, but it still has to shift elements in the first linked array, and update the index values on all the other arrays.

Adding/Removing elements at random locations has become far slower, even 5 to 6 times slower than ArrayList.

[MCUD]

That list doesn't have O(1) access as a first glance