Hacker News Reader

Comment by epistasis | Hacker News Reader

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.

View on HN

In 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.)

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

HoTT 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

That'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.

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

I remember when that first came out. I have not checked in on it in a while. Do you have any links to communities/reddits/etc working with that? (/r/haskell was very excited for a while, but then the energy went somewhere else, and I don't know where.)

One of the things I only alluded to in my third paragraph, but very much had this sort of thing in mind, is that it's going to take a lot of type work and a lot of thinking in properties (like Traversable, Functor, etc. in Haskell) to make this work out well, because a lot of these rewrites to underlying representation will have manifestations at the property level (this array is now Traversable but no longer RandomAccessible, etc.).

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

Here is the demo video of the stuff zero_iq is talking about: https://www.youtube.com/watch?v=ZHqFrNyLlpA

Basically right on point with what the GP is saying.

That video briefly mentions the CppCon 2014 talk by Mike Afton, "Data-oriented Design and C++". The talk was great, pretty much lined up with how I think of modern systems (treat RAM like disk: seeks take a long time, but streams will likely be able to maximize CPU usage)

But the questions at the end, and the resistance to these basic ideas, roughly "what about platform portability, programmer productivity, etc."; these questions were a bit shocking to me. Is this not a C++ conference? This was six years ago, so perhaps the machine constraints were not as well known back then, but it really shows how strongly the community culture will influence a language and its capabilities.

I thought he pulled that back out of the language, though with the intent of re implementing it with as a library with the metaprogramming facilities of the language for anyone who wanted it?

I haven't seen the update, but to me that seems a bit silly. This is a pretty fundamental type manipulation, and ideally the compiler would have some understanding of it...

There is no Jai.

There Is Only IBM And AT&T And Exxon?

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

It'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.)

Well, 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.

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

Yes, 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.

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

I am sure I am missing something, but this thread of comments really got me thinking. I started thinking this was a use case for existential types, but I’m not sure it’s immediately applicable. Then went down a research paper rabbit hole and google binge looking at various ideas. Now I’m sitting here thinking (and I doubt this scotch is making it clearer) that this is sort of like Haskell’s type classes being seen as the ‘Data Type’ level and regular type constructors being seen as the ‘Data Structure’ level. Obviously a language would need to incorporate the class syntax as a less separate construct than it is in Haskell, but I can’t shake the feeling this almost captures the thrust of the concept.

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

Isn't this just an interface in an OO language?

Typically 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!

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

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

Reply on news.ycombinator.com