find_texture_pos_for_glyph() is hideously inefficient with many glyphs (Chinese)

[nikitalita]

Godot version

4.0 dev @ 9afc833

System information

Windows 10

Issue description

find_texture_pos_for_glyph() is very inefficient when we have text that has a large amount of unique glyphs, like Chinese text.

The culprit is here:

When we have text that contains a large amount of glyphs, the time spent calculating the position of each font texture grows enormously because of the continuous slow lookup in the ct.offsets vector. In the case of DroidSansFallback with very small characters, the fonts are 16x16, so 256 offsets, per glyph. This grows to 1024 with subpixel hinting. With sharper fonts with larger characters, this can be an astronomical amount of offset lookups.

This is fine for text with Latin characters, since we only have to rasterize around 30-40 different glyphs. But for Chinese text, where a few paragraphs can contain 1000+ glyphs, this is very slow. As a result, rendering text elements with any large amount of Chinese text slows to a crawl.

Changing find_texture_pos_for_glyph() to index into the ct.offsets.ptr() instead of going through the Vector[] lookup speeds it up by about 4x, but it is still rather slow just due to the sheer amount of lookups:

I'm not quite sure how to fix this; this would necessarily be O(n) bound (n being the amount of offsets) if we must look up each offset to determine the max. Pre-sorting, maybe?

Steps to reproduce

I've included a test program to test the more extreme end; it is a text box that contains the entire Unicode set of both traditional and simplified characters. For comparison, I've also included a Lorem Ipsum text box of comparable size to demonstrate how fast it renders compared to the Chinese text box.

Minimal reproduction project

chinese_text_test.zip

[bruvzg]

For the reference: this glyph packing code was not significantly changed since it was introduces it 5bb7cef 7 years ago, so it's relevant for all Godot versions.

[bruvzg]

Done some testing, and yes, it's really bad. The first packing algorithm I have found after 5 minute of googling is 25-30 times faster (this is including #67521 improvement) and seems to result in more dense packing.