Allow for multiple dependencies/dependents from the same package by alalazo · Pull Request #28673 · spack/spack

alalazo · 2022-01-29T17:10:08Z

fixes #11983
closes #16447

same as #21683 which I cannot reopen after a force push for some reason

This PR changes the internal representation of Spec to allow for multiple dependencies or dependents stemming from the same package. This change permits to represent cases which are frequent in cross compiled environments or to bootstrap compilers.

Modifications:

Substitute DependencyMap with _EdgeMap. The main differences are that the latter does not support direct item assignment and can be modified only through its API. It also provides a select_by method to query items.
Reworked a few public APIs of Spec to get list of dependencies or related edges.
Added unit tests to prevent regression on Incomplete computation of installed dependents #11983 and prove the synthetic construction of specs with multiple deps from the same package.

Since #22845 went in first, this PR reuses that format and thus it should not change hashes. What happens is that in the list of dependencies we may have the same package being present multiple times with different associated specs.

becker33

Mostly LGTM

becker33 · 2022-02-03T00:16:55Z

lib/spack/spack/graph.py

-    Return a list of dependency specs sorted topologically.  The spec
-    argument is not modified in the process.

+def topological_sort(spec, deptype='all'):


This function could use some comments

Should be fixed in 950f436

becker33 · 2022-02-04T06:19:16Z

lib/spack/spack/spec.py

+        original_spec = getattr(spec, 'wrapped_obj', spec)
+        self.wrapped_obj = original_spec
+        self.token = original_spec, name, query_parameters


Should this logic be pushed into lang.ObjectWrapper? It seems like it would apply to any object that cares about it's id, so we could use __getattr__ and __getitem__ to make sure methods are called on the wrapped object.

Hmm, I need to think about that. I think __getattr__ wouldn't work since the way we create a wrapper object is to fake the class name and share the __dict__ object:

spack/lib/spack/llnl/util/lang.py

Lines 742 to 747 in c791ddc

if type(self) not in wrapped_cls.__mro__:

self.__class__ = type(wrapped_name, (type(self), wrapped_cls), {})

else:

self.__class__ = type(wrapped_name, (wrapped_cls,), {})

self.__dict__ = wrapped_object.__dict__

We can probably create though a better API to say that a method should be forwarded to the real object.

becker33

I think this is ready to go, but I'm a little nervous that we could be missing something.

balay

Approving petsc/package.py change [checked a couple of builds - they go through fine]

tgamblin

Ok I have two main things here:

Can you check the performance of this implementation? With something like spack buildcache list where we have to construct and sort a lot of specs? I am worried that the edge structures are going to be too complicated and that we'll run into issues with large build caches. If there's no noticeable slowdown then I think that's fine, but it would be good to know b/c this is a major change to a core data structure. I made a few comments inline to this effect.
The interface for accessing dependencies here seems awkward in places. I get why there are both edges_from _dependents(name) and edges_to _dependencies(name), for symmetry, but essentially every place we ask for a dependency by name, there is going to be one element in that list. The dependencies case (where there will only be one) is far more common than the dependents case (where we have to think about multiple). So I think the interface should not be the same for these.

I think there should be a way to get the single edge with, e.g., edge_to_dependency(name) (which should fail with an assertion error if there are multiple), and edges_from _dependents should probably not take a name argument. I don't think this leaks out of spec.py too much -- the dicts with list values are mostly hidden in the details of _EdgeMap, but there were places where I found the code harder to follow and had to think about the lists in _EdgeMap when they did not matter at all - that was hard to read.

lib/spack/spack/dependency.py

lib/spack/spack/spec.py

tgamblin · 2022-02-19T07:51:52Z

lib/spack/spack/spec.py

+
+        return clone
+
+    def select_by(self, parent=None, child=None, dependency_types='all'):


dependency_types should be renamed to deptypes, because we call it that in every other place it's used as an argument.

I slightly disagree with that. We call them both deptype and deptypes and we had bugs because of the two similar spellings¹. Writing the full name in my opinion helps avoiding these kind of issues.

Footnotes

Actually looking again at the code base there are more bugs than I caught in the past. I'll submit a separate PR to fix them. See for instance this call: https://github.com/spack/spack/blob/1ddad522a4b1527d337bfface0a62b26b8520347/lib/spack/spack/package.py#L1192
where deptypes gets forwarded to this other method:
https://github.com/spack/spack/blob/1ddad522a4b1527d337bfface0a62b26b8520347/lib/spack/spack/spec.py#L1350
that gets a deptype (without s) instead. ↩

I think we should standardize on deptypes here and fix the other occurrences in the separate PR

See #29397 and f99c721

lib/spack/spack/spec.py

lib/spack/spack/solver/asp.py

lib/spack/spack/graph.py

becker33 · 2022-02-22T21:06:51Z

For Todd's point (2), we need the dependency edge information for when we split build dependencies for cross-compilation. It's not possible yet, and it won't be in the first separate concretization of build deps PR, but we will need that eventually. I think that's a good enough reason to keep this now, since we'll need it in the long run.

alalazo · 2022-02-23T07:56:27Z

we need the dependency edge information for when we split build dependencies for cross-compilation.

I agree with @becker33 That is one of the point why we have this PR, to allow splitting edges for the same dependency if need be. A prominent example would be python being a (build,run) dependency in a cross-compilation environment.

Also, the common case - the one where we have a single dependency - should be covered by __getitem__:

dep = root[dep_name]

tgamblin · 2022-02-23T08:27:25Z

Ok, yes you guys are right -- when we properly handle cross-compilation and can split a dependency node between build and link/run environments, we'll care about this. So for point 2 above, yeah, let's keep the interface symmetric.

I guess right now, root[dep_name] will give you the link dependency if there happen to be two with the same name, which I guess is the right thing to do here. I guess we can make the indexing fancier if we want later -- e.g., root[dep_name, 'build'] if we really have to refine it.

tgamblin · 2022-02-23T08:47:16Z

Ok updated the review and resolved the points around multiple edges to dependencies.

lib/spack/spack/solver/asp.py

alalazo · 2022-02-23T09:32:22Z

From a fresh clone of Spack, setting up the instance with these commands:

$ spack solve zlib
$ spack mirror add E4S https://cache.e4s.io
$ spack buildcache keys -it
==> Fetching https://cache.e4s.io/build_cache/_pgp/25645FA2B218FE55B4EF649E4345F04B40005581.pub
gpg: key 4345F04B40005581: public key "University of Oregon - E4S" imported
gpg: Total number processed: 1
gpg:               imported: 1
gpg: inserting ownertrust of 6

and running on:

Spack: 0.17.1-1343-455fd15e86
Python: 3.8.10
Platform: linux-ubuntu20.04-icelake
Concretizer: clingo

This is the timing I obtain on this branch:

$ time spack buildcache list
==> 0 cached builds.
==> You can query all available architectures with:
  spack buildcache list --allarch

real	1m8,325s
user	1m5,968s
sys	0m0,399s

$ time spack buildcache list --allarch
[ ... ]
real	1m13,419s
user	1m10,911s
sys	0m0,453s

On develop:

$ time spack buildcache list
==> 0 cached builds.
==> You can query all available architectures with:
  spack buildcache list --allarch

real	0m51,076s
user	0m38,516s
sys	0m0,918s

$ time spack buildcache list --allarch
[ ... ]
real	0m52,793s
user	0m50,168s
sys	0m0,424s

so it seems there's a ~15-20% increase in time for this call.

tgamblin · 2022-02-23T09:50:04Z

Can you profile it with pyinstrument? When I've looked at this in the past it was very sensitive to canonicalizing dependencies in too many places (as that happens a lot as part of traversal). I'm suspicious of that and maybe the new list structure -- but moreso the canonicalizing.

tgamblin · 2022-02-23T09:51:25Z

Also another way to benchmark this that's faster than waiting for buildcache list is to concretize a large spec, save it as json, then run pyinstrument on a script that just loads it and traverses it a hundred (maybe a few hundred?) times.

I tend to run pyinstrument like this, to show everything:

python3 -m pyinstrument --show-all --hide zzz $(which spack) help

--hide zzz overrides the somewhat annoying default hide settings it has -- which apparently are not overridden by --show-all

alalazo · 2022-02-23T11:29:01Z

With c19ef50 I have this profiling buildcache_list.spy.txt obtained with:

$ py-spy record -f speedscope -o buildcache_list.spy -s -n $(which spack) buildcache list

It can be seen at https://www.speedscope.app/ It seems we spend a lot of time (for what this PR is concerned) in the comparisons at:

spack/lib/spack/spack/spec.py

Line 826 in c19ef50

if edge.spec == dep.spec and edge.parent == dep.parent:

If I read the profiling data correctly canonicalizing doesn't have a major impact for the command above.

alalazo · 2022-03-07T18:02:29Z

lib/spack/spack/spec.py

+        for edge in selected:
+            if id(dependency_spec) == id(edge.spec):
+                edge.add_type(deptype)
+                return


@tgamblin ~~I still need to update this part, to do the symmetric operation on the parent It seems though we have no test that detected this.~~ Ok, it turns out this is correct, since we push the same object into two dictionaries, so when we update the dependency types the other reference sees the update too.

alalazo · 2022-03-08T10:13:37Z

@tgamblin From what I can see locally the timing of this branch is now more in line with develop. On 43bd292 I got:

$ time spack buildcache list
==> 0 cached builds.
==> You can query all available architectures with:
  spack buildcache list --allarch

real	0m47,115s
user	0m44,382s
sys	0m0,356s

$ time spack buildcache list --allarch
[ ... ]
real	0m50,916s
user	0m48,500s
sys	0m0,429s

while on `develop:

$ time spack buildcache list
==> 0 cached builds.
==> You can query all available architectures with:
  spack buildcache list --allarch

real	0m46,886s
user	0m44,530s
sys	0m0,380s

$ time spack buildcache list --allarch
[ ... ]
real	0m44,941s
user	0m42,481s
sys	0m0,469s

For the record, I am using:

Spack: 0.17.1-1492-43bd292e13
Python: 3.8.10
Platform: linux-ubuntu20.04-icelake
Concretizer: clingo

tgamblin · 2022-03-09T22:07:42Z

lib/spack/spack/spec.py

+        key = edge.spec.name if self.store_by_child else edge.parent.name
+        current_list = self.edges.setdefault(key, [])
+        current_list.append(edge)
+        current_list.sort(key=_sort_by_dep_types)


Note that while this guarantees deterministic dependency traversal order, it doesn't guarantee a deterministic dependent traversal order for the same spec. I do not think that matters currently (we don't hash dependent traversals) but it's worth remembering.

tgamblin · 2022-03-10T19:15:20Z

lib/spack/spack/test/spec_dag.py

+    c2 = Spec('[email protected]').concretized()
+
+    p.add_dependency_edge(c1, deptype=c1_deptypes)
+    with pytest.raises(spack.error.SpackError):


I verified that this raises the right exception but for the future: this test should probably not have the parent and the dependencies as b. If we added cycle checking or something I could see this error getting confused with another.

This is true for a few tests above too

tgamblin · 2022-03-10T19:40:58Z

lib/spack/spack/spec.py

+                raise spack.error.SpecError(msg.format(edge, deptype))
+
+        for edge in selected:
+            if id(dependency_spec) == id(edge.spec):


this should probably be shortened to is but I think we can leave it for now.

tgamblin

I have a few really minor nitpicks above but none of them should impede getting this merged -- they can be follow-ons. LGTM! The new tests and minimal performance hit are great.

sethrj · 2022-03-12T18:55:06Z

@alalazo I think this change is responsible for #29478: installing the exact same python spec with the new spack core fails because link_deps = spec.dependencies('link') seems to evaluate to an empty list now. Is this behavior change expected? What can be done to fix it?

…age (spack#28673)" This reverts commit 2cd5c00.

alalazo · 2022-03-12T21:53:57Z

@sethrj Changes to fix the package:

spec.dependencies(deptype='link')

As it is now it's looking for a dependency named link. Let me submit a PR.

spackbot-app bot added commands tests General test capability(ies) update-package utilities labels Jan 29, 2022

spackbot-app bot requested review from BarrySmith, balay and jedbrown January 29, 2022 17:10

alalazo requested review from becker33, scheibelp and tgamblin January 29, 2022 18:50

becker33 reviewed Feb 4, 2022

View reviewed changes

alalazo force-pushed the features/subscript_api_multiple_nodes_per_package branch from deb51c4 to 950f436 Compare February 7, 2022 15:42

alalazo requested a review from becker33 February 7, 2022 16:56

becker33 previously approved these changes Feb 7, 2022

View reviewed changes

balay previously approved these changes Feb 7, 2022

View reviewed changes

tgamblin mentioned this pull request Feb 8, 2022

Switch to full hash everywhere #28504

Merged

10 tasks

tgamblin requested changes Feb 19, 2022

View reviewed changes

tgamblin mentioned this pull request Feb 21, 2022

Upcoming high-impact changes (perma-pin) #24223

Closed

tgamblin reviewed Feb 23, 2022

View reviewed changes

lib/spack/spack/solver/asp.py Show resolved Hide resolved

alalazo dismissed stale reviews from balay and becker33 via c19ef50 February 23, 2022 11:02

alalazo force-pushed the features/subscript_api_multiple_nodes_per_package branch from 950f436 to c19ef50 Compare February 23, 2022 11:02

alalazo added 4 commits March 7, 2022 10:28

Use public API instead of private attributes for dependencies/dependents

9ed709b

Avoid explicitly nested loop in traverse edges

3fa8855

Add assertion in asp.py to avoid having 2 deps of the same name

8a0ef78

Move edge checks from _EdgeMap.add to Spec

df30e6c

alalazo force-pushed the features/subscript_api_multiple_nodes_per_package branch from 5d77b88 to df30e6c Compare March 7, 2022 15:03

alalazo commented Mar 7, 2022

View reviewed changes

Add two unit-tests to validate the addition of edges

085dcf8

alalazo mentioned this pull request Mar 8, 2022

Rename all the arguments expecting a dependency type to "deptypes" #29397

Open

alalazo added 2 commits March 8, 2022 09:42

Rename "dependency_types" to "deptypes"

f99c721

Reduce the number of calls to dependency.canonical_deptype

43bd292

Remove a redundant sort operation

8d98882

alalazo mentioned this pull request Mar 8, 2022

Allow more fine-grained control over what submodules are updated: part 2 #27293

Merged

tgamblin reviewed Mar 9, 2022

View reviewed changes

tgamblin reviewed Mar 10, 2022

View reviewed changes

tgamblin approved these changes Mar 10, 2022

View reviewed changes

tgamblin merged commit 2cd5c00 into spack:develop Mar 10, 2022

alalazo deleted the features/subscript_api_multiple_nodes_per_package branch March 10, 2022 20:05

dylex mentioned this pull request Mar 11, 2022

broken after multidep spack/spack#28673 flatironinstitute/nixpack#12

Closed

sethrj mentioned this pull request Mar 12, 2022

Installation issue: python+ctypes #29478

Closed

4 tasks

sethrj added the breaking-change label Mar 12, 2022

sethrj added a commit to sethrj/spack that referenced this pull request Mar 12, 2022

Revert "Allow for multiple dependencies/dependents from the same pack…

5bf8a4b

…age (spack#28673)" This reverts commit 2cd5c00.

alalazo mentioned this pull request Mar 14, 2022

Best effort co-concretization (iterative algorithm) #28941

Merged

cgmb mentioned this pull request Mar 15, 2022

update rocm-recipes with master version #28500

Closed

alalazo mentioned this pull request Apr 25, 2022

spack dependents --installed only shows one installed variant of dependent specs #23569

Closed

3 tasks

tgamblin mentioned this pull request Oct 28, 2022

Consolidate DAG traversal in traverse.py, support DFS/BFS #33406

Merged

haampie mentioned this pull request Nov 21, 2022

traverse: add topo #33817

Merged

	if type(self) not in wrapped_cls.__mro__:
	self.__class__ = type(wrapped_name, (type(self), wrapped_cls), {})
	else:
	self.__class__ = type(wrapped_name, (wrapped_cls,), {})

	self.__dict__ = wrapped_object.__dict__


		return clone

		def select_by(self, parent=None, child=None, dependency_types='all'):

Conversation

alalazo commented Jan 29, 2022 • edited by tgamblin Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

becker33 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

becker33 left a comment

Choose a reason for hiding this comment

Uh oh!

balay left a comment

Choose a reason for hiding this comment

Uh oh!

tgamblin left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Footnotes

Uh oh!

tgamblin Mar 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

becker33 commented Feb 22, 2022

Uh oh!

alalazo commented Feb 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tgamblin commented Feb 23, 2022

Uh oh!

tgamblin commented Feb 23, 2022

Uh oh!

Uh oh!

alalazo commented Feb 23, 2022

Uh oh!

tgamblin commented Feb 23, 2022

Uh oh!

tgamblin commented Feb 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alalazo commented Feb 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alalazo Mar 7, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alalazo commented Mar 8, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tgamblin Mar 10, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tgamblin left a comment

alalazo commented Jan 29, 2022 •

edited by tgamblin

Loading

tgamblin left a comment •

edited

Loading

tgamblin Mar 5, 2022 •

edited

Loading

alalazo commented Feb 23, 2022 •

edited

Loading

tgamblin commented Feb 23, 2022 •

edited

Loading

alalazo commented Feb 23, 2022 •

edited

Loading

alalazo Mar 7, 2022 •

edited

Loading

tgamblin Mar 10, 2022 •

edited

Loading

sethrj commented Mar 12, 2022 •

edited

Loading