Branchless Conditionals (2011) • Hacker News Board

Re: Branchless Conditionals (2011)

#11

Post by vardump » Mon, Apr 20, 2015, 9:44 PM UTC

strictfp wrote: post #4

Nice article. It inspired me to look around for some more straightforward way of optimizing, and I found the setcc class of instructions: http://www.nynaeve.net/?p=178 I'm thinking that this combined with some CAS (CMPXCHG8B) could acheive the same, right? Something like (pseudo): Comparewith(4) Ifequalstore(54) Ifnotequalstore(2) Return

I think CAS is a pretty slow operation even without a LOCK prefix. You probably don't want to use it for purposes other than intercore synchronization.

If you have a lot of data to process, using SSE/AVX is a huge win. Conditional masking and min/max instructions for example.

SIMD is a huge win especially in sorting, you can have 10-40x speed-up by using a bitonic sorting network.

Re: Branchless Conditionals (2011)

#12

Post by vardump » Mon, Apr 20, 2015, 9:47 PM UTC

zwieback wrote: post #2

It's interesting that ARM32 has conditional execution and I like them a lot for writing readable assembly code. Short jumps that result from a simple if can be encoded in three successive instructions, no branches. However, it's now falling out of favor (mostly gone from ARM 64) and apparently it's due to the relative cost of putting conditional execution on the die vs. relying on smarter compilers.

I think ARM64 dropped predicates to remove excessive flags-register read ports. Nearly every instruction could read flags register and this limited core frequency (critical path), opportunities to out-of-order execution (and register renaming). Not sure though, maybe someone who knows more about OoO on ARM64 could fill me in?

Re: Branchless Conditionals (2011)

#13

Post by chipsy » Mon, Apr 20, 2015, 9:54 PM UTC

1_player wrote: post #8

chipsy wrote: post #7

One simple branchless optimization form I've used is collision detection across an array of values: instead of testing each one, i add their value to a counter(perhaps with some mapping of data to collision value). After iterating over a lot of them, I can do just one test. This is very cpu-friendly as the pipeline gets to crunch all the numbers in one go.

Sounds interesting, can you provide a code example?

The example I was going to provide [0] it turns out was reduced into a memory comparison.

I wrote a little C program for you instead: [1]

[0] https://github.com/triplefox/three-packer/blob/master/packer...

[1] https://gist.github.com/triplefox/47d620fc556e3f7da9bb

Re: Branchless Conditionals (2011)

#14

Post by vardump » Mon, Apr 20, 2015, 9:57 PM UTC

One example seems a bit odd.

  if(LocalVariable & 0x00001000)
      return 1;
  else
      return 0;

  mov eax, [ebp - 10]
  and eax, 0x00001000
  neg eax
  sbb eax, eax
  neg eax
  ret

Hmm... wouldn't this be faster? Two instructions less:

  mov eax, [ebp - 10]
  and eax, 0x00001000
  shr eax, 12
  ret

Well, who knows. Didn't bother to analyze this case. Maybe the article's example is faster somehow?

Re: Branchless Conditionals (2011)

#15

Post by nezza-_- » Mon, Apr 20, 2015, 10:01 PM UTC

strictfp wrote: post #5

zwieback wrote: post #2

It's interesting that ARM32 has conditional execution and I like them a lot for writing readable assembly code. Short jumps that result from a simple if can be encoded in three successive instructions, no branches. However, it's now falling out of favor (mostly gone from ARM 64) and apparently it's due to the relative cost of putting conditional execution on the die vs. relying on smarter compilers.

Nice! How do you do this on ARM exactly?

The first 4 bit of each (32 bit long..) instruction can be used to check for conditions: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....

Re: Branchless Conditionals (2011)

#16

Post by kragen » Mon, Apr 20, 2015, 10:23 PM UTC

strictfp wrote: post #5

zwieback wrote: post #2

It's interesting that ARM32 has conditional execution and I like them a lot for writing readable assembly code. Short jumps that result from a simple if can be encoded in three successive instructions, no branches. However, it's now falling out of favor (mostly gone from ARM 64) and apparently it's due to the relative cost of putting conditional execution on the die vs. relying on smarter compilers.

Nice! How do you do this on ARM exactly?

Every instruction on ARM (vanilla: no 64, no Thumb) has a condition code field.

Re: Branchless Conditionals (2011)

#17

Post by kstenerud » Mon, Apr 20, 2015, 10:27 PM UTC

I know that gcc and clang both have __builtin_expect(). If you tell the compiler the more likely path, wouldn't that make the branching version faster?

Actually, I've always wondered how __builtin_expect translates to something the CPU's branch prediction engine can use...

Re: Branchless Conditionals (2011)

#18

Post by vardump » Mon, Apr 20, 2015, 10:48 PM UTC

kstenerud wrote: post #17

I know that gcc and clang both have __builtin_expect(). If you tell the compiler the more likely path, wouldn't that make the branching version faster? Actually, I've always wondered how __builtin_expect translates to something the CPU's branch prediction engine can use...

Branches can have prefixes x86 CPU can use as a hint. Modern x86 CPUs ignore these hints.

Re: Branchless Conditionals (2011)

#19

Post by CHY872 » Mon, Apr 20, 2015, 10:54 PM UTC

kstenerud wrote: post #17

I know that gcc and clang both have __builtin_expect(). If you tell the compiler the more likely path, wouldn't that make the branching version faster? Actually, I've always wondered how __builtin_expect translates to something the CPU's branch prediction engine can use...

I think in general, most CPU architectures pick branch not taken for forward branches and branch taken for backwards branches on the first try. So I feel like builtin_expect gives weighting to let the compiler shuffle code around to make it fit that pattern.

There are ways of doing it in hardware, I remember a supervisor discussing it with respect to MIPS. I also remember them saying they went through the entire code generation stage of GCC and found that every single point at which GCC would try to use it was somewhere where it would be actively unhelpful.

Re: Branchless Conditionals (2011)

#20

Post by astrange » Mon, Apr 20, 2015, 11:12 PM UTC

vardump wrote: post #14

One example seems a bit odd. if(LocalVariable & 0x00001000) return 1; else return 0; mov eax, [ebp - 10] and eax, 0x00001000 neg eax sbb eax, eax neg eax ret Hmm... wouldn't this be faster? Two instructions less: mov eax, [ebp - 10] and eax, 0x00001000 shr eax, 12 ret Well, who knows. Didn't bother to analyze this case. Maybe the article's example is faster somehow?

The neg/sbb/neg operation is 'x = x != 0' or 'x = !!x', I think.

You're right that yours should work too, because after the and the value can only have 1 bit set. But it only works for this particular and mask.