Details

Reviewers

Commits

rB0d7aab2375e6: Refactor: BLF Kerning Cache After Use

Summary

Optimization of font kerning by only caching kerning values after a
pair is encountered. Also saves unscaled values so they don't have to
be rebuilt between font size changes.

We cache kerning values for ASCII characters, but we do so in a very inefficient manner. We do so in units that are specific to the current font size, which means the cache is invalidated when the font size changes. And we change font sizes constantly while drawing the UI. And whenever it becomes invalidated we preload the cache by interrogating the font for all possible character combinations. This is more than 16,000 function calls. And we do this very very often as we print with size 12 then size 11 then 12 again...

This patch saves the kerning values in design amounts that are unscaled. This means a single kerning cache table can be used for all font sizes. We just create it once when we load the font and then use it throughout all uses without having to recreate it. This means that if we encounter "Te" in one font size we will already have it cached when we see the same two letters in a different size.

This patch also makes it so that kerning values are only cached after kerning pairs are encountered. So we never waste time caching values that are never used.

Performance Comparison

On my old machine, with scale set to 1 and thumbnail size set to "tiny". I can delete my local thumbnail cache, open File Browser fullscreen in my fonts folder. It creates 350 font previews, each with "The quick brown fox.." so using a nice portion of the alphabet.

In 2.93 this takes 20.4 seconds. With this patch (and the other changes before it) this take about half a second.

Diff Detail

Repository: rB Blender

Event Timeline

Harley Acheson (harley) requested review of this revision.Aug 19 2021, 9:43 PM

Harley Acheson (harley) created this revision.

Harley Acheson (harley) retitled this revision from Refactor: BLF Kerning After Use to Refactor: BLF Kerning Cache After Use.

Harley Acheson (harley) edited the summary of this revision. (Show Details)Aug 19 2021, 10:27 PM

Looks good, minor issue issue noted.

source/blender/blenfont/intern/blf_font.c
378	Use `UNLIKELY(...)` since most cases the values will be cached.
386	This uses different rounding to the un-cached code, this can match the existing logic: kern = (int)FT_MulFix(kern, font->face->size->metrics.x_scale); *pen_x_p += (int)delta.x >> 6;
1323	`uint` can be used.
1325	indentation (use clang-format).

This revision now requires changes to proceed.Aug 20 2021, 1:42 AM

Campbell Barton (campbellbarton) added inline comments.Aug 20 2021, 1:47 AM

source/blender/blenfont/intern/blf_font.c
375	Prefer to use `FT_HAS_KERNING(font->face)` here, so if the cache is ever cleared or out of sync, it doesn't fail silently. It's not obvious to someone reading the code that the cache pointer is used to check if a font uses kerning. Compared to the cache not yet having been initialized.

@Campbell Barton (campbellbarton) - This uses different rounding to the un-cached code, this can match the existing logic

Probably not, but I'll double-check the values just in case. The uncached one is using FT_KERNING_DEFAULT which returns values that are already rounded, in that they are returned in multiples of 64. So our bit-shifting doesn't affect it. But FT_KERNING_UNSCALED should be unrounded so if bitshifted the same way will result in truncation instead of rounding. That is my understanding anyway.

Updated to incorporate changes suggested by @Campbell Barton (campbellbarton)

Added UNLIKELY compiler optimization hint
Using FT_HAS_KERNING to test if font has kerning
Using uint instead of unsigned int
Fixed indentation

I didn't change the calculation of cached kern though as I'm not finding the difference.

with FT_KERNING_DEFAULT, FT_Get_Kerning returns values that are scaled and rounded to pixel values, which in their case means the values are even multiples of 64. Bit shifting for the divide should not change any significance.

But with FT_KERNING_UNSCALED it returns values that are unscaled, and unrounded. So I see values like -45, -36,-112, -73, -159. So after scaling the values we'd want to round them to match what we get from FT_KERNING_DEFAULT otherwise we'd truncate instead.

Or I am just not seeing or understanding something, which is always possible.

I didn't change the calculation of cached kern though as I'm not finding the difference.

The code currently in master uses all integer types, you've added float division + rounding which will give different results in some cases.

Even if you can't find the difference I don't see any advantage of using a different division/rounding method based on the existence of cache,
it makes the code more difficult to read as the reader doesn't see any explanation for why there is a difference.

All things considered it would be a lot simpler just to keep the current method of rounding / division both with and without cache.
Then there is no need to justify the difference.

Campbell Barton (campbellbarton) added inline comments.Aug 20 2021, 4:46 AM

source/blender/blenfont/intern/blf_font.c
380	Error checking shouldn't be removed.
380	No error checking.

@Campbell Barton (campbellbarton) - The code currently in master uses all integer types, you've added float division + rounding which will give different results in some cases.

No, not really.,

FreeType uses integers for everything, but to get extra precision it counts in 64ths. So every value is 64X bigger than expected.

In the old code we had two choices and that turned into calling FT_Get_Kerning with FT_KERNING_DEFAULT or FT_KERNING_UNFITTED. And you are right that either way would just use the value >> 6. But that was the problem.

When you call with FT_KERNING_DEFAULT it internally rounds the values to fit at even pixel boundaries (what it calls grid-fitting). This meant that the values out were multiples of 64, like -128 or 192. With these results it works fine to just >>6 and use -2 or 3 as that was what was intended when freetype did the rounding for us.

FT_KERNING_DEFAULT was better than the older option, which called with FT_KERNING_UNFITTED. With that one it sounds better in that it does not round the values first. So you get things like -90 or 153 which are more exact. BUT we then just >>6 and assign that to an int so we ended up using -1 or 2 instead because we ended up just truncing the value instead of using rounded values.

So FT_KERNING_DEFAULT is just simpler, but we could get similar results from FT_KERNING_UNFITTED if didn't use the simple bit shifting. FT_KERNING_UNSIZED returns unrounded values like FT_KERNING_UNFITTED

All things considered it would be a lot simpler just to keep the current method of rounding / division both with and without cache.
Then there is no need to justify the difference.

It might be clearer to then use FT_KERNING_UNSIZED for cached and FT_KERNING_UNFITTED for not but then NOT use that bitshifting. Then they could both use the same code of float division and round. Unless there is a nicer/simpler way to get the rounded values.

No error checking. Error checking shouldn't be removed.

I can put that back in, but this is the recommended behavior from FreeType on their implementation page. "We do not check the error code returned by FT_Get_Kerning. This is because the function always sets the content of delta to (0,0) if an error occurs." https://www.freetype.org/freetype2/docs/tutorial/step2.html

blf_kerning_step_fast() is getting too confusing with the differing calculations when unscaled, unfitted, or default.

Will probably pull get_kerning into a separate function, probably use FT_KERNING_UNSCALED and FT_KERNING_UNSCALED so the math is the same.

blf_kerning_step_fast() becomes much prettier, simpler, and easier to follow. Only a single call to FT_Get_Kerning() getting all values unscaled. Then a function added that converts from unscaled 26.6 to rounded pixel integers using the same (fast) math as FreeType's implementation.