Use RRB-Tree in Vector

[Methuselah96]

From @nathansobo on Tue, 05 Aug 2014 18:42:46 GMT

I'm attempting to use vectors to represent the contents of 5-line tiles in Atom, and I'm keeping the groups of lines up to date with repeated applications of splice. After not very long, however, performance of iteration seems to degrade. Is this a known issue?

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38

[Methuselah96]

From @leebyron on Tue, 05 Aug 2014 20:18:12 GMT

Not yet known, you're definitely giving it a good stress test.

Is there a more contrived version of this that you can share so I can figure out what's up?

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51253496

[Methuselah96]

From @swannodette on Fri, 16 Jan 2015 01:05:39 GMT

@Pauan concat in Mori just produces a lazy sequence so the cost is amortized.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70192693

[Methuselah96]

From @leebyron on Tue, 05 Aug 2014 20:24:36 GMT

Oh I just re-read this and realizing you said splice() not slice(). Yes, splice is quite inefficient.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51254324

[Methuselah96]

From @leebyron on Fri, 16 Jan 2015 13:55:15 GMT

Totally. The beauty of data structures is that there are so many variants and each one has its ideal use.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70256155

[Methuselah96]

From @leebyron on Wed, 06 Aug 2014 01:48:35 GMT

I'll definitely keep it in mind, so I'll keep this open. At the very least I think a real TODO is clarifying splice()'s use with withMutable and even finding incremental perf improvements. — Sent from Mailbox

On Tue, Aug 5, 2014 at 3:04 PM, Nathan Sobo notifications@github.com wrote:

Yeah, great point. I'll just replace the entire Vector for now because it has so few elements. Thanks for your thoughts. Feel free to close this unless you'd like to look into improving splice so far as it's possible.

Reply to this email directly or view it on GitHub: https://github.com/facebook/immutable-js/issues/38#issuecomment-51267032

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51284776

[Methuselah96]

From @leebyron on Fri, 16 Jan 2015 13:42:33 GMT

Nice work @Pauan!

I haven't spent much time benchmarking or optimizing Immutable.js yet, so there are likely some wins to be had. A huge thanks to you and @swannodette for illustrating some baselines to strive for. It's always awesome and inspiring to see the headroom to strive to close :). However one thing I want to be cautious of, and part of why I've under-prioritized benchmarking, is comparing benchmarks to every day use. I don't think benchmarks are enough to prove or disprove an idea unless they closely mirror common use scenarios. AVL trees are really interesting and I'm looking forward to seeing how they may play a role in this lib, or at least in the new landscape of these structures as a whole. May I also suggest a composite test where reads and writes are interleaved at different frequencies? Most common use tends to read a lot more than write which is part of why Clojure/Scala/immutable chose to optimize for reads instead of writes

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70254713

[Methuselah96]

From @swannodette on Thu, 15 Jan 2015 20:28:40 GMT

@graue your assessment of subvec aka slice in Clojure is correct. concat is not O(1) in Mori.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70155723

[Methuselah96]

From @leebyron on Wed, 06 Aug 2014 15:05:34 GMT

Interesting. I'll read up! Thanks guys. — Sent from Mailbox

On Wed, Aug 6, 2014 at 6:23 AM, Alexander Semenov notifications@github.com wrote:

BTW, that official paper on RRB trees is lacking many details. I would recommend to look at this thesis.

Reply to this email directly or view it on GitHub: https://github.com/facebook/immutable-js/issues/38#issuecomment-51333012

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51347466

[Methuselah96]

From @dahjelle on Thu, 13 Nov 2014 17:08:04 GMT

Nevermind. #37 explains. Thanks!

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-62927808

[Methuselah96]

From @leebyron on Tue, 05 Aug 2014 21:50:36 GMT

splice() is definitely an exensive operation regardless as everything after the splice point needs to be shifted (moved in memory) for regular arrays. The same is true for a HAMT.

I was thinking about this a bit and wonder if you might benefit from a different kind of data structure that's designed around making splice() fast. Linked lists are really fast at this if you're willing to give up O(1) access and immutability. Perhaps some kind of b-tree would be well adapted to immutable(persistent) form and deal well with splicing.

What's the specific use case here? — Sent from Mailbox

On Tue, Aug 5, 2014 at 1:43 PM, Nathan Sobo notifications@github.com wrote:

For now I'm just building a new vector as they're quite small.

Is this inefficiency inherent in the nature of the trie data structure you're using or something implementation-specific? Do the ClojureScript data structures exhibit this issue?

Reply to this email directly or view it on GitHub: https://github.com/facebook/immutable-js/issues/38#issuecomment-51256755

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51265409

[Methuselah96]

From @graue on Sat, 01 Nov 2014 05:51:31 GMT

@hypirion (author of the thesis above): didn't you say you found RRB-trees slower in practice (like, by a constant factor) than the Clojure-style vector for some operations?

I bring this up because if so, that may be an argument for presenting RRB-trees as an alternative implementation rather than replacing the current one.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-61359140

[Methuselah96]

From @nathansobo on Tue, 05 Aug 2014 20:43:06 GMT

For now I'm just building a new vector as they're quite small.

Is this inefficiency inherent in the nature of the trie data structure you're using or something implementation-specific? Do the ClojureScript data structures exhibit this issue?

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51256755

[Methuselah96]

From @nathansobo on Tue, 05 Aug 2014 22:04:37 GMT

Yeah, great point. I'll just replace the entire Vector for now because it has so few elements. Thanks for your thoughts. Feel free to close this unless you'd like to look into improving splice so far as it's possible.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51267032

[Methuselah96]

From @Pauan on Fri, 16 Jan 2015 13:32:27 GMT

With @swannodette's help, I updated the benchmarks to use the latest versions of Immutable-js and Mori. You can find it here:

https://github.com/Pauan/Immutable/blob/javascript/benchmarks/List/2015-01-16

Mori 0.3.2 is significantly faster than 0.2.9. Most of the speed gain comes from using fixed-arity functions in the benchmark code.

My library (without transients) holds up well compared to Mori and Immutable-js (with transients).

My library has extremely fast concat and slice. It does not "cheat": concat and slice are not lazy, they return new Lists, and the old Lists can be garbage collected.

The price for this is a very minor loss of lookup speed: for a list with 1,000,000 elements, my library takes 13 operations to lookup a value. Mori and Immutable-js takes 4 operations.

So, if you only need to insert / remove at the end of a list, then either Mori or Immutable-js are excellent choices.

But if you want good concat / slice performance, or you need to insert at arbitrary indexes, my library offers a much faster alternative. I think the performance of AVL trees + arrays is a lot better than what most people think.

I'm curious to see if RRB-trees improve the performance of splice / concat / slice.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70253569

[Methuselah96]

From @hypirion on Sat, 01 Nov 2014 11:54:28 GMT

There is a lot of additional code required for the RRB-tree cases, but it's designed to switch over to the persistent vector code whenever possible: RRB-tree code can generally detect when the substructure of a node is persistent vector-ish, and will jump to pvec performance at that point in the tree. I did some benchmarks on that, and found no notable performance difference if no slices/concatenations were done on the RRB-tree.

That being said, those were implemented with a lot of twiddling in C with Boehm-GC, and I'd hardly call that equivalent with a javascript engine. I'm not JS expert, but I'd guess the initial implementation of the RRB-tree will be slower than the immutable list for non-slice and concat use, until it's tweaked to the JS engines. I suspect it would be harder to inline and optimise for the optimising compiler. Making it optimisable may take some time (at least based on my own experience), and you probably want to not degrade immutable list performance while you do it.

So If I were you, I would probably start out having the RRB-tree be a different class, and let slice() and concat() convert the immutable lists to RRB-trees, and delegate the work to the RRB-tree implentation. The only additional change in the immutable list implementation would be that VNodes should have an additional field for RRB-tree size tables, which will by default be null.

Again, I don't have much knowledge and experience on how the JS engines optimises and how one would tweak JS code. Perhaps the points I bring up is of no concern at all, and for some reason the performance is equivalent from the get-go.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-61365883

[Methuselah96]

From @Pauan on Fri, 16 Jan 2015 10:42:46 GMT

@swannodette Okay, cool, so it's like a concat over ES6 Iterables. Thanks for answering my many questions.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70236616

[Methuselah96]

From @Pauan on Fri, 16 Jan 2015 01:03:48 GMT

@graue I see, I was afraid it might be something like that. Thanks for the explanation.

@graue @swannodette I mentioned Mori's concat being O(1) because in the benchmarks I showed, you can clearly see that it has O(1) behavior. I have checked, and my benchmark code appears to be correct.

Since Mori vectors don't seem to have a specialized concat function, I'm using mori.concat, which converts its arguments to sequences. So, when you say that Mori doesn't have O(1) concat, do you mean that the concat itself is O(1), but it costs time if you want to convert back to a vector? Or do you mean that the concat itself is O(log32(n))?

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70192515

[Methuselah96]

From @Tvaroh on Wed, 06 Aug 2014 13:22:59 GMT

BTW, that official paper on RRB trees is lacking many details. I would recommend to look at this thesis.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51333012

[Methuselah96]

From @leebyron on Sat, 01 Nov 2014 05:53:07 GMT

My understanding was the constant perf hit only came if the RRB nodes are in the path, which means the result of slice/concat. 

I'm interested to hear more though. 

— Sent from Mailbox

On Fri, Oct 31, 2014 at 10:51 PM, Scott Feeney notifications@github.com wrote:

@hypirion (author of the thesis above): didn't you say you found RRB-trees slower in practice (like, by a constant factor) than the Clojure-style vector for some operations?

I bring this up because if so, that may be an argument for presenting RRB-trees as an alternative implementation rather than replacing the current one.

Reply to this email directly or view it on GitHub: https://github.com/facebook/immutable-js/issues/38#issuecomment-61359140

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-61359158

[Methuselah96]

From @swannodette on Fri, 16 Jan 2015 15:33:55 GMT

@Pauan the speedups do not come primarily from fixed arity invokes. Two things changed in ClojureScript, we no longer leak arguments and the standard library is compiled itself with static invokes enabled thus removing any internal overheads. Even without JS static invokes you will see Mori win out in many cases.

@leebyron while I appreciate the conservatism with wrt. micro benchmarking, let's not be disingenuous, Clojure and thus ClojureScript's many optimizations are the direct result of 7 years of observing common usage patterns in production applications.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70270226

[Methuselah96]

From @Pauan on Fri, 16 Jan 2015 13:53:32 GMT

@leebyron Indeed, real-world examples always trump synthetic benchmarks. But it's also much harder to find and test real-world examples.

Adding in more benchmarks for different scenarios (like interleaving read/write) is a good idea, and I might add them in at some point.

I agree, reads tend to be more frequent than writes, so optimizing for read is a good idea. But when you're trading minor read performance for multiple orders of magnitude of write performance, I think that's a good tradeoff. It will of course depend upon the particular programmer's use-cases, though.

My library also supports Tuples, for the situations where read performance is needed much more so than write performance. I think this is a good idea: a general-purpose List that's good at everything (reading, inserting, concatenating, etc.), and a more specialized data structure that can be faster for a particular operation (like reading).

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70255971

[Methuselah96]

From @graue on Thu, 15 Jan 2015 19:53:49 GMT

@Pauan: Slice in Mori is O(1) time because it creates a view over the original vector. In essence, it's like

function slice(vec, start, length) {
  if (isAlreadyASlice(vec)) {
    start += vec.offset;
    vec = vec.originalVector;
  }
  return {
    originalVector: vec,
    offset: start,
    length: length
  };
}

Totally made-up pseudocode, but conceptually, that's what is going on. So, as long as the slice lives, nothing in the original vector can be garbage collected.

I copied this behavior in my immutable-vector implementation, but warned about it in the docs, since it's a pretty big caveat, and can lead to memory leaks if not understood.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70150056

[Methuselah96]

From @Pauan on Wed, 14 Jan 2015 18:53:11 GMT

@swannodette Those are all excellent points. Once the new version of Mori comes out, I would love to re-run the benchmarks. I was actually quite disappointed when I first benchmarked Mori: I was expecting it to be faster, so an improvement there would make me happy.

Do you have any recommendations for how I can run the benchmarks better? I think my usage is pretty straight-forward: https://github.com/Pauan/Immutable/blob/javascript/src/Benchmark/List.js

I simply load up Mori as a Node.js module and use it in the typical way that I would expect a developer to do. I did the same with the other libraries.

The random access issue is a bit complicated. You are right that it is consistently slower than Immutable-js, but not by that much. In exchange for that, it has vastly better performance for lots of other things, especially random inserts (which is a big part of the reason I wrote the library in the first place, I needed decent-speed random inserts). This could change if Immutable-js gets the aforementioned RRB-tree optimizations.

It's also important to note that the performance of "100 values" is misleading: as an optimization, I use cons cells for O(1) push at the end, but that means that lookup degrades to O(n) for lists with less than 125 values in them. Once it hits the 125 limit, performance jumps up significantly. You can see that with "1000 values".

In the past I have benchmarked transients (in both Immutable-js and Mori), and I found that in some cases they were slower, for bulk inserts they were generally faster, but in general they don't make a huge difference. It wasn't worth the extra time it took to benchmark them, so I took them out. But I can add them back in if you would like to see the results.

P.S. O(1) concat and slice in Mori is insane. I'm curious how that's implemented, and whether it involves some other tradeoffs or not.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-69969419

[Methuselah96]

From @swannodette on Wed, 06 Aug 2014 13:21:04 GMT

FWIW efficient splice (and other ops) is supported if you implement RRB-Trees - a variant of bitmapped vector tries (i.e. Vectors) http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51332799

[Methuselah96]

From @leebyron on Sun, 02 Nov 2014 04:01:36 GMT

Thanks @hyPiRion this is really helpful.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-61393495

[Methuselah96]

From @leebyron on Tue, 05 Aug 2014 20:26:52 GMT

If you're calling it repeatedly, you might try replacing .splice(...) with .splice(...).toVector()

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-51254607

[Methuselah96]

From @swannodette on Wed, 14 Jan 2015 17:33:59 GMT

@Pauan in the case of Mori you're not measuring what you think you're measuring, there's a pending update to Mori which will permit performance comparisons of the actual data structures from plain JavaScript. Also your AVL tree implementation seems to come in consistently behind for random access/update in these benchmarks which is one of the value propositions for Bitmapped Array Tries. Also you're not benchmarking against transients in the Immutable.js case nor the Mori case.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-69955902

[Methuselah96]

From @dahjelle on Thu, 13 Nov 2014 17:06:52 GMT

@leebyron You hinted about something using splice and withMutations together—is there some speedup to be gained in general, or is that only with repeated calls to splice? While I realize you won't get better than O(n), it'd be nice to get a bit closer to a native array's performance.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-62927507

[Methuselah96]

From @graue on Thu, 15 Jan 2015 19:55:44 GMT

@swannodette: Correct me if I'm remembering wrong or the above behavior has since changed.

As for concat, I don't remember concat in Mori being O(1), and I'm confused by the notion that it is.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-70150360

[Methuselah96]

From @Pauan on Wed, 14 Jan 2015 16:03:15 GMT

Another alternative implementation is to use AVL trees (any binary tree will do, really, but AVL trees are fast and easy to implement) where each AVL node contains a JavaScript array. Once the JavaScript array reaches a certain size, it splits it into two AVL nodes. I found through benchmarking that 125 is a good limit for the JavaScript arrays.

I wrote a library that implements immutable lists in the above manner, you can find the benchmarks here:

https://github.com/Pauan/Immutable/blob/javascript/benchmarks/List/2015-01-13

As you can see, they are quite a bit faster than Immutable-js, for most operations. I'm willing to go into more detail on their implementation, if you want.

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/38#issuecomment-69939151