core.logic

binding to a deep nested vector takes too much time

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:
    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)))

Activity

Hide
Dmitry Geurkov added a comment - - edited

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 %))))
Show
Dmitry Geurkov added a comment - - edited 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 %))))

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated: