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

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).

Environment

None

Activity

Show:
Andy Fingerhut
June 3, 2014, 9:18 PM

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

Andy Fingerhut
June 3, 2014, 9:20 PM

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).

Stuart Sierra
June 6, 2014, 4:27 PM

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 ?

Stuart Sierra
July 11, 2014, 10:42 PM

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.

Stuart Sierra
September 19, 2014, 3:08 PM

Included in release 0.2.6

Completed

Assignee

Stuart Sierra

Reporter

Andy Fingerhut

Labels

None

Approval

None

Patch

Code

Priority

Major