My advice for the author and anybody else considering this is to break out the confirmed-correct assembler code into its own non-Go object and then link it in; otherwise, you're depending on the compiler to never change and inadvertently introduce branches. Since the functionality of the code wouldn't change it would be difficult to check with a unit test. (I guess you could add one that did the assembly step and then grepped for jump instructions, but that has problems of its own.)
Branchless Coding in Go
11–20 of 56 posts
Re: Branchless Coding in Go
#12Can anyone explain the “why does this matter” paragraph where the author seems to suggest that using branches in our program is a security risk? I know that branch speculation can be used as an attack vector if our program is the aggressor - but does simply using branches in some way make us more likely to be the victim?
This is regarding a JWT[0] which is often used for authentication.
Server-side code which takes a different amount of time depending on what bits are set in the JWT (or any similar authentication token) can be probed by repeating the operation with different values. Think of lockpicking—if you can move a pin and hear a click or feel more or less resistance, you know you've poked something critical in the core.
[0] https://jwt.io/
Re: Branchless Coding in Go
#13Can anyone explain the “why does this matter” paragraph where the author seems to suggest that using branches in our program is a security risk? I know that branch speculation can be used as an attack vector if our program is the aggressor - but does simply using branches in some way make us more likely to be the victim?
One classical example of this is a side-channel attack on RSA. In brief, the central computation is to raise a number to the power of a secret key. This is naively accomplished through a square-and-multiply algorithm -- where multiplications happen for every 1 of the binary representation of the secret key. By watching the power consumption of a device as it encodes/decodes a message, you can read off the secret key with relative ease.
Re: Branchless Coding in Go
#14Usual disclaimer: The branch predictor is one of the things that will make your program slower, so keep it in mind, but it's the memory stupid(!) so if the powers that be want a faster program in a few days focus on memory layout and cache usage first.
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.
depends how deep the pipeline is - with a long pipeline, a pipeline flush as a result of an incorrect predict can stall for tens of cycles.
Re: Branchless Coding in Go
#15Can anyone explain the “why does this matter” paragraph where the author seems to suggest that using branches in our program is a security risk? I know that branch speculation can be used as an attack vector if our program is the aggressor - but does simply using branches in some way make us more likely to be the victim?
The only thing I could think of is when writing crypto code, you want your execution time to be constant for all inputs to avoid timing related attacks (e.g. https://www.chosenplaintext.ca/articles/beginners-guide-cons...)
Re: Branchless Coding in Go
#16Instead 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?
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.
Re: Branchless Coding in Go
#17Sounds like https://capnproto.org/
Re: Branchless Coding in Go
#18Earlier 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.
You're probably right, too many beers perhaps!
Re: Branchless Coding in Go
#19Usual disclaimer: The branch predictor is one of the things that will make your program slower, so keep it in mind, but it's the memory stupid(!) so if the powers that be want a faster program in a few days focus on memory layout and cache usage first.
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.
Re: Branchless Coding in Go
#20Earlier 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.
depends how deep the pipeline is - with a long pipeline, a pipeline flush as a result of an incorrect predict can stall for tens of cycles.
That's still dwarfed by a cache miss if you're unlucky.
I just found a bug (slow code is a bug) in the D backend where bad data layout led to 32 MILLION LLC misses (85% of the whole program) coming from one line!
Think about how much of a cacheline you are using per iteration folks.