5 ms·

GapList – A Lightning-Fast List Implementation

43 points by saurabh 14y ago

rollypolly 14y ago
I wonder how the GapList performance compares to unrolled linked lists. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list
jaimzob 14y 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.h https://github.com/jaimz/core_ds/blob/master/MxStringBuffer....
- politician 14y ago
  I believe the data structure you're referring to is called a rope. http://www.ibm.com/developerworks/java/library/j-ropes/index.html http://www.ibm.com/developerworks/java/library/j-ropes/index...
- ExpiredLink 14y 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; };
  - gravitronic 14y 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.
    - dpark 14y ago
      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.
      - gravitronic 14y ago
        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.
        jaimzob 14y ago
        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.
        ExpiredLink 14y ago
        > 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.
        dpark 14y ago
        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.
    - mikeash 14y ago
      Excuse me? His response was nothing but polite and a perfect example of constructive criticism.
    - pasbesoin 14y ago
      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.
  - jaimzob 14y 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 14y 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.
    - ExpiredLink 14y ago
      When you put the definition of _MxStringBuffer into the *.c file you can "access the internals". The advantage of forward declaration is encapsulation.
    - haberman 14y ago
      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.
fooooobar 14y ago
Is it just me, or did he just implement an array-based Deque?
Leszek 14y ago
I find it odd that "get" is faster on a GapList than an ArrayList. Surely "get" on an ArrayList should be unbeatable.
- colomon 14y 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 14y ago
  from GapList.java:get // A note about the inlining capabilities of the Java HotSpot Performance Engine // (http://java.sun.com/developer/technicalArticles/Networking/HotSpot/inlining.html 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 14y ago
    Out of curiosity, how do you go about finding out if your code is inlined or not?
- DennisP 14y 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 14y ago
This appears to me to be an implementation of a gap buffer: http://en.wikipedia.org/wiki/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 https://github.com/jasontbradshaw/gapbuffer

43 points by saurabh 14y ago

I wonder how the GapList performance compares to unrolled linked lists. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list

jaimzob 14y 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.h https://github.com/jaimz/core_ds/blob/master/MxStringBuffer....

politician 14y ago
I believe the data structure you're referring to is called a rope. http://www.ibm.com/developerworks/java/library/j-ropes/index.html http://www.ibm.com/developerworks/java/library/j-ropes/index...
ExpiredLink 14y 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; };
- gravitronic 14y 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.
  - dpark 14y ago
    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.
    - gravitronic 14y ago
      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.
      - jaimzob 14y ago
        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.
        ExpiredLink 14y ago
        > 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.
      - dpark 14y ago
        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.
  - mikeash 14y ago
    Excuse me? His response was nothing but polite and a perfect example of constructive criticism.
  - pasbesoin 14y ago
    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.
- jaimzob 14y 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 14y 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.
  - ExpiredLink 14y ago
    When you put the definition of _MxStringBuffer into the *.c file you can "access the internals". The advantage of forward declaration is encapsulation.
  - haberman 14y ago
    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.

fooooobar 14y ago

Is it just me, or did he just implement an array-based Deque?

Leszek 14y ago

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

colomon 14y 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 14y ago
from GapList.java:get // A note about the inlining capabilities of the Java HotSpot Performance Engine // (http://java.sun.com/developer/technicalArticles/Networking/HotSpot/inlining.html 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 14y ago
  Out of curiosity, how do you go about finding out if your code is inlined or not?
DennisP 14y 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 14y ago

This appears to me to be an implementation of a gap buffer: http://en.wikipedia.org/wiki/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 https://github.com/jasontbradshaw/gapbuffer