Skip to content

Speed up topsort in parsing #133

Closed
Closed
@masinag

Description

@masinag

Currently the parser uses the toposort_flatten from the toposort library

for lit in toposort_flatten(state.nodes):

However, I noticed that this really slows down the parsing of files with many gates, e.g. this file.

After some investigation, I noticed that the implementation of topsort in the toposort library is very inefficient, as it is O(n^2) instead of O(n+m).
https://gitlab.com/ericvsmith/toposort/-/blob/master/src/toposort.py#L47

I suggest using the graphlib library, it should be enough to replace the above line with:

    for lit in graphlib.TopologicalSorter(state.nodes).static_order():

What do you think?

Activity

mvcisback

mvcisback commented on Dec 12, 2023

@mvcisback
Owner

thanks for looking into this. Would you be open to creating a PR?

masinag

masinag commented on Dec 12, 2023

@masinag
ContributorAuthor

I found out that graphlib is supported only since python 3.9, I'm looking for an alternative

masinag

masinag commented on Dec 12, 2023

@masinag
ContributorAuthor

I can implement a simple topsort function instead of relying on an external library, what do you think?
It shouldn't be longer than 10-15 sloc

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

        Participants

        @mvcisback@masinag

        Issue actions

          Speed up topsort in parsing · Issue #133 · mvcisback/py-aiger