GapList – A Lightning-Fast List Implementation | Hacker News Reader

GapList – A Lightning-Fast List Implementation

java.dzone.com

43 pointssaurabh22 comments

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....

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

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; };

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.

Why is it a jerk response? He took the time to look at the code and offer suggestions. That hardly seems like a negative thing.

If I was sharing code and the response I got was "you should dot your i's and cross your t's" instead of "thanks for providing functional code for free" it would make me reconsider sharing more in the future.

Meh. I'm sure his comment was well-intentioned: If you spend most of your time communicating with computers then your communication with humans can sometimes tend toward the 'abrupt', after this long in the industry I'm pretty used to it.

> Meh. I'm sure his comment was well-intentioned

I'm surprised about the possibility of misunderstanding.

BTW, the code is 'open source' and copyrighted: I have found no license to use it freely.

The honestly, maybe you just shouldn't be so sensitive. The suggestions made were not harsh or insulting. If this kind of gentle feedback is so hurtful, then not sharing code is probably the right choice for you.

Excuse me? His response was nothing but polite and a perfect example of constructive criticism.

Part of the assumption demanded by and centrally beneficial to HN, is that we are adults here and can approach critical review looking for its constructive nature and well-meaning aspects. HN has greatly benefited from countless individuals, both commentors and recipients, being willing to see or assume that such comments are not personal.

(As one other reply has put it, "constructive criticism".

In this case, the great-grandparent is free to reflect upon the g.p response, or not, depending upon their inclination and time. Perhaps it sparks further refinement; perhaps not. But I don't see it as being personally critical; to reiterate, it offers a perspective of possible refinement.

In the past some months, I've noticed the tone of comments on HN becoming more "emotional". That, I believe, is a slippery slope for the community. HN seems to function best when we all exercise emotional restraint, along with our technical and professional enthusiasm.

With regard, and hopefully not "calling out" the parent too much (or at all) in what I have taken primarily as an opportunity to make a more general comment.

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... ;)

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.

When you put the definition of _MxStringBuffer into the *.c file you can "access the internals". The advantage of forward declaration is encapsulation.

Structures that are kept opaque both enforce encapsulation and give binary/ABI compatibility for free. These are two very large advantages. The documentation of a type should come from the supported operations you can perform on it, not the way it represents its data internally.

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

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

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

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

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.

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.

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

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.

Reply on news.ycombinator.com