A few years ago (2003, time flies) I wrote a piece table with a twist, instead of using a linked list I used a tree. I put a description of the whole algorithm

A few years ago (2003, time flies) I wrote a piece table with a twist, instead of using a linked list I used a tree. I put a description of the whole algorithm here: http://e98cuenc.free.fr/wordprocessor/piecetable.html http://e98cuenc.free.fr/wordprocessor/piecetable.html A years later it was integrated in AbiWord. There was a major mistake in the profiling. The dots in the graphs were the best of 3 measuraments. At the time I thought that was the fairest to prevent outliers due to concurrent process. It also warms the data in the cache making the best measurement super fast.