Has anyone looked at vlists for clojure?
https://www.gnu.org/software/guile/manual/html_node/VLists.html
https://github.com/skangas/guile/blob/master/module/ice-9/vlist.scm
https://hg.sr.ht/~bjoli/guile-fector
They're another Bagwell structure for persistent array like things. The Guile folks have what looks like a consistent port of persistent vectors, and they (u/bjoli) seem to observe about a 2x estimated random access difference between the pvector (fector) and the vlist implementation. I found that curious, since it could indicate another persistent data structure with some tradeoffs that could be useful. Curious if there are any java/clojure implementations. There's a Java implementation, no idea if it's quality or not though.
Posted Aug 24, 2020, 11:45 AM UTC · edited
115
edit: looks like this implementation is actually mutating for some reason, never mind! Maybe there's something I missed about the notion of persistence here (seems like another implementation I found is also mutable). It looks like you only get derived copies when you use .rest, otherwise adding to the root mutates it.
u/bjoli fyi, I'm getting similar results with the unscientific benchmarking of the Java implemented VList (of 10^6 elements); faster random access for vlist (~2-5x), random update (~5x faster), much slower count (~10x). Interesting.edit: count is only slower via clojure.core/count, if you use direct method invocation via .size they are surprisingly comparable. Looks like size is cached in the java implementation.Read the guile manual on VLists. It covers some caveats of using it safely. The guile implementation uses internal mutation and thus is not thread safe, but there is nothing really stopping that except for efficiency concerns I guile.
The downside with VLists is that you do not get any updating.
The reasons for my numbers regarding going from front to back is because I didn't get any option to go into the underlying data structure (whereas the fector-fold used in my unscientific benchmarks does just that: it iterates over the vector parts that together build the fector.
Compared to factors, VLists are very simple. A good implementation can be made in about 50loc.
Looks like cljs bootstraps pvector (and all protocol implementations) in about 384 loc (adding in subvec and transient bulks up to 827). I did similarly (off a somewhat verbose port of the java implementation) in clclojure in about the same LOC (although I didn't get all the protocol implementations due to the bootstrapping nature). Ice 9's vlist looks to about about the same LOC-wise (not including the vhash stuff at the bottom).
I guess in practice, I'd be more than willing to spend more time implementing a fundamental data structure that would be used all over the place. That's probably true in practice (I am incredibly less likely to have to bootstrap a persistent array / vector from scratch than I am to use one bundled with the language runtime; probably the only reason I even did that was for implementing clclojure's pvector, which wasn't too hard [mostly a pedagogical exercise of learning java, pvector theory and implementation, and common lisp at the same time]). 7x the written length isn't really a deal breaker to me; even if I were bootstrapping something from scratch.
I think the real prize would be a persistent data structure with better performance than the existing pvector (or optimized performance profiles for certain use cases and established tradeoffs). It's not clear that's the case at the moment.
What would the expected impact be of making VList thread safe like pvector then? If efficiency is a concern, this seems like a significant limitation (I can toss pvectors around threads without any care, and they still perform well, really decreasing the barrier for FP style multithreaded stuff when used with reference types).
Ah, this is equivalent to iterating over a pvector by
nthinstead of using the iterator (which just traverses the leaf arrays in order) or internal reduce. Makes sense.Do you mean that, given VList
lof elements[1 2 3 4 5], I cannot compute a new VList with element at index 2 changed to -99? Where a pvector of the same entries would support(assoc v 2 -99)->[1 2 -99 4 5], while preserving the original vector? That seems like a substantial limitation compared to the generality of the pvector (update in ~O(1) via OLog32(n) time).As I have mentioned before: sure, pvectors are cool (RRB trees are even cooler!), but I have found I rarely need them. When I need fast random access, I usually need fast random access, not fast-ish random access. When I need persistance, I rarely need indexed update.
If I were to start over, like rich did, I would probably make rrb-tree-based vectors the default, but scheme is already a language with idioms and libraries built around the linked list, and that's fine. Almost everyone agree that pvectors (particularly RRB-tree based ones :)) are a are superior in many ways. In practice, however, linked lists are sufficient for most cases. They are well understood, fast enough if you build your data once and then iterate over it and have access to either lazy transformations or transducers (all of which are standardised as SRFIs in scheme). Clojure has had pvectors since forever, and because of that idiomatic clojure promotes means code that makes use of pvectors. Scheme/CL has other idioms. That is why I believe you were met with mostly shrugs in your other thread. Most people agree that pvectors are cool and sometimes useful, but they are not a requirement. Scheme has standardised mappings based on HAMTs in srfi 146,
Regarding VLists:
The reason VLists ain guile are not thread safe are because guile internals. They could be made thread safe without much fuzz, at the expense of making regular lists slower (IIRC), which was not a priority.
That they lack update procedures means only that they are used as regular lists but with o(1)-ish random access. The "substantial limitation" is in the eye of the beholder. The implementation is simpler, and you have a lower overhead (the meaty bits of the guile implementation are before line 200-something, and is less that 100loc).
I am far from shocked that the CL/Scheme communities already have a prevalence toward list-based idioms (even when just as general and more efficient alternatives exist in their ecosystems, historical momentum matters); that's kind of baked into the cake at this point (not unlike Haskell's long term grappling with Prelude and list representations permeating things).
I guess I could care less about simplicity of implementation over the relative leverage and utility the data structure provides. The two concepts (simplicity of implementation and performance) seem orthogonal here - as does the notion of "coolness" of a data structure; maybe there's intrinsic value to the theoretical compsci folks, but practically it's meaningless unless simplicity automatically translates into dominant performance. Andrei Alexandrescu's talk here is a counter-intuitive exploration of simplicity and performance ).
I do not know who in our conversation said they are a requirement (except maybe implicitly Rich Hickey, who decided they were fundamental to his language). Experience has shown they are a great general purpose choice though, one that's not immediately veered from in favor of say lists (aside from lazy ones of course). If I were limited (or strongly pushed) to use lists or list-centric APIs by the ecosystem, and I didn't have a better structure idiomatically present, then I would have to suffice with the tools at hand (I have actually, in other languages). That doesn't mean I wouldn't be wanting for a pvector though.
I remain surprised by the practical performance of the persistent vector (and persistent map). When I need random access, the idiomatic structures are usually already up to the task. The fact that I don't have to typically drop down to other structures, and retain good performance on the first idiomatic cut, is a boon that keeps paying off. I have less junk to juggle to get viable prototypes working, and prototypes end up being performant enough most of the time.
Substantially faster performance (relative to the list alternative) along with persistence is, in my experience, more potent than you've expressed. Having a structure that's "good" for a lot of things, and demonstrably better in computational complexity than other general purpose structures, kind of leads me to naturally use the thing that's generally better (e.g. pvector is ubiquitous).
Perhaps rrb-tree backed vectors have emerged in this category, although there are tradeoffs yet (vec's O(1) leaky subvec vs. non-leaky, "true" O(logN), O(N) cat/split vs. rrb's O(logN)). For some reason, linear traversal (at least via reduce) is ~4x slower on a microbench and I can't fathom why; maybe it's an implementation detail in clojure.core.rrb-vector (I will remember to ask). If the rrb-vector dominates in general (as it appears to), I could see it supplying the persistent vector implementation when clj moves on to 2.0 at some point (since it would break the existing subvec behavior).
Where necessary, sure, you can and should move to primitive, mutable structures and the like; except you lose out on the benefits of the persistent stuff. I'm typically seeing ~4x+ performance increase just going mutable, and obviously substantially more if you are say doing numerics and shift to primitives and unchecked stuff, over linearly stored containers. Those cases are relatively rare due to the performance the default structures give (even being persistent), which makes the jump toward further optimized (and limited) paths less desirable.
In my eye, I behold that not having the ability to efficiently compute new persistent vector values from old via "update" would restrict a lot of algorithmic choices. So the trade off would be regressing to maybe O(n) update for what? At least in my current situation, that's a decision I really don't have to consider, since I already have a thing that can support the operations I need without the tradeoffs.