Switched the font atlas to discrete math for hash keys #164822
Conversation
|
In theory this can give us higher fidelity too. I don't take advantage of it here. But we could start doing |
| auto foo = | ||
| frame->GetTransform() * Matrix::MakeTranslation(frame->GetOffset()); |
There was a problem hiding this comment.
ooops, I left this debugging code in. It's going to have to be fixed when I merge with the workaround we are about to land though.
| if (num_ == 0) { | ||
| return 0; | ||
| } | ||
| uint64_t gcd = std::gcd(num_, den_); | ||
| return ((num_ / gcd) << 32) | (den_ / gcd); |
There was a problem hiding this comment.
So the goal here is to compute a hash that is == when the values are equal, basically making sure that 1/5 and 2/10 have the same hash?
There was a problem hiding this comment.
Exactly, we had a few other options:
- Simplify the fractions in the constructor so that if you ask for Rational(2, 10) you get Rational(1, 5), but I tried to optimize the math for fractions with the same denominator.
- Make the denominator part of the type, so
Rational(1,5)becomesRational<5>(1). That way we could have made sure everything has the same denominator. It only occurred to me later, it is a bit awkward though.
There was a problem hiding this comment.
I'm slightly concerned about the performance of computing the gcd (nlogn ?) for the hash, given that we end up hashing each glyph each frame. the subpixel hash already shows up quite hot in the flame graphs. this can be verified on an app with a moderate amount of text, like the old flutter gallery.
I'd lean towards an approach where we computed the float and then hashed that.
There was a problem hiding this comment.
I had the same concern, but gcd isn't actually that expensive. Our denominator will typically be 200, so the worst case scenario is Rational(199,200). The euclidean method loops 3 times in order to figure that out which is like 12 operations.
I don't think we want to compute the float since you'll be throwing away precision. We have the opportunity to have a perfect hash function without gcd in it in the 2 approaches I listed above.
There was a problem hiding this comment.
More thoughts:
- gcd is
log(n) - I was concerned about having to use gcd in operator== with approach 1 to avoid overflow but it's actually fine. With denominators of 200 (our case) we can go up to 21 million, 1000 goes to 4 million (we use this in some tests).
There was a problem hiding this comment.
Let's land it like this and look at the numbers afterwards. I say if we notice any change we should switch to approach 2 since it is the fastest.
| @@ -54,16 +55,35 @@ struct ScaledFont { | |||
| }; | |||
| }; | |||
|
|
|||
| enum SubpixelPosition : uint8_t { | |||
| kSubpixel00 = 0x0, | |||
There was a problem hiding this comment.
Lets document this a bit more: which ones are the X positions and which ones are Y positions?
| @@ -205,6 +205,10 @@ static ISize ComputeNextAtlasSize( | |||
| return {}; | |||
| } | |||
|
|
|||
| static Point SubpixelPositionToPoint(SubpixelPosition pos) { | |||
issue: #164606
This is a refactor of how we store font atlas data. Previously we were using floating point values with custom hash functions as keys. This was very hard to debug. This change instead makes all keys used in the font atlas discrete.
The hope was that this might fix #164606, or at least make it easier to debug. It didn't fix the issue.
Pre-launch Checklist
///).If you need help, consider asking for advice on the #hackers-new channel on Discord.