4 ms·

> So when people say "C-like performance" in this sort of context, what they really mean is "the performance if we choose to make a foreign call to a function w

> So when people say "C-like performance" in this sort of context, what they really mean is "the performance if we choose to make a foreign call to a function written in C instead of writing the same function in Haskell". That's not really why we use C(or C++ or Rust) for high performance code. The author got really close by calling out branch prediction overhead and reading 1mb from memory. However he completely missed the overhead of a cache miss. We use C because you can be explicit about your memory layout so that when you read memory in a predictable pattern(linearly forward/backward) the prefetcher can keep ahead of you and avoid cache misses. You're looking at 400-1200 cycles per cache miss which can happen on each reference access if you're not careful. I don't know how rich Haskell's support for Value vs Reference types and memory layout are but this is something you can't just wave a compiler at since it's highly dependent on your dataset and use cases.

Karrot_Kream 8y ago
Can this be done in Rust?
- vvanders 8y ago
  Yup, in fact everything in Rust is by default a value type, you have to use Box<T> to get a heap allocated value so otherwise it's on the stack and usually pretty memory local. You've also got things like mem::transmute to let you do the really fun stuff like direct mmap of data structures and other fun(but potentially very platform specific) operations. In fact it's not turned on by default(but I understand in the works) but the way Rust is designed(single mutable pointer, no aliasing) means that you could turn on restrict[1] by default, which can be a huge performance win in certain circumstances. [1] http://en.cppreference.com/w/c/language/restrict http://en.cppreference.com/w/c/language/restrict
  - steveklabnik 8y ago
    We turned it back on quite recently! I haven’t seen any numbers yet though.
    - vvanders 8y ago
      Dude! That's awesome, I was under the impression it was a ways away. Is this on nightly or going to be making it into one of the upcoming stable releases?
      - steveklabnik 8y ago
        Both, it landed a few hours ago, and so will be in 1.28 stable. Here's the PR: https://github.com/rust-lang/rust/pull/50744 https://github.com/rust-lang/rust/pull/50744
        vvanders 8y ago
        Damn, you guys are knocking it out of the park with Rust. We used to have to do all sorts of convolutions to turn on restrict in the few places it made sense(particle systems, etc). Pretty amazing to have it turned on by default across the whole language.
        steveklabnik 8y ago
        Thanks! It’s a great example of how “less restrictions” doesn’t always mean “fastest code”. In some ways, this specific optimization is the core of what Rust is about.
tathougies 8y ago
> I don't know how rich Haskell's support for Value vs Reference types and memory layout are but this is something you can't just wave a compiler at since it's highly dependent on your dataset and use cases. Haskell has both value types (unboxed types) and reference types. By default, lazy reference types are the default. If you add a '!' before the types of fields in a record, you get direct pointers. If you add a '! {-# UNPACK -#}' or enable the '-funbox-strict-fields' option, you get directly embedded value types. That being said, C has more first-class support for low-level manipulation, but if you wanted to, you could just add this kind of manipulation onto Haskell as a library. In my last company, we developed a library that used higher-kinded polymorphism and phantom types to basically make low-level memory manipulation a 'first class' value that could be reasoned about using Haskell's type system. However, this required that you annotate your types appropriately. Nevertheless, code would end up compiling into highly efficient direct memory and register manipulation, while still having all of Haskell's typical type safety.
- vvanders 8y ago
  Interesting, thanks for the detailed breakdown. How's support for directly mapping chunks of memory to packed structures? We used to do a lot of in-place loading in games(yay for spinning, physical disks) so it being able to do blind casts was almost as important as value types themselves.
  - tathougies 8y ago
    Haskell allows unsafe pointer arithmetic and manipulation (of course, the functions are all named 'unsafe'!). But, you can write safe interfaces on top of it. I have an example of an external sort using the standard fibonacci merge algorithm, which uses raw pointers and memory mapped IO under the hood, but which exposes a safe API. I've done some basic benchmarking, and it's about as fast as Postgres's sort on my machine, for simple binary doubles and ints. Here it is: https://github.com/tathougies/extsort/blob/master/Data/External/Sort.hs https://github.com/tathougies/extsort/blob/master/Data/Exter... . I think it's a good example of 'low-level' Haskell.
  - nickpsecurity 8y ago
dragonwriter 8y ago
> this is something you can't just wave a compiler at since it's highly dependent on your dataset and use cases. While this particular issue might not be addressed in current conpilers, isn't the class of “desired compiler optimizations which are highly dependent on datasets and use cases rather than being analytically determinable from bare code” exactly what profile guided optimizations are about?
- vvanders 8y ago
  PGO is great and definitely helps but only in the micro level and not at the macro, algorithmic level. To say it another way, once you've chosen your data structures it's already too late to take advantage of memory layout because either the language forces a specific layout(C/C++/Rust) or you have pointers which can take up a bunch of extra space. Take a toy example of adding all the x values of a vec3 together, usually you'd represent that as: struct Vec3 { float x, y, z; } However that gives you a memory layout of: "xyzxyzxyzxyz...." If instead you flip that from AoS(array of structures) to SoA(structures of array) you get: "xxxxyyyyzzzz..." and now all your x values are adjacent and nicely cache local. If instead we were talking about other objects instead of x/y/z now each one of those becomes a potential cache miss in the first example but in the second they'd already be fetched by the prefetcher and hot in the cache. Those type of optimizations are things that compilers aren't good at because they have impact on how the data is actually defined, abstractions being leaky and all that.

Karrot_Kream 8y ago

Can this be done in Rust?

vvanders 8y ago
Yup, in fact everything in Rust is by default a value type, you have to use Box<T> to get a heap allocated value so otherwise it's on the stack and usually pretty memory local. You've also got things like mem::transmute to let you do the really fun stuff like direct mmap of data structures and other fun(but potentially very platform specific) operations. In fact it's not turned on by default(but I understand in the works) but the way Rust is designed(single mutable pointer, no aliasing) means that you could turn on restrict[1] by default, which can be a huge performance win in certain circumstances. [1] http://en.cppreference.com/w/c/language/restrict http://en.cppreference.com/w/c/language/restrict
- steveklabnik 8y ago
  We turned it back on quite recently! I haven’t seen any numbers yet though.
  - vvanders 8y ago
    Dude! That's awesome, I was under the impression it was a ways away. Is this on nightly or going to be making it into one of the upcoming stable releases?
    - steveklabnik 8y ago
      Both, it landed a few hours ago, and so will be in 1.28 stable. Here's the PR: https://github.com/rust-lang/rust/pull/50744 https://github.com/rust-lang/rust/pull/50744
      - vvanders 8y ago
        Damn, you guys are knocking it out of the park with Rust. We used to have to do all sorts of convolutions to turn on restrict in the few places it made sense(particle systems, etc). Pretty amazing to have it turned on by default across the whole language.
        steveklabnik 8y ago
        Thanks! It’s a great example of how “less restrictions” doesn’t always mean “fastest code”. In some ways, this specific optimization is the core of what Rust is about.

tathougies 8y ago

> I don't know how rich Haskell's support for Value vs Reference types and memory layout are but this is something you can't just wave a compiler at since it's highly dependent on your dataset and use cases. Haskell has both value types (unboxed types) and reference types. By default, lazy reference types are the default. If you add a '!' before the types of fields in a record, you get direct pointers. If you add a '! {-# UNPACK -#}' or enable the '-funbox-strict-fields' option, you get directly embedded value types. That being said, C has more first-class support for low-level manipulation, but if you wanted to, you could just add this kind of manipulation onto Haskell as a library. In my last company, we developed a library that used higher-kinded polymorphism and phantom types to basically make low-level memory manipulation a 'first class' value that could be reasoned about using Haskell's type system. However, this required that you annotate your types appropriately. Nevertheless, code would end up compiling into highly efficient direct memory and register manipulation, while still having all of Haskell's typical type safety.

vvanders 8y ago
Interesting, thanks for the detailed breakdown. How's support for directly mapping chunks of memory to packed structures? We used to do a lot of in-place loading in games(yay for spinning, physical disks) so it being able to do blind casts was almost as important as value types themselves.
- tathougies 8y ago
  Haskell allows unsafe pointer arithmetic and manipulation (of course, the functions are all named 'unsafe'!). But, you can write safe interfaces on top of it. I have an example of an external sort using the standard fibonacci merge algorithm, which uses raw pointers and memory mapped IO under the hood, but which exposes a safe API. I've done some basic benchmarking, and it's about as fast as Postgres's sort on my machine, for simple binary doubles and ints. Here it is: https://github.com/tathougies/extsort/blob/master/Data/External/Sort.hs https://github.com/tathougies/extsort/blob/master/Data/Exter... . I think it's a good example of 'low-level' Haskell.
- nickpsecurity 8y ago

dragonwriter 8y ago

> this is something you can't just wave a compiler at since it's highly dependent on your dataset and use cases. While this particular issue might not be addressed in current conpilers, isn't the class of “desired compiler optimizations which are highly dependent on datasets and use cases rather than being analytically determinable from bare code” exactly what profile guided optimizations are about?

vvanders 8y ago
PGO is great and definitely helps but only in the micro level and not at the macro, algorithmic level. To say it another way, once you've chosen your data structures it's already too late to take advantage of memory layout because either the language forces a specific layout(C/C++/Rust) or you have pointers which can take up a bunch of extra space. Take a toy example of adding all the x values of a vec3 together, usually you'd represent that as: struct Vec3 { float x, y, z; } However that gives you a memory layout of: "xyzxyzxyzxyz...." If instead you flip that from AoS(array of structures) to SoA(structures of array) you get: "xxxxyyyyzzzz..." and now all your x values are adjacent and nicely cache local. If instead we were talking about other objects instead of x/y/z now each one of those becomes a potential cache miss in the first example but in the second they'd already be fetched by the prefetcher and hot in the cache. Those type of optimizations are things that compilers aren't good at because they have impact on how the data is actually defined, abstractions being leaky and all that.