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<javascript:> > > 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 > > 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 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
tabling.clj
Description: Binary data
