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.
- _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; };
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.
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.
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.
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.
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.
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.
23 comments
[ 6.1 ms ] story [ 67.6 ms ] threadhttp://en.wikipedia.org/wiki/Unrolled_linked_list
For anyone interested in a C version, I wrote this a while ago, YMMV: https://github.com/jaimz/core_ds/blob/master/MxStringBuffer....
- _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; };
It's on github. Post a pull request or keep it to yourself. Especially as your comments are stylistic.
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.
(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.
Edit: In fact, you must need the declaration to access the internals.
GapList.get inlines everything, including the rangechecks. ArrayList has two calls to functions.
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.
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