On Apr 19, 2015 09:44, "Joachim Breitner" wrote:

Dear devs,

in https://ghc.haskell.org/trac/ghc/ticket/10124 bgamari suggested that code like

f :: Int -> Bool f a = case a of 1 -> True 5 -> True 8 -> True 9 -> True 11 -> True 19 -> True _ -> False {-# NOINLINE f #-}

should not compile to a series of conditional jumps, but rather a branchless code akin to

let !p = a ==# 1 `orI#` a ==# 5 `orI#` a ==# 8 `orI#` a ==# 9 `orI#` a ==# 11 `orI#` a ==# 19 case p of 1 -> do_something 0 -> do_something_else

Subsequently, I refactored the way we produce Cmm code from STG, opening the possibility to implement this optimization at that stage¹.

But when I then added this implementation, I could not measure any runtime improvement, see https://ghc.haskell.org/trac/ghc/ticket/10124#comment:15

So my question to the general audience: Is such branchless code really better than the current, branching code? Can someone provide us with an example that shows that it is better? Do I need to produce different branchless assembly?

If it is not better, I can again refactor the switch generation and simplify it a bit again.

Hmm, only now I see that rwbarton has replied there. Not sure why I missed that. Anyways, more voices are welcome :-)

Greetings, Joachim

¹ This should not preclude an implementation on the Core level, which SPJ preferred. But I improved other aspects of the code generation as well, so this is worthwhile on its own.

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Joachim Breitner writes:

Dear devs,

in https://ghc.haskell.org/trac/ghc/ticket/10124 bgamari suggested that code like

f :: Int -> Bool f a = case a of 1 -> True 5 -> True 8 -> True 9 -> True 11 -> True 19 -> True _ -> False {-# NOINLINE f #-}

should not compile to a series of conditional jumps, but rather a branchless code akin to

let !p = a ==# 1 `orI#` a ==# 5 `orI#` a ==# 8 `orI#` a ==# 9 `orI#` a ==# 11 `orI#` a ==# 19 case p of 1 -> do_something 0 -> do_something_else

Hi Joachim, Thanks for trying this and I'm sorry to hear that the optimization hasn't yielded the improvement I would have expected. I've been a bit silent on the issue as I've been working on finishing up my PhD. Hopefully in a couple of months after I'm settled in Germany I'll have time to delve into this more deeply.

Subsequently, I refactored the way we produce Cmm code from STG, opening the possibility to implement this optimization at that stage¹.

But when I then added this implementation, I could not measure any runtime improvement, see https://ghc.haskell.org/trac/ghc/ticket/10124#comment:15

So my question to the general audience: Is such branchless code really better than the current, branching code? Can someone provide us with an example that shows that it is better? Do I need to produce different branchless assembly?

Have you had a look at the Intel Optimization manual? I'll admit that I haven't looked myself but I'd imagine they'd probably have a few things to say about this. Cheers, - Ben

2015-04-19 9:44 GMT+02:00 Joachim Breitner :

[...] So my question to the general audience: Is such branchless code really better than the current, branching code? Can someone provide us with an example that shows that it is better? Do I need to produce different branchless assembly? [...]

Just a few war stories regarding this from the trenches (= Chrome's JavaScript JIT): * Branchless code in itself is a non-goal. What you care about is performance and/or code size, but both don't have a direct relationship to using branches or not. * "Hacker's Delight" is a cool book, but don't use the bit fiddling tricks in there blindly. We actually reverted to straightforward code with branches from some seemingly "better" branchless code, because even with branches the performance was better. * Even within a processor family like x64, performance characteristics vary vastly. What can be a performance improvement for the modern beefy Xeon machine you're benchmarking on, can make things worse for a low-end Atom. The same holds in the other direction. * The same holds for different architectures, i.e. an "optimization" which makes things fast on most Intel cores could make things worse on e.g. ARM cores (and vice versa). * On more powerful cores with heavy out-of-order execution, it's hard to beat a well-predicted branch. * On Linux, the perf tool is your best friend. Without it you don't have a clue what's making your code slower than expected, it could be bad branch prediction, stalled units with the CPU, bad luck with caches, etc. * Micro-benchmarks can be highly misleading, e.g. due to totally different branching patterns, cache usage, etc. In a nutshell: If you don't know the details of the architecture you're compiling for, you simply don't know if the "optimization" you have in mind actually makes things better or worse. Therefore these kind of decision have to be pushed very far towards the end of the compiler pipeline. Having some kind of feedback about previous runs of the same code is very helpful, too, but this is a bit complicated in a batch compiler (but doable).

I've gotten substantial speedups (>30%) in the past (e.g. in the hashtables package) by replacing search loops with branchless code, but the technique works best in situations where you have a long run of straight-line integer code for the CPU to chew on; for branchless to be a win you need to feed enough instructions into the pipeline such that the savings of getting 3 instructions per cycle and avoiding paying for branch mispredictions outweighs the savings you would get from not doing the work. I don't think the use case you posted falls into that category. On Sun, Apr 19, 2015 at 12:44 AM, Joachim Breitner

wrote:

Dear devs,

in https://ghc.haskell.org/trac/ghc/ticket/10124 bgamari suggested that code like

f :: Int -> Bool f a = case a of 1 -> True 5 -> True 8 -> True 9 -> True 11 -> True 19 -> True _ -> False {-# NOINLINE f #-}

should not compile to a series of conditional jumps, but rather a branchless code akin to

let !p = a ==# 1 `orI#` a ==# 5 `orI#` a ==# 8 `orI#` a ==# 9 `orI#` a ==# 11 `orI#` a ==# 19 case p of 1 -> do_something 0 -> do_something_else

Subsequently, I refactored the way we produce Cmm code from STG, opening the possibility to implement this optimization at that stage¹.

But when I then added this implementation, I could not measure any runtime improvement, see https://ghc.haskell.org/trac/ghc/ticket/10124#comment:15

So my question to the general audience: Is such branchless code really better than the current, branching code? Can someone provide us with an example that shows that it is better? Do I need to produce different branchless assembly?

If it is not better, I can again refactor the switch generation and simplify it a bit again.

Hmm, only now I see that rwbarton has replied there. Not sure why I missed that. Anyways, more voices are welcome :-)

Greetings, Joachim

¹ This should not preclude an implementation on the Core level, which SPJ preferred. But I improved other aspects of the code generation as well, so this is worthwhile on its own.

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

-- Gregory Collins