Hi all,
I'm struggeling with some really strange problem. I have a function
`p-apply', which can be used find all reachable vertices in a graph
matching a regular expression modeled as nested vector of functions, to
which the results are chained through. Here's an example call:
(p-apply v1 [p-seq --> --> [p-alt --<>
[p-+ [--> :cls 'Foo]]]])
That means, starting from v1 you first have to traverse 2 outgoing
edges, and then you may either traverse an aggregation from part to
whole side, or you may iterate one or many outgoing edges of type Foo.
Sometimes, memoization can bring a performance win, so I use a global
var with a macro to dispatch to internal p-apply functions.
Here's the relevant parts of the code. You can basically jump to the
last function.
--8<---------------cut here---------------start------------->8---
(def ^{:private true}
*memoize-path-eval* false)
(defn- p-apply-normal
[v p]
(cond
;; funs -->
(fn? p) (p v)
;; funs with params [--> :cls 'Foo]
(coll? p) (apply (first p) v (next p))
;; adjacences / role names
(or (string? p) (keyword? p) (symbol? p))
(let [vs (into-oset v)]
(apply into-oset (map #(adjacences % p) vs)))
:else (throw (RuntimeException.
(format "Don't know how to apply %s."
p)))))
(def ^{:private true}
p-apply-memoized
(memoize p-apply-normal))
(defmacro with-path-eval-memoization
[& body]
`(binding [*memoize-path-eval* true]
~@body))
(defn- p-apply-internal
[v p]
(if *memoize-path-eval*
(let [vs (into-oset v)
r (map #(p-apply-memoized % p) vs)]
(if (seq r)
(apply into-oset r)
(ordered-set)))
(p-apply-normal v p)))
(defn p-apply
[v p]
(let [counter (atom -1)]
(p-apply-internal
v
;;; Using p with metadata somehow makes things SLOW
;(clojure.walk/postwalk #(if (fn? %)
; (with-meta % {:state (swap! counter inc)})
; %) p)
;;; using just p is FAST
p
)))
--8<---------------cut here---------------end--------------->8---
Because I'd like to extend the search to collect also the shortest paths
to all reachable vertices that conform the given regular expression, I
wanted to put metadata on the function symbols that are given to
`p-apply'.
But as soon as I comment `p' and uncomment the `postwalk' call returning
`p' with metadata on the function symbols, memoization seems to stop
working.
With the code above (`p' passed to `p-apply-internal'), I get these
timings with memoization turned on:
With memoization
================
cbo-q-sequential
"Elapsed time: 6805.37119 msecs"
cbo-q-parallel
"Elapsed time: 212.276041 msecs"
With memoization 2
==================
cbo-q-sequential
"Elapsed time: 178.102362 msecs"
cbo-q-parallel
"Elapsed time: 172.027562 msecs"
So the first function, which in effect fills the memoization cache and
doesn't much benefit from it itself runs ~7 secs, but repeating the
queries is lightning fast.
If I comment `p' and pass it first through `postwalk' to put metadata on
the functions, then the timings are these:
With memoization
================
cbo-q-sequential
"Elapsed time: 8247.753366 msecs"
cbo-q-parallel
"Elapsed time: 8962.930698 msecs"
With memoization 2
==================
cbo-q-sequential
"Elapsed time: 11010.302911 msecs"
cbo-q-parallel
"Elapsed time: 9098.196259 msecs"
What's the matter? Why does it get that slow only because of metadata?
Bye,
Tassilo
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
