[LOGIC-166] walk* exponential in depth of tree terms? Created: 27/Jan/15 Updated: 03/Feb/15
|Reporter:||Tom Jack||Assignee:||David Nolen|
By 'reification' I mean e.g.:
Demonstration of exponential performance, using nested vectors (, [], [[]]...):
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.
|Comment by Tom Jack [ 28/Jan/15 4:31 AM ]|
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
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.