Switched the font atlas to discrete math for hash keys by gaaclarke · Pull Request #164822 · flutter/flutter

gaaclarke · 2025-03-07T22:11:21Z

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

I read the Contributor Guide and followed the process outlined there for submitting PRs.
I read the Tree Hygiene wiki page, which explains my responsibilities.
I read and followed the Flutter Style Guide, including Features we expect every widget to implement.
I signed the CLA.
I listed at least one issue that this PR fixes in the description above.
I updated/added relevant documentation (doc comments with ///).
I added new tests to check the change I am making, or this PR is test-exempt.
I followed the breaking change policy and added Data Driven Fixes where supported.
All existing and new tests are passing.

If you need help, consider asking for advice on the #hackers-new channel on Discord.

gaaclarke · 2025-03-10T21:23:08Z

In theory this can give us higher fidelity too. I don't take advantage of it here. But we could start doing (x*y)/z instead of x*(y/z).

gaaclarke · 2025-03-10T21:44:44Z

engine/src/flutter/impeller/typographer/backends/skia/typographer_context_skia.cc

+        auto foo =
+            frame->GetTransform() * Matrix::MakeTranslation(frame->GetOffset());


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.

jonahwilliams

Like this approach, mostly just nits!

jonahwilliams · 2025-03-11T02:07:25Z

engine/src/flutter/impeller/geometry/rational.cc

+  if (num_ == 0) {
+    return 0;
+  }
+  uint64_t gcd = std::gcd(num_, den_);
+  return ((num_ / gcd) << 32) | (den_ / gcd);


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?

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) becomes Rational<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.

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.

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.

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).

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.

jonahwilliams · 2025-03-11T02:08:48Z

engine/src/flutter/impeller/typographer/font_glyph_pair.h

 };

+enum SubpixelPosition : uint8_t {
+  kSubpixel00 = 0x0,


Lets document this a bit more: which ones are the X positions and which ones are Y positions?

jonahwilliams · 2025-03-11T02:09:36Z

engine/src/flutter/impeller/typographer/backends/skia/typographer_context_skia.cc

  return {};
 }

+static Point SubpixelPositionToPoint(SubpixelPosition pos) {


hmm yess... yes

jonahwilliams

LGTM

…er/flutter#164822)

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].  [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

gaaclarke added 5 commits March 7, 2025 10:35

moved the glyph atlas to rational numbers

1917476

moved scaledfont to rational

1a35aef

added subpixel position

43ec400

fixed guard

703849c

format

5defa4b

gaaclarke changed the title ~~Rational~~ Switched the font atlas to discrete math for hash keys Mar 7, 2025

gaaclarke added 2 commits March 7, 2025 14:16

fixed hash

abce4b3

made creation explicit

a99253d

github-actions bot added a: text input Entering text in a text field or keyboard related problems engine flutter/engine related. See also e: labels. e: impeller Impeller rendering backend issues and features requests labels Mar 8, 2025

gaaclarke added 4 commits March 7, 2025 17:33

fixed test

9df2d35

fixed test

280ab6b

removed chance of overflow

b19fded

license

1a4d67b

gaaclarke marked this pull request as ready for review March 10, 2025 21:15

gaaclarke requested a review from jonahwilliams March 10, 2025 21:15

gaaclarke commented Mar 10, 2025

View reviewed changes

jonahwilliams reviewed Mar 11, 2025

View reviewed changes

gaaclarke added 3 commits March 11, 2025 08:28

jonah feedback

d7cb11f

Merge remote-tracking branch 'origin/main' into rational

c6b5709

switched the order of numbers in subpixel position

f09aa43

gaaclarke force-pushed the rational branch from fa32b0a to f09aa43 Compare March 11, 2025 16:29

jonahwilliams approved these changes Mar 11, 2025

View reviewed changes

gaaclarke added this pull request to the merge queue Mar 11, 2025

Merged via the queue into flutter:master with commit 61a5fe7 Mar 11, 2025
170 checks passed

gaaclarke deleted the rational branch March 11, 2025 18:40

engine-flutter-autoroll mentioned this pull request Mar 11, 2025

Roll Flutter from b16430b2fd57 to 61a5fe792957 (26 revisions) flutter/packages#8852

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 15, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

58f866d

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 15, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

e102345

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 16, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

cf31514

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 16, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

92fd2a8

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 16, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

69aa9f3

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 17, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

33e4692

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 20, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

730d4b1

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 25, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

8a40d96

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 25, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

33c7c1f

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

a0393d0

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

12ca25c

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

ca7f952

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

02b0a92

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

2fa122a

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

8e295c6

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

685e12b

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 26, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

f080f93

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

394cf61

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

e5a080e

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

b74d34d

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

a8e0f04

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

f83858d

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

11ec2c9

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

02bcbcc

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 27, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

cf9e8ad

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Mar 28, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

20240a7

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request May 20, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

71edd2a

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request May 20, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

f2f3ede

…er/flutter#164822)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request May 21, 2025

61a5fe7 Switched the font atlas to discrete math for hash keys (flutt…

10c3d37

…er/flutter#164822)

		auto foo =
		frame->GetTransform() * Matrix::MakeTranslation(frame->GetOffset());

Conversation

gaaclarke commented Mar 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pre-launch Checklist

Uh oh!

gaaclarke commented Mar 10, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonahwilliams left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonahwilliams left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

gaaclarke commented Mar 7, 2025 •

edited

Loading