Does this really make much of a practical difference these last decades? I wrote a text editor back in the late 90s in DOS using DJGPP with per-line allocation and it worked fine on the Pentium MMX i had at the time (and my approach to optimization at that time was be ignorant of the concept :-P), i'm not sure it'd really make much of a difference on any desktop or laptop CPU released past 2000 - at least as far as users editing text files are concerned (might make a difference if you try to open a multiGB file with barely a line break and accidentally press a letter :-P).
The only sensible normalisation one can implement is the full decomposition (NFD), and maybe the full composition (NFC). You rely on the full decomposition if you want to collate correctly, which is a problem because the amount of memory needed to store the decomposition is unbounded in general. I don't want to make the libgrapheme users jump through hoops, and I also don't want to do any memory allocations in libgrapheme either.
There is an idea floating in my head on how to solve this, but I'm currently busy finalising Unicode 15.1 support (Unicode 16.0, released on the 10th, will be trivial to upgrade to) and releasing my already fully-compliant implementation of the Unicode bidirectional algorithm.
LLVM has been using rope data structures for some time. There is more discussion about it here:
https://lists.llvm.org/pipermail/llvm-dev/2011-July/041639.h...
In my situation when parsing lines of code Twine stores the file path and concats the line number and column when getting the location within a file. It does this a lot so using Twine there really helps. The rope data structure can be used in a number of ways.
However, my two suggestions would be:
- add Unicode support (it's the 21st century, so ∑, ®, etc. should finally work); this is not easy, but the earlier you do it the less dramatic the changes will be (check out https://github.com/unicode-org/icu/tree/main/icu4c);
- don't allocate the lines individually (as you do now with malloc, having looked at the code); at least use an arena allocator, i.e. allocate larger chunks of memory and the provide your own alloc_line function that uses the larger chunks (called arenas) piecemeal. This will speed things up and reduce fragmentation. A more advanced approach would be not to use per-line buffers but to switch to rope data structures e.g. https://github.com/josephg/librope).