FRESH

Hacker News

Home

Quadrupling code performance with a "useless" if

110 points by birdculture

by nonadhocproblem

0 subcomment

I've also been working on a compressor recently, and the same general idea (letting the compiler know that a data dependency occurs very infrequently, and it should therefore assume none exists to exploit ILP) has allowed me to speed up my decompression by a lot:
https://github.com/welcome-to-the-sunny-side/misa77/blob/777...

by throawayonthe

0 subcomment

lobsters comment points out [[unlikely]] works here for clang
https://clang.godbolt.org/z/r4xYWfPfe
edit: oh the article also mentions it now :)

by akoboldfrying

0 subcomment

This is really surprising! I've never considered the possibility that using an equality test to skip a write that would be a no-op could break a dependency and thus lead to higher perf overall if the "equal" outcome occurs often enough. This might be applicable in many situations where you "edit" some data in-place, but most of the time there are few or no changes.

by exmadscientist

1 subcomments

A huge part of the problem here is that you're playing with the 8-bit registers. They work, but they're like travelling the back roads: the CPU designers put all their effort into the big highway next door, and not so much into keeping the back roads clear. They're infamous for random weird stalls and such. I wouldn't be surprised at all if there's dependency chain tracking weirdness using them.
If you can change the type on `next_j` over to `unsigned` (or `size_t` or ...) then a lot of weird stuff goes away. The dependency chains in address calculation at the beginning of the loop are gone too, which seems a win. (Or I'm sure there's some other, more complicated, way to get the compiler to get rid of them.) But if the space hit from using `unsigned` is allowable, I'd expect it to be both faster and less brittle.
The processor doesn't really know what you're up to, it only sees registers. When `j` is stored in `ecx`/`rcx` and `ecx` isn't changing, it knows it's free to push ahead pretty far on speculation. If the update to `ecx` is rare, putting it behind a well-predicted-not-taken branch will make it go away, as far as the speculation engine is concerned, and let the processor go far and fast. (The rollback on mispredict can be pretty painful, but, well, that's out-of-order execution for you.) That's what we're really trying to accomplish here: stuff that single register write behind a rare branch, somehow.
Here's what that can look like: https://clang.godbolt.org/z/1ss6hsEKb
Note that I disabled unrolling because some approaches got unrolled more than others. (I saw no unrolling, 2x, and more!) Comparing them without unrolling is fairest, I think, though it's also interesting to see how far they can unroll without assistance.
I also found that clang didn't need any additional fencing (or care if it was present), but gcc did, so there's an `asm volatile` style fence, which I think is a lot more clear than the other tricks. (Your mileage may vary; people who've done a lot of low-level work won't blink at these, while others will just stare agape. Perhaps also not blinking, but for opposite reasons!)
(Mind you, I didn't actually run any of this, so, well, you get what you pay for.)

by mcv

1 subcomments

Interesting. I thought modern CPU optimisation required avoiding branches, but here adding the branch allows the branch pediction to parallelise what it otherwise couldn't.

by pillmillipedes

1 subcomments

wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?

by anematode

0 subcomment

Brilliant! Hadn't seen this technique before.

by patrulek

2 subcomments

You can utilize MLP (memory-level parallelism) and reduce memory latency by reading whole 8 bytes of next_j at every iteration. Just do something like
`uint64_t packed_next_j = *(uint64_t*)(&next_j[i])`
and then just shift right to find proper j. This way you remove dependency on previous iteration. Did you tried that?

by anthonj

3 subcomments

I think this call for something similar to "__builtin_expect" or linux' likely()/unlikely().
Not very clean, but better than inserting obscure optimisations in the source.

by anirudhak47

0 subcomment

latency optimization is a skill. I liked how you went till CSE pass. I myself wrote several passes to go to lowest latency possible

by 6510

0 subcomment

my js brain keeps thinking encoding[i] = next_j[i][j];