Matcher incredibly slow?

zxcalc / quantomatic

Quantomatic is a tool for doing automated graph rewriting.

http://quantomatic.github.io

151 stars 22 forks source link

Matcher incredibly slow? #249

Open rossduncan opened 5 years ago

rossduncan commented 5 years ago

Just built the latest integration and matching seems to have become incredibly slow. To the point where interactive use looks like it's crashed, but it's taking minutes to come up with any matches for about 5 rules and a graph with 10--15 vertices.

Is anyone else seeing this?

rossduncan commented 5 years ago

By way of example: I have a circuit consisting of 8 CNOTS, I apply rotate_simp and it takes 16 minutes to perform the first rewrite (and then all the rest follow within a couple of seconds.)

SaraWolffs commented 5 years ago

Could you give a good and a bad commit, as well as a project which demonstrates the issue? Probably not hard to craft, but you seem to have one on hand already.

rossduncan commented 5 years ago

Good commit - I don't know; something that was current in the summer? Bad commit -- today : 17797e05790d747a2cb05fcb6c28f50199055e7f Example I just mentioned is attached, however I am seeing this on everything. screen shot 2018-11-14 at 15 15 00

SaraWolffs commented 5 years ago

Could you include the rules you're using? Having a demo project available makes reproduction a lot easier. I'll be creating my own, but can't guarantee I'll see what you're seeing without having the same project (theory+rewrite rules).

rossduncan commented 5 years ago

I'm using the example zx-stabilzier project. The only rule loaded is axioms/gen_bialg_simp, both in forward and backward directions. Attached is the current state of my proof development, which is currently hung with the CPU pegged at 391% and has been there for some time.

I am running Mac OS X 10.13.6. I have Java : java version "10.0.2" 2018-07-17 Java(TM) SE Runtime Environment 18.3 (build 10.0.2+13) Java HotSpot(TM) 64-Bit Server VM 18.3 (build 10.0.2+13, mixed mode)

and sbt: stable 1.2.6

screen shot 2018-11-14 at 15 38 44

SaraWolffs commented 5 years ago

Just got a full project with a minimal set of rules running, I think I see what you mean. Let me just identify a good commit and I'll run a bisect on it.

SaraWolffs commented 5 years ago

Finally found one, but had to dump a few that I was sure I'd already used without any issues. Starting to suspect one of the dependencies broke something.

rossduncan commented 5 years ago

Which commit is good? I need a working version :)

SaraWolffs commented 5 years ago

qpc2018 seems to be good. Which is weird, because a moment ago it wasn't. I'll run it again on the sample case.

SaraWolffs commented 5 years ago

Nope, never mind, qpc2018 is also bad, it just takes a bit longer to show. You might want to try qpc-practical-2018 next, but I'm going to take a break from this issue now and take another look later this evening, or maybe tomorrow. If you find any commit which works, could you please share it here?

The weird thing is, I've used qpc2018. It was fine. And now it's not. But only in interactive mode does it really break this badly.

rossduncan commented 5 years ago

Hi Sal, Actually I'm not seeing the problem with the qpc2018 branch. Don't know what's going on here! -r

SaraWolffs commented 5 years ago

Try applying green fusion twice (first the one highlighted in your picture, then the one above that). After that, it locked up on my machine.

rossduncan commented 5 years ago

Confirmed, not the example you mention but using the spider rules seems to trigger it.