Hacker News Reader

Comment by josephg | Hacker News Reader

I’ve been wondering something similar. I recently published a rust rope library based on skip lists. (Ropes are “fat strings” optimized for efficient insertion and deletion of arbitrary characters.)

My rope is backed by a skip list, where each node in the skip list has a gap buffer. Even without the gap buffer my skip list is ~1.5x faster than the next fastest library on cargo (ropey - which is b-tree based). With gap buffers the resulting code is 4x faster. My library is also significantly smaller, both in lines of code and compiled size.

I’ve got another b-tree library I’ve been using for CRDT editing in Diamond Types. Based on this result I’m considering rewriting my btree as a skip list to see how it compares. It’d be a direct apples to apples comparison - I’ve already tuned my btree well as I can. I’m very curious how performance would change.

https://crates.io/crates/jumprope

View on HN

Wow, jumprope is really cool!

I'd had, but never gotten at all close to implementing, this idea of something like a a mutable RRB tree (think https://docs.rs/im/latest/im/struct.Vector.html but, again, mutable) with somewhat chunky (say, few-KB) gap buffers as the leaves. The tree gives you asymptotically not-terrible behavior with zillions of items, and the gap buffers could help practical performance when there's a lot of locality in your accesses.

I figure merging two lists of items or filtering some items out of a list might have the sort of locality of edits gap buffers handle well, and largish gap buffers could allow iteration to mostly spend time walking through contiguous chunks.

I still don't know how well something like that applies to a non-rope use case, but it's incredibly cool to see you actually did the work to build a hybrid structure out, validated it, and it does very well.

Oh I hadn't heard of RRB trees! Very cool.

> might have the sort of locality of edits gap buffers handle well, and largish gap buffers could allow iteration to mostly spend time walking through contiguous chunks.

Yeah this was my insight too. The gap buffers allow the leaves to be larger (because there's fewer memcpys). And large leaves improve the cache behaviour. I was really surprised how well it works in practice - its crazy fast. Like, 30M keystrokes / second fast based on some real world editing traces. I can replay the edits from an 11 page academic paper in 5ms. Doing the same thing naively in javascript takes ~1s - which is 200x slower.

> I still don't know how well something like that applies to a non-rope use case,

My intuition agrees with you. I think the performance gain is mostly thanks to the high locality of edits in a rope. And you'd get that with some data sets in a tree structure, but not all.

But what if the data is semi-random? I'm imagining a BTreeMap-like data structure with gap buffers at the leaves. In this case, you would still get fast O(log n) performance of the btree / skip list. The gap buffer would help a lot less - but it would still halve the number of items memcpy'ed in the average case when inserting or deleting. Performance might still improve a little thanks to the gap buffers.

> I can replay the edits from an 11 page academic paper in 5ms.

That's super cool.

FWIW, what got me curious about RRB trees and so on was the idea of trying for a structure that's fast in some happy cases and degrades to...maybe slow but not, say, quadratic. The thread around https://news.ycombinator.com/item?id=24357976 and got me started and mentions some other fun stuff, including a "tier vector" with sqrt(N) insert/remove anywhere.

Cool! I was surprised to see ropey as a dependency, I agree those utility functions should be inlined.

I'm currently using ropey to keep the server side state of documents in an LSP server. I recommend you add at least a slice type, as that's typically desirable. But looks great otherwise!

Yeah those utility methods will be inlined anyway by the compiler. But copy+paste (with a comment for attribution) is still probably the right tool here.

I like the idea of adding a slice type. What use case do you have in mind for that?

I don't know about other people, but my tokenizer is parameterized over string slice types. So I tokenize from a slice (be it &str or ropey's RopeSlice) and some of the returned tokens have subslices. This allows tokenization to do no heap allocation.

Please write an article contrasting the performance difference you achieve, that would be a super interesting read. Best wishes and good luck!

Reply on news.ycombinator.com