One good trick when trying to look for ways to optimize software is to stay away from areas that are very likely already quite well optimized, and instead focus on areas that might have been overlooked, either because they are too obscure or don’t show up during regular profiling sessions. This tactic worked well in the past, as shown with my optimization of tooltip creation, or the loading of editor localization files.
This was also the reason why I mostly skip over any functions that contain words like “Shader Compilation” or “Shader Source” when I stumble over them in my profiler. The compilation of shaders is a famously long and elaborate process, and I’m pretty sure that very smart people at Epic already spent a lot of time optimizing those areas. That’s the reason why I would, for example, skip the function “Compile Global Shader Map,” even though its runtime would typically multiple seconds:
This was, at least, true until one day I skipped over it using an unusually high zoom level and saw one of the functions that was called by it:
I am certainly not an expert for hash algorithms, but SHA1 is one of the (very few) hash algorithms that even I know. And seeing this hash algorithm being used to hash shaders seemed somehow wrong to me. That’s because SHA1 is was a cryptographically safe hashing algorithm, originally developed by the NSA to encrypt sensitive information. And even though it was broken years ago and actually shouldn’t be used for sensitive information this origin means that it is – to put it politely – not particularly fast.
What does not fast mean in this context? Well see for yourself in this comparison test of a bunch of commonly used hash algorithms that Aras Pranckevičius did a few years ago (actually, it was 10 years ago – I’m getting old). SHA1 was not even included as an actual competitor but as the start of the article notes just “to illustrate the performance differences.” Ouch.
That’s especially annoying since the data being hashed is the shader source code, including all comments and copyright notice.
This means both that we have to hash a lot of data (source files can be quite big) and that there is no reason to hash it using a cryptographically secure hash, since it is no sensitive data.
Therefore, using a cryptographically safe but fast hash algorithm should be an easy win, right? And the linked article candidate already presented a good alternative, for which I even found an existing implementation in Unreal’s code base: xxHash.
Note before somebody asks: xxHash is not necessarily the fastest hash. Other, potentially even faster hashes do exist, but for now using faster hash that is already a used and tested part of the engine we are working on is a much more straightforward option.
Changing the used hash wasn’t too complicated, even though I had to change more places in the code than expected, since all places where the produced hash was stored or passed also had to be updated. A nice side effect of this change was that the stored hashes were a bit smaller than before (8 instead of 20 bytes).
But, of course, the effect that I made the change for wasn’t about memory, but CPU time. For testing purposes, I opened one of Unreal’s own sample projects, Electric Dreams, in the editor 5 times, both with and without the change, for a total of 10 runs. Profiling was done with Superluminal.
To put the following numbers into perspective, let me note that I will mostly talk about the overall CPU time, summed up over all threads, not just the time on the game thread. This is not done to artificially inflate the numbers, but to make the numbers more consistent and easier to compare. The actual effect on the editor start time is (very roughly) the measured time divided by the number of cores.
In the vanilla version of the engine, a whopping 12.90 seconds were spent in FSHA1::Update. In the modified version using xxHash, this time shrunk to just 1.59 seconds spent in FXxHash64Builder::Update. That’s eight times faster! Mission accomplished.
Normally this article would now end with a link to a pull request so that anybody interested in the change could integrate it into their own version of the engine while we wait and hope that somebody at Epic would see the pull request and merge it into the main branch.
Well, this time I have even better news: The change already got merged!
I submitted the pull request just a few days before writing this article and those few days were already enough for somebody at Epic to not only review my change but also polish it up. So let’s take a look some of the changes that were done to my proposed change:
One very smart feat that I hadn’t thought of was to wrap the xxHash into another struct, FShaderHash. This doesn’t change the behavior right now but will make it easier to change the hash algorithm again in the future if an even faster is needed without changing the code in many different places.
Fixed a compile error for non-editor builds: That was an oversight on my sight. I had only tested my change in an editor build, mainly because my original profiling was also done in editor. I might need to add editor builds to my growing list of pre-pull-request-check-list in the future.
And that was it. If you enjoyed this article and want to read more about game optimization in the future consider following me on BlueSky, Mastodon or Linkedin where I post all my articles. Or subscribe directly to my Blog right below the article.
Leave a Reply