tools.namespace

Use linear time algorithm to calculate transitive dependencies, instead of current exponential time algorithm

Details

  • Type: Enhancement Enhancement
  • Status: Resolved Resolved
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code

Description

The function clojure.tools.namespace.dependency/transitive takes exponential time for cases where there are an exponential number of paths in the DAG (directed acyclic graph) of dependencies. I discovered this when using tools.namespace on the namespaces of project core.typed, where the total time for finding a topological order was several minutes on a reasonably fast machine.

It is easy to calculate transitive dependents/dependencies in linear time in the worst case (linear in the number of dependency arcs in the DAG).

Activity

Hide
Andy Fingerhut added a comment -

Patch demo-exponential-algo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.

Show
Andy Fingerhut added a comment - Patch demo-exponential-algo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.
Hide
Andy Fingerhut added a comment -

Patch linear-time-no-debug.patch is one way to implement transitive dependencies in linear time. It also introduces additional protocol functions, which may not be desired. I am definitely open to suggestions on what kind of change you would like to see here (assuming you want any changes at all).

Show
Andy Fingerhut added a comment - Patch linear-time-no-debug.patch is one way to implement transitive dependencies in linear time. It also introduces additional protocol functions, which may not be desired. I am definitely open to suggestions on what kind of change you would like to see here (assuming you want any changes at all).
Hide
Stuart Sierra added a comment - - edited

This is a valuable improvement — thanks, Andy!

I don't want to add more methods to the protocol, but I don't see any way to avoid it right now. Ideally, transitive-dependencies would change to take a set, but that breaks backwards-compatibility.

I'll give it a week or so to think about naming:

  • transitive-dependencies-of-node-set is too long
  • transitive-dependencies-all ?
  • transitive-dependencies-set ?
  • all-transitive-dependencies ?
Show
Stuart Sierra added a comment - - edited This is a valuable improvement — thanks, Andy! I don't want to add more methods to the protocol, but I don't see any way to avoid it right now. Ideally, transitive-dependencies would change to take a set, but that breaks backwards-compatibility. I'll give it a week or so to think about naming:
  • transitive-dependencies-of-node-set is too long
  • transitive-dependencies-all ?
  • transitive-dependencies-set ?
  • all-transitive-dependencies ?
Hide
Stuart Sierra added a comment -

Merged on master as of commit 3f946380. Will be in release 0.2.5.

New functions are named transitive-dependencies-set and transitive-dependents-set.

Show
Stuart Sierra added a comment - Merged on master as of commit 3f946380. Will be in release 0.2.5. New functions are named transitive-dependencies-set and transitive-dependents-set.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: