Problem: Passing primitives from an inner loop to an outer loop efficiently.
Here is what I've found.
The fastest method of result batching, amazingly, is to pass out a list and:
(let [foo (loop ... )
x (double (first foo))
r1 (rest foo)
y (double (first r1))
r2 (rest r1)
z (double (first r2))] ... )
(here passing out three doubles).
About half as fast is:
(let [[x y z] (loop ... )] ... ) with (double x), (double y), and (double z)
used later in place of x y z and only one occurrence of each (so no more
(double foo) conversions than before). The destructuring bind apparently
exerts a higher run-time overhead compared to manual destructuring.
(with-locals [x (double 0) y (double 0) z (double 0)]
(loop ... )
(do-something-with (double (var-get x)) (double (var-get y)) (double
(var-get z))))
is two full orders of magnitude slower (here the loop doesn't return a list
but uses var-set).
Using atoms is even worse.
(let [#^doubles xyz (double-array (int 3))]
(loop ... )
(do-something-with (aget xyz (int 0)) (aget xyz (int 1)) (aget xyz (int
2))))
with the loop using aset-double to pass out values is, surprisingly, no
faster. Using plain aset makes no difference, as does removing the (int ...)
wrappings around the numbers.
Intermediate in speed is using a clojure vector to pass out values, e.g.
[result-x result-y result-z] is the expression that returns a value from the
loop, and
(do-something-with (get results (int 0)) (get results (int 1)) (get
results (int 2)))
It's surprising that this is faster than using a primitive Java array with
type-hints, and interesting that retrieving sequential items from a list is
faster than a like number of in-order indexed retrievals from a vector,
which could theoretically be optimized to a pointer-walk with each retrieval
involving an increment and a dereference and a store, rather than an
increment, three dereferences, and a store. (Dereference linked list entry
item pointer, store, increment pointer, dereference to get next-entry
pointer, dereference again, repeat.)
Whatever, these results may be useful to someone, along with:
(defn- extract-result-list-into [conv hint gensyms result-generator] (let
[rs (take (count gensyms) (repeatedly gensym))] (into [(first rs)
result-generator] (loop [r rs g (if hint (map #(with-meta % {:tag hint})
gensyms) gensyms) output []] (if (empty? r) output (let [fr (first r) rr
(rest r) frr (first rr)] (recur (rest r) (rest g) (into output (concat
[(first g) (if conv `(~conv (first ~fr)) `(first ~fr))] (if frr [frr `(rest
~fr)]))))))))))
This helper function can be used in a macro to suck the contents of a list
into variables with conversions, type hints, or both; conv would be a symbol
like `double, hint something like BigInteger, gensyms some gensyms (or other
symbols) for the variable names (in order), and result-generator some code
(e.g. resulting from a backtick expression). The output is a vector
resembling
[G__5877 (loop ... whatever code)
#^hint G__5874 (conv (first G__5877))
G_5878 (rest G__5877)
#^hint G__5875 (conv (first G__5878))
G_5879 (rest G__5878)
#^hint G__5876 (conv (first G__5879))]
which can be used in a let, loop, or other construct that uses bindings with
the usual clojure syntax, and can even have other things added to it by
macro code.
The downside is relative inflexibility. If you pass in a gensyms seq with an
embedded vector of two gensyms you'll get a valid destructuring bind for a
composite item in the results, but it won't work with type hints or
conversions, nor can those be mixed. Making it more sophisticated would be
possible, though.
This arose when I had a performance-critical double-barreled loop to
optimize, and found that the outer loop was spending several thousand
iterations of the inner loop worth of time just to extract the results via
with-locals. I did some experimenting and benchmarking of various ways to
get the output of the inner loop to code in the outer loop, using
System/nanoTime, millions of repetitions, and averaging to determine the
winner.
An efficient "labeled recur" would be nice for clojure 2.0. :) (Limited
though it would be to when the inner loop was in tail position in the outer
loop.)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
