Opening this issue because I think it is the root cause of pop-os/cosmic-files#1892 while I was looking into it.
Repro
Shape a large (100-200 KiB) string containing all NULL bytes or characters that do not exist in any font. It will hang.
Details
The shape_run function has quadratic performance when the run has any characters that cannot be rendered by the primary font. For each of these "missing" characters, they are resolved via fallback font and inserted one at a time into the run. If you have a very long string of "missing" characters (like the large null byte file bug above), it basically freezes. Technically it will complete, but not before the user thinks it's broken.
The big culprit seems to be the use of vectors instead of hashsets. Many of the operations are O(N). For example:
|
if !missing.contains(&start) || fb_missing.contains(&start) { |
This one is within a loop:
|
missing.remove(missing_i); |
And these two are potentially doing large memory moves:
|
let _glyph = glyphs.remove(i); |
|
glyphs.insert(i, fb_glyph); |
NB: It seems the devs are aware of the bad perf 😄️
|
//TODO: improve performance! |
Possible Fix?
I think using HashSet<> instead of Vec<> would go a long way here. Use a hashset for the missing set of characters and maybe use it to index the positions of fallback glyphs in the run instead of removing/inserting repeatedly?
Opening this issue because I think it is the root cause of pop-os/cosmic-files#1892 while I was looking into it.
Repro
Shape a large (100-200 KiB) string containing all NULL bytes or characters that do not exist in any font. It will hang.
Details
The
shape_runfunction has quadratic performance when the run has any characters that cannot be rendered by the primary font. For each of these "missing" characters, they are resolved via fallback font and inserted one at a time into the run. If you have a very long string of "missing" characters (like the large null byte file bug above), it basically freezes. Technically it will complete, but not before the user thinks it's broken.The big culprit seems to be the use of vectors instead of hashsets. Many of the operations are O(N). For example:
cosmic-text/src/shape.rs
Line 380 in 899d74d
This one is within a loop:
cosmic-text/src/shape.rs
Line 389 in 899d74d
And these two are potentially doing large memory moves:
cosmic-text/src/shape.rs
Line 407 in 899d74d
cosmic-text/src/shape.rs
Line 418 in 899d74d
NB: It seems the devs are aware of the bad perf 😄️
cosmic-text/src/shape.rs
Line 350 in 899d74d
Possible Fix?
I think using
HashSet<>instead ofVec<>would go a long way here. Use a hashset for themissingset of characters and maybe use it to index the positions of fallback glyphs in the run instead of removing/inserting repeatedly?