Skip to content

spack diff has exponential complexity #51253

Closed
#51270
Closed
spack diff has exponential complexity#51253
#51270
Labels
bugSomething isn't workingtriageThe issue needs to be prioritized
@haampie

Description

@haampie
haampie
opened on Aug 31, 2025

Steps to reproduce

spack diff /x /y

recurses through all possible paths, which means worst case O(2^N) complexity for a DAG with N nodes with edges v_i -> v_j if i < j.

This is due to unconditional

spack/lib/spack/spack/solver/asp.py

Lines 2554 to 2560 in 5853eb9

dependency_clauses = self._spec_clauses(
dep,
body=body,
expand_hashes=expand_hashes,
concrete_build_deps=concrete_build_deps,
context=context,
)

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingtriageThe issue needs to be prioritized

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions