[ANN] Understanding the Persistent Vector

[Jean Niklas L'orange]

Hello fellow Clojurians,

I am happy to announce that I have finished my blogpost series on the persistent

vector. It consists of five parts:

1. The basic algorithms
   
2. Indexing
   
3. The tail optimisation
   
4. Transients
5. Performance (which is a summary of this detailed blogpost)

I hope this will help you to get a good understanding of how the algorithms on

the data structure work, how the optimisations work, and how efficient it is on

the JVM.

Constructive criticism, both positive and negative, is appreciated.

Enjoy!

(NB: I haven't gotten around to fix the illustrations in part 3, so

unfortunately it will be a bit hard to read if you print it out in grayscale.

It's on my todo-list.)

-- Jean Niklas L'orange

[Rangel Spasov]

Great work!

[Dave Della Costa]

This is wonderful, I can't wait to dig in!

On 2015/03/01 1:14, Jean Niklas L'orange wrote:
> Hello fellow Clojurians,
>
> I am happy to announce that I have finished my blogpost series on the
> persistent
> vector. It consists of five parts:
>

> 1. The basic algorithms
> <http://hypirion.com/musings/understanding-persistent-vector-pt-1>
> 2. Indexing
> <http://hypirion.com/musings/understanding-persistent-vector-pt-2>
> 3. The tail optimisation
> <http://hypirion.com/musings/understanding-persistent-vector-pt-3>
> 4. Transients
> <http://hypirion.com/musings/understanding-clojure-transients>
> 5. Performance
> <http://hypirion.com/musings/persistent-vector-performance-summarised>

> (which is a summary of this detailed blogpost

> <http://hypirion.com/musings/persistent-vector-performance>)

>
> I hope this will help you to get a good understanding of how the
> algorithms on
> the data structure work, how the optimisations work, and how efficient
> it is on
> the JVM.
>
> Constructive criticism, both positive and negative, is appreciated.
>
> Enjoy!
>
> (NB: I haven't gotten around to fix the illustrations in part 3, so
> unfortunately it will be a bit hard to read if you print it out in
> grayscale.
> It's on my todo-list.)
>
> -- Jean Niklas L'orange
>

> --
> 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 unsubscribe from this group and stop receiving emails from it, send
> an email to clojure+u...@googlegroups.com
> <mailto:clojure+u...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

[Rostislav Svoboda]

Great work! Thank you

On 28 February 2015 at 17:14, Jean Niklas L'orange

> --
> 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 unsubscribe from this group and stop receiving emails from it, send an

> email to clojure+u...@googlegroups.com.

[Rostislav Svoboda]

Hi Jean

> The tail optimisation
> http://hypirion.com/musings/understanding-clojure-transients

It took me a second to find out how the graphs for the vector-trie and
tail correspond to each other.
Please consider slightly deeper explanation or add some visual clues.
Something like:
http://picpaste.com/pics/tails-colored.1425379672.png

[Jean Niklas L'orange]

Hi Bost,

Thanks for the input!

Yeah, I agree it might be a bit confusing right now. I'll definitely change it to something that's a bit easier to grok, probably with some inspiration from your suggestion.

[Frank Castellucci]

Jean

It's been added to the must reads list.

Will you be doing this for other data types?

Again, Great Work!

Frank

[Jean Niklas L'orange]

Hi Frank,

On Wednesday, March 4, 2015 at 12:24:42 PM UTC+1, Frank Castellucci wrote:

Will you be doing this for other data types?

I will have a small break first, but I intend to do the same kind of series for persistent hash maps/sets. Maybe even RRB-trees if people are interested (I found them to be pretty hard to grasp by the paper alone).

Again, Great Work!

Thanks! =)

-- Jean Niklas

[danl...@gmail.com]

This was fantastic.  Really looking forward to the RRB Tree.