nth performance (was: performance in versions >= 1.4.0)

[Karsten Schmidt]

I understand the O(n) aspect, however this was also true for 1.3.0. And since nth is used to obtain arguments in every single destructuring call, it seems to me that its performance should not just suddenly be allowed to drop and especially this drastically. New versions of a software should be equal or faster than a predecessor, not the way round, no?

I've also seen the checks for RandomAccess and Sequential and by simply moving them to the top (after the null check) of the long if-then cascade in RT.nthFrom(), the old performance is restored. I will open a ticket and submit a patch, but have to send in the CA first.

Thoughts? Does no one else find this is an issue that our beloved Clojure has become slower because of this?

K.

On 4 Oct 2012 12:24, "Ben Smith-Mannschott" <bsmit...@gmail.com> wrote:

nth only promises O(n) performance for all things sequential. However,
the implementation on master in RT.java appears to special case
indexed and random-access collections for faster access, so I'm not
sure why you're seeing such a difference. You could try using get in
place of nth, though from reading the source I'm not sure why it would
produce results that are any different from what you're already
seeing.

The code that looks like it runs when you call nth on a vector has
been in Clojure since:

    # commit ff27522840fb3c1681c331ad1fb44a313bd44e0a
    # Author: Rich Hickey <richh...@gmail.com>
    # Date:   2009-05-28 13:42:16 +0000
    #
    # first cut of chunked seqs
    # Chunked seqs, initial Java-side support

So, I'm not finding any easy explanation for the performance
difference you're seeing.

Color me confused.

// Ben


On Thu, Oct 4, 2012 at 12:33 PM, Karsten Schmidt <in...@toxi.co.uk> wrote:
> Okay, after several hours of more testing & profiling it seems the culprit
> is the implementation of (nth) - and IMHO this is quite a biggie:
>
> (use 'macrochrono.core) ; only used for bench macro below
>
> (def t [[0 0] [100 0] [100 100] [[0 0] 10000 100]])
>
> (defn foo [[a b c [[dx dy] r x2]] [px py]]
>   (let [xx (- dx px) yy (- dy py)]
>     (< (+ (* xx xx) (* yy yy)) r)))
>
> 1.3.0
>
> user=> (bench 100 (dotimes [i 100000] (foo t [i i])))
> {:median 12.647, :max 31.255, :min 11.365, :avg 12.73133999999999}
>
> 1.4.0:
>
> (bench 100 (dotimes [i 100000] (foo t [i i])))
> {:median 21.574, :max 32.243, :min 18.031, :avg 22.32677999999999}
>
> 1.5.0-master-SNAPSHOT:
>
> (bench 100 (dotimes [i 100000] (foo t [i i])))
> {:median 21.429, :max 106.704, :min 17.776999999999997, :avg 22.94385}
>
> VisualVM shows most of the time is spent in calls to nth, which makes sense
> since the function makes heavy use of destructuring.
>
> However, could someone please explain why its implementation is now almost
> half the speed as compared to 1.3.0? nth is such a fundamental function that
> it should not show such degradation in performance. I'm about to dig through
> the commit logs to find out more, but that's gonna take a while and I hope
> someone from Clojure/Core can shed some light instead.
>
> Proposals for workarounds are appreciated too (apart from avoiding
> destructuring)... Moving & reducing destructuring in the inner (let)
> improves it somewhat, but not much and makes the code less legible:
>
> (defn foo2 [t p]
>   (let [[d r x2] (t 3)
>         xx (- (d 0) (p 0)) yy (- (d 0) (p 0))]
>     (< (+ (* xx xx) (* yy yy)) r)))
>
> 1.4.0
>
> user=> (bench 100 (dotimes [i 100000] (foo2 t [i i])))
> {:median 17.122, :max 108.78, :min 14.293, :avg 19.723170000000007}
>
> 1.5.0-master-SNAPSHOT
>
> user=> (bench 100 (dotimes [i 100000] (foo2 t [i i])))
> {:median 17.146, :max 93.47699999999999, :min 13.777, :avg
> 18.988480000000003}
>
> Many thanks!
>
> K.
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Meikel Brandmeyer (kotarak)]

Hi,

Am Freitag, 5. Oktober 2012 10:58:05 UTC+2 schrieb Karsten Schmidt:

I've also seen the checks for RandomAccess and Sequential and by simply moving them to the top (after the null check) of the long if-then cascade in RT.nthFrom(), the old performance is restored. I will open a ticket and submit a patch, but have to send in the CA first.

I'm a bit surprised about this, because vectors are Indexed. So they should not hit nthFrom() at all, since this case is handled in nth(). So changing nthFrom() should not have any impact on the speed of vector destructuring.

Kind regards
Meikel