[HN Gopher] Text Showdown: Gap Buffers vs. Ropes
___________________________________________________________________
Text Showdown: Gap Buffers vs. Ropes
Author : celeritascelery
Score : 172 points
Date : 2023-10-09 14:00 UTC (9 hours ago)
(HTM) web link (coredumped.dev)
(TXT) w3m dump (coredumped.dev)
| jll29 wrote:
| I'm curious: who invented gap buffers originally? Do we know if
| it was RMS? What was the first peer-reviewed publication
| describing or mentioning them?
|
| A quick search brings up only references in the 1990s or later...
| gumby wrote:
| Emacs uses a gap buffer because TECO used one, long before RMS
| finished high school.
|
| Emacs was initially just a bunch of macros (in Eugene
| Ciccarelli's TECO init file IIRC) that provided an easier
| interface to TECO once a realtime display mode (^R mode of
| course!) had been added.
|
| Yes, in TECO, control R was a keyword in the language. If you
| don't know TECO it looks like line noise. For controlling an
| editor, that's not necessarily insane.
| zogrodea wrote:
| This is an interesting article. Not 100% sure about the
| implementation of JumpRope, but I think it combines a gap buffer
| together with a rope. Ropey (and I think Crop too?) also support
| cheap persistence.
| celeritascelery wrote:
| I should have added a section on that.
|
| JumpRope combines a gap buffer with a skip list. Crop combines
| a gap buffer with a rope. ropey is a "traditional" rope that
| doesn't use a gap buffer under the hood.
| zogrodea wrote:
| Thank you for writing the fun article and experiments! :)
| josephg wrote:
| Author of jumprope here. Great post! It's cool seeing so many
| other good rope libraries ready to use.
|
| It's interesting seeing how poorly jumprope does on memory
| efficiency. I could definitely change the code to more
| aggressively join small text nodes together to bring the memory
| overhead more in line with the other algorithms. I'm just not
| sure how much anyone cares. Text is _really_ small - a raspberry
| pi or phone has gigabytes of memory these days. If a 1mb text
| document takes up 5mb of ram - well, does that matter? I suppose
| if you're opening a 1gb log file I do appreciate that some of the
| other approaches tested here have no overhead until you start
| making edits.
|
| From a performance standpoint there's one more trick jumprope has
| not mentioned here, though it could easily be applied to the
| other algorithms. And that is, in regular text editing sessions
| (and in replaying CRDT editing traces) we can buffer the most
| recent editing run before committing it to the data structure.
| So, if you start typing some contiguous characters, they get
| stored separately and only when you move the cursor or start
| deleting do we flush that change down. This improves performance
| of replaying editing traces by nearly 10x. But I'm not sure how
| applicable it is to the "regular" case of text editing. It is,
| however, super useful for replaying edits in a collaborative
| editor. It's fast enough that my crdt doesn't even bother storing
| the most recent document on disk - we just replay the entire
| editing history when a document is opened. Even for large
| documents, files can usually still be opened in about 1ms
| (including replaying the entire editing trace). This case doesn't
| show up in all benchmarks because you have to opt in to it using
| the JumpropeBuf wrapper instead of Jumprope.
| KerrAvon wrote:
| > If a 1mb text document takes up 5mb of ram
|
| Text files are sometimes not that small. It's not that unusual
| to have a multigigabyte text log, sometimes larger than system
| RAM on the machine.
| celeritascelery wrote:
| Thanks for all the work in bootstrapping this part of the
| ecosystem! I opened an issue[1] on the memory issue for
| jumprope. It seems to really come down to the large size of
| skiplist nodes relative to the text.
|
| I did some testing with JumpRopeBuf, but ultimately did not
| include it because I was comparing things from an "interactive
| editor" perspective where edits are applied immediately instead
| of a collaborative/CRDT use case where edits are async. But it
| did perform very well as you said! I feel like JumpRopeBuf
| feels similar to a piece table, where edits are stored
| separately and then joined for reading.
|
| [1] https://github.com/josephg/jumprope-rs/issues/5
| IshKebab wrote:
| > Text is really small
|
| Tell that to my 10GB JSON files.
| josephg wrote:
| That doesn't sound like a text file. Sounds like you have the
| world's least convenient database.
|
| You're on your own with that one. Sounds like a job for
| SQLite, not a rope library.
| KerrAvon wrote:
| Dude. TFA is literally about the core data structures for a
| text editor. Many people care about large text files. It's
| something people actually do. BBEdit on the Mac can edit
| files much larger than RAM without thrashing. If you don't
| want to support text editors, that's fine, but then what is
| your rope library for?
| pphysch wrote:
| You're opening those in a text editor?
| mananaysiempre wrote:
| Absolutely, although sometimes I have to resort to less(1)
| when everything else crashes and burns on them. The
| advanced troubleshooting technique known as "look" is as
| useful as ever.
| subarctic wrote:
| I really like this article's structure for showing benchmarks.
| each benchmark has its own heading and a paragraph explaining the
| reason for it and analyzing the results.
|
| I was a bit surprised, though, with how it ends right after the
| search benchmark. This seems like the perfect setup to talk about
| search/replace (aka find/replace), which seems like the best use
| case for non-local edits that I can think of, and therefore would
| be a great opportunity to show how the algorithms compare in
| something the ropes should be better at.
| raphlinus wrote:
| Interesting article, and I love to see performance numbers to
| back up engineering decisions. I'm also glad xi-rope wasn't
| included, as I'm sure it's performance lags :)
|
| That said, it's not measuring what I would measure. The jumprope
| benchmarks are reported as the total time to complete a number of
| tasks. To me, the massive strength of the rope data structure is
| its O(log n) _worst case_ performance when performing a simple
| operation such as inserting or deleting a character. That
| translates into user-perceivable latency. If you have a sequence
| of a thousand edits, and your rope accomplishes each in 200us,
| while your gap buffer has a mean of 100us but variance extending
| to 10ms, then I 'd much prefer the former, even though this
| benchmark would indicate the latter is 2x faster.
| loeg wrote:
| Also, the author is quick to dismiss 20-100ms latencies as
| imperceptible, or nearly so. That is too high.
| chongli wrote:
| Yeah. 20ms is more than a full frame at 60hz. This sort of
| delay is unacceptable in 3D games! And here we're talking
| about inserting a character into the data structure used to
| keep track of edits to a text file!
|
| It's also ignorant of the heavily pipelined nature of input
| and output on modern computers. If you add up all of the
| latency from the time you press a key on the keyboard to the
| time a character appears on the screen -- even if you
| subtract all the time spent inside your text editor -- it
| adds up to many ms of delay. Now the author thinks it's okay
| to add another 20-100ms to that just for the basic data
| structure holding the text? No thank you!
|
| _Edit: I have to add this link to a classic post by Dan Luu
| [1]. The Apple IIe leads the pack with 30ms latency from
| keystroke down to character on the screen. 20ms for a data
| structure (in the key-to-screen critical path) on a 2023
| computer, even if it only occurs 1% of the time, is totally
| unacceptable._
|
| [1] https://danluu.com/input-lag/
| _a_a_a_ wrote:
| I thought your first para was sarcasm. Now I'm just not
| sure. It sits on the razor's edge, ready to fall either way
| in my mind.
|
| NB. Elite running on Emacs
| https://www.salkosuo.net/2015/10/22/elite-for-emacs.html
| intelVISA wrote:
| The true end goal of all posts here, such craftsmanship.
| IshKebab wrote:
| I don't think he's quick to dismiss it. He talks about it
| several times. Those latencies are when editing files in the
| hundreds of MB, and only in the worst case non-local edit.
| How often do you edit I file that big?
|
| Also I expect if that was a real problem you could probably
| implement a system where you have more than one gap. Does
| that exist?
| gpderetta wrote:
| > How often do you edit I file that big?
|
| On the other hand, does speed really matter for small
| files?
|
| Handling uncommon scenarios gracefully is important.
| celeritascelery wrote:
| > Also I expect if that was a real problem you could
| probably implement a system where you have more than one
| gap. Does that exist?
|
| That is a really cool idea! I actually tried implementing
| that. However I gave up because the code became quite a bit
| more complex, but it would totally be possible! That being
| said, multiple gaps would only help the "move gap" latency,
| they wouldn't help with the resizing latency. The later is
| both less predictable and much higher then moving the gap.
| Also when you need to coalesce the text for searching you
| would loose all your gaps.
| celeritascelery wrote:
| depends on the context. The rule of thumb I have seen is that
| anything under 100ms is perceived as instantaneous by a user.
| So for interactive editing those latencies are acceptable.
| Though is should be noted those latencies are only for 1 GB
| file, so they will get worse as the edited file gets larger.
| But if you are building something like a CRDT where you can
| have edits coming in from many sources then those will start
| to compound, and will destroy your responsiveness. Also if
| you are performing edits while doing something like scrolling
| you will start to drop frames. Jumprope and Xi-rope were
| specifically designed for the CRDT use case. As Raph points
| out, the latencies are what will really bite you. And latency
| is actually why I picked a gap buffer; the ropes have too
| high of latency with regex searches. If that was ever fixed I
| would be tempted to switch to ropes.
| vlovich123 wrote:
| I've always found that latency number to be suspect. In
| some contexts, it's imperceivable. In others it is.
|
| For example, dragging an item around a screen with your
| finger, 100ms is definitely noticeable. Typing seems to be
| less although I had a coworker claim he could. So it's hard
| to say if we don't notice it vs we've just become
| accustomed to interacting with text with 100ms of latency
| (or something about the task of typing is more latency
| insensitive).
|
| I would be interested in seeing the the same data driven
| analysis for human factors as HCI is even less intuitive
| than computer algorithm performance.
|
| Searching is not a particularly latency sensitive task as
| your next match is probably significantly within 1 gib
| where you're paying 250ms at worst. But yeah, if regex
| searching is _the_ task to optimize around, ropes in Rust
| won't work well due to the lack of incremental search at
| this time.
| burntsushi wrote:
| What regex engines do people use for this task generally?
| Most regex engines I'm aware of don't support
| stream/incremental searching.
| zogrodea wrote:
| This comment by someone at GitHub mentioned that Atom
| used PCRE's partial match functionality, but I have no
| idea about what is used most commonly.
|
| https://news.ycombinator.com/item?id=15386155
| vlovich123 wrote:
| I was just going from the linked issue where I thought I
| read that Go's engine supports incremental search. Maybe
| I misread?
|
| While I have you, how close is the Rust incremental
| search support? It sounded like regex-automata might make
| it possible but hard to easily get a sense of high level
| progress from a GitHub issue.
| burntsushi wrote:
| Go has this: https://pkg.go.dev/regexp#Regexp.MatchReader
| --- That just tells you whether an io.Reader contains a
| match anywhere or not. I don't think it tells you
| anything else, like the position of the match.
|
| > While I have you, how close is the Rust incremental
| search support? It sounded like regex-automata might make
| it possible but hard to easily get a sense of high level
| progress from a GitHub issue.
|
| I'm not working on it. The current status is that other
| people are working on trying to write it themselves on
| top of regex-automata in a way that works for their
| specific use case. That was my high level strategy:
| release a separately versioned library with the regex
| internals[1] exposed so that others can experiment and
| build on top of it.
|
| The regex-automata crate exposes the low level DFA (and
| lazy DFA) transition function. So you can pretty much do
| some kind of stream searching out of the box today
| (certainly at least what Go provides):
| https://docs.rs/regex-
| automata/latest/regex_automata/#build-...
|
| Bottom line here is that if you're looking to implement
| stream searching in Rust, then you should be able to go
| out and build something to do it today with regex-
| automata. But you aren't going to get a streamlined
| experience. (And whether you ever will or not remains
| unclear to me.)
|
| [1]: https://blog.burntsushi.net/regex-internals/
| alpaca128 wrote:
| > ropes in Rust won't work well due to the lack of
| incremental search at this time
|
| Unless you don't mind implementing a couple dozen lines
| yourself. The _regex_automata_ crate allows you to
| directly access the DFA, so with iteration through the
| rope and a bit of state tracking you can already do this,
| just not as convenient (yet) as a single method call.
| _dain_ wrote:
| _> The rule of thumb I have seen is that anything under
| 100ms is perceived as instantaneous by a user._
|
| for typing characters into a text box this is not
| imperceptible. it should happen in a single frame.
| deagle50 wrote:
| And it gets more perceptible when moving the caret (more
| pixels to track and you're actively tracking).
| deagle50 wrote:
| Users can easily feel one frame of latency at 60hz given
| enough visual feedback (pixels in this case). It gets
| harder at 120hz and above. I have a toy editor with Ropey
| and WGPU, just added a 100ms wait on char insert and it's
| rubber banding when typing fast.
| raphlinus wrote:
| Search is 100% a valid justification to use contiguous
| storage. It wasn't high in my list of considerations when I
| was starting out.
| 4death4 wrote:
| Instead of the rule of thumb you've seen how about the rule
| of thumb you've tried? Make two simple HTML forms: one with
| an input that instantaneously accepts input and another
| with 100 ms delay. You can definitely tell the difference.
| gary_0 wrote:
| An occasional 100ms pause while I'm editing a huge 1GB file
| wouldn't be a deal-breaker for me, as long as regular-sized
| files have <10ms latency. It's been a long time since I
| opened a text file that huge, and I think the editor I was
| using at the time chugged something awful.
|
| VSCode is slightly laggy for me just editing a 10k line
| text file, so my standards are sadly not that high, even
| though I find typing latency really annoying.
| scotty79 wrote:
| I wonder if these benchmarks include the time spent on updating
| the tree that stores information where the lines begin. Because
| if you have a gap at the beginning of the buffer and you make an
| insert you need to update all of that information.
| celeritascelery wrote:
| All the containers store the metrics (line endings, unicode
| codepoints, UTF-16 codepoints, etc) in a tree. The tree stores
| the value of all it's children summed up. So if if you do an
| insert at the start you only need to update a single branch.
| When calculating the line count you have to walk down the tree
| summing all the children as you go. But this means updating and
| lookup are both logn instead of having to update N nodes.
|
| These benchmarks include that time.
| ahefner wrote:
| A neat trick with gap buffers is you can track the line
| boundaries as indices into the gap buffer itself rather than
| 'real' indices into the document. In this way the indices of
| line starts seldom change except when the gap buffer is
| resized. You can then keep a second gap buffer, this one
| recording the start of line indices, and keep its gap in sync
| with cursor movement in the text gap buffer, making insertion
| cheap and giving a trivial way to map from line numbers to a
| position in the gap buffer. No trees necessary.
| celeritascelery wrote:
| hmm. What happens when you move the gap from the front to
| the end of the text (or vice versa)? wouldn't that require
| you to update all the line boundaries? And wouldn't finding
| the position of the Nth line be O(n).
| gumby wrote:
| In a modern OS, you can combine the gap and the piece table
| approaches using the MMU to eliminate most copying in the common
| cases.
|
| Basically: if you need to make a gap, split the page it's on into
| two (so your region copy is always less than one page long). You
| can start the copy into the middle of second page or not (I don't
| actually think that's an optimization in practice but have never
| measured it).
|
| If you get a lot of fragmentation you can have a background
| process that does coalescence away from the active insertion
| point.
___________________________________________________________________
(page generated 2023-10-09 23:00 UTC)