If you’re interested in editors or even just Emacs internals you probably know about gap buffers. They’re a way of holding the data being edited so that it can be updated and displayed quickly and easily. It’s not the only method and certainly not the most obvious. The first thing most of us think of is an array of lines but gap buffers has substantial advantages over that.
The short story about gap buffers is that empty space is opened at the point so that text can be added, deleted, or edited. When the point is moved to another region, the old gap is closed and reopened at the new location. Newer editors mostly use more modern data structures for this such as piece tables or ropes.
Troy Hinckley has been experimenting with replacing the Emacs C core with Rust. Recently, he started looking at the best way to represent a text buffer. Rust, he says, has some particularly good implementations of ropes but he wondered whether they really were better than gap buffers for this particular application. He decided to answer the question scientifically.
He wrote an instrumented version of gap buffers and some of the Rust rope implementations and
ran some benchmarks. The results were illuminating. Gap buffers performed much better than you might expect against ropes. His post takes a detailed look at the question so you should definitely head on over there if you have any interest at all in the matter. It’s a good post and an excellent example of letting the evidence decide an issue.