@spackbot run pipeline

I've started that pipeline for you!

@haampie and I talked about this and the one remaining nit is that BFS will produce a somewhat unintuitive display of dependencies -- i.e. you aren't guaranteed that the line above any node you look at is that node's parent.

@haampie is going to look into whether we can tweak the vis code slightly to handle this, since there are lot of advantages to BFS, but I think we still want clear connections bt/w nodes in the tree output. I think it'll be a way better tree if you're guaranteed to see each node's undiscovered children at each level and you're guaranteed that nodes shown at a given level of indentation are children of the first outdented thing above them.

cover = nodes, depth vs breadth first in tree(...):

cover = edges, depth vs breadth first in tree(...):

I like the new version better -- it presents things higher up when it can and the parent/child relationships are real ones. LGTM!

You can see:

• perl pulled from depth 3 -> 2
• xz pulled from depth 4 -> 3
• readline pulled from depth 5 -> 3
• m4 pulled from depth 3 -> 2
• diffutils pulled from depth 5 -> 3
• libiconv pulled from depth 6 -> 2
• etc.

It's more compact and easier to read IMO

The other kind of cool thing about this is that you could add a depth argument/default to spack spec, and things left over after pruning would be the most important ones in a much more real sense than before, since now we're displaying at min depth of the node, not depth in a particular traversal.

Closed / reopen to trigger a new merge commit without changing history in the branch. Fix in #33429 should get us past the previous CI error.

@tgamblin one key (pun intended) difference between current dfs logic and bfs is that the former defaults to unique on id whereas the latter uses spec.dag_hash. As far as I can see, there's no real issue with dag_hash by default, as it exists for non-concrete specs, and the dag_hash logic does not depend on spec.traverse(...) but has its own logic and recursion. The advantage of sticking to dag_hash is that you can load two root specs from the filesystem and print the dag where their common deps are not duplicated.

@spackbot run pipeline

I've started that pipeline for you!

Hm, can readthedocs be re-triggered? Otherwise code coverage looks good now.

Not in this PR, but when feeding environment root specs to the BFS and outputting a tree, you can get these kinds of concretizer outputs (no duplication of python, and as shallow output as possible):

I think @adamjstewart would appreciate that ;p

I like this a lot. I always check the DAG to see what version of Python I'm building with but it's always buried somewhere in a deep tree even though it's a direct dependency.

@haampie:

As far as I can see, there's no real issue with dag_hash by default, as it exists for non-concrete specs, and the dag_hash logic does not depend on spec.traverse(...) but has its own logic and recursion. The advantage of sticking to dag_hash is that you can load two root specs from the filesystem and print the dag where their common deps are not duplicated.

Logically, I don't see a problem with using dag_hash by default. It is probably the most sensible thing for reasons you mentioned above. Could tree() just ask for it though, instead of making it the default? I think it is better in the code, at least if both traversals have the same defaults. See comment in review below about making the two traversals consistent.

There are a few other considerations to think about, most of which don't have anything to do with tree()... but they'll matter if we do more with BFS:

1. id is really there for the tests, and because it's fast. The tests use it to make sure we're not building crazy graphs with duplicated nodes. If you can guarantee that, then you don't have to care about dag_hash and you can do fast id comparisons.
2. Historically, we didn't use dag_hash() because it hashed YAML, and it was very expensive to generate the YAML. Now that we use json, it's way faster, but also much slower than asking for id, especially for abstract specs. There are really two places where this stuff matters:
   a. Loading package files: parsing all the directives in packages involves putting lots of little tiny specs in dictionaries and comparing them. It is probably not good if we have to hash json for those comparisons, but see the TODO and comment at https://github.com/spack/spack/pull/32516/files#diff-9e28cdd6f9cd66e61101de6e9d22b1c33561959e4305c63147bbfbf7b22da936R4071-R4080. It would be nice to consolidate the dag_hash and __hash__ logic.
   b. Sorting large databases: If we compare specs like graphs, traversal needs to be fast. See specs: use lazy lexicographic comparison instead of key_ordering #21618. Then again, @alalazo removed sorting on query here: https://github.com/spack/spack/pull/30806/files#diff-751ae3f6692a00d628a34b4729c3ca2f8a5bbead2b18d8c6c5314e4e7da2c193L1530-R1535, and I think that's likely the right thing to do -- just avoid major traversals when comparing concrete specs and compare by attributes the client code actually cares about instead of imposing a total order.
3. dag_hash() exists for abstract specs but it is not cached for them. I wonder if that will affect performance (particularly in 2a above).
4. The two root specs thing seems nice, semantically. Should we need it though? I guess right now we probably do. But it makes me want to make the spec implementation immutable, at least for concrete specs. I think Specs with the same hash should probably also be the same object... eventually. That may make things difficult if we ever have to deal with specs that get the same hash for bad reasons, though.

@tgamblin I've consolidated the depth/breadth first traversal in a single generator now:

spack.traverse.traverse_edges([spec_a, spec_b], order="pre/post/breadth")

with the usual kwargs. The key function and visited set can now also be passed to be compatible with what we had. Note that it takes a list of specs; so s.traverse_edges(...) is implemented as traverse_edges([self], ...).

I'm quite happy with the implementation, especially now that the cover/direction logic is extracted to visitors and reused in both traversal orders.

Two comments:

1. One big concern I have though, when moving from key=lambda s: s.dag_hash() to key=id to be compatible, one of my BFS tests failed, the reason being that I used something along the lines of:

   # Get two roots:
   x = Spec("x").concretized()
   y = x["y"]
   
   traverse_edges([x, y], order="breadth", cover="nodes")

   And this traverses the edge from x -> y because id(x) != id(y), since indexing a spec yields an object that looks like a Spec, but it's really SpecBuildInterface.

   So, I would strongly suggest to avoid id cause the bug is so subtle, instead we should default to key= lambda s: s.dag_hash().

2. Not sure what the prettiest interface is for generating trees. spack.traverse.traverse_edges([s], order="pre", cover="nodes") "just happens" to generate edges in a favorable order. But spack.traverse.traverse_edges([s], order="breadth", cover="nodes") does not. Should I add say spack.traverse.tree([s], ???) that dispatches to traverse_edges for DFS and something more advanced for BFS? What's a nice API? For example it wouldn't make sense to be able to pass spack.traverse.tree([s], order="post") so the API should be different.

Edit: solved 2 by creating a small helper traverse_tree that returns an appropriate generator.

Regarding the performance, here are some details regarding concrete specs (I also checked they were doing the same thing). This is on a database with 485 specs.

import spack.store
specs = spack.store.db.query()
%timeit [[x.name for x in s.traverse(...)] for s in specs]

develop order=pre

cover=nodes
59.1 ms ± 261 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

cover=edges
66.6 ms ± 97.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

cover=edges, key=lambda s: s.dag_hash()
76.8 ms ± 94.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

PR order=pre

cover=nodes
44.6 ms ± 115 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

cover=edges
50.7 ms ± 60.3 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

cover=edges, key=lambda s: s.dag_hash()
62.1 ms ± 310 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

PR order=breadth

order=breadth, cover=nodes
38.8 ms ± 84.1 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

order=breadth, cover=edges
41.1 ms ± 333 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

order=breadth, cover=edges, key=lambda s: s.dagh_hash()
49.7 ms ± 259 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

PR order=pre without edge sort

cover=nodes
44.1 ms ± 689 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

covers=edges
48.9 ms ± 353 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Somewhat unexpectedly, breadth first iteration is faster, maybe function call overhead / recursion in Python is slow? And overall I think the improvements in this PR compared to develop are thanks to moving logic into visitors, so we simply have fewer branches during traversal.

Regarding edge sorting: apparently the overhead is very limited, probably because things are typically sorted already?

Finally wrt key=lambda s: s.dag_hash(), I think we can live with that, not a major penalty.

Regarding abstract specs, yeah, there's a huge penalty, I guess it's an extra dag traversal per dag_hash() call?

import random
import string
import spack.spec

def random_str():
    return ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(3, 8)))

def random_variant():
    if random.random() < 0.4:
        return random.choice(('+', '~')) + random_str()
    return random_str() + '=' + random_str()

def random_spec_str():
    components = [random_str()]
    components.extend(random_variant() for _ in range(random.randint(0, 4)))
    return ' '.join(components)

def random_deptype():
    return random.sample(("link", "build", "run", "test"), random.randint(1, 4))

def generate_random_abstract_specs(num_nodes=500, edge_odds=0.1):
    specs = [spack.spec.Spec(random_spec_str()) for _ in range(num_nodes)]
    total_edges = 0
    
    for i in range(num_nodes):
        num_edges = int(random.random() * edge_odds * (num_nodes - i - 1))
        total_edges += num_edges
        for j in random.sample(range(i+1, num_nodes), num_edges):
            specs[i].add_dependency_edge(specs[j], deptype=random_deptype())
    
    return specs, total_edges

And then for example, generating a dag with a 100 nodes and 192 edges:

In [1]: specs, edges = spack.spec.generate_random_abstract_specs(100, 0.1)

In [2]: %timeit [[x.name for x in s.traverse(order='breadth', cover='edges', key=lambda s: s.dag_hash())] for s in specs]
95 ms ± 809 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %timeit [[x.name for x in s.traverse(order='breadth', cover='edges')] for s in specs]
2.37 ms ± 7.34 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Finally, actually dumping a tree for each concrete spec in the database:

In [12]: %timeit [s.tree(depth_first=True) for s in specs]
1.05 s ± 5.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [13]: %timeit [s.tree(depth_first=False) for s in specs]
1 s ± 9.27 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

I also noticed there's an amazing O(n^2) string concat issue here, lots of str += ... in tree.

Final comment before next round of reviews: I think it's good to leave the PR as is, with the original key=id default and edge sorting. I think changing the key may lead to unforeseen issues and edge sorting like this has been in place for a long time, and doesn't seem to be performing terribly bad (also: python promises stable sort, so if we just sort by pkg name, the edge type stays in original order anyways).

I also noticed there's an amazing O(n^2) string concat issue here, lots of str += ... in tree.

This seems maybe worth fixing in some later PR (though it's likely not bottlenecking anything at the moment)