core.logic

walk* exponential in depth of tree terms?

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Environment:
    [org.clojure/clojure "1.7.0-alpha5"]
    [org.clojure/core.logic "0.8.9"]

Description

By 'reification' I mean e.g.:

(run 1 [t]
  (== t <some-constant-to-be-reified>))

Demonstration of exponential performance, using nested vectors ([], [[]], [[[]]]...):
https://www.refheap.com/1e30c198d528300fcba9ef24a

Is this expected, or a bug? I'm guessing the former, but hoping the latter. Feel free to close without comment if this is just the way it is.

Activity

Hide
Tom Jack added a comment -

Attached patch 0001-Walk-less.patch gets me this nice result. It also makes my real case work quite speedily (25ms now, where before it took so long that I never saw it finish). That's a huge relief!

The problem wasn't reification, but walk-term. In the patch I attempt to avoid doing some walking which appears to be redundant. I hope the fact that most of the tests still pass is good evidence that it's redundant.

However, the patch breaks some unifier tests. I noticed that my refheap test 'passes' as of bd65104ec3~, but fails as of bd65104ec3 (the patch for LOGIC-69). It seems the fix made the unifier rely on the current behavior of walk-term.

I'm going to press on with my patched ./checkouts copy for now, since I'm not using the unifier. I may come back to try to fix it sometime.

Show
Tom Jack added a comment - Attached patch 0001-Walk-less.patch gets me this nice result. It also makes my real case work quite speedily (25ms now, where before it took so long that I never saw it finish). That's a huge relief! The problem wasn't reification, but walk-term. In the patch I attempt to avoid doing some walking which appears to be redundant. I hope the fact that most of the tests still pass is good evidence that it's redundant. However, the patch breaks some unifier tests. I noticed that my refheap test 'passes' as of bd65104ec3~, but fails as of bd65104ec3 (the patch for LOGIC-69). It seems the fix made the unifier rely on the current behavior of walk-term. I'm going to press on with my patched ./checkouts copy for now, since I'm not using the unifier. I may come back to try to fix it sometime.
Tom Jack made changes -
Field Original Value New Value
Attachment 0001-Walk-less.patch [ 13810 ]
Tom Jack made changes -
Summary Reification exponential in depth of tree terms? walk* exponential in depth of tree terms?

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated: