In profiling the counter demo

flutter run -d chrome --profile

I see 80-100ms is spent in the first frame in FallbackFontManager.createNotoFontTree

(This is on Chrome 115.0.5790.110 (Official Build) (64-bit) in Linux, on a powerful workstation, but I don't think the problem is specific to that configuration)

The code constructs an interval tree of ~25k nodes.

• The initialization happens even if fallback fonts are not needed (as in the counter demo). Perhaps the initialization could be lazy, or async with substeps.
• Half of the time is spent in sorting. I have recently improved sorting and expect that to reduce from ~50ms to ~10ms dart-lang/sdk@74242b1
• 10-15% of the time is spent copying lists via sublist in the recursive makeBalancedTree. Rewriting makeBalancedTree to use a [start,end) range as parameters could completely remove this overhead.
• NotoFont._unpackFontRange takes ~10%.~~ I am working on a new encoding which should be faster because it parses fewer characters, but it still has to allocate ~25k ranges (reduction was 10ms->5ms)

A more complicated idea would be to try to avoid the interval tree. The interval tree has ~25k nodes but if this is transformed into a non-overlapping range tree, there would be ~22k nodes. The nodes would then need to map to the set of fonts supporting the code point (range). This tree would be directly useful and could be 'unpacked' in approximately the same time as the aggregate calls to NotoFont._unpackFontRange. If the fallback algorithm was modified to not need NotoFont.contains, so the ranges list was not needed, this unpacking could replace _unpackFontRange.

The fallback algorithm has some inefficiencies too, but I am not sure how important that is, since one remedy is to bundle a font covering the missing code-points.