5 ms·
Everything I read these days seems to trend towards columnar stores... I write a mixture of R, Python, C and C++, in that order of prevalence, and mostly for d
by epistasis 6y ago
Everything I read these days seems to trend towards columnar stores...
I write a mixture of R, Python, C and C++, in that order of prevalence, and mostly for data intensive tasks. After nearly two decades of unlearning loops and implementing instead with FP idioms, vectorization, and matrix multiplies to take advantage of R's strengths, I often have trouble recreating R's performance when I first reimplement in C or C++.
I think it would be beneficial to start with functional programming in more CS programs, they are a much better fit for modern CPU architectures in many ways.
- jerf 6y agoIn my Perfect Programming Language That Doesn't Have To Deal With The Problems Of Actually Existing, serialization of data structures into memory is explicitly defined in the language, just as one would define a JSON or Protobuf serialization. One could define a "Point3{x,y,z}", and hypothetically define one array of them in the conventional manner, define another array as a columnar serialization, and potentially even define a compressed data structure right there in memory if that was advantageous. It opens a wide array of exciting problems and possibilities, if you start thinking of that as something a language should let you twiddle with rather than hard coding it. It seems like a lot of high performance stuff is moving in a direction where this would be advantageous. (For example, if you compress an array, you lose random access. The language would have to carefully build up capabilities from scratch so it can have a concept of "arrays" that can't be randomly accessed, can only be written in some very particular manner that may even require a "flush" concept, etc. My gut says it ought to be possible, since, after all, we can do it manually, but it would be a very careful operation to disentangle casual assumptions about what data structures can do based on the definition of what data they contain vs. how they are represented in memory, and what capabilities you get from that.)
- svrb 6y agoSign me up! I'm constantly defining `XYZ` and `PackedXYZ` for memory-bound problems and I have often though it would be nice to be able to do this (in a more generic way than mere bitfields). It never occurred to me that it could be extended to column stores though.
- zero_iq 6y agoJonathan Blow's new language, Jai, has some control over layout allowing easy switching between array of structs and struct of arrays without having to change the accessing code.
- andi999 6y agoThere is no Jai.
- jacobush 6y agoThere Is Only IBM And AT&T And Exxon?
- andi999 6y agoCould you explain? What I meant, I believe Jai is vaporware and gets too much attention. I mean Jai sound exciting until you find out that the download link is missing.
- zero_iq 6y agoIt's still under development, with no public release, but I think it's a bit unfair to call it vapourware, since he has produced plenty of material that demonstrates he has a working compiler and has clearly spent a great deal of time developing it, not just talking about it. Whether it gets too much attention is debatable. He has some good ideas, imo, worth exploring, although I don't agree with all of his opinions. He has a prominent enough profile that it will likely inspire others to incorporate features from Jai if they are seen to be desirable, even if Jai is not ultimately released. (Personally, I think it will eventually.)
- andi999 6y agoWell, what is your hunch when it will be released? My expectation is eithet never, or there will be a release and it will crumble quickly when people want to do things with it.
- thechao 6y agoI was privy to a fairly high-wattage conversation between Walid Taha, Jeremy Siek, Todd Veldhuizen, et al, where they discussed this issue at length. They were concerned that languages almost universally equate data types with data structures. Their opinion (drunkenly expressed) was that the program semantics should be based on both. The wrinkle was was happened if you wanted to expose transformations of the underlying structure against the type when trying to say something reasonable about escape hatches. If I had a PPLTDHTWTPOAE (?) it'd have this capability for sure.
- jerf 6y agoYes, as I was typing this up I began to realize that's where I was really going. Essentially turning an entire struct of, say, { int A; string B; Thingy C } into only a set of promises about being able to get an int, a string, a Thingy, etc., and promises around being able to set them (let's just do a struct for now, no methods or hiding), and then decoupling the type, being the set of promises being made, from the structure, being the concrete layout in memory and corresponding code capable of fulfilling those promises. It's all easy in the simple struct case, gets more interesting when you start trying to manipulate them by putting them into arrays or associative maps, etc. On the one hand, this is nearly revolutionary in some sense, but in another it's simply an incremental advance in a direction we're already going. "Object's are a poor man's closures, closures are a poor man's objects" being an old saying leaning in this direction, and it's hardly a new observation in Haskell that there's not a heck of a lot of practical difference between an associative array of X -> Y and a function (x -> y), at least when it comes to reading them.
- thechao 6y agoIn a language like Haskell, you'd parameterize every function by both the "data type" and the "data structure": monomorphization will happily emit ABI-compatible functions. I think a more interesting case is how you'd do this without a monomorphization explosion. It seems like being able to describe both subtyping and substructuring relationship (a la C's structure prefix ABI convention) would keep things mostly in check. I dunno... seems like you'd be combining all the hard bits of a nominative type system with all the hard bits of a polymorphic structural type subsystem.
- chriswarbo 6y agoThe idea of "univalence", being pursued in Homotopy Type Theory (AKA HoTT), is that isomorphic types (i.e. we can convert back and forth without information loss) are equal, and hence one can be used in place of the other. The dream scenario is to write all of our libraries and application code using types that are the most straightforward (e.g. counting in unary, mapping over linked-lists, looking up values from lists of key/value pairs, etc.), then cast these to more efficient types (e.g. machine words, arrays, tries, etc.) for the final program. It's still ongoing, and a naive approach would simply lead to a bunch of conversion functions being scattered around (making the program even slower), so a smart approach would be needed, e.g. where compilers can fuse away these conversions.
- voxl 6y agoHoTT changes what equal means. In order for univalence to work you must be comfortable with arbitrary code running to perform the necessary substitutions. Isomorphism isn't for free, you can do some fancy cast-conversions (where cast is an identity function) that has been explored in generic zero-cost reuse [1] but this is not HoTT and uses essentially an UIP equality (which is inconsistent with HoTT). Your usage of the word "cast" in the second paragraph is a misnomer, because no systems programmer is going to want to perform an expensive transporation in HoTT! [1] https://arxiv.org/abs/1803.08150 https://arxiv.org/abs/1803.08150
- rocqua 6y agoThat sounds like, for performance reasons, you want control over the actual types used. But you could eliminate those changes from affecting the semantic representation of your program. Or at the very least with an easy check that the optimization doesn't affect your semantics.
- chriswarbo 6y agoThat's what I was getting at w.r.t. naive vs smart implementations. The point of univalence is that, from a logical/functional perspective, `slowFoo(slowX)` is indistinguishable from `fastToSlow(fastFoo(slowToFast(slowX)))`. Applying this to composite expressions will produce lots of calls like `slowToFast(fastToSlow(x))` which can be optimised down to `x`. The problem, of course, is that we can't enforce this within the logic (since those expressions are indistinguishable), so we must rely on compiler optimisations (i.e. deforestation/fusion). That link looks interesting, but appears to be more about re-using the same computational-content/runtime-representation for multiple compile-time/proof-context semantics (akin to McBride's "ornaments"), which seems more like a dual problem to that of swapping out slow representations for fast ones.
- p1necone 6y agoIsn't this just an interface in an OO language?
- throwaway894345 6y agoTypically functional programming isn’t considered to be CPU friendly. Specifically typical functional programming allocates memory all over the heap, especially given the prevalence of things like linked lists and so on. This obviously makes for crumby cache performance and memory pressure. I’m not sure in what sense FP lends itself to columnar data structures, but those would obviously have still better cache and vectorization properties. I’d be curious to learn more!
- epistasis 6y agoThe difference is that if you're doing functional programming with vectors as the fundamental data type (rather than scalars in linked lists), then the implementation could be hyper optimized underneath the programmer to maximize computational throughout. Whereas with imperative for loops, the implementation is somewhat fixed because python, C, and C++ force you to choose row (array of struct), or columnar (struct of arrays). R prefers struct of arrays, and makes arrays of struct a very difficult and horribly unacceptable slow. But if you are willing to use higher order functions, R makes struct of arrays suuuuuper fast. Python/C/C++ make arrays of structs the "default", by programmer culture if not by language/runtime capabilities.
- carlmr 6y agoAlso I always find it's so easy to make everything data parallel if you program in a functional way. Sure it might not be the most efficient implementation possible, but due to the ease of parallelizing, you are more likely to just try it out.