Looking into it. On Monday, October 1, 2012, Reinout Stevens wrote:
> > > On Saturday, September 29, 2012 11:10:38 PM UTC+2, David Nolen wrote: >> >> On Wed, Sep 26, 2012 at 9:20 AM, Reinout Stevens <rest...@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<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 >> >> > Hi, > > > I quickly changed the code so that the graph structure no longer contains > the list of nodes, and the same behaviour still persists. For the actual > implementation I have changed it to a function that returns a list of > nodes, which can be compared in O(1) instead of looping over the data > structure, and also here we get the same behaviour. > > Personally, I don't see the difference between calling solve-goal or > solve-goals, as both should have an equally large table. The recursive step > of solve-goals shouldn't do anything, as we are only passing a list > containing a single item. In attachment the updated code (aka: just removed > the :node key from the graph). > > > Thanks for taking your time and looking into this, > > > Reinout > > -- > 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<javascript:_e({}, 'cvml', > '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 <javascript:_e({}, 'cvml', > 'clojure%2bunsubscr...@googlegroups.com');> > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- 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
