7 ms·

There should be a minor law in the spirit of Greenspun’s tenth rule: Every sufficiently performance-sensitive system eventually grows some version of a slab all

There should be a minor law in the spirit of Greenspun’s tenth rule: Every sufficiently performance-sensitive system eventually grows some version of a slab allocator[1]. There’s really no substitute for packing fixed-sized objects together in N big array chunks. If you can operate in a particular context (or entirely) with N=1, you can substitute handles for pointers. For any reasonable # of objects, those handles can be smaller than a pointer and provide even better compaction and thus cache effectiveness. [1] https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-S14/hand-outs/bonwick_slab.pdf https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-...

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 ago
  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.)
  - svrb 6y ago
    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.
  - zero_iq 6y ago
    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.
    - andi999 6y ago
      There is no Jai.
      - jacobush 6y ago
        There Is Only IBM And AT&T And Exxon?
        andi999 6y ago
        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.
        zero_iq 6y ago
        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.)
- throwaway894345 6y ago
  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!
  - epistasis 6y ago
    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.
    - carlmr 6y ago
      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.

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 ago
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.)
- svrb 6y ago
  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.
- zero_iq 6y ago
  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.
  - andi999 6y ago
    There is no Jai.
    - jacobush 6y ago
      There Is Only IBM And AT&T And Exxon?
      - andi999 6y ago
        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.
        zero_iq 6y ago
        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.)
throwaway894345 6y ago
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!
- epistasis 6y ago
  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.
  - carlmr 6y ago
    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.