Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lomuto's Comeback

dlang.org

Post reply on HN
Print view View original

11–20 of 104 posts

Re: Lomuto's Comeback

#11

Post by sesuximo »

mehrdadn wrote: post #5

Notice that this is on random longs . Of course branch misprediction and memory bandwidth is going to crush you for a branchy sort... you'll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn't random, so I'd expect branch predictors to do much better with recognizing patterns. And your sorting isn't going to be as simple as sorting integers according to their values all th…

Sorting is the case study but not the insight. I think the cool/surprising part of the article is that doing more work can be faster... Even more memory work (which per conventional wisdom is not trivial!)

Re: Lomuto's Comeback

#12

Post by MauranKilom »

banachtarski wrote: post #10
codeflo wrote: post #9

I’ve read that some vector instruction sets use masking instructions to avoid branching. You execute both arms of the conditional and discard the unwanted computation, which can be cheaper than an X% chance of a branch misprediction. Should CPUs include more masking instructions for regular, non-vectorized code as well?

I’m unconvinced because the instruction set sizes are already becoming fairly bloated (increasing microcode translation cost and i-cache pressure) but also because CPUs already do speculative execution which has a nearly equivalent effect to the idiom you’re referring to. *edit: wording

To be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case.

The problem in question is due to predictive execution in which the CPU has to flush the pipeline on misprediction. This is dominant in desktop PC CPUs. I have no knowledge on what is prevalent in e.g. server or mobile CPUs.

Both are (according to https://en.wikipedia.org/wiki/Speculative_execution) forms of speculative execution.

Re: Lomuto's Comeback

#13

Post by repsilat »

cozzyd wrote: post #4

Writing branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an attempt at better tooling for this.

One thing people have made is array languages. The "primitive" operations apply to arrays of data, so branches around individual elements can't be expressed.

I think it's also generally less expressive, though. Writing Lomuto's partition as efficiently would likely be impossible, but writing it branch-free might not be -- you would compose branch-free primitives like

    left = filter(array, array  array[0])
where `filter` is branch-free and takes an array of Boolean values as its second argument.

Shrugs, aside from some standard set of functions/primitives and idioms I'm not sure it would help much, though perhaps a mindset-shift is a more likely solution than something more technical.

Re: Lomuto's Comeback

#14

Post by eloff »

If you have a branch free algorithm, you can vectorize it. If he discussed implementing this with SIMD instructions (whether by human hand or compiler auto vectorization) I missed that part. But that seems an interesting angle to me.

Re: Lomuto's Comeback

#15

Post by mehrdadn »

sesuximo wrote: post #11
mehrdadn wrote: post #5

Notice that this is on random longs . Of course branch misprediction and memory bandwidth is going to crush you for a branchy sort... you'll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn't random, so I'd expect branch predictors to do much better with recognizing patterns. And your sorting isn't going to be as simple as sorting integers according to their values all th…

Sorting is the case study but not the insight. I think the cool/surprising part of the article is that doing more work can be faster... Even more memory work (which per conventional wisdom is not trivial!)

My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.

Re: Lomuto's Comeback

#17

Post by banachtarski »

MauranKilom wrote: post #12
banachtarski wrote: post #10

Earlier quoted context omitted.

I’m unconvinced because the instruction set sizes are already becoming fairly bloated (increasing microcode translation cost and i-cache pressure) but also because CPUs already do speculative execution which has a nearly equivalent effect to the idiom you’re referring to. *edit: wording

To be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation ) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case. The problem in question is due to predictive execution in which the CPU has to flush the pipeline on mi…

I'm speaking broadly about desktop/console CPUs which I have low-level familiarity with. I don't know of any CPUs in this class that don't perform some form of speculative execution.

I'm not sure if eager evaluation is related to the topic at hand and was speaking specifically about speculative execution. Eager evaluation is just what pretty much every language except Haskell (or Haskell-like) does.

Re: Lomuto's Comeback

#18

Post by MauranKilom »

banachtarski wrote: post #17
MauranKilom wrote: post #12

Earlier quoted context omitted.

To be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation ) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case. The problem in question is due to predictive execution in which the CPU has to flush the pipeline on mi…

I'm speaking broadly about desktop/console CPUs which I have low-level familiarity with. I don't know of any CPUs in this class that don't perform some form of speculative execution. I'm not sure if eager evaluation is related to the topic at hand and was speaking specifically about speculative execution. Eager evaluation is just what pretty much every language except Haskell (or Haskell-like) does.

Sorry, that first link was nonsense. I just copied the wiki link under "Eager execution" in the Speculative Execution page, but that is of course far from the same as "eager evaluation" (which is what the link goes to). I apologized for the confusion.

The point is that there are at least two ways CPUs can speculatively execute a conditional: Either predict which branch is taken and flush the pipeline if the prediction was wrong, or execute both arms of the conditional and discard the one that was not actually taken. The top-level SIMD comment is about the latter, but most optimization around speculative execution is for the former.

Yes, CPUs do speculative execution. The "flush pipeline on mispredict" kind ("predictive execution"). That is not the same as the "execute both and discard the untaken one" kind ("eager execution"). Your first reply suggests you consider them equivalent when they are not. I just wanted to clear that up.

Re: Lomuto's Comeback

#19

Post by VHRanger »

repsilat wrote: post #13
cozzyd wrote: post #4

Writing branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an attempt at better tooling for this.

One thing people have made is array languages. The "primitive" operations apply to arrays of data, so branches around individual elements can't be expressed. I think it's also generally less expressive, though. Writing Lomuto's partition as efficiently would likely be impossible, but writing it branch-free might not be -- you would compose branch-free primitives like left = filter(array, array array[0]) where `filter…

This sort of vectorised pseudo branching is often used in SIMD algorithms

Re: Lomuto's Comeback

#20

Post by cozzyd »

VHRanger wrote: post #19
repsilat wrote: post #13

Earlier quoted context omitted.

One thing people have made is array languages. The "primitive" operations apply to arrays of data, so branches around individual elements can't be expressed. I think it's also generally less expressive, though. Writing Lomuto's partition as efficiently would likely be impossible, but writing it branch-free might not be -- you would compose branch-free primitives like left = filter(array, array array[0]) where `filter…

This sort of vectorised pseudo branching is often used in SIMD algorithms

Yes... and the transformations are often non-trivial (especially when considering the possibility of out-of-bounds elements, which can't just safely be multiplied by zero--they might be a NaN, or on the edge of a page). It would be nice if there was a tool (or compiler option!) that could convert my branchy code into an "identical" (assuming floating-point associativity, etc.) branchless version.
Post reply on HN