Arc Forumnew | comments | leaders | submitlogin
3 points by Pauan 3661 days ago | link | parent

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 3661 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 3661 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.

-----