4 ms·
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 m
by gumby 3y ago
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.
- kammerdiener 3y agoDo you have any more info on this?
- gumby 3y agoI thought my comment was pretty comprehensive on the technique. Is there something that was unclear? I can clarify. I’ve used this technique a few times over the decades in non-editor applications with large sorted vectors.
- PH95VuimJjqBqy 3y agoNot only was it clear but it's the approach that popped into my head immediately while reading the article.
- kammerdiener 3y agoYour explanation was just fine. I was simply asking what else you knew about the technique. Perhaps where you first heard of it or some examples where it has been applied/benchmarked.