Re: Passing primitives from an inner loop to an outer loop efficiently
Jonathan showed destructuring/indexing very nicely. Here are some timings for vector/list creation: (let [lst '(1 2 3)] (timings 1e7 (list 1 2 3) (cons 1 (cons 2 (cons 3 ( (conj (conj (conj () 3) 2) 1) (vector 1 2 3) (vec lst) (conj (conj (conj [] 1) 2) 3))) 6590.33 ms 61.2% 1.6x (list 1 2 3) 7571.30 ms 70.3% 1.4x (cons 1 (cons 2 (cons 3 ( 7773.67 ms 72.2% 1.4x (conj (conj (conj () 3) 2) 1) 9601.74 ms 89.1% 1.1x (vector 1 2 3) 8612.29 ms 79.9% 1.3x (vec lst) 10772.88 ms 100.0% 1.0x (conj (conj (conj [] 1) 2) 3) Yes, it looks that list creation is faster than vector creation. Frantisek On Jul 9, 12:17 am, John Harrop wrote: > On Wed, Jul 8, 2009 at 4:57 PM, Frantisek Sodomka wrote: > > > So far it seems that vectors win in Clojure: > > > (timings 3e5 > > (let [v (vector 1 2 3) a (nth v 0) b (nth v 1) c (nth v 2)] (+ a b > > c)) > > (let [lst (list 1 2 3) a (nth lst 0) b (nth lst 1) c (nth lst 2)] (+ > > a b c))) > > > => > > 680.63 ms 83.6% 1.2x (let [v (vector 1 2 3) a (nth v 0) b (nth > > v 1) c (nth v 2)] (+ a b c)) > > 813.79 ms 100.0% 1.0x (let [lst (list 1 2 3) a (nth lst 0) b > > (nth lst 1) c (nth lst 2)] (+ a b c)) > > Does using vec instead of vector make a difference? Using first, rest, > first, rest instead of nth to destructure the list? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
On Wed, Jul 8, 2009 at 4:57 PM, Frantisek Sodomka wrote: > > So far it seems that vectors win in Clojure: > > (timings 3e5 > (let [v (vector 1 2 3) a (nth v 0) b (nth v 1) c (nth v 2)] (+ a b > c)) > (let [lst (list 1 2 3) a (nth lst 0) b (nth lst 1) c (nth lst 2)] (+ > a b c))) > > => > 680.63 ms 83.6% 1.2x (let [v (vector 1 2 3) a (nth v 0) b (nth > v 1) c (nth v 2)] (+ a b c)) > 813.79 ms 100.0% 1.0x (let [lst (list 1 2 3) a (nth lst 0) b > (nth lst 1) c (nth lst 2)] (+ a b c)) > Does using vec instead of vector make a difference? Using first, rest, first, rest instead of nth to destructure the list? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
Seperate so it can be easily ignored:
Changed in core.clj:
(defn nth
"Returns the value at the index. get returns nil if index out of
bounds, nth throws an exception unless not-found is supplied. nth
also works for strings, Java arrays, regex Matchers and Lists, and,
in O(n) time, for sequences."
{:inline (fn ([c i] `(. clojure.lang.RT (nth ~c ~i)))
([c i n] `(. clojure.lang.RT (nth ~c ~i ~n
:inline-arities #{2 3}}
([coll index] (. clojure.lang.RT (nth coll index)))
([coll index not-found] (. clojure.lang.RT (nth coll index not-
found
;;changed to inline the 3ary version of nth
(defn destructure [bindings]
(let [bmap (apply array-map bindings)
pb (fn pb [bvec b v]
(let [pvec
(fn [bvec b val]
(let [gvec (if (symbol? val) val (gensym
"vec__")),
length-val (:length ^val)]
(loop [ret (if (symbol? val) bvec (-> bvec
(conj gvec) (conj val)))
n 0
bs b
seen-rest? false]
(if (seq bs)
(let [firstb (first bs)]
(cond
(= firstb '&) (recur (pb ret (second
bs) (list `nthnext gvec n))
n
(nnext bs)
true)
(= firstb :as) (pb ret (second bs)
gvec)
:else (if seen-rest?
(throw (new Exception
"Unsupported binding form, only :as can follow & parameter"))
(recur (pb ret firstb (if (and
length-val (< n length-val))
(if (or
(vector? val)(= (:tag ^val) :vector))
(list
gvec n)
(list
`nth gvec n))
(list `nth gvec
n nil)))
(inc n)
(next bs)
seen-rest?
ret
pmap
(fn [bvec b v]
(let [gmap (or (:as b) (if (symbol? v) v
(gensym "map__")))
defaults (:or b)]
(loop [ret (if (symbol? v) bvec (-> bvec
(conj gmap) (conj v)))
bes (reduce
(fn [bes entry]
(reduce #(assoc %1 %2 ((val
entry) %2))
(dissoc bes (key
entry))
((key entry) bes)))
(dissoc b :as :or)
{:keys #(keyword (str %)), :strs
str, :syms #(list `quote %)})]
(if (seq bes)
(let [bb (key (first bes))
bk (val (first bes))
has-default (contains? defaults
bb)]
(recur (pb ret bb (if has-default
(list `get gmap bk
(defaults bb))
(list `get gmap
bk)))
(next bes)))
ret]
(cond
(symbol? b) (-> bvec (conj b) (conj v))
(vector? b) (pvec bvec b v)
(map? b) (pmap bvec b v)
:else (throw (new Exception (str "Unsupported
binding form: " b))
process-entry (fn [bvec b] (pb bvec (key b) (val b)))]
(if (every? symbol? (keys bmap))
bindings
(reduce process-entry [] bmap
;;I wasn't sure how to do a 'vector' (kept getting the 'vector'
function instead) so I just used
;;:vector keyword to dispatch on. Becomes kind of unsafe if you
violate the 'length' promise.
;;this also eliminates a redundancy where you were binding (let [v [1
2 3]] (let [[a b c] v]))
;;and the inner let would have (let [gensym_vec v, a (nth gensym_vec
0)...])
;;as opposed to (let [a (nth v 0)...]...)
;;which should be ok because we don't have to worry about multiple
evaluation if we are destructuring from a symbol.
--~--~-~--~~~---~--~~
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
Re: Passing primitives from an inner loop to an outer loop efficiently
On Jul 8, 4:57 pm, Frantisek Sodomka wrote:
> So far it seems that vectors win in Clojure:
>
> (timings 3e5
> (let [v (vector 1 2 3) a (nth v 0) b (nth v 1) c (nth v 2)] (+ a b
> c))
> (let [lst (list 1 2 3) a (nth lst 0) b (nth lst 1) c (nth lst 2)] (+
> a b c)))
>
> =>
> 680.63 ms 83.6% 1.2x (let [v (vector 1 2 3) a (nth v 0) b (nth
> v 1) c (nth v 2)] (+ a b c))
> 813.79 ms 100.0% 1.0x (let [lst (list 1 2 3) a (nth lst 0) b
> (nth lst 1) c (nth lst 2)] (+ a b c))
>
> Frantisek
>
> On Jul 8, 7:29 pm, John Harrop wrote:
>
> > Interesting. How are these timings affected if you add in the time taken to
> > pack the list or vector in the first place, though? I have the feeling it
> > may be slightly cheaper to unpack a vector, but noticeably cheaper to pack a
> > list...
>
>
I did some playing and it seems that the x-factor is really whether or
not the array access function is in-lined into the code. I made a few
tweaks to the source code so that the destructuring bind is able to
rewrite the code with the 2-ary version and avoid rebinding overhead.
I'll post it in reply to this.
Here are some results I collected:
(I like your 'timings' macro, by the way).
(let [v [1 2 3] lst '(1 2 3)]
(timings 1e7
(let [[a b c] v] a b c)
(let [[a b c] #^{:length 3} v] a b c)
(let [[a b c] #^{:tag :vector :length 3} v] a b c)
(let [[a b c] #^{:length 3} [1 2 3]] a b c)
(let [a (v 0) b (v 1) c (v 2)] a b c)
(let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c)
(let [a (first v) b (second v) c (first (rest (rest v)))] a b c)
(let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first
r2)] x y z)
(let [[a b c] lst] a b c)
;; (let [a (lst 0) b (lst 1) c (lst 2)] [a b c])
(let [a (nth lst 0) b (nth lst 1) c (nth lst 2)] a b c)
(let [a (first lst) b (second lst) c (first (rest (rest lst)))] a
b c)
(let [x (first lst) r1 (rest lst) y (first r1) r2 (rest r1) z
(first r2)] x y z)))
---
no inlining of 3-ary version (inlines 2ary version as normal),
rewriting to 2-ary version dependant on :length :tag metadata and
4650.19 ms 34.2% 2.9x (let [[a b c] v] a b c) ;;nothing
3675.41 ms 27.0% 3.7x (let [[a b c] v] a b c) ;;length
3414.78 ms 25.1% 4.0x (let [[a b c] v] a b c) ;; tag length
13606.68 ms 100.0% 1.0x (let [[a b c] [1 2 3]] a b c)
3459.74 ms 25.4% 3.9x (let [a (v 0) b (v 1) c (v 2)] a b c)
3551.73 ms 26.1% 3.8x (let [a (nth v 0) b (nth v 1) c (nth v 2)]
a b c)
9810.52 ms 72.1% 1.4x (let [a (first v) b (second v) c (first
(rest (rest v)))] a b c)
9234.34 ms 67.9% 1.5x (let [x (first v) r1 (rest v) y (first r1)
r2 (rest r1) z (first r2)] x y z)
9519.99 ms 70.0% 1.4x (let [[a b c] lst] a b c)
7131.29 ms 52.4% 1.9x (let [a (nth lst 0) b (nth lst 1) c (nth
lst 2)] a b c)
7665.99 ms 56.3% 1.8x (let [a (first lst) b (second lst) c
(first (rest (rest lst)))] a b c)
7490.44 ms 55.0% 1.8x (let [x (first lst) r1 (rest lst) y (first
r1) r2 (rest r1) z (first r2)] x y z)
---
inlining 3ary version, rewriting dependant on :length and :tag.
3230.53 ms 24.6% 4.1x (let [[a b c] v] a b c) ;;nothing
3557.94 ms 27.1% 3.7x (let [[a b c] v] a b c) ;;length
3287.01 ms 25.1% 4.0x (let [[a b c] v] a b c) ;;tag +length
13116.50 ms 100.0% 1.0x (let [[a b c] [1 2 3]] a b c)
3287.39 ms 25.1% 4.0x (let [a (v 0) b (v 1) c (v 2)] a b c)
3615.61 ms 27.6% 3.6x (let [a (nth v 0) b (nth v 1) c (nth v 2)]
a b c)
10634.64 ms 81.1% 1.2x (let [a (first v) b (second v) c (first
(rest (rest v)))] a b c)
10147.02 ms 77.4% 1.3x (let [x (first v) r1 (rest v) y (first r1)
r2 (rest r1) z (first r2)] x y z)
8476.63 ms 64.6% 1.5x (let [[a b c] lst] a b c)
7106.42 ms 54.2% 1.8x (let [a (nth lst 0) b (nth lst 1) c (nth
lst 2)] a b c)
8172.17 ms 62.3% 1.6x (let [a (first lst) b (second lst) c
(first (rest (rest lst)))] a b c)
8031.60 ms 61.2% 1.6x (let [x (first lst) r1 (rest lst) y (first
r1) r2 (rest r1) z (first r2)] x y z)
I'll post the rather small tweaks in a response to this post. Please
note that i was playing with a (month old) alpha 1.1 version of
clojure.core, so I am not sure what the differences would be between
it and a current version. I think the most interesting part is that
you can get pretty much the same effect by just telling it to inline
the 3ary version of nth. (Although it is a multi function, so it seems
there is still some sort of funcall overhead).
--~--~-~--~~~---~--~~
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
-~--~~~~--~-
Re: Passing primitives from an inner loop to an outer loop efficiently
So far it seems that vectors win in Clojure: (timings 3e5 (let [v (vector 1 2 3) a (nth v 0) b (nth v 1) c (nth v 2)] (+ a b c)) (let [lst (list 1 2 3) a (nth lst 0) b (nth lst 1) c (nth lst 2)] (+ a b c))) => 680.63 ms 83.6% 1.2x (let [v (vector 1 2 3) a (nth v 0) b (nth v 1) c (nth v 2)] (+ a b c)) 813.79 ms 100.0% 1.0x (let [lst (list 1 2 3) a (nth lst 0) b (nth lst 1) c (nth lst 2)] (+ a b c)) Frantisek On Jul 8, 7:29 pm, John Harrop wrote: > Interesting. How are these timings affected if you add in the time taken to > pack the list or vector in the first place, though? I have the feeling it > may be slightly cheaper to unpack a vector, but noticeably cheaper to pack a > list... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
Interesting. How are these timings affected if you add in the time taken to pack the list or vector in the first place, though? I have the feeling it may be slightly cheaper to unpack a vector, but noticeably cheaper to pack a list... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
To compare timings, I use this macro: (defmacro time-ms [n expr] `(let [start# (. System (nanoTime))] (dotimes [i# ~n] ~expr) (/ (double (- (. System (nanoTime)) start#)) 100.0))) (defmacro timings [n & expr] (let [expr-are-not-equal (cons 'not= expr) expr-times (cons 'vector (map #(list 'time-ms n %) expr))] `(if ~expr-are-not-equal (do (println "Expressions:\n") (dorun (map prn '~expr)) (println "\nare NOT equal!")) (let [ts# ~expr-times max-time# (apply max ts#)] (dorun (map (fn [~'t ~'e] (printf "%8.2f ms %6.1f%% %5.1fx " ~'t (* 100.0 (/ ~'t max-time#)) (/ max-time# ~'t)) (prn ~'e)) ts# '~expr)) Use is: user=> (timings 1e6 (+ 2 4 5) (+ 2 (+ 4 5))) 727.50 ms 100.0% 1.0x (+ 2 4 5) 353.18 ms 48.5% 2.1x (+ 2 (+ 4 5)) For our case: (let [v [1 2 3] lst '(1 2 3)] (timings 1e5 (let [[a b c] v] [a b c]) (let [a (v 0) b (v 1) c (v 2)] [a b c]) (let [a (nth v 0) b (nth v 1) c (nth v 2)] [a b c]) (let [a (first v) b (second v) c (first (rest (rest v)))] [a b c]) (let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first r2)] [x y z]) (let [[a b c] lst] [a b c]) ;; (let [a (lst 0) b (lst 1) c (lst 2)] [a b c]) (let [a (nth lst 0) b (nth lst 1) c (nth lst 2)] [a b c]) (let [a (first lst) b (second lst) c (first (rest (rest lst)))] [a b c]) (let [x (first lst) r1 (rest lst) y (first r1) r2 (rest r1) z (first r2)] [x y z]))) And on my computer I get these numbers: 145.86 ms 64.5% 1.6x (let [[a b c] v] [a b c]) 97.37 ms 43.1% 2.3x (let [a (v 0) b (v 1) c (v 2)] [a b c]) 94.66 ms 41.9% 2.4x (let [a (nth v 0) b (nth v 1) c (nth v 2)] [a b c]) 226.15 ms 100.0% 1.0x (let [a (first v) b (second v) c (first (rest (rest v)))] [a b c]) 205.05 ms 90.7% 1.1x (let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first r2)] [x y z]) 219.42 ms 97.0% 1.0x (let [[a b c] lst] [a b c]) 171.32 ms 75.8% 1.3x (let [a (nth lst 0) b (nth lst 1) c (nth lst 2)] [a b c]) 179.03 ms 79.2% 1.3x (let [a (first lst) b (second lst) c (first (rest (rest lst)))] [a b c]) 170.41 ms 75.4% 1.3x (let [x (first lst) r1 (rest lst) y (first r1) r2 (rest r1) z (first r2)] [x y z]) Frantisek On Jul 8, 9:53 am, John Harrop wrote: > On Wed, Jul 8, 2009 at 3:42 AM, Frantisek Sodomka wrote: > > > > > If result is a vector v, then from these 4 cases: > > (let [v [1 2 3]] > > (let [[a b c] v] a b c) > > (let [a (v 0) b (v 1) c (v 2)] a b c) > > (let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c) > > (let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first > > r2)] x y z)) > > > using 'nth' > > (let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c) > > is the fastest. > > Is it faster than using list and manually destructuring the list? > > If so, that would mean that (nth v n) is faster than (get v n), which would > be odd since the latter should turn into the former anyway and be inlinable > by the JIT. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
On Wed, Jul 8, 2009 at 3:42 AM, Frantisek Sodomka wrote: > > If result is a vector v, then from these 4 cases: > (let [v [1 2 3]] > (let [[a b c] v] a b c) > (let [a (v 0) b (v 1) c (v 2)] a b c) > (let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c) > (let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first > r2)] x y z)) > > using 'nth' > (let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c) > is the fastest. > Is it faster than using list and manually destructuring the list? If so, that would mean that (nth v n) is faster than (get v n), which would be odd since the latter should turn into the former anyway and be inlinable by the JIT. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Passing primitives from an inner loop to an outer loop efficiently
If result is a vector v, then from these 4 cases:
(let [v [1 2 3]]
(let [[a b c] v] a b c)
(let [a (v 0) b (v 1) c (v 2)] a b c)
(let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c)
(let [x (first v) r1 (rest v) y (first r1) r2 (rest r1) z (first
r2)] x y z))
using 'nth'
(let [a (nth v 0) b (nth v 1) c (nth v 2)] a b c)
is the fastest.
Frantisek
On Jul 7, 11:10 pm, John Harrop wrote:
> 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 post
Re: Passing primitives from an inner loop to an outer loop efficiently
On Jul 7, 5:10 pm, John Harrop wrote:
> 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))] ... )
>
This isn't suprising if you think about it.
In the list situation you are just grabbing the next pointer,
in an array situation you have to do math to access a vector.
> (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.
>
If you look at the source code this isn't that surprising.
The big difference between (for example):
(let [[x y z] [1 2 3]] ...) and
(let [v [1 2 3] x (v 0) y (v 1) z (v 2)] ...)
Most of the slowdown Seems to have to do with bounds checking:
The first is 'safe' and returns nil for out of bounds, the second
throws an exception.
but
If you look at the source the 2ary version of nth gets inlined and the
3ary version (which destructuring bind expands to) does not.
and
if you put a symbol in the second position you'll note that
Destructuring bind rebinds the symbol with a Gensym even though it
cannot suffer from multiple evaluation.
If you look here:
http://gnuvince.wordpress.com/2009/05/11/clojure-performance-tips/
And look at 'avoid destructuring binding for vectors'
I did some hacking and improved the worst case from about 500ms on my
computer to 300ms.
(By inlining the 3ary version and removing the duplication; compiling
a destructuring function without bounds checking breaks compilation
for obvious reasons...). There are probably better ways to optimize it
as this was just me screwing around ('What can i break this
evening?').
I will note that there is something very funny going on with the
destructuring/binding example in the link above. The fast version on
my machine returns every number of times(1e7 1e8 1e9 etc...) returns
26 ms. It is kind of like it all just got collapsed into a constant.
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
