4 ms·
On Competing with C Using Haskell (2017)
- tathougies 9y agoIn his explicit recursion example, the author questions why the compiler doesn't convert it into a tail call. The issue here is that the speed he gained in the tall call version had nothing to do with the tail call. It has to do with the fact that the accumulating parameter is strict. The explicitly recursive version is lazy, which means there is a thunk structure of (1 + 1 + ... ) being built up in memory, which is then evaluated. This overhead of building up this thunk, and then evaluating it (awful cache characteristics) is what he's seeing. By adding a bit of strictness, the author could likely get the optimizer to convert it into a strict tail call.
- gowld 9y agohttps://wiki.haskell.org/Foldr_Foldl_Foldl%27 https://wiki.haskell.org/Foldr_Foldl_Foldl%27 explains this in detail.
- vvanders 9y ago> 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 9y agoCan this be done in Rust?
- vvanders 9y agoYup, 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 9y agoWe turned it back on quite recently! I haven’t seen any numbers yet though.
- vvanders 9y agoDude! 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 9y agoBoth, 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 9y agoDamn, 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.
- glangdale 9y agoI am not convinced that advancing over two different string buffers and comparing their contents - even with a variable amount of advance due to character encoding - would have a branch miss in it if programmed by a competent programmer in any language. I am also not convinced that this problem can't be completely clobbered by SIMD, regardless of platform (x86 vs Neon) and language (Haskell, C, whatever). A comparison of languages in this case for performance (outside the kiddy division) would either (a) center around which language could get the hell out of the way and let the programmer use intrinsics or (b) which language could actually allow the programmer to express SIMD concepts in a nice language-friendly way. I have occasionally seen some pretty cool stuff from FP folks in the latter direction, which, if brought to production quality, would allow FP people to absolutely slaughter naive C code.
- tathougies 9y agoThere is a summer of code project this year to make GHC output SIMD code from standard Haskell code. The llvm backend does this now, but it comes at the cost of being less efficient on normal Haskell code, and also unable to access all the rich type information that GHC theoretically could. Nevertheless, GHC has all SIMD intrinsics available for use, and they're all type checked, as you'd expect: https://hackage.haskell.org/package/ghc-prim-0.5.2.0/docs/GHC-Prim.html#g:29 https://hackage.haskell.org/package/ghc-prim-0.5.2.0/docs/GH...
- kccqzy 9y ago> I have occasionally seen some pretty cool stuff from FP folks in the latter direction, which, if brought to production quality, would allow FP people to absolutely slaughter naive C code. I'd love to hear more stories about this! Any links? So far my own approach is to use Haskell as basically a glorified DSL for LLVM IR and bypass Haskell codegen altogether. From there either JIT it or AOT it into native code.
- toolslive 9y agoIn OCaml, there's the option to directly call the native function without any setup cost or overhead, in fact, some of the standard library's function are offered this way. For example: external sqrt : float -> float = "caml_sqrt_float" "sqrt" [@@unboxed] [@@noalloc]
- anonymouz 9y agoThe overhead that is being talked about in the blog post is mostly the impossibility to inline/optimize the C code of the callee, setting up the stack frame, etc. How would OCaml avoid that?
- toolslive 9y agoIt does a reasonable job: external my_sqrt : float -> float = "caml_sqrt_float" "sqrt" [@@unboxed] [@@noalloc] let () = let x= my_sqrt 1.0 in Printf.printf "x = %f" x becomes something like: ... camlInline__entry: .cfi_startproc subq $8, %rsp .cfi_adjust_cfa_offset 8 .L102: movsd .L103(%rip), %xmm0 sqrtsd %xmm0, %xmm0 movsd %xmm0, (%rsp) movq camlInline__6@GOTPCREL(%rip), %rbx movq camlPervasives@GOTPCREL(%rip), %rax movq 208(%rax), %rax call camlPrintf__fprintf_1291@PLT ....
- ncmncm 9y agoCompeting with C is a pretty low bar, nowadays; although I appreciate the uniquely careful definition used here. When you are serious about performance, nowadays, cache misses and branch prediction are decreasingly relevant. You need to talk about drawing on computational resources practically inaccessible from C, including AVXn vector units, and shaders. C's weakness for expressing abstractions is a fundamental and unbridgeable handicap for such computation. C++ might be up to the job, and Haskell should be. It is not clear whether Rust is. For this kind of hardware exploitation, direct compiler support will always lag far behind. You need for the language to be expressive enough to support writing libraries that wrap access to the platform's hardware features in a way that the library can be ported to other hardware without changing client code, and present its capabilities in a way natural for the language. Compiler optimizers are good at merging client code with library implementation when both are in the same language, and can identify efficiencies not available to library or clients taken in isolation. It is not typically less work to write such a library than to tailor a compiler, but the work has better longevity. Other people port the library for their hardware, and all the compilers and programs are brought along. In the case of rustc and ghc, where there is momentarily only one compiler, it may be harder to see this.