News for hackers. Stuff that matters.
Re:Optimising Haskell for a tight inner loop by evmar on Wednesday January 08, 2014 @07:03PM (#7027807)
Ironically, the C++ code he's attempting to match itself uses a higher-level language[1] to generate a soup of tables and gotos[2]. But I think that observation supports the point he'd likely make: Haskell allows both the higher-level expressions of problems that produce optimization opportunities while preserving the option of dropping down to low-level trickiness if that's what you really need.

[1] https://github.com/martine/ninja/blob/master/src/lexer.in.cc...

[2] https://github.com/martine/ninja/blob/master/src/lexer.cc#L1...

Re:Optimising Haskell for a tight inner loop by carterschonwald on Wednesday January 08, 2014 @07:02PM (#7027801)
I may take this blog post and turn it into a bug report for the ghc optimizer. :-)

The moment you start trying to compete against hand written assembly, any high level lang gets a bit quirky. One nice thing about ghc Haskell is you can though! A lot of my own open source work is towards a vision of making that much easier than it is today :-)

Re:Optimising Haskell for a tight inner loop by carterschonwald on Wednesday January 08, 2014 @10:56PM (#7028647)
anyways, heres a link to the reddit thread: http://www.reddit.com/r/haskell/comments/1ukwu1/optimising_h...

its a very thoughtful, informative, thread. enjoy!

Re:Optimising Haskell for a tight inner loop by tenslisi on Wednesday January 08, 2014 @07:09PM (#7027833)
> The moment you start trying to compete against hand written assembly, any high level lang gets a bit quirky.

Yes, which is why I wonder why GHC went with it's own code generator instead of using LLVM? It seems like a lot of the outputted assembly would be coalesced with LLVM's optimizer passes. Is there work on this problem within the Haskell world?

Re:Optimising Haskell for a tight inner loop by carterschonwald on Wednesday January 08, 2014 @07:45PM (#7027981)
GHC has an llvm backend.

If you read the blog post, you'll see Neil mentions " tried the LLVM backend, but it generated significantly worse assembly code https://github.com/ndmitchell/blogs/blob/master/inner-loop/I...

@tenslsi : theres certainly room for improving llvm, the ghc native code gen, and pretty much any compiler generally (ghc is no different). I'm actively involved in GHC dev, and i've somewhat committed to spending some volunteer time this year improving the NCG and various backend optimization tooling.

anyways, the reddit discussion of the blog post is also pretty interesting

Re:Optimising Haskell for a tight inner loop by axman6 on Thursday January 09, 2014 @01:35AM (#7029126)
> ... tried the LLVM backend, but it generated significantly worse assembly code.

It's worth noting the LLVM version Neil tried was 2.8, from Dec 2010. LLVM has come a long way since then and I'd be surprised to see if produce such horrible code. I'm hoping Neil will do an updated post using LLVM 3.4 released last week.

Re:Optimising Haskell for a tight inner loop by sanxiyn on Thursday January 09, 2014 @06:10AM (#7029814)
My understanding is that the main problem is translating from Haskell to LLVM IR is a lossy process, not the difference between LLVM 2.8 and LLVM 3.4. This blog post demonstrates one such issue:

http://blog.omega-prime.co.uk/?p=135

Quote: "In particular, LLVM conservatively assumes that GHC's stack and the heap may alias". LLVM has to assume that short of Haskell-specific analysis, so updating to LLVM 3.4 won't help with such issues.

Re:Optimising Haskell for a tight inner loop by carterschonwald on Thursday January 09, 2014 @02:33PM (#7032605)
not quite, I think the issue is that llvm doesn't understand ghc's stack, so which I guess is the same issue :)
Re:Optimising Haskell for a tight inner loop by gnuvince on Wednesday January 08, 2014 @07:25PM (#7027907)
> Yes, which is why I wonder why GHC went with it's own code generator instead of using LLVM?

LLVM didn't exist when GHC was started.

Re:Optimising Haskell for a tight inner loop by thirsteh on Wednesday January 08, 2014 @07:38PM (#7027958)
It's pretty amazing: The initial release of GHC was in 1989.
Re:Optimising Haskell for a tight inner loop by masklinn on Thursday January 09, 2014 @02:34AM (#7029286)
Neither did the NCG though, I believe. And the NCG only finally overtook the C backend late in the 6.x cycle (6.8? 6.10?)
Re:Optimising Haskell for a tight inner loop by thirsteh on Wednesday January 08, 2014 @07:16PM (#7027865)
GHC's -fllvm flag already makes it use LLVM, although the native code generator remains the default.

This backend (usually coupled with -O2) tends to slow down compile times tremendously, but can make some math-heavy programs much faster.

Re:Optimising Haskell for a tight inner loop by comex on Wednesday January 08, 2014 @08:45PM (#7028212)
Note that since all of the characters in question are less than 64, you could also do a bit test between (1 << x) and a 64-bit mask, simplifying the control flow; I'm not sure whether this would actually be faster, assuming the post is correct that other characters that happen to be <= '$' are rare in practice, but you could then load several bytes at a time into some SSE registers and do the test in parallel, probably netting a substantial speedup at the cost of becoming architecture dependent.
Re:Optimising Haskell for a tight inner loop by awda on Wednesday January 08, 2014 @06:57PM (#7027779)
By break0, it looks like we're just writing Haskell-ified C. (Lots of ugly, similar safety guarantees.)
Re:Optimising Haskell for a tight inner loop by thirsteh on Wednesday January 08, 2014 @07:13PM (#7027855)
Indeed. Many of the high-performance libraries like bytestring, aeson, etc. are written like this.

Haskell's performance is very good for nearly everything I write--and I don't write anything nearly that low level--but I can't deny that this is one of the uglier sides of the language.

On the other hand: In most other languages you'd just be dropping down to the C ABI (that's easy to do in Haskell, too, for that matter.) It is kind of impressive that you can write code that is as fast as C without writing C, even if it is ugly.

Re:Optimising Haskell for a tight inner loop by 1amzave on Thursday January 09, 2014 @01:38AM (#7029136)
> It is kind of impressive that you can write code that is as fast as C without writing C, even if it is ugly.

Impressive, perhaps -- but from a maintainability perspective I think I might prefer to pay the cost of jumping the language barrier to be able to write natural, comprehensible C rather than staying within one language and dealing with an unreadable jumble, even if it performs as well.

Re:Optimising Haskell for a tight inner loop by thu on Thursday January 09, 2014 @05:11AM (#7029647)
The final Haskell code, while being low-level, is not unreadable jumble. Maybe you're talking about the generated Core or the C-- code.
Re:Optimising Haskell for a tight inner loop by chongli on Wednesday January 08, 2014 @09:31PM (#7028396)
The difference is that with Haskell you can wrap a nice, clean, type-safe interface around all that ugly optimization. With C, you're still dealing with casts, null pointer checks, array bounds checks and all sorts of other tedious bug sources that Haskell users don't have to deal with -- unless there's a library bug, of course.
Re:Optimising Haskell for a tight inner loop by nightski on Wednesday January 08, 2014 @08:09PM (#7028079)
I disagree wholeheartedly on the similar safety guarantees part, Haskell still provides you with a significant amount over C in this case. But it does "look" more like it, if that means anything.
Re:Optimising Haskell for a tight inner loop by userbinator on Wednesday January 08, 2014 @08:36PM (#7028177)
I wonder how a table lookup compares? Something like

     mov edx, @table
     xor eax, eax
    loop:
     mov al, [ecx]
     inc ecx
     cmp byte [edx+eax], 0
     jnz loop
I really wish Intel would optimise lodsb, scasb, and the rest of the string instructions, since they're powerful and particularly suited for this sort of scanning.
Re:Optimising Haskell for a tight inner loop by zvrba on Thursday January 09, 2014 @02:26AM (#7029268)
I think it's more likely that they'll eventually re-purpose these opcodes (further ISA extensions), and string operations will be optimized through simple hardware matching of documented instruction sequences. Already today, Intel's optimization manual gives SSE-optimized string search routines, which consume 16 bytes at a time.

Removing and re-purposing instructions is not unprecedented; it has already been done at 32->64 jump. (Prefixes, decimal instructions, etc.)

Re:Optimising Haskell for a tight inner loop by pbsd on Thursday January 09, 2014 @07:40AM (#7030099)
I doubt those instructions (especially stos* and movs*, respectively matching memset and memcpy) are going anywhere. Intel has even changed their semantics in recent chips to work on 16-byte or larger chunks, and to have out-of-order memory accesses. Current MOVSB, for instance, should be nearly as fast as SSE/AVX optimized memory transfers.
Re:Optimising Haskell for a tight inner loop by userbinator on Thursday January 09, 2014 @09:13PM (#7034660)
I wouldn't say their semantics have changed but certainly their implementation. The fact that Intel used to recommend against using them but now advises the opposite, suggests that scas/cmps (memchr/memset) could be next. In any case, the thought of one machine instruction doing better than lots of carefully hand-written assembly is nice.
Re:Optimising Haskell for a tight inner loop by jheriko on Thursday January 09, 2014 @04:56AM (#7029605)
I know its not necessarily avoidable in practice due to legacy reasons, but my main takeaway from this is that Haskell is not for high performance code.