ASP-based solver: unique objects for reused specs by alalazo · Pull Request #39590 · spack/spack

alalazo · 2023-08-23T15:20:24Z

Reused specs used to be referenced directly into the built spec.

This might cause issues like in #39570 where two objects in memory represent the same node, because two reused specs were loaded from different sources but referred to the same spec by DAG hash.

Here the issue is solved by registering the concrete specs to be reused in a container that ensures their consistency.

lib/spack/spack/solver/asp.py

haampie · 2023-10-16T14:51:19Z

lib/spack/spack/solver/asp.py

+            return False
+
+        # Unify objects in the container
+        for edge in reversed(spack.traverse.traverse_edges_topo([spec], direction="children")):


why edges / double loop / topo order?

fyi: if the goal is to early exit on sub-dag added before, don't use topo order, cause it has to traverse the full dag to order things :) so, just use dfs and don't recurse into children already added (so, use a visitor directly cause an iterator can't be stopped from recursing; if that's too verbose, do recursion or keep a stack)

why edges?

Cause I forgot to update this function

if the goal is to early exit on sub-dag added before

No, the goal is to unify object for subdags added before - similarly to a roundtrip to-from DB. That unifies the 2 Python objects with the same DAG we have in memory.

Can you do early exit though? It doesn't make sense to iterate over everything and skip every node from each subdag seen before.

I mean, you must do this. Your current implementation effectively copies a database in O(n^2) time.

Actually, ReusableSpecsByHash is rather wasteful, it always copies everything.

By design daghash(x) == daghash(y) => id(x) == id(y) for all x and y from the same database. So the issue is just about merging databases (and adding small number of specs from say spec.json files).

So, why not duplicate only dependents of specs that occur in multiple databases? There's already a dictionary of dag hashes per db.

haampie

Let's avoid copies of all specs from all databases, and instead exploit the invariant that each database has one spec instance per unique dag hash -- if there are two databases A and B, it's only necessary to copy those nodes that are unique to A but have dependencies in common with B.

alalazo · 2023-10-16T17:05:24Z

I'll look into that optimization, but for reference this is what I get with:

Spack: 0.21.0.dev0 (ef06f0d)
Python: 3.11.5
Platform: linux-ubuntu20.04-icelake
Concretizer: clingo

after adding:

$ spack mirror add v0.20.1 https://binaries.spack.io/v0.20.1

develop: 10999c0
PR: ef06f0d

radiuss-pr.csv
radiuss-develop.csv
radiuss.txt

and that is the reason why this implementation seemed viable. I'll try with a bigger buildcache (more traversal and copies) and see what I get.

haampie · 2023-10-16T17:43:11Z

sure, but these things add up over time, so why not implement it efficiently from the start, if that's not difficult to achieve.

At the very least, make it linear time...

haampie · 2023-10-17T09:35:22Z

notice: BinaryCacheIndex._mirrors_for_spec is a mapping from dag hash -> list of mirrors, so it should be rather trivial to "dedupe" specs.

alalazo · 2023-10-17T12:19:12Z

I implemented an explicit visitor. With that, using:

Spack: 0.21.0.dev0 (34b99e3)
Python: 3.11.5
Platform: linux-ubuntu20.04-icelake
Concretizer: clingo

with a setup like:

$ spack mirror add v0.20.1 https://binaries.spack.io/v0.20.1
$ spack mirror add E4S https://cache.e4s.io

develop: 348e5cb
PR: 34b99e3

radiuss-develop.csv
radiuss-pr.csv
radiuss.txt

The case of ascent, where develop is slower, seems to be some transitory issue - repeating the concretization on that leads to similar times in both the PR and develop. Overall, I wouldn't complicate the code further to optimize the tiny difference in the setup phase.

haampie · 2023-10-17T12:37:06Z

Hm okay. The current implementation is roughly equivalent to db = Database(); for x in xs: db.add(x) ; reusable_specs = db.query_local(). Wouldn't that be simpler than?

alalazo · 2023-10-17T12:45:42Z

Wouldn't that be simpler than?

Yes, I looked into that as a first approach, but wouldn't that require to have a temporary DB on the filesystem? This one doesn't.¹

I agree though that the code should be consolidated at some point, among all the various flavors of "DBs" ↩

Reused specs used to be referenced directly into the built spec. This might cause issues like in spack#39570 where two objects in memory represent the same node, because two reused specs were loaded from different sources but referred to the same spec by DAG hash. Here the issue is solved by registering the concrete specs to be reused in a container that ensures their consistency.

Since the test is brittle, just add the spec to a temporary store

haampie · 2023-10-19T11:31:40Z

lib/spack/spack/test/concretize.py

    assert spack.solver.asp._is_checksummed_version((v, v_opts)) == checksummed
+
+
+class TestConcreteSpecsByHash:


why is this a class?

Just to group tests for the ConcreteSpecsByHash class. This can be used during development:

$ spack unit-test lib/spack/spack/test/concretize.py::TestConcreteSpecsByHash

to run all related unit tests.

all as in one, but sure ;p

lib/spack/spack/test/concretize.py

Reused specs used to be referenced directly into the built spec. This might cause issues like in issue 39570 where two objects in memory represent the same node, because two reused specs were loaded from different sources but referred to the same spec by DAG hash. The issue is solved by copying concrete specs to a dictionary keyed by dag hash.

spackbot-app bot added the core PR affects Spack core functionality label Aug 23, 2023

This comment was marked as outdated.

Sign in to view

alalazo requested a review from tgamblin August 23, 2023 15:24

alalazo force-pushed the bugfix/double-python branch from 156e802 to a8e99c7 Compare August 24, 2023 13:46

spackbot-app bot added stand-alone-tests Stand-alone (or smoke) tests for installed packages tests General test capability(ies) labels Aug 24, 2023

alalazo commented Aug 24, 2023

View reviewed changes

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

This comment was marked as outdated.

Sign in to view

alalazo force-pushed the bugfix/double-python branch from a8e99c7 to 7f8c44a Compare October 16, 2023 14:39

alalazo changed the title ~~ASP-based solver: reconstruct edges for reused specs~~ ASP-based solver: unify spec objects for reused specs Oct 16, 2023

alalazo requested a review from haampie October 16, 2023 14:44

haampie reviewed Oct 16, 2023

View reviewed changes

haampie changed the title ~~ASP-based solver: unify spec objects for reused specs~~ ASP-based solver: unique objects for reused specs Oct 16, 2023

haampie requested changes Oct 16, 2023

View reviewed changes

alalazo mentioned this pull request Oct 16, 2023

Use string representation of deptypes for concrete specs #40566

Merged

alalazo force-pushed the bugfix/double-python branch from ef06f0d to 1970a6f Compare October 17, 2023 07:03

alalazo requested a review from haampie October 17, 2023 12:30

tgamblin added this to the v0.21.0 milestone Oct 17, 2023

tgamblin assigned alalazo Oct 17, 2023

tldahlgren assigned haampie Oct 17, 2023

alalazo force-pushed the bugfix/double-python branch from 34b99e3 to 16b3a2f Compare October 18, 2023 18:41

alalazo added 3 commits October 18, 2023 22:39

Remove variable not needed since spack#37584

5d7e23a

Add unit-test

ce41d1f

alalazo added 3 commits October 18, 2023 22:39

Iterate on nodes

b7b38fe

Use a visitor explicitly to skip already registered nodes

6f82fa1

Fix a test mocking the wrong internal functions

c4d84b5

Since the test is brittle, just add the spec to a temporary store

alalazo force-pushed the bugfix/double-python branch from 16b3a2f to c4d84b5 Compare October 18, 2023 21:15

alalazo added 2 commits October 19, 2023 12:15

Simplify implementation by dropping visitor

b13d800

Add unit-tests for the new class

e7d7210

haampie reviewed Oct 19, 2023

View reviewed changes

lib/spack/spack/test/concretize.py Outdated Show resolved Hide resolved

Address request

bfc3d5e

haampie approved these changes Oct 19, 2023

View reviewed changes

haampie merged commit a1ca1a9 into spack:develop Oct 19, 2023

alalazo deleted the bugfix/double-python branch October 19, 2023 14:09

alalazo mentioned this pull request Nov 15, 2023

Introduce a class to represent a "closed set of concrete specs" #40636

Closed

		assert spack.solver.asp._is_checksummed_version((v, v_opts)) == checksummed


		class TestConcreteSpecsByHash:

Conversation

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

Uh oh!

Uh oh!

This comment was marked as outdated.

Uh oh!

This comment was marked as outdated.

haampie Oct 16, 2023 • 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!

haampie Oct 16, 2023 • 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 Oct 16, 2023 • 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 Oct 16, 2023

Choose a reason for hiding this comment

Uh oh!

haampie Oct 16, 2023 • 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!

haampie Oct 16, 2023

Choose a reason for hiding this comment

Uh oh!

haampie Oct 16, 2023 • 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!

haampie left a comment

Choose a reason for hiding this comment

Uh oh!

alalazo commented Oct 16, 2023

Uh oh!

haampie commented Oct 16, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

haampie commented Oct 17, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alalazo commented Oct 17, 2023

Uh oh!

haampie commented Oct 17, 2023

Uh oh!

alalazo commented Oct 17, 2023

Footnotes

Uh oh!

haampie Oct 19, 2023

Choose a reason for hiding this comment

Uh oh!

alalazo Oct 19, 2023 • 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!

haampie Oct 19, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

alalazo commented Aug 23, 2023 •

edited

Loading

haampie Oct 16, 2023 •

edited

Loading

haampie Oct 16, 2023 •

edited

Loading

alalazo Oct 16, 2023 •

edited

Loading

haampie Oct 16, 2023 •

edited

Loading

haampie Oct 16, 2023 •

edited

Loading

haampie commented Oct 16, 2023 •

edited

Loading

haampie commented Oct 17, 2023 •

edited

Loading

alalazo Oct 19, 2023 •

edited

Loading