GapList – A Lightning-Fast List Implementation

http://java.dzone.com/articles/gaplist-lightning-fast-list

by saurabh • 14 years ago

43 22 14 years ago

java.dzone.com

rollypolly• 14 years ago

I wonder how the GapList performance compares to unrolled linked lists.

http://en.wikipedia.org/wiki/Unrolled_linked_list

jaimzob3• 14 years ago

This is often how text buffers are implemented in editors. Since most text edits are contiguous, the gap means you don't keep shuffling memory around with each insertion and therefore it's extremely fast. I think it dates back to a pretty early version of emacs, maybe even before.

For anyone interested in a C version, I wrote this a while ago, YMMV: https://github.com/jaimz/core_ds/blob/master/MxStringBuffer....

politician• 14 years ago

I believe the data structure you're referring to is called a rope. http://www.ibm.com/developerworks/java/library/j-ropes/index...

ExpiredLink3• 14 years ago

Some stylistic remarks:

- _MxStringBuffer need not be defined in the header, a forward declaration would be sufficient (a.k.a. encapsulation).

- the two #defines can be removed form the header, too.

- I wouldn't try to typedef away a pointer (as in typedef struct _MxStringBuffer * MxStringBufferRef) but either use the pointer (MxStringBuffer* ) or create a handle: struct MxHandleStringBuffer { _MxStringBuffer * impl; };

gravitronic2• 14 years ago

Pretty jerk response to someone sharing something for free.

It's on github. Post a pull request or keep it to yourself. Especially as your comments are stylistic.

jaimzob3• 14 years ago

Thanks, I'll patch this up when I have more time - though I'm not sure there's enough time in the world to fix my sloppy C code... ;)

alexchamberlain• 14 years ago

Point 1 needs expanding... Assuming that you only need to access MxStringBuffer via a pointer, you don't need to include it in the header. However, this is somewhat deceptive and doesn't self-document. I don't think there is much advantage to it at all.

Edit: In fact, you must need the declaration to access the internals.

Leszek• 14 years ago

I find it odd that "get" is faster on a GapList than an ArrayList. Surely "get" on an ArrayList should be unbeatable.

colomon• 14 years ago

Agreed. I can imagine a situation where GapList might perform better if you were alternating requests to the beginning and ending of the list and GapList happened to store them close enough in memory that they were both on the same cache line. But by their names, none of the benchmarks seem likely to test that case.

Tuna-Fish• 14 years ago

from GapList.java:get // A note about the inlining capabilities of the Java HotSpot Performance Engine // (http://java.sun.com/developer/technicalArticles/Networking/H...) // The JVM seems not able to inline the methods called within // this method, irrespective whether they are "private final" or not. // Also -XX:+AggressiveOpts seems not to help. // We therefore do inlining manually.

GapList.get inlines everything, including the rangechecks. ArrayList has two calls to functions.

_casperc• 14 years ago

Out of curiosity, how do you go about finding out if your code is inlined or not?

DennisP• 14 years ago

I'm wondering why GapList is slower than LinkedList on random add. The LinkedList is constant time, the GapList has to copy data around.

It might be due to caching, but even so it's going to depend on how big the data is. When the data's bigger than cache and the GapList is copying large amounts of data for every random insert, the O(1) linked-list insert is going to beat it.

Or maybe he's inserting to an indexed location, and counting the time required for the LinkedList to traverse to that location.

fendrak• 14 years ago

This appears to me to be an implementation of a gap buffer:

http://en.wikipedia.org/wiki/Gap_buffer

I actually just implemented one in Python on top of the array module, planning to use it in a text editor:

https://github.com/jasontbradshaw/gapbuffer

GapList – A Lightning-Fast List Implementation

Related Stories