Fork me on GitHub
#cljs-dev
<
2018-08-29
>
john01:08:04

how about this idea for an optimized reverse. Just produce a new vector of shared structure where all the bit-navigating and lookups and conjs are just calculated in reverse. So it's just another mirrored view over the same structure. It's immutable anyway. I guess there are a number of things you could make into "virtual data structures" in that sense. Especially useful when you just want to temporarily change the view of some data, say, to map things over a different ordering or sort characteristic, but then switch back to the original view without having to re-order and reallocate everything.

john01:08:27

hmm, well what would happen if you cut a vector in half, reversed the second half, then conjed the second one back on to the first? I guess doing a seq on the whole thing would result in a seq going backwards, starting at the halfway point, from the tail. And the more often you slice and dice up the same vector via functional views, the less it has Vector's performance characteristics

john02:08:43

hmm, you could always do with-reversed, so the reversal only applies to the body and returns the thing back in its original sort order, so as not to produce nested structures with internal reversals... but actually, just doing a little testing in the repl, vectors actually read backwards from the tail about 25% faster for me. compared to forward.

john02:08:47

reverse in particular is just really costly (correction, really bad for lists):

john03:08:29

So I guess tl;dr, maybe there should be something like a MirrorPersistentVector for a corresponding PersistentVector, if it get's reversed. And perhaps VectorNodes and friends would need their Mirror counterparts too.

john03:08:48

Hmm, here's the clojure/jvm numbers:

john03:08:16

Maybe it's doing the reversal lazily

john03:08:39

Pro tip: you can speed some clojure vector algorithms up by first reversing them 😄

john03:08:01

Those cljs non-reversed numbers are super fast though. I wonder if the nths are getting called

john03:08:11

Yeah, linear access is just super fast in clojurescript. In both directions.

john04:08:57

nevermind, that's not a vector 🙂

john04:08:24

ah, hmm. way faster when boxed in vecs:

john04:08:29

So when wrapping them in vecs, that's actually not bad performance. Only about half as slow as going forward through it, for larger ranges

john04:08:40

and for vectors in clojure, it looks like linear access in either direction is roughly 4 times faster than linear access from left to right, in cljs lists. Whereas they're about 10 times faster than cljs's vectors for linear access in either direction

mfikes10:08:36

@john I haven’t followed all of the above, but just wanted to point out that cljs.core/reverse already has a (constant time?) optimization for collections that are reversible?.

mfikes10:08:17

In the case of passing a vector to reverse, you get the goodness that rseq produces.

john14:08:40

Aye, seems constant time. So maybe the benefits of functionally "mirrored" structures isn't really a worthwhile idea.