[engine] Walk references in the ProductGraph
Review Request #3803 — Created May 1, 2016 and submitted
With caching disabled (will revisit in a future review), the majority of the runtime for
./pants list ::with the new engine was in cycle detection. After attempting to implement a smarter cycle detection algorithm
, it became obvious that the actual cost of walking was the dominant factor.
This review replaces the internals of ProductGraph with
_Entryobjects that directly reference one another. This avoids executing dict lookups (and thus a lot of
Nodeequality checks) during graph walks.
- Add explicit tests of cycle detection.
- Move from multiple defaultdicts to a non-default dict of
_Entryobjects and walk the graph directly by
_Entryreference, which avoids a lot of dict lookups (~20% improvement).
- Switch from recursion to iteration for graph walk (~6% improvement).
- Enable some default filters in
With caching disabled, the runtimes for
time ./pants -q run src/python/pants/engine/exp/legacy:fsnodes -- //:: > /dev/null were:
master: real 0m22.143s user 0m19.913s sys 0m1.914s complex algorithm (with reference walking): real 0m22.874s user 0m20.438s sys 0m2.078s this review (simple algorithm, with reference walking): real 0m17.940s user 0m15.944s sys 0m1.847s
: I was able to get that algorithm solidly working, but in addition to being more complicated, the extra overheads meant that (at least for the content of the
pantsbuild/pants repo) it was significantly slower than the naive
m^2 approach. For posterity, the implementation is tagged here.
lgtm! handful of misc comments.
assuming the default object equality is identity based anyway, could this be made clearer with an explicit
how about making the
all_predicatefunction signature default the second arg e.g.:
def all_predicate(node, state=None): return True
and reusing that here?
maybe these definitions should happen under if branches to avoid potentially unnecessary function definition overhead?
if predicate: def entry_predicate(...): return predicate(...) else: def entry_predicate(...): ...default case...
quick micro-optimization: use object literals where possible for initial creation (e.g.
root_entries = ) - they're 2-3x faster:
[illuminati source (master)]$ python -m timeit -n 10000 "x = " 10000 loops, best of 3: 0.0245 usec per loop [illuminati source (master)]$ python -m timeit -n 10000 "x = list()" 10000 loops, best of 3: 0.0888 usec per loop
Revision 3 (+196 -150)