Switched the font atlas to discrete math for hash keys #164822
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
gaaclarke
changed the title
github-actions
bot
added
a: text input
Member
Author
|
In theory this can give us higher fidelity too. I don't take advantage of it here. But we could start doing |
gaaclarke
commented
Mar 10, 2025
Comment on lines
467
to
468
| auto foo = | ||
| frame->GetTransform() * Matrix::MakeTranslation(frame->GetOffset()); |
Member
Author
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.
Contributor
jonahwilliams
left a comment
jonahwilliams
left a comment
There was a problem hiding this comment.
Like this approach, mostly just nits!
Comment on lines
+43
to
+47
| if (num_ == 0) { | ||
| return 0; | ||
| } | ||
| uint64_t gcd = std::gcd(num_, den_); | ||
| return ((num_ / gcd) << 32) | (den_ / gcd); |
Contributor
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?
Member
Author
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.
Contributor
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.
Member
Author
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.
Member
Author
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).
Member
Author
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.
| }; | ||
|
|
||
| enum SubpixelPosition : uint8_t { | ||
| kSubpixel00 = 0x0, |
Contributor
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?
| return {}; | ||
| } | ||
|
|
||
| static Point SubpixelPositionToPoint(SubpixelPosition pos) { |
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 15, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 15, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 16, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 16, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 16, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 17, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 20, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 25, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 25, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 26, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 27, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
Mar 28, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
May 20, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
May 20, 2025
engine-flutter-autoroll
added a commit
to engine-flutter-autoroll/packages
that referenced
this pull request
May 21, 2025
romanejaquez
pushed a commit
to romanejaquez/flutter
that referenced
this pull request
Aug 14, 2025
issue: flutter#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 flutter#164606, or at least make it easier to debug. It didn't fix the issue. ## Pre-launch Checklist - [x] I read the [Contributor Guide] and followed the process outlined there for submitting PRs. - [x] I read the [Tree Hygiene] wiki page, which explains my responsibilities. - [x] I read and followed the [Flutter Style Guide], including [Features we expect every widget to implement]. - [x] I signed the [CLA]. - [x] I listed at least one issue that this PR fixes in the description above. - [x] I updated/added relevant documentation (doc comments with `///`). - [x] I added new tests to check the change I am making, or this PR is [test-exempt]. - [x] I followed the [breaking change policy] and added [Data Driven Fixes] where supported. - [x] All existing and new tests are passing. If you need help, consider asking for advice on the #hackers-new channel on [Discord]. <!-- Links --> [Contributor Guide]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#overview [Tree Hygiene]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md [test-exempt]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#tests [Flutter Style Guide]: https://github.com/flutter/flutter/blob/main/docs/contributing/Style-guide-for-Flutter-repo.md [Features we expect every widget to implement]: https://github.com/flutter/flutter/blob/main/docs/contributing/Style-guide-for-Flutter-repo.md#features-we-expect-every-widget-to-implement [CLA]: https://cla.developers.google.com/ [flutter/tests]: https://github.com/flutter/tests [breaking change policy]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#handling-breaking-changes [Discord]: https://github.com/flutter/flutter/blob/main/docs/contributing/Chat.md [Data Driven Fixes]: https://github.com/flutter/flutter/blob/main/docs/contributing/Data-driven-Fixes.md
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
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.