Re: [q-lang-users] Compilation time
Brought to you by:
agraef
From: Albert G. <Dr....@t-...> - 2006-05-18 06:59:11
|
Dear Arnoldo, Arnoldo Muller wrote: > I am trying to compile a 106 rule script (attached in this e-mail). I > started it an hour ago and hasn't finished yet. Sorry for the bad news, but it looks like you really hit one of the (few?) cases where the deterministic left-to-right tree matching automaton is exponentially larger than the nondeterministic one. Specifically, it seems that the number of states triples with each rule (at least some of them), and you can imagine where that leads... In fact, I isolated three of the rules near the beginning of your script which already produce an automaton with more than 4500 states. And the effect even gets worse with a bugfix I recently did to resolve an obscure bug in the pattern matching code. :( Well, it's the first real-world example that I see which exhibits the behaviour. I suppose that your ruleset is generated in some way? There's still the faint possibility that there might be a bug in my implementation of the pattern matching algorithm, I'll have to take another look at the generated automata to figure this out. Even if it doesn't turn out to be a bug, there might be ways to cope with the situation, but not with deterministic left-to-right matching, and in any case that surely needs a complete overhaul of the pattern matching algorithm. (AFAICS, using backtracking matching is not an option in general, since that would make the pattern matching much too slow.) To work around this problem, the only thing I can suggest right now is to rewrite the overlapping rules in order to reduce the complexity. E.g.: checkAvailability (X,Y) = true where X = farrayRef (V0,fphi (fintConstant 1,V1)), Y = farrayRef (V0,fphi (flocalRef BC0,V1)); I know that this is not very convenient (kind of defeats the purpose of using term rewriting), and it will also be slow since this effectively makes the pattern matching work in a backtracking way. But I hope it's still a workable solution until I find something better. Cheers, Albert -- Dr. Albert Gr"af Dept. of Music-Informatics, University of Mainz, Germany Email: Dr....@t-..., ag...@mu... WWW: http://www.musikinformatik.uni-mainz.de/ag |