20 Days of Clojure - Day 7: PersistentVector

[Lou Franco]

I've been doing 20 days of clojure on my blog.  Today's describes the internals of PersistentVector objects.  If anyone sees errors in the description, please let me know.

http://loufranco.com/blog/files/20-Days-of-Clojure-Day-7.html

--
Lou Franco
lfr...@greenwave-solutions.com

[Rich Hickey]

On Mar 7, 2:02 pm, "Lou Franco" <loumfra...@gmail.com> wrote:
> I've been doing 20 days of clojure on my blog. Today's describes the
> internals of PersistentVector objects. If anyone sees errors in the
> description, please let me know.
>

I've been enjoying the series Lou, thanks.

I think where you say:

(def v2 (assoc v1 4))

you intended:

(def v2 (assoc v1 1 4))

I think the comparison to Okasaki's is tenuous - he's going for the
interface of list with better-than-linear random lookup performance,
while I'm going for near-O(1) performance for all operations.

Your point about the resulting vectors being immutable is spot on -
that's the key to multithreading. An interesting point of comparison
with purely-functional solutions such as that which Okasaki writes
about is that the Clojure vector can be log32N specifically because I
can use mutation - when cloning - , i.e. the tree is log32N deep and a
node can be copied in O(1) time due to arraycopy + indexed array set.
And yes, the vectors are optimized for lookup - in practice, log32N
blows logN out of the water.

Looking forward to more (leave me something to talk about on the
20th :)

Rich

[Rich Hickey]

On Mar 7, 3:07 pm, Rich Hickey <richhic...@gmail.com> wrote:
> On Mar 7, 2:02 pm, "Lou Franco" <loumfra...@gmail.com> wrote:
>
> > I've been doing 20 days of clojure on my blog. Today's describes the
> > internals of PersistentVector objects. If anyone sees errors in the
> > description, please let me know.
>
> I've been enjoying the series Lou, thanks.

> I think the comparison to Okasaki's is tenuous - he's going for the
> interface of list with better-than-linear random lookup performance,
> while I'm going for near-O(1) performance for all operations.
>

I re-read Okasaki's paper yesterday and woke up today with an idea for
speeding up the Clojure vector conj and pop. They are now 2-5x faster
than they were. The trick is to keep the tail of the vector out of the
tree until it is a full (32-element) node. Note that this greatly
speeds up vector construction, which typically consists of repeatedly
conj'ing onto [].

Make sure you check out Lou's latest entry, where he delves into the
details of PersistentHashMap:

http://loufranco.com/blog/files/20-Days-of-Clojure-Day-8.html

Rich