10% is impressive. Albeit a web browser isn't quite the same situation but shaving even a percent off a program could save millions for a company like Google.
but the executable that is built with these optimizations is running on people's computers, not as a backend on google servers.. or am I missing something?
Perhaps I didn't understand the question. I thought the question was about why anyone would save a lot of money from software going "only" 10% faster. Most large datacenter operators will get unreasonably excited about even 1%. But you're probably right that Google itself will not directly benefit from making Chrome faster on macOS.
Did they just render the alexa top 1M sites and generate a profile from that? It would seem some bits of the codebase might only be exercised by real users (eg. touch input during a mobile game).
Did they instead gather PGO information from real users? If so, how did they do that in a way to not degrade performance too much while profiling, and maintaining user privacy (sequences and addresses of branches in some cases will reveal user data)?
Yeah normally you would have some kind of CI system that runs a typical session. I doubt they load a million sites though. Also it doesn't really matter if it isn't perfect - if code isn't exercised by the profile then it will presumably just be compiled as normal.
> To gather this data, the nightly build process now produces a special version of Chrome that tracks how often functions are used.
It doesn't say how Chrome is exercised (what pages are loaded, what user actions are simulated) during the nightly build. It seems like it must be some kind of fixed test data.
But that at least eliminates the possibility that they're gathering the profiling data from production builds used by real users, so the privacy concerns shouldn't be an issue.
(Also note that info is from 2016, so it could have changed.)
I wonder how far we can take this sort of effort -- collect exact usage statistics for users and optimize software exactly for known usage patterns. Of course some statistical technique would be needed to deal with the long tail of usage patterns -- surely some program branches are used extremely rarely (or not even seen in collected samples), but you still wouldn't want them to be extremely slow (slower than necessary) or crash just because they're rarely used. The cumulative usage of many of those long tail events can be large.
Either (regularized) statistical inference of branches or something like assuming a baseline usage for every branch would be necessary.
This is all significantly complex of course, so for anything that are not the consumer megaprojects of software (browsers and operating systems?), I wonder if those tools could be used as well. Perhaps there could be some automated, anonymized usage reporting that does all this work?
Fun fact, I wrote the first version of this code as a Google Intern. Imagine my surprise when I saw that they're still using it, and it's been developed and fleshed out!
(as a historical aside, the name is "Quipper" because I kept trying to pronounce the project name (ChromeOS-Wide Profiling, or CWP) and ended up quite liking "Quip".
The internal aggregation code, of course, is known as Bartlett.
Ages ago I had a conversation with a coworker about why was it that if databases collect statistics for optimizations, that data structures in programming languages don't do the same thing?
This would come up a few more times in my career. The next time was a few years later when I was having to go through a code base removing premature optimizations for initial list size in a code base. The average length of our data had grown such that our lists were now bigger than the defaults would have been. That was added to my growing collection of "making code faster by removing code" examples.
We talk about using better algorithms instead of tweaking code with micro-optimizations but then we never talk about tuning the better algorithms. So they default to the average case or worse.
> Ages ago I had a conversation with a coworker about why was it that if databases collect statistics for optimizations, that data structures in programming languages don't do the same thing?
Lus tables in LuaJIT, Hack arrays, and JavaScript arrays can use different representations depending on what is stored in them.
NYU’s SETL project also did some work on automatically identifying what data structure should be used.
IBM’s Hermes project was also working on this; I’m not sure whether they shipped it.
What do these profiles consist of? Simply which branches are taken vs not taken? Or do they include a history (eg. if this branch is taken then that one will not be)?
Do they depend on the stack? Ie. when called from this function, that branch is always taken. That could encourage the compiler to inline the function so it can have a faster path on the branch.
This all depends on what hardware you use to capture your profile, but on recent (Skylake and later) Intel CPUs you can use the Last Branch Record (LBR) to get branch source and target, including the call stack.
For the instrumentation based profiling, there are other extra information collected, like frequent indirect branch targets (e.g. virtual calls in C++, to support speculative devirtualization which again enables inlining), specific values for certain arithmetic operations that can be sped up if you know the typical value (e.g. a particular division in the code only or mostly handles power-of-2, it can be optimized to use shift if the target cpu has particularly slow division, etc, etc), or values of certain function calls (e.g. length of memcpy) that can be optimized if you know the typical value (inline/unroll memcpy instead of doing a call), etc.
Clang has what they call context-sensitive profile:
https://reviews.llvm.org/D54175
which partially achieves what you're asking.
Firefox has done this since forever. It's why official builds will generally be faster than compiling from scratch yourself. I'm surprised Chrome wasn't already taking advantage of PGO.
I'm surprised that there isn't a way to do PGO when compiling from scratch. A way of telling the compiler exactly what parts are, but build it into the codebase so that one could get the best of both worlds.
You can pass a PGO flag to the build system [0], but IIRC from when I was there last, Mozilla puts some serious machine hours into PGO cycles for each release and that isn't easy to replicate as an individual developer. The profiling captures things which are very specific to the actual build being optimized, so inlining that information into the codebase wouldn't be so helpful. Though there are already static optimization hints spread throughout the code (off the top of my head, MOZ_LIKELY/MOZ_UNLIKELY for marking conditionals).
They are public, but you have to know where to look. I do think they should be published alongside the builds on archive.mozilla.org. (disclaimer: I work for Mozilla)
PGO guides inlining and branch prediction IIRC. You can give static hints about each of these. But the hints aren't on a continuum like they are with PGO. So finding an optimal balance for these will be harder. Also you have to maintain these hints. So if you were somehow giving hints with a hotness ratio in the source it would be impossible to maintain and keep it accurate.
Also hot/cold partitioning. Keeping cold code code away from hot code can help L1I cache utilization, iTLB utilization, Operating system page-out, etc.
This isn't the same, but some compilers have support for macros that tell it which branches are more likely to be taken than others, and in C++20, it's even a language feature.
The G stands for guide. You need a testsuite to create a guided profile to optimize the branch hints.
Normally there's a simple make target, like chrome.pgo to create the initial binary chrome, run the testsuite with pgo or better autofdo via perf and from this create the optimized chrome.pgo. using Facebook's bolt is even better.
I have no idea about Google's byzantinian bazel tool. With make it's a simple target which automates these steps.
>It's why official builds will generally be faster than compiling from scratch yourself.
Would it be possible for Google to publish the profile data along with the source code to enable those who compile from scratch to have these same optimizations?
>I'm surprised Chrome wasn't already taking advantage of PGO.
They have been on windows since M53 (released in 2016), but this seems to be a better implementation and it's now for MacOS as well now.
From the article: "PGO was initially introduced in M53 for Chrome on Windows using Microsoft Visual C++ (MSVC) […] In M85, we are rolling out PGO on Mac and Windows using Clang."
So it sounds like they've been using PGO for a while using MSVC, and now they've started using PGO with Clang.
Wouldn't PGO only work with the exact source code, flags, compiler version, etc... used by google ? At which point you'll end up with the exact same binary than Google's too
Firefox started using PGO on Windows in Firefox in 2008 [1], Android last year [2], and macOS earlier this year [3]. Firefox uses PGO on Linux, but I don't remember when it was enabled.
The all-new Firefox for Android (codename Daylight) is lightening fast, and perceptibly seems on-par with the Chrome for Android in terms of responsiveness.
What stumps me is Chrome for Android is 3.8MB whereas Firefox Daylight is upwards of 40MB.
I haven't looked at what Google does recently but you're likely getting most of Chrome in a separate package (e.g. the system WebView). Chrome and Firefox are of compareble size IIRC (56MB vs 65MB)
Don't be misled, it was enabled for windows then got disabled when they switched to clang. To windows will get back this optimization so newer Chrome releases will get up to 10% more performance on windows
It seems Google is running their nightly pipelines with additional profile generation, but sounds like that's restricted to their internal Chrome (not Chromium) pipelines.
Microsoft would have to do their own setup. Hopefully they do.
Linux optimizations were the very first and are much better than this trivial old-style PGO. On Linux you can use perf profiles with already optimized binaries, not bloated by pgo, and use these profiles to optimize inlining, branches and hot/cold seperation via autofdo or bolt.
What is missing is using dTrace profiles for other OS's. PGO doesn't lead that far. dTrace would be the best cross platform solution. It's also secure.
I decided to measure the memory consumption of browser's new tab pages using a woefully unscientific method (simply looking at the memory usage tab in Activity Monitor and tallying everything up):
Is that a blank tab? For someone who browsed the web quite successfully for a long time on a PC with only a quarter of that RAM in total, those numbers look outrageously huge. If they're blank pages, one has to wonder what exactly needs to use that much.
There are sooo many places in the source code of a browser where the developer has to choose between "we could use an extra 100 kilobytes of RAM here", or "we have to use more CPU/be slower/add more complexity/add possible security risks/etc."
I think in most cases, and for most real world users, they have made the right call. And the product I'm building right now, every kilobyte of RAM Chrome uses to render my webpage costs me multiple dollars per month, and I still think the devs made the right choice.
Somehow mobile Chrome keeps opening a new tab for everything I do, and I found I had over 1000. Since the tabs aren't actually loaded unless you switch to them, I assumed keeping 1000 URL's in memory wouldn't impact performance much, but when I closed them random freezes when clicking every link went away...
Sigh. I used to love Chromium, when it was the new kid on the block. But now, because of this browser monoculture, I wouldn't use it even if it was far better than Firefox.
This is nice, but I remember the pain trying make a multiplayer browser game run fine, even when you put it in a background tab. The problem is that the game had matchmaking, so players would change tabs while a match was found and for the first few seconds of the start of the game. While doing so, many of the CSS animations, sounds, JavaScript functions would be queued and all executed at once when you switched back to the tab, leading to a bad experience, or in some cases the game breaking. I assume this would only get worse with this tab throttling feature, but there are legitimate use cases where both developers and users would prefer a tab to still be running at normal speed even when not focused. We use this every day in desktop applications, where we start a game or some video encoding task and just let it run, non-throttled, in the background
As a developer, you probably ought to just send a message to the server saying "I am throttled", and then later when the tab is reactivated send another message saying "I am unthrottled, please send me the current state of the game".
You shouldn't be expecting to queue up thousands of messages from potentially hours of the tab being backgrounded and handle them all when the tab is unbackgrounded. Nor should you process all the state changes as they come in even though the tab is backgrounded - no user wants to spend data/power/cpu/battery/heat on something like that.
That's a good solution if your game receives game states, but in our case the game was deterministic and ran the simulation on the client at 50FPS, only receiving the inputs from other players. This means that if your game freezes for 10 seconds (or tab out for 10 seconds), when you go back it would have to simulate all those 10 seconds before it could continue.
Imagine having GTA 5 multi-player running in a background window, you would still want to hear the other people, hear the in-game sounds so you can come back to the game if something important happens, and also not have to simulate instantly all the events that you missed when you come back.
This also reminded me that we had problems with just playing a sound when a game started to let the players know they should come back to the tab. Players complained that sometimes the game does not notify them it has started, but it was just Chrome simply not executing JavaScript anymore.
I think the Chrome developers are trying to tell you you shouldn't be using your users devices as game servers...
How about when a tab is backgrounded, a server continues running the game and just streams an mp3 audio stream to the users device. Most devices can stream audio with the CPU actually turned off.
The devices are used as game clients, not game servers.
Streaming audio sounds like an interesting idea, so instead of the server sending an event and the client playing a sound when that event is received, the client would constantly stream a dynamically created audio file. This solution could work, feels a bit complex as you would still have to make sure stream catches up if user has a lag spike, instead of buffering the audio (timing should still be accurate).
That being said, what it the game is single-player and there is no server? Then the client itself would have to generate the audio stream and stream it to itself, which wouldn't work if the background thread is throttled.
>That's a good solution if your game receives game states, but in our case the game was deterministic and ran the simulation on the client at 50FPS, only receiving the inputs from other players. This means that if your game freezes for 10 seconds (or tab out for 10 seconds), when you go back it would have to simulate all those 10 seconds before it could continue.
I would imagine you could do a "catch-up" mode -- execute the simulation at uncapped FPS till the simulation reaches parity, and turn off ui/sounds/etc during it.
Actually, if you didn't have such a mode already, I'm not clear on how the simulation would ever be able to catch up (eg most RTS's won't let you rejoin a match due to this)
> You shouldn't be expecting to queue up thousands of messages from potentially hours of the tab being backgrounded and handle them all when the tab is unbackgrounded.
In this specific case, the games only lasted 3-4 minutes each and players were also timed-out after periods of inactivity.
> Nor should you process all the state changes as they come in even though the tab is backgrounded - no user wants to spend data/power/cpu/battery/heat on something like that.
In the case of games, players do expect multiplayer games to keep running (unless it is paused, and you can't usually pause multiplayer games). Yes, I agree that the game could optimize this AFK period, for example by disabling rendering, but game events should still be triggered in real-time and notify players (with sound at least) of what's happening.
My point is, there are cases when a browser background tab should still run at 100%. Other examples: uploading a video to YouTube in a background tab, running a chess engine to get best move in a position, converting a video, etc.
Unrelated: my Chrome (on Windows) randomly freezes for 1-2 seconds whenever I focus one tab/window after I am away from it for a while. Is there any way to debug those kind of freezes?
103 comments
[ 3.1 ms ] story [ 149 ms ] threadHere's a little Wikipedia stub about Profile-Guided Optimization, for those who'd like to read more about the technique.
https://en.wikipedia.org/wiki/Profile-guided_optimization
Math may vary depending on cost of electricity.
Did they just render the alexa top 1M sites and generate a profile from that? It would seem some bits of the codebase might only be exercised by real users (eg. touch input during a mobile game).
Did they instead gather PGO information from real users? If so, how did they do that in a way to not degrade performance too much while profiling, and maintaining user privacy (sequences and addresses of branches in some cases will reveal user data)?
> To gather this data, the nightly build process now produces a special version of Chrome that tracks how often functions are used.
It doesn't say how Chrome is exercised (what pages are loaded, what user actions are simulated) during the nightly build. It seems like it must be some kind of fixed test data.
But that at least eliminates the possibility that they're gathering the profiling data from production builds used by real users, so the privacy concerns shouldn't be an issue.
(Also note that info is from 2016, so it could have changed.)
Either (regularized) statistical inference of branches or something like assuming a baseline usage for every branch would be necessary.
This is all significantly complex of course, so for anything that are not the consumer megaprojects of software (browsers and operating systems?), I wonder if those tools could be used as well. Perhaps there could be some automated, anonymized usage reporting that does all this work?
https://github.com/google/perf_data_converter/tree/master/sr...
The internal aggregation code, of course, is known as Bartlett.
This would come up a few more times in my career. The next time was a few years later when I was having to go through a code base removing premature optimizations for initial list size in a code base. The average length of our data had grown such that our lists were now bigger than the defaults would have been. That was added to my growing collection of "making code faster by removing code" examples.
We talk about using better algorithms instead of tweaking code with micro-optimizations but then we never talk about tuning the better algorithms. So they default to the average case or worse.
I wonder if in memory representations for compute such as apache arrow exploit this
Lus tables in LuaJIT, Hack arrays, and JavaScript arrays can use different representations depending on what is stored in them.
NYU’s SETL project also did some work on automatically identifying what data structure should be used.
IBM’s Hermes project was also working on this; I’m not sure whether they shipped it.
Do they depend on the stack? Ie. when called from this function, that branch is always taken. That could encourage the compiler to inline the function so it can have a faster path on the branch.
This deck can give you some idea of what the modern Intel PMU can do: https://protools19.github.io/slides/Eranian_KeynoteSC19.pdf
For the instrumentation based profiling, there are other extra information collected, like frequent indirect branch targets (e.g. virtual calls in C++, to support speculative devirtualization which again enables inlining), specific values for certain arithmetic operations that can be sped up if you know the typical value (e.g. a particular division in the code only or mostly handles power-of-2, it can be optimized to use shift if the target cpu has particularly slow division, etc, etc), or values of certain function calls (e.g. length of memcpy) that can be optimized if you know the typical value (inline/unroll memcpy instead of doing a call), etc.
Clang has what they call context-sensitive profile: https://reviews.llvm.org/D54175 which partially achieves what you're asking.
Clang also supports sampling profiler - https://clang.llvm.org/docs/UsersManual.html#using-sampling-... which gives you somewhat similar control flow profile.
[0] https://firefox-source-docs.mozilla.org/build/buildsystem/pg...
Normally there's a simple make target, like chrome.pgo to create the initial binary chrome, run the testsuite with pgo or better autofdo via perf and from this create the optimized chrome.pgo. using Facebook's bolt is even better.
I have no idea about Google's byzantinian bazel tool. With make it's a simple target which automates these steps.
Would it be possible for Google to publish the profile data along with the source code to enable those who compile from scratch to have these same optimizations?
>I'm surprised Chrome wasn't already taking advantage of PGO.
They have been on windows since M53 (released in 2016), but this seems to be a better implementation and it's now for MacOS as well now.
[1] https://blog.chromium.org/2016/10/making-chrome-on-windows-f...
So it sounds like they've been using PGO for a while using MSVC, and now they've started using PGO with Clang.
They do.
https://chromium.googlesource.com/chromium/src.git/+/master/...
https://yoric.github.io/post/why-did-mozilla-remove-xul-addo...
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=418865
[2] https://bugzilla.mozilla.org/show_bug.cgi?id=632954
[3] https://bugzilla.mozilla.org/show_bug.cgi?id=1604578
The all-new Firefox for Android (codename Daylight) is lightening fast, and perceptibly seems on-par with the Chrome for Android in terms of responsiveness.
What stumps me is Chrome for Android is 3.8MB whereas Firefox Daylight is upwards of 40MB.
Microsoft would have to do their own setup. Hopefully they do.
https://chromium.googlesource.com/chromiumos/chromite/+/mast...
What is missing is using dTrace profiles for other OS's. PGO doesn't lead that far. dTrace would be the best cross platform solution. It's also secure.
*she :-)
> Chrome will literally go towards the high 70s for no fudging reason, while idle
That seems extraordinarily high, and I've personally never experienced that problem.
I think in most cases, and for most real world users, they have made the right call. And the product I'm building right now, every kilobyte of RAM Chrome uses to render my webpage costs me multiple dollars per month, and I still think the devs made the right choice.
Chromium is an excellent project but just sometimes slow to adopt certain features.
I love chrome and chromium browsers, I hardly have any issues with them.
Unlike garbage FF and unreliable Safari
Somehow mobile Chrome keeps opening a new tab for everything I do, and I found I had over 1000. Since the tabs aren't actually loaded unless you switch to them, I assumed keeping 1000 URL's in memory wouldn't impact performance much, but when I closed them random freezes when clicking every link went away...
...but is PGO referring to the compilation of Chrome itself, or the compilation of JavaScript on sites?
The blog post doesn't actually specify which compilation is being talked about, and page performance could obviously depend on either.
How times change.
This is nice, but I remember the pain trying make a multiplayer browser game run fine, even when you put it in a background tab. The problem is that the game had matchmaking, so players would change tabs while a match was found and for the first few seconds of the start of the game. While doing so, many of the CSS animations, sounds, JavaScript functions would be queued and all executed at once when you switched back to the tab, leading to a bad experience, or in some cases the game breaking. I assume this would only get worse with this tab throttling feature, but there are legitimate use cases where both developers and users would prefer a tab to still be running at normal speed even when not focused. We use this every day in desktop applications, where we start a game or some video encoding task and just let it run, non-throttled, in the background
You shouldn't be expecting to queue up thousands of messages from potentially hours of the tab being backgrounded and handle them all when the tab is unbackgrounded. Nor should you process all the state changes as they come in even though the tab is backgrounded - no user wants to spend data/power/cpu/battery/heat on something like that.
Imagine having GTA 5 multi-player running in a background window, you would still want to hear the other people, hear the in-game sounds so you can come back to the game if something important happens, and also not have to simulate instantly all the events that you missed when you come back.
This also reminded me that we had problems with just playing a sound when a game started to let the players know they should come back to the tab. Players complained that sometimes the game does not notify them it has started, but it was just Chrome simply not executing JavaScript anymore.
How about when a tab is backgrounded, a server continues running the game and just streams an mp3 audio stream to the users device. Most devices can stream audio with the CPU actually turned off.
Streaming audio sounds like an interesting idea, so instead of the server sending an event and the client playing a sound when that event is received, the client would constantly stream a dynamically created audio file. This solution could work, feels a bit complex as you would still have to make sure stream catches up if user has a lag spike, instead of buffering the audio (timing should still be accurate).
That being said, what it the game is single-player and there is no server? Then the client itself would have to generate the audio stream and stream it to itself, which wouldn't work if the background thread is throttled.
I would imagine you could do a "catch-up" mode -- execute the simulation at uncapped FPS till the simulation reaches parity, and turn off ui/sounds/etc during it.
Actually, if you didn't have such a mode already, I'm not clear on how the simulation would ever be able to catch up (eg most RTS's won't let you rejoin a match due to this)
In this specific case, the games only lasted 3-4 minutes each and players were also timed-out after periods of inactivity.
> Nor should you process all the state changes as they come in even though the tab is backgrounded - no user wants to spend data/power/cpu/battery/heat on something like that.
In the case of games, players do expect multiplayer games to keep running (unless it is paused, and you can't usually pause multiplayer games). Yes, I agree that the game could optimize this AFK period, for example by disabling rendering, but game events should still be triggered in real-time and notify players (with sound at least) of what's happening.
My point is, there are cases when a browser background tab should still run at 100%. Other examples: uploading a video to YouTube in a background tab, running a chess engine to get best move in a position, converting a video, etc.
https://imgur.com/a/gUX2CIF
Safari/Webkit still the "fastest browser possible" on macOS.