transient quicksort

[Jonas]

Hi

I'm playing with the new transient/persistent! features in Clojure. I
have implemented quicksort as described on wikipedia (http://
en.wikipedia.org/wiki/Quicksort#Algorithm). Here is the code:

(defn swap-index! [v i j]
(let [tmp (v i)]
(assoc! v i (v j))
(assoc! v j tmp)))

(defn partition! [v left-index right-index pivot-index]
(let [pivot-value (v pivot-index)]
(swap-index! v pivot-index right-index)
(loop [i left-index store-index left-index]
(if (< i right-index)
(if (<= (v i) pivot-value)
(do (swap-index! v i store-index)
(recur (inc i) (inc store-index)))
(recur (inc i) store-index))
(do (swap-index! v store-index right-index)
store-index)))))

(defn qsort! [v left right]
(when (> right left)
(let [pivot-index left
pivot-new-index (partition! v left right pivot-index)]
(qsort! v left (dec pivot-new-index))
(qsort! v (inc pivot-new-index) right))))

(defn qsort [v]
(let [tv (transient v)]
(qsort! tv 0 (dec (count v)))
(persistent! tv)))

This sorts a vector of doubles in about 6000-7000 msec on my machine:

user=> (def s (time (qsort (rvector 1000000))))
"Elapsed time: 6681.35889 msecs"

This is much faster than the classical functional programming
"quicksort":

; From http://rosettacode.org/wiki/Quicksort#Clojure
(defn qsort-rs [[pivot & xs]]
(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
[pivot]
(qsort (remove smaller xs))))))

user=> (def s (time (doall (qsort-rs (rvector 1000000)))))
"Elapsed time: 32565.537389 msecs"

The Java sort however is about 5 times faster then the transient
version:

user=> (def s (time (sort (rvector 1000000))))
"Elapsed time: 1354.427239 msecs"

Can you give any hints on how I can make the transient sort faster? I
would like to get as close as possible to the native Java speed.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Here is the rvector function as used in the timing tests (for
completeness):

(defn rvector [n]
(loop [i 0 v (transient [])]
(if (< i n)
(recur (inc i) (conj! v (Math/random)))
(persistent! v))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

These new clojure features are so much fun!

[Albert Cardona]

Jonas wrote:
> Can you give any hints on how I can make the transient sort faster? I
> would like to get as close as possible to the native Java speed.

My guess is that you need primitive type hints. For example:

(let [pivot-value (v pivot-index)]

could be:

(let [pivot-value (int (v pivot-index))]

... and so on.

Albert

--
Albert Cardona
http://albert.rierol.net

[Jonas Enlund]

I get ~8% performance boost by turning swap-index! into a macro:

(defmacro swap-index! [v i j]
`(let [tmp# (~v ~i)]
(assoc! ~v ~i (~v ~j))
(assoc! ~v ~j tmp#)))

[Jonas Enlund]

On Tue, Aug 4, 2009 at 3:55 PM, Albert Cardona<sapr...@gmail.com> wrote:
>
> Jonas wrote:
>>  Can you give any hints on how I can make the transient sort faster? I
>>  would like to get as close as possible to the native Java speed.
>
>
> My guess is that you need primitive type hints. For example:
>
>     (let [pivot-value (v pivot-index)]
>
>
>
> could be:
>
>    (let [pivot-value (int (v pivot-index))]
>
>
> ... and so on.
>
> Albert
>

I have tried to add type hints but they don't seem to speed things up.
For example, if I add type hints to the partition! loop (where I would
have thought that
type hints would make the biggest difference) I don't see a speedup at all:

(defn partition! [....]
...
(loop [i (int left-index) store-index (int left-index)]
...)

[Mark Addleman]

I haven't tried the code, so caveat emptor:

If you convert partition to a macro *AND* use type-hints, I suspect
you'll see a win. The issue here is the primitive boxing that must
occur when when calling a function. It's my hope that when a macro is
used with the appropriate type hints, the Clojure compiler won't box
the primitives but I don't know that.

On Aug 4, 6:03 am, Jonas Enlund <jonas.enl...@gmail.com> wrote:

>    ...)- Hide quoted text -
>
> - Show quoted text -

[Jarkko Oranen]

On Aug 4, 11:08 am, Jonas <jonas.enl...@gmail.com> wrote:
> Hi
>
> I'm playing with the new transient/persistent! features in Clojure. I
> have implemented quicksort as described on wikipedia (http://
> en.wikipedia.org/wiki/Quicksort#Algorithm). Here is the code:
>
> (defn swap-index! [v i j]
>   (let [tmp (v i)]
>     (assoc! v i (v j))
>     (assoc! v j tmp)))

I think Rich mentioned on IRC that you should not reuse the transient
vector binding after an operation; that it works is merely an
implementation detail. The transient documentation page also says
tells to "capture return value, use for next call". So:

(defn swap-index! [tv i j]
(let [tmp (tv i)]
(-> tv
(assoc! i (v j))
(assoc! j tmp))))

And similar modifications for the quicksort below.

> ; Fromhttp://rosettacode.org/wiki/Quicksort#Clojure

> (defn qsort-rs [[pivot & xs]]
>   (when pivot
>     (let [smaller #(< % pivot)]
>       (lazy-cat (qsort (filter smaller xs))
>                 [pivot]
>                 (qsort (remove smaller xs))))))
>
> user=> (def s (time (doall (qsort-rs (rvector 1000000)))))
> "Elapsed time: 32565.537389 msecs"
>
> The Java sort however is about 5 times faster then the transient
> version:
>
> user=> (def s (time (sort (rvector 1000000))))
> "Elapsed time: 1354.427239 msecs"
>
> Can you give any hints on how I can make the transient sort faster? I
> would like to get as close as possible to the native Java speed.

This is partially comparing apples to oranges though: sort returns a
lazy seq, while
the quicksort algorithm produces a proper vector.

Anyway, (nth v i) might be somewhat faster than (v i) because it gets
inlined. I did not try, though.

Below is code that avoids reusing the reference to v:

(defn swap-index! [v i j]

(let [tmp (nth v i)]
(-> v
(assoc! i (nth v j))
(assoc! j tmp))))

(defn partition! [v left-index right-index pivot-index]

(let [pivot-value (nth v pivot-index)
new-v (swap-index! v pivot-index right-index)]
(loop [v new-v, i left-index, store-index left-index]
(if (< i right-index)
(if (<= (nth v i) pivot-value)
(recur (swap-index! v i store-index) (inc i) (inc store-
index))
(recur v (inc i) store-index))
[(swap-index! v store-index right-index)
store-index]))))

(defn qsort! [v left right]

(if (> right left)
(let [pivot-index left
[new-v pivot-new-index] (partition! v left right pivot-
index)]
(-> new-v
(qsort! left (dec pivot-new-index))
(qsort! (inc pivot-new-index) right))))
v)

(defn qsort [v]
(let [tv (transient v)]
(qsort! tv 0 (dec (count v)))
(persistent! tv)))

--
Jarkko

[jdz]

On Aug 4, 11:08 am, Jonas <jonas.enl...@gmail.com> wrote:

> Can you give any hints on how I can make the transient sort faster? I
> would like to get as close as possible to the native Java speed.

You are comparing apples to oranges. Clojure's persistent vectors do
not magically turn into Java arrays when using the new transients
feature; they are still good old persistent vectors, with the added
bonus that some operations can be done by mutating existing structure.
But this structure is still the same old awesome piece of persistent
vector!

A bit lame analogy, but maybe helps some people understand the point
I'm trying to make. It's like the good old story about how MySQL is
"faster" than PostgreSQL. Not. At least if you want safety.

What the native sort function does is just what I wanted to suggest
you do: turn the persistent vector into a plain old array, sort that,
and then convert the sorted array back into a Clojure data structure.

[Jonas Enlund]

Hi,

Thank's for pointing this out for me. I didn't realize how to use
these constructs correctly. Seeing the !-mark i just thought that
assoc! was to be used like set! set-car! set-cdr! in Scheme... my
mistake.

Ok, I will try that

Nice, thank you!

>
> --
> Jarkko
> >
>