On Wed, Sep 26, 2012 at 9:20 AM, Reinout Stevens <reste...@vub.ac.be> wrote:
> Hi, > > > I'm the author of a DSL that allows reasoning over paths throughout graphs > using core.logic ( https://github.com/ReinoutStevens/damp.qwal ). We > noticed that for larger graphs performance became horribly slow, even > though there is no apparent reason why it should be. First investigations > lead me to believe tabling was the issue. We use tabling to prevent > infinite loops due to cycles in the graph. After writing a small testcase > that exhibits the described problems I've noticed that it is a combination > of tabling and looping over a list. > > In the test case we construct a linear graph (so: a graph where each node > has a single successor). We want to asser that there exists a path from the > start to the end node. This is done by using the logical rule trans > [graph current next], which given a graph and the current node binds next to > the possible successors. We write this query in three different ways. > First, we try to succeed the goal trans as many times as needed, until we > end up in the end state. Next, we do the same but tabling our loop. This > prevents looping in case our graph would contain a cycle (in this case, > there is no such cycle). Finally, instead of directly proving trans, we > prove a list of goals. This list contains a single goal (trans). This last > scenario runs much slower than the previous two, even though I don't see a > large difference with the first two scenarios. > > In attachment the code of our test case. There are 3 functions at the end, > each implementing one of the described scenarios. Note the difference > between solve-goal and solve-goals. > > Any pointers how to solve the issue, or work around it are appreciated > I took some time to look into this. The issue is that your terms are quite complex - the entire graph is the first arg to the tabled goal! In order for tabling to work this argument needs to be reified (completely walked and all logic vars replaced with copies) and this is used as the table cache key. As you can imagine this means given the way you've written your program the entries in the table can get quite large and the comparisons to determine whether a reusable cached answer term exists is quite expensive! It's important to table at the right "level". Does this make sense and can you formulate a solution so that you're not passing in the entire graph as the first argument to the tabled goal? David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
