search

bazel-contrib / bazel-gazelle

Gazelle is a Bazel build file generator for Bazel projects. It natively supports Go and protobuf, and it may be extended to support new languages and custom rule sets.
Apache License 2.0
1.21k stars 381 forks source link

perf: walk workspace directories in parallel #1893

Closed jbedard closed 2 months ago

jbedard commented 3 months ago

What type of PR is this? Other

What package or component does this PR mostly affect? all

What does this PR do? Why is it needed?

Walk the bazel workspace fs directories in parallel to build a structure representing the workspace before invoking the gazelle phases.

Similar to https://github.com/bazelbuild/bazel-gazelle/pull/1820 from @dzbarsky including using the same a simplified pathTrie struct but using a simple custom walkDir method instead of introducing a new external dep.

Which issues(s) does this PR fix?

Fixes #1819 Closes #1820

dzbarsky commented 3 months ago

Thanks @jbedard for running with https://github.com/bazelbuild/bazel-gazelle/pull/1820 and getting it to a state where it will hopefully be acceptable. I've confirmed that this has subtantially the same performance as the original PR (except for the Configure2 bit, which we can submit separately). The parallelization is indeed important, it's roughly a 2x speedup for our repo.

In addition, Jason and I have discussed how this opens up the path to potentially reading BUILD files in the initial traversal, which can parallelize additional work as well as allow to respect exclude directives during the parallel walk.

Interestingly enough, when I profile the approach here compared to fastwalk, I am seeing that fastwalk reimplemented os.Readdir in a faster way, and that's responsible for around .6s of our 4s runtime, i.e. 15%. However, fastwalk appears to spend more time in contention/orchestration of goroutines than the errgroup approach, so the overall runtime is around the same. Potentially os.Readdir can be further optimized in upstream Go stdlib.

dzbarsky commented 2 months ago

@tyler-french wdyt of this approach? We have been trying to land this perf improvement in one shape or another for months now

jbedard commented 2 months ago

@fmeum have you had a chance to look into this and compare with the original PR from @dzbarsky?

alandonham commented 2 months ago

@tyler-french wdyt of this approach? We have been trying to land this perf improvement in one shape or another for months now

I'm also interested to see some movement on this PR. I'm working with some rather large repositories, and these changes should solve some of the performance bottlenecks I've been investigating.

DavidZbarsky-at commented 2 months ago

We wanted to double-check the perf numbers. Here's what I see on Airtable's repo:

No parallel walk:

image

fastwalk implementation from #1820

image

This PR's parallel walk:

image

So this PR is roughly similar to fastwalk, maybe a little faster, and much simpler. Looks like 15% speedup overall on our repo. Let's merge it!

jbedard commented 2 months ago

LGTM, should I merge (PR is marked as draft)?

I wanted to double check the improvements were still the same as when we last measured. Looks like @DavidZbarsky-at has confirmed it's still 15% with his tests 👍