| > if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly. This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same. I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors. Another point with multiple cursors and gap buffers is that Chris Wellons animations show the gap moving back to the first cursor every time it needed to add a new character. But in reality you would just walk the cursors in reverse order each time, saving a trip. I have actually written and benchmarked a very naive and unoptimized gap buffer, and the results showed that it was faster than highly optimized rope implementations on all real world benchmarks[2], including multiple cursors. That being said, a gap buffer is still probably not the best data structure for a text editor because it has worse “worse case” performance than something like a rope or piece-tree. Even though it is faster overall, it’s the tail latency's that really matter for interactive programs. Overall I enjoyed reading the post, I find the topics fascinating and this was well presented. [1] http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-... [2] https://github.com/CeleritasCelery/rune/issues/17#issuecomme... |