Very high memory usage overhead

[CeleritasCelery]

I was doing some comparisons between this and other rope-like crates, and I noticed that jumprope has over 90% memory overhead. This is due to the small size of the GapBuffer (400 bytes) relative to the nexts lists of SkipEntry's (336 bytes). The nexts field is almost as large as the gap buffer itself so this leads to almost doubling the memory overhead.

[josephg]

I must have missed this while I was travelling. (I only just got back a few days ago). Sorry about that!

My impression from reading your blog post is that there’s two problems here:

1. As you say, text nodes are inefficient due to the small relative size of the text string in each node compared to the next pointers.
2. Jumprope isn’t very agressive about merging nodes back once they’ve split. Eg, if you delete all-but-1 character in a node, that node isn’t deleted, and it hovers around with just 1 character in it. Hence jumprope sitting around 400% overhead after a lot of edits have happened.

Re: 1, we could increase the size of the text buffer per node. But I’m worried about performance. The current number was chosen to get the best performance from benchmarks. Might be worth revisiting - if doubling that would halve memory usage but might only reduce performance by 5-10% it’s probably worth doing. Could use some benchmarking.

Re: 2, I suspect being more aggressive about merging nodes would yield a net improvement for performance on top of the memory savings due to cache. It’s tricky code to write though, and I don’t have the bandwidth to do it right now.

[CeleritasCelery]

I have a fork of jumprope with the get-size crate added. That is how I measured overhead. Of the two issues you pointed out, I think 1 is by far the bigger contributor. Note that in the edit heavy scenario, Jumprope only grew 4x, compared to 8x and 20x for the other ropes.