Branchless Coding in Go • Hacker News Board

Re: Branchless Coding in Go

#21

Post by mhh__ » Tue, May 04, 2021, 11:49 PM UTC

jupp0r wrote: post #19

naikrovek wrote: post #9

Earlier quoted context omitted.

yes, thank you. improving cache efficiency is by far the biggest single thing you can do to increase performance. if the code and data for both outcomes of an 'if' are in L1 cache, that 'if' is never going to be slow.

Exactly! This is best achieved by keeping data on the stack and avoiding allocations as much as possible.

The kind of data that is going to generate (enough) cache misses (to be a problem) behind your back is usually the stuff which you can't put on the stack.

Re: Branchless Coding in Go

#22

Post by jupp0r » Wed, May 05, 2021, 12:01 AM UTC

mhh__ wrote: post #21

jupp0r wrote: post #19

Earlier quoted context omitted.

Exactly! This is best achieved by keeping data on the stack and avoiding allocations as much as possible.

The kind of data that is going to generate (enough) cache misses (to be a problem) behind your back is usually the stuff which you can't put on the stack.

It can also be lots of small careless allocations all over the place.

Re: Branchless Coding in Go

#23

Post by mhh__ » Wed, May 05, 2021, 1:38 AM UTC

bmm6o wrote: post #16

mhh__ wrote: post #7

Earlier quoted context omitted.

I never got round to trying it but I was wondering whether you could generate a Cauchy-distributed wait as a way of breaking badly written benchmarks/timing gadgets (i.e. the mean is indeterminate)

Doesn't the indeterminate mean rely on the distribution including negative values? Sleep() requires a non-negative value.

Actually, Log-Cauchy?

Re: Branchless Coding in Go

#24

Post by AlexCoventry » Wed, May 05, 2021, 1:51 AM UTC

movedx wrote: post #4

Instead of a "minimum wait", could you implement a random wait? Some random number of ns/ms between calls. Something that's enough to make any timing attack measurements unusable?

A random wait still leaks, but if you can guarantee a reasonable upper bound on the time required, always waiting until that upper bound has passed before responding does not leak.

Re: Branchless Coding in Go

#25

Post by api » Wed, May 05, 2021, 2:05 AM UTC

I love me some branchless coding tricks. It's fun. My favorite is how you can multiply a bool by integers and use masking to conditionally set variables without branching. Just make sure that's defined behavior in your language. Casting bools to ints and bit shifting them can also be used to conditionally bit pack without branching. Lots of fun.

(Might not be worth it if your architecture has conditional move instructions and your compiler is smart enough to use them.)

Re: Branchless Coding in Go

#26

Post by alphawong » Wed, May 05, 2021, 2:57 AM UTC

If I am working in the huge company or project. I will use `if` statement to increase my code readability.

This essay just sit in good to know level.

Re: Branchless Coding in Go

#27

Post by kstenerud » Wed, May 05, 2021, 3:03 AM UTC

jupp0r wrote: post #22

mhh__ wrote: post #21

Earlier quoted context omitted.

The kind of data that is going to generate (enough) cache misses (to be a problem) behind your back is usually the stuff which you can't put on the stack.

It can also be lots of small careless allocations all over the place.

Yup, and go is particularly bad for this because it handles allocations automatically (and poorly). I can double a go program's performance by going through the memory profile and rearranging the instructions to minimize hidden applications.

The worst offender is slices, since you can't mark them read only or stack allocated.

Re: Branchless Coding in Go

#28

Post by Spivak » Wed, May 05, 2021, 3:53 AM UTC

movedx wrote: post #4

Instead of a "minimum wait", could you implement a random wait? Some random number of ns/ms between calls. Something that's enough to make any timing attack measurements unusable?

The time it takes for your function to complete is now a continuous random variable X + r where r is the real time it take for your function to complete.

    E(X + r) = E(X) + E(r) = E(X) + r

    E(X + r) is the sample mean which is easy to calculate
    
    E(X) = 1/2 * (max(sample) - min(sample))

Re: Branchless Coding in Go

#29

Post by userbinator » Wed, May 05, 2021, 4:16 AM UTC

The "branchful" version is not only slower for the processor, it's also slower for a human - this one, at least, would never write code like that; the verboseness and repetition just screams "you're doing it wrong". When I see such duplication, it slows me down because I have to inspect each case to determine that there's not one that's subtly different. I would at least use a loop.

Also, shifting right by n and picking off the least significant bit (&1) may save an instruction or two, depending on the processor.

Finally, an array of bools is itself intrinsically wasteful[1], as the processor can easily test whether a certain bit is set, or set and clear bits, with a single instruction if you keep them packed them together into bytes. There's another comment here about memory layout and cache usage.

[1] It reminds me of the questions "what's the fastest way to generate/parse ?" in an application where you control both ends and a human almost never needs to see the data.

Re: Branchless Coding in Go

#30

Post by nemo1618 » Wed, May 05, 2021, 5:04 AM UTC

userbinator wrote: post #29

The "branchful" version is not only slower for the processor, it's also slower for a human - this one, at least, would never write code like that; the verboseness and repetition just screams "you're doing it wrong". When I see such duplication, it slows me down because I have to inspect each case to determine that there's not one that's subtly different. I would at least use a loop. Also, shifting right by n and pick…

The main goal here is security against side channel attacks, not performance.