Arc Forumnew | comments | leaders | submitlogin
Re: waterhouse's AVL trees
3 points by Pauan 3619 days ago | 9 comments
Because I cannot post on http://arclanguage.org/item?id=14181 anymore, I created this discussion instead.

waterhouse's post on AVL trees was extremely helpful to me, and I thank you a lot for it. It's hard finding algorithms to create efficient immutable data structures (almost all tutorials teach you how to make mutable AVL/Red Black trees).

I was astonished at how simple the code was, and I was recently in need of a tree data structure, so I tried porting the code over to JavaScript. In doing so, I found that insertion works very well (and is actually really fast! The immutable AVL trees are competitive in speed to JavaScript's built-in mutable objects!).

However, deletion did not work correctly. To be more specific, the deletion algorithm can sometimes create an unbalanced tree.

First, I must correct the "aremove" function a little, since it had some typos:

  (def aremove (less x tree)
    (if no.tree
        (err "aremove: failed to find" x "in" tree)
        (is x tree!dt)
        (amerge tree!lf tree!rt)
        (less x tree!dt)
        (node/r tree!dt
                (aremove less x tree!lf)
                tree!rt)
        (node/r tree!dt
                tree!lf
                (aremove less x tree!rt))))
Now I will introduce a "verify" function that will test that a tree conforms to all of the AVL requirements:

  ; Depth must be correct
  (def verify-depth (tree)
    (is (depth tree)
        (inc:max (depth tree!lf)
                 (depth tree!rt))))

  ; Depth must not vary by more than 1
  (def verify-height (tree)
    (let diff (- (depth tree!lf)
                 (depth tree!rt))
      (in diff -1 0 1)))

  (def verify-tree (tree tests)
    ; Empty trees are always valid
    (or (no tree)
        (and (verify-depth  tree)
             (verify-height tree)

             ; Verify that:
             ;   #1 all keys to the left  are lower   than
             ;   #2 all keys to the right are greater than
             (all (fn (f) (f tree)) tests)
             (verify-tree tree!lf (cons (fn (x) (< x!dt tree!dt)) tests))
             (verify-tree tree!rt (cons (fn (x) (> x!dt tree!dt)) tests)))))

  (def verify (tree)
    (if (verify-tree tree nil)
      tree
      (err "bad tree")))
Now I will create a list of the numbers 0 to 1000, but in a random order:

  ; This is a part of Arc/Nu and is *not* a part of Arc 3.1,
  ; but it's necessary because Racket has a shuffle function and Arc doesn't
  (%:namespace-require 'racket/list)

  ; Get a list of numbers from 0 - 1000, but shuffled in a random order
  (= numbers (%.shuffle (range 0 1000)))
I also need to create a "foldl" function since Arc's "reduce" does not accept an init argument:

  (def foldl (f init x)
    (if (no x)
      init
      (foldl f (f init (car x)) (cdr x))))
And now let's create an AVL tree by inserting the numbers into it, in sorted order:

  ; This takes a while, but it does eventually finish
  (= tree
    (foldl (fn (x y)
             (verify (ainsert < y x)))
           nil
           numbers))
Notice the call to "verify", which makes sure that at the end of every insertion, the tree is still correct.

Now let's try removing the elements from the tree:

  (= tree
    (foldl (fn (x y)
             (verify (aremove < y x)))
           tree
           numbers))
With extremely high probability, you will get "error: bad tree".

The problem is actually with the "node/r" function. Strangely enough, it's incorrect in a way that only causes problems with deletion, not insertion. The fix is really simple, though:

  (def node/r (d x y) ;like node but rebalances
    (if (> depth.x (inc depth.y))
        (if (< (depth x!lf) (depth x!rt))
            (node x!rt!dt (node x!dt x!lf x!rt!lf)
                  (node d x!rt!rt y))
            (node x!dt x!lf (node d x!rt y)))
        (> depth.y (inc depth.x))
        (if (< (depth y!rt) (depth y!lf))
            (node y!lf!dt (node d x y!lf!lf)
                  (node y!dt y!lf!rt y!rt))
            (node y!dt (node d x y!lf) y!rt))
        (node d x y)))
All I did was swap the calls to "node" so that the double rotation is checked for first, using "<" rather than ">". And that's it! It took me quite a while to figure out what the problem was, since "node/r" works fine for insertion.

Also, I was quite surprised that the "amerge" function actually works. It seems quite clever to me. Binary search tree deletion normally uses an algorithm like this:

  ; Finds the minimum element in a tree and returns a list of:
  ;   #1 The minimum element
  ;   #2 The tree, excluding the minimum element
  (def amin (tree)
    (if (no tree!lf)
      (list tree tree!rt)
      (let (min left) (amin tree!lf)
        (list min (node/r tree!dt left tree!rt)))))

  (def amerge (a b) ;not a general merge; assumes [all of a] ≤ [all of b]
    (if no.a b
        no.b a
        (let (min right) (amin b)
          (node/r min!dt a right))))
In any case, thanks again! Now I have lovely fast immutable sorted dictionaries, sorted sets, and unsorted arrays using AVL trees. Most operations are O(log n), including concatenating two arrays!


3 points by Pauan 3616 days ago | link

Here are some performance metrics, using Node.js v0.10.22 and http://benchmarkjs.com/. Higher numbers are better.

Get from a dictionary with 1 key:

  Mutable object     x 27,279,012 ops/sec ±0.74% (97 runs sampled)
  Frozen object      x 26,178,537 ops/sec ±0.18% (101 runs sampled)
  RB Tree            x 43,176,557 ops/sec ±0.34% (94 runs sampled)
  Immutable AVL Tree x 38,223,676 ops/sec ±0.12% (101 runs sampled)
  Immutable-js Map   x 19,359,187 ops/sec ±0.22% (100 runs sampled)
Insert 1 key into an empty dictionary:

  Mutable object             x 6,957,772 ops/sec ±1.96% (96 runs sampled)
  Mutable object copying     x 6,323,751 ops/sec ±0.62% (99 runs sampled)
  Frozen object copying      x   201,268 ops/sec ±1.56% (91 runs sampled)
  RB Tree                    x 7,872,867 ops/sec ±0.42% (100 runs sampled)
  Immutable AVL Tree         x 6,349,293 ops/sec ±0.63% (97 runs sampled)
  Immutable-js Map           x 1,872,937 ops/sec ±0.17% (102 runs sampled)
  Immutable-js Map Transient x 2,056,430 ops/sec ±1.75% (96 runs sampled)
Insert 1 key into an empty dictionary and then remove 1 key:

  Mutable object             x 2,217,063 ops/sec ±0.72% (99 runs sampled)
  Mutable object copying     x 1,993,320 ops/sec ±0.58% (98 runs sampled)
  Frozen object copying      x   143,611 ops/sec ±1.48% (93 runs sampled)
  RB Tree                    x 3,923,739 ops/sec ±0.41% (95 runs sampled)
  Immutable AVL Tree         x 3,511,233 ops/sec ±0.38% (97 runs sampled)
  Immutable-js Map           x 1,334,255 ops/sec ±0.55% (100 runs sampled)
  Immutable-js Map Transient x   886,683 ops/sec ±0.16% (103 runs sampled)
----

Get from a dictionary with 10 keys:

  Mutable object     x 28,446,194 ops/sec ±0.44% (99 runs sampled)
  Frozen object      x 25,922,457 ops/sec ±0.24% (99 runs sampled)
  RB Tree            x 16,603,460 ops/sec ±0.43% (97 runs sampled)
  Immutable AVL Tree x 22,367,775 ops/sec ±0.61% (95 runs sampled)
  Immutable-js Map   x 17,869,208 ops/sec ±0.28% (100 runs sampled)
Insert 10 keys into an empty dictionary:

  Mutable object             x 600,844 ops/sec ±0.71% (100 runs sampled)
  Mutable object copying     x 137,961 ops/sec ±0.16% (102 runs sampled)
  Frozen object copying      x   8,982 ops/sec ±1.77% (97 runs sampled)
  RB Tree                    x 914,296 ops/sec ±0.25% (99 runs sampled)
  Immutable AVL Tree         x 414,025 ops/sec ±0.48% (100 runs sampled)
  Immutable-js Map           x 219,537 ops/sec ±0.44% (101 runs sampled)
  Immutable-js Map Transient x 305,737 ops/sec ±1.06% (98 runs sampled)
Insert 10 keys into an empty dictionary and then remove 10 keys:

  Mutable object             x 302,855 ops/sec ±0.74% (100 runs sampled)
  Mutable object copying     x  49,878 ops/sec ±0.57% (98 runs sampled)
  Frozen object copying      x   8,899 ops/sec ±1.59% (95 runs sampled)
  RB Tree                    x 534,523 ops/sec ±0.54% (99 runs sampled)
  Immutable AVL Tree         x 144,249 ops/sec ±0.16% (99 runs sampled)
  Immutable-js Map           x 111,517 ops/sec ±0.37% (99 runs sampled)
  Immutable-js Map Transient x 173,799 ops/sec ±0.48% (100 runs sampled)
----

Get from a dictionary with 100 keys:

  Mutable object     x 25,410,034 ops/sec ±0.19% (102 runs sampled)
  Frozen object      x 25,156,950 ops/sec ±0.27% (101 runs sampled)
  RB Tree            x 23,728,410 ops/sec ±0.17% (100 runs sampled)
  Immutable AVL Tree x 21,287,235 ops/sec ±0.40% (97 runs sampled)
  Immutable-js Map   x 14,605,600 ops/sec ±0.55% (92 runs sampled)
Insert 100 keys into an empty dictionary:

  Mutable object             x 58,322 ops/sec ±0.55% (100 runs sampled)
  Mutable object copying     x    818 ops/sec ±0.44% (99 runs sampled)
  Frozen object copying      x    139 ops/sec ±0.93% (81 runs sampled)
  RB Tree                    x 51,910 ops/sec ±0.45% (99 runs sampled)
  Immutable AVL Tree         x 20,738 ops/sec ±0.47% (100 runs sampled)
  Immutable-js Map           x 14,000 ops/sec ±1.65% (97 runs sampled)
  Immutable-js Map Transient x 37,714 ops/sec ±0.16% (102 runs sampled)
Insert 100 keys into an empty dictionary and then remove 100 keys:

  Mutable object             x 31,602 ops/sec ±0.56% (100 runs sampled)
  Mutable object copying     x    729 ops/sec ±1.54% (97 runs sampled)
  Frozen object copying      x    137 ops/sec ±2.12% (80 runs sampled)
  RB Tree                    x 31,957 ops/sec ±0.43% (99 runs sampled)
  Immutable AVL Tree         x  7,122 ops/sec ±0.47% (99 runs sampled)
  Immutable-js Map           x  6,001 ops/sec ±0.57% (99 runs sampled)
  Immutable-js Map Transient x 19,958 ops/sec ±0.49% (99 runs sampled)
----

"Mutable object" means a plain old mutable JavaScript object.

"Frozen object" means a plain old mutable JavaScript object that was made immutable using `Object.freeze(foo)`.

"Mutable object copying" means a plain old mutable JavaScript object that was first copied before performing each insertion/deletion.

"RB Tree" means mutable Red Black trees that I implemented in JavaScript: https://github.com/onilabs/stratifiedjs/blob/91d173989c64181...

"Immutable AVL Tree" means waterhouse's algorithm, ported to JavaScript: https://github.com/onilabs/stratifiedjs/blob/c1e5d670784f659...

"Immutable-js Map" means https://github.com/facebook/immutable-js.

"Immutable-js Map Transient" means an Immutable-js Map that uses "withMutations" for extra speed.

I also want to test out ClojureScript's data structures, but I haven't gotten around to it yet.

----

As I said earlier, AVL trees are fast. They tend to be 0-3x slower than JavaScript objects.

Stop and think about that for a moment: JavaScript objects are mutable, they're written in C++, they're heavily optimized with various tricks, and they're probably implemented as hash tables.

Meanwhile, AVL trees are immutable, do not use any kind of optimization tricks (the algorithms are very simple and straightforward), and they are implemented in vanilla JavaScript, in less than 400 lines of code.

JavaScript engines are fast. So fast that immutable AVL trees are completely viable. I would not hesitate to replace all my programs with them. This is quite amazing.

In addition, notice that according to those benchmark numbers, you can create 20 empty AVL trees, then insert 100 keys into each AVL tree (for a total of 2,000 insert operations)... once per millisecond. In this case, worrying about the performance cost of immutability is a huge premature optimization.

(I'm not directing this at anybody in particular, in fact I am the kind of person that does premature optimization, so these numbers help with my own personal fears about performance.)

----

I'll test the performance of unsorted arrays soon and post the results here.

-----

2 points by Pauan 3616 days ago | link

How disappointing. Mori[1] (which uses ClojureScript's data structures) was either the same as Immutable-js, or significantly worse. In the end, AVL trees win by a large margin for small to medium dictionaries, while Immutable-js performs better for large (> 100 keys) dictionaries.

Get/insert/remove 1 key:

  Immutable AVL Tree x 37,909,434 ops/sec ±0.37% (101 runs sampled)
  Immutable-js Map   x 19,492,874 ops/sec ±0.15% (101 runs sampled)
  Mori Hash Map      x  2,306,565 ops/sec ±0.74% (96 runs sampled)
  Mori Sorted Map    x 13,424,409 ops/sec ±0.51% (97 runs sampled)

  Immutable AVL Tree x 6,257,569 ops/sec ±0.43% (99 runs sampled)
  Immutable-js Map   x 2,111,085 ops/sec ±1.07% (91 runs sampled)
  Mori Hash Map      x 1,553,193 ops/sec ±0.77% (93 runs sampled)
  Mori Sorted Map    x 3,785,671 ops/sec ±0.43% (96 runs sampled)

  Immutable AVL Tree x 3,426,260 ops/sec ±1.38% (97 runs sampled)
  Immutable-js Map   x 1,415,893 ops/sec ±0.41% (96 runs sampled)
  Mori Hash Map      x   699,113 ops/sec ±0.40% (98 runs sampled)
  Mori Sorted Map    x 1,550,116 ops/sec ±1.54% (100 runs sampled)
Get/insert/remove 10 keys:

  Immutable AVL Tree x 21,954,005 ops/sec ±0.81% (98 runs sampled)
  Immutable-js Map   x 17,236,706 ops/sec ±1.02% (99 runs sampled)
  Mori Hash Map      x  2,474,120 ops/sec ±0.77% (95 runs sampled)
  Mori Sorted Map    x    911,264 ops/sec ±0.41% (100 runs sampled)

  Immutable AVL Tree x 399,700 ops/sec ±0.15% (97 runs sampled)
  Immutable-js Map   x 218,274 ops/sec ±0.63% (98 runs sampled)
  Mori Hash Map      x 150,978 ops/sec ±0.74% (96 runs sampled)
  Mori Sorted Map    x  73,598 ops/sec ±0.68% (98 runs sampled)

  Immutable AVL Tree x 135,120 ops/sec ±0.76% (99 runs sampled)
  Immutable-js Map   x 100,893 ops/sec ±0.20% (97 runs sampled)
  Mori Hash Map      x  74,750 ops/sec ±10.95% (96 runs sampled)
  Mori Sorted Map    x  42,696 ops/sec ±0.45% (99 runs sampled)
Get/insert/remove 100 keys:

  Immutable AVL Tree x  6,467,149 ops/sec ±0.38% (93 runs sampled)
  Immutable-js Map   x 14,233,214 ops/sec ±1.05% (96 runs sampled)
  Mori Hash Map      x  2,513,928 ops/sec ±1.24% (98 runs sampled)
  Mori Sorted Map    x    384,132 ops/sec ±0.53% (98 runs sampled)

  Immutable AVL Tree x 19,760 ops/sec ±0.52% (100 runs sampled)
  Immutable-js Map   x 12,798 ops/sec ±0.26% (100 runs sampled)
  Mori Hash Map      x 10,619 ops/sec ±2.59% (93 runs sampled)
  Mori Sorted Map    x  3,078 ops/sec ±1.49% (98 runs sampled)

  Immutable AVL Tree x  6,420 ops/sec ±0.51% (101 runs sampled)
  Immutable-js Map   x  6,204 ops/sec ±0.20% (99 runs sampled)
  Mori Hash Map      x  5,394 ops/sec ±0.81% (93 runs sampled)
  Mori Sorted Map    x  1,757 ops/sec ±0.51% (100 runs sampled)
---

* [1]: https://github.com/swannodette/mori

-----

2 points by Pauan 3616 days ago | link

As promised, here are the benchmarks for unsorted arrays: http://pastebin.com/raw.php?i=DyTHMHNZ

You can also see it in chart form: http://i.imgur.com/BI0NDoD.png

----

So, today I learned that cons cells, despite having O(n) behavior, are really fast. They outperform mutable JS arrays at random inserts!

It's only once you get up to ~100 elements that AVL trees start to outperform cons cells. A good optimization would be to use cons cells for small lists, and then automatically switch to AVL trees once the list grows to be a certain size.

-----

4 points by waterhouse 3617 days ago | link

Thank you for your kind words. I'm glad you've found my post useful. And that's a good catch about node/r.

It looks like the two versions of node/r differ just in the case when (depth x!lf) = (depth x!rt) [and likewise for y], which it appears I had assumed would not be true; perhaps that was valid for insertions but not deletions. (I must admit deletions came as a bit of an afterthought, as evidenced by the typos in "aremove".) I'm pleased that the resolution is so simple.

Anyway, thanks to you, we now have AVL trees that are actually tested and proven to work.

-----

2 points by Pauan 3616 days ago | link

In case anybody wants it, here is the JavaScript code for sorted dictionaries, sorted sets, and unsorted arrays[1]:

https://github.com/onilabs/stratifiedjs/blob/c1e5d670784f659...

It includes algorithms for getting/inserting/removing an element at a particular index (in the case of arrays), and code for getting/inserting/removing an element in sorted order (for dictionaries and sets).

If anybody wants, I can translate the code from JavaScript to Arc.

---

* [1]: Adding in sorted arrays shouldn't be hard, but I haven't had any need for them yet.

-----

3 points by Pauan 3619 days ago | link

In fact, the normal binary search tree deletion can sometimes cause an unbalanced tree when concatting two arrays, but waterhouse's "amerge" function works correctly!

-----

1 point by akkartik 3616 days ago | link

What arc did you run this on, Pauan? I'm trying to add it to anarki and having trouble with nil-terminated lists and shuffle:

  arc> ($.shuffle '(1 2 3))
  sort: contract violation
    expected: list?
    given: '(1 2 3 . nil)
    context...:
     /home/agaram/.local/racket/collects/racket/private/list.rkt:43:2: sort7
     /home/agaram/Desktop/s/anarki/ac.scm:1215:4
(The require seems unnecessary on anarki.)

-----

2 points by Pauan 3616 days ago | link

I used Arc/Nu (https://github.com/arclanguage/arc-nu).

It seems the problem with Anarki is that Arc's lists are terminated with the symbol 'nil rather than Racket's null. So you have to convert from Arc lists to Racket lists (and back again). Here is the relevant code:

https://github.com/arclanguage/anarki/blob/0c4eb66c162f973e7...

-----

2 points by akkartik 3616 days ago | link

Pushed, thanks. https://github.com/arclanguage/anarki/commit/af2ea9c8f4

-----