#213 delayed execution causes buildup in tables

Performance problem
open
nobody
None
5
2013-12-13
2013-11-28
No

Change supplied by Michael Kifer to constraintLib:suspend/2:

suspend(V,Goal) :-
( get_attr(V,when,List) ->
%% MK: this memberchk prevents the buildup
%% of identical attributes
(memberchk(Goal,List) -> true
; put_attr(V,when,[Goal|List])
)
;
put_attr(V,when,[Goal])
).

Discussion

  • Theresa Swift

    Theresa Swift - 2013-12-13

    In case Peter is reading this -- I'll try to take a look soon, now that I have time to breathe after finishing the implementation of ISO incremental tables.

     
    • Peter Ludemann

      Peter Ludemann - 2013-12-14

      Yes I'm reading this.
      Ideally, it would be nice if some attributes could be marked as "ignore
      this entirely", or perhaps there could be a custom hook for what
      constitutes "similarity" (or "subsumption", if that's being used), similar
      to the unification hook for attributes.

      If we take Michael's "memberchk" solution, it will still compute extra
      results until all the possible delays have been added to the variable,
      whereas it'd be better if we could ignore all the delays because they're
      attributes that add no "meaning" to the variable. But I think that
      Michael's solution will terminate for most programs because there ought to
      be a finite set of predicates that delay on a variable (but I could
      envisage a combinatoric explosion in some cases).

      There's a related problem, which is how to handle "output" values from
      predicates. A simple example is finding a path through a graph with cycles
      ... testing for the existence of a path is easy with tabling but if the
      path itself is part of the tabled predicate, then termination might not
      happen. One way out of this could be to attach the path information as an
      attribute to a variable and mark it as not interesting for the tabling
      decision (this could also be used to attach debug information to a
      variable). To get path information, my work-around is to use
      get_calls_for_table and infer the path information from that, but it's a
      bit tricky. (I've also tried partial-order subsumption but wasn't
      successful, although that might just be my poor programming skills.)

       

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks