tree 0d15089640aa8c220b66ac6c04ec2546f7398e3a
parent cca33299a58da23d1040d259ecd32be874ed174c
author nharmata <nharmata@google.com> 1603836112 -0700
committer Copybara-Service <copybara-worker@google.com> 1603836170 -0700

During change pruning, when a parent node notices all its children are done, finish processing that parent node intra-thread rather than enqueue it and have it be processed in the future by a different Skyframe thread.

I discovered this room for improvement myself by running benchmarks with a Blaze binary instrumented with a ton of log statements in the Skyframe engine codebase. I was excited to go work on this commit. But when I started editing the code, I was surprised and happy to see that @ericfelly curiously had added a TODO for exactly this in passing in commit e97bba1 in 2016!

For highly parallel change pruning situations (e.g. N parent nodes each with a single common child node, such that N >> num_skyframe_threads >= num_cores), this avoids the contention of enqueueing each parent node and also is just plain faster since we process the parent node now rather than in the future. On a benchmark of a particularly extreme incremental build situation internally at Google, this increased the change pruning rate by ~175% and decreased overall wall time by ~60%.

The contention mentioned above is between busy Skyframe threads enqueueing more work units (PriorityBlockingQueue#offer) and idle Skyframe threads picking up a work unit (PriorityBlockingQueue#take). It's something that's been on my radar for ~years, and I even have a pending CL to completely remove it. I've never prioritized pushing that CL through because I've never been able to show the contention is obviously causing real problems, and my fix is to implement a low-contention priority queue data structure. Well, this CL here reduces the impact of that contention even more, so maybe I'll never get around to mailing out my new queue code ¯\_(ツ)_/¯

RELNOTES: None
PiperOrigin-RevId: 339337198