quilc icon indicating copy to clipboard operation
quilc copied to clipboard

Clean up `lscheduler-walk-graph`

Open ecpeterson opened this issue 6 years ago • 1 comments
trafficstars

The current implementation of this function was written under time pressure and could stand to be cleaned up. For example, using an actual queue would let us write the function much closer to how a breadth-first search / topological sort is typically done, which is likely to save on runtime as well as conceptual overhead.

Clean-up might also allow for early termination: it's likely that lscheduler-instruction-tiers needs only to be run out to some small depth for the greedy addresser to work, and that this savings would be significant when compiling longer programs. The current implementation of lscheduler-walk-graph is not written in a way that supports this.

ecpeterson avatar Feb 08 '19 21:02 ecpeterson

Just to add here: I think PR "reimplement logical-scheduler walker more efficiently #741" partially addresses this issue, as it was a cleanup of lscheduler-walk-graph and is written "much closer to how a breadth-first search / topological sort is typically done". Not sure about the "actual queue" part. And it does not allow for early termination.

ghost avatar Nov 10 '21 01:11 ghost