Skip to content

Circular dependency checker can be slow #65

Open

Description

@vbraun

Angular runs circular-dependency-plugin on each incremental build, so speed is somewhat important

On a largeish hybrid app with complicate imports (in particular, the angularjs part doesn't use modules / barrel files, so the import graph is pretty complicated) a no-change incremental build is about 8s with and 3s without circular dependency checking on a state of the art desktop.

Initially reported at angular/angular-cli#19794

There is a PR languishing at #49, but Tarjan's algorithm is also suboptimal for detecting whether there is a cycle (however it is a good algorithm for enumerating all cycles).

See also: https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

Activity

  1. hedgepigdaniel commented on Dec 15, 2021

    @hedgepigdaniel
    Contributor

    Tarjan's algorithm is also suboptimal for detecting whether there is a cycle (however it is a good algorithm for enumerating all cycles).

    It's linear in the number of modules + dependencies. Can you do better than that to find if a cycle exists?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions