<< Back to previous view

[LOGIC-177] binding to a deep nested vector takes too much time Created: 24/Dec/15  Updated: 28/Dec/15

Status: Open
Project: core.logic
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Dmitry Geurkov Assignee: David Nolen
Resolution: Unresolved Votes: 0
Labels: performance
Environment:

Ubuntu Linux 12.04 Java: OpenJDK 64-Bit Server VM 1.8.0_45-internal-b14 Clojure: 1.7.0 core.logic "0.8.10"



 Description   

It's probably related to how core.logic is printing out the vector structure

Following is minimal case to reproduce the issue

(ns testclj.logic
(:require [clojure.core.logic :as l]))

(def data [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[:a]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]])

(time (l/run* [q] (l/== q data)))



 Comments   
Comment by Dmitry Geurkov [ 28/Dec/15 6:48 AM ]

I think the problem is related to following piece of code

(defn walk* [s v]
  (let [v (walk s v)]
    (walk-term v
      (fn [x]
        (let [x (walk s x)]
         (if (tree-term? x)
           (walk* s x)
           x))))))

this on the other hand calls

clojure.lang.IPersistentVector
  (walk-term [v f]
    (with-meta
      (loop [v v r (transient [])]
        (if (seq v)
          (recur (next v) (conj! r (walk-term (f (first v)) f)))
          (persistent! r)))
      (meta v)))

What this does is that it recursively calls walk-term for all elements of vector.
and subsequently calls walk-term for each element of vector which in turn results in calling walk* over the
elements of vector which had previously been visited which in turn ends into calling walk-term again on the elements of the vector again going down and until it visits the entire structure multiple times.

This overall results in revisiting sub nodes multiple times

The problem is in walk* function part which is recursively calling walk* for vector elements that had been previously walked by walk-term function call itself

(if (tree-term? x)
           (walk* s x)
           x)

I think there is a huge problem with how this whole part is designed, I'm not sure what to suggest here but I think we need to somehow combine walk-term and walk* into one function that would walk the entire datastructure in one go, any suggestions?

Possible solution is following code but I'm not sure if it's correct one or not

(defn walk* [s v]
  (let [v (walk s v)]
    (walk-term v
        #(walk s %))))




[LOGIC-166] walk* exponential in depth of tree terms? Created: 27/Jan/15  Updated: 03/Feb/15

Status: Open
Project: core.logic
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Tom Jack Assignee: David Nolen
Resolution: Unresolved Votes: 0
Labels: performance
Environment:

[org.clojure/clojure "1.7.0-alpha5"]
[org.clojure/core.logic "0.8.9"]


Attachments: Text File 0001-Walk-less.patch    

 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.



 Comments   
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 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.





[LOGIC-50] Rel relation PersistentHashSet becomes LazySeq after issuing a retraction Created: 01/Sep/12  Updated: 28/Jul/13  Resolved: 05/Sep/12

Status: Closed
Project: core.logic
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Aaron Brooks Assignee: David Nolen
Resolution: Completed Votes: 0
Labels: performance

Attachments: Text File core.logic-rel-001.patch     Text File core.logic-rel-002.patch    
Patch: Code

 Description   

The first retraction of facts from a relation transforms the internal PersistentHashSet -set var+atom, which guarantees uniqueness, into a LazySeq which allows duplicate facts to be added. Once the first retraction occurs, a LazySeq persists for the rest of the life of the relation. Only the value of the primary -set var+atom is affected, not the -index var+atom values.

This issue is not an external correctness issue but does affect performance of subsequent duplicate fact additions which grow the size relation.

Preparation:

user=> (defrel foo x y)
#<user$eval4287$fn__4288 user$eval4287$fn__4288@1a9d489b>
user=> (facts foo [[:joe :man][:jane :woman][:sue :boy]])
nil
user=> foo_2-set
#<Atom@52aaf223: #{[:joe :man] [:jane :woman] [:sue :boy]}>
user=> (class @foo_2-set)
clojure.lang.PersistentHashSet
user=> (retraction foo :jane :woman)
nil

Without patch applied:

user=> foo_2-set
#<Atom@52aaf223: ([:joe :man] [:sue :boy])>
user=> (class @foo_2-set)
clojure.lang.LazySeq
user=> (facts foo [[:joe :man][:jane :woman][:sue :boy]])
nil
user=> foo_2-set
#<Atom@52aaf223: ([:sue :boy] [:jane :woman] [:joe :man] [:joe :man] [:sue :boy])>
user=> (class @foo_2-set)
clojure.lang.LazySeq

With patch applied:

user=> foo_2-set
#<Atom@31eb9b15: #{[:joe :man] [:sue :boy]}>
user=> (class @foo_2-set)
clojure.lang.PersistentHashSet
user=> (facts foo [[:joe :man][:jane :woman][:sue :boy]])
nil
user=> foo_2-set
#<Atom@31eb9b15: #{[:joe :man] [:jane :woman] [:sue :boy]}>
user=> (class @foo_2-set)
clojure.lang.PersistentHashSet

I've filed this as a Minor issue as it does not affect core.logic correctness and degraded performance can be avoided by not re-asserting duplicate facts.

I will also issue a GitHub pull request which can be used or ignored at your convenience.



 Comments   
Comment by David Nolen [ 02/Sep/12 5:45 PM ]

Thanks! Is this meant to be applied to master?

Comment by Aaron Brooks [ 03/Sep/12 6:56 PM ]

(cf. here and GitHub I'll keep this thread on JIRA.) Yes, this is targeted for master. I don't know if this warrants a release unto itself.

Comment by Aaron Brooks [ 04/Sep/12 9:17 AM ]

I forgot to mention that I needed to add "src/test/clojure" to the project.clj :source-paths vector to get lein1/2's test command to run the tests. Is that expected? Is there another way to run the tests that I'm missing? I'm happy to file a separate ticket/patch to address this if project.clj needs to be modified.

Comment by David Nolen [ 04/Sep/12 9:25 AM ]

Thanks for the information. Will apply to master. I actually run tests with "mvn test", I've updated :source-paths so other people can run the tests with lein.

Comment by David Nolen [ 04/Sep/12 9:26 AM ]

I tried to apply the patch but I'm getting a "Patch format detection failed".

Comment by Aaron Brooks [ 04/Sep/12 4:16 PM ]

The attached patch should work fine with git-apply (in either "cat foo.patch |git apply" or "git apply foo.patch" form). I made the GitHub pull request as I figured that would be the easiest path to pull the changes in.

Comment by David Nolen [ 04/Sep/12 6:04 PM ]

Yes the patch is not properly formatted and we're not supposed to take pull requests. The patch is missing attribution info. I normally apply patches with "git am foo.patch". I used the following guide for figuring out how to generate patches that can be applied with "git am", http://ariejan.net/2009/10/26/how-to-create-and-apply-a-patch-with-git.

Comment by Aaron Brooks [ 05/Sep/12 9:25 AM ]

My apologies for the extra run-around here. I've attached an -002 version of the patch created with git-format-patch which should be amenable to git-am.

Comment by David Nolen [ 05/Sep/12 11:32 AM ]

fixed, http://github.com/clojure/core.logic/commit/9bc6eb42be28bfd2b493657344f6eea8f5ed657c. pushing out a 0.8.0-alpha3 release as well.





Generated at Sat Oct 01 13:59:09 CDT 2016 using JIRA 4.4#649-r158309.