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

Branchless Coding in Go

mattnakama.com

Post reply on HN
Print view View original

31–40 of 56 posts

Re: Branchless Coding in Go

#31

Post by nemo1618 »

ericbarrett wrote: post #11

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 the…

Sad but true. This is why I'm hopeful that Zig will add support for "constant time" blocks: https://github.com/ziglang/zig/issues/1776

Re: Branchless Coding in Go

#32

Post by nemo1618 »

mwint wrote: post #10

Can 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?

Here's a simple example:

Say that your server has an admin login that simply compares the submitted password to "thisistherootpassword", one byte at a time. The attacker starts by trying "a","b","c", etc. and measuring the time it takes for the server to respond. When they get to "t", the server takes slightly longer, so they start trying "ta","tb","tc", etc. until the server takes even longer to respond. This allows the attacker to crack the password much, much faster than naively brute-forcing the space.

Actually, I have an even better example: I performed exactly this attack in order to get 1st place in a programming competition. You can read my writeup here: https://lukechampine.com/progcomp.html

Re: Branchless Coding in Go

#33

Post by pcwalton »

Clang generates slightly better code than Go, I think, because it fuses the mov and or together into an lea (demoting or to add in the process): https://godbolt.org/z/1Gz5KzrzK

I'm unsure whether there is a perf difference, though, as register-to-register mov may get boiled away to nothing in register renaming.

Re: Branchless Coding in Go

#34

Post by antpls »

mhh__ wrote: post #6

Usual 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.

People need to focus on solving business problem first. "memory layout" and "cache usage" should be abstracted with premade data structures and algorithms into a library. You could then use "CacheFriendlyHashMap" class as a drop in. Does such library already exist for any language ?

Re: Branchless Coding in Go

#35

Post by adrianN »

antpls wrote: post #34
mhh__ wrote: post #6

Usual 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.

People need to focus on solving business problem first. "memory layout" and "cache usage" should be abstracted with premade data structures and algorithms into a library. You could then use "CacheFriendlyHashMap" class as a drop in. Does such library already exist for any language ?

I have a hard time imagining a programming language where memory layout of your data can be abstracted away like that. You need to think about which data to group together in memory and that depends on the access patterns. It's not enough to replace your binary trees with cache-friendlier B-trees if you still need to access half a dozen of them to perform one iteration of a loop.

Re: Branchless Coding in Go

#36

Post by gnum4n »

jimktrains2 wrote: post #3

I thought TEST did a subtract, setting the appropriate flags and discarded the result?

You're probably thinking of the CMP instruction: https://www.aldeid.com/wiki/X86-assembly/Instructions/cmp

TEST does a boolean AND test: https://www.aldeid.com/wiki/X86-assembly/Instructions/test

Re: Branchless Coding in Go

#37

Post by logicchains »

antpls wrote: post #34
mhh__ wrote: post #6

Usual 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.

People need to focus on solving business problem first. "memory layout" and "cache usage" should be abstracted with premade data structures and algorithms into a library. You could then use "CacheFriendlyHashMap" class as a drop in. Does such library already exist for any language ?

>You could then use "CacheFriendlyHashMap" class as a drop in

It's impossible to have a generic cache-friendly datastructure because the optimal datastructure depends on access patterns. E.g. if I have a collection of struct{x:int, y:int, z:int, w:int}, and I know the two main usecases are indexing by x, and iterating over the collection performing some opp on (y,z,w), then the ideal datastructure is one where all the x are contiguous in memory ([x1, x2, x3...]) and separately the y,z,w triples are contiguous ([y1,z1,w1,y2,z2,w2,y3,z3,w3...]).

Re: Branchless Coding in Go

#38

Post by gnum4n »

AlexCoventry wrote: post #2

> we have to use if to convert bools into bits. What if you can use the unsafe package?

In that case, the code would probably work like the C code example I gave. So... I guess you're right. It _can_ be done in Go without `if` if we use unsafe. I can't argue with that =)

In general, I try to to avoid using unsafe as much as possible. Not because I worry that it's "unsafe" or prone to errors (I'm experienced in C, C++, and assembly), but because it makes the code harder to read, and I don't think my coworkers would appreciate that. ;)

Re: Branchless Coding in Go

#39

Post by eternalban »

adrianN wrote: post #35
antpls wrote: post #34

Earlier quoted context omitted.

People need to focus on solving business problem first. "memory layout" and "cache usage" should be abstracted with premade data structures and algorithms into a library. You could then use "CacheFriendlyHashMap" class as a drop in. Does such library already exist for any language ?

I have a hard time imagining a programming language where memory layout of your data can be abstracted away like that. You need to think about which data to group together in memory and that depends on the access patterns. It's not enough to replace your binary trees with cache-friendlier B-trees if you still need to access half a dozen of them to perform one iteration of a loop.

JIT for data, or an off-line simulation run pass for compiler could help. We'd probably have this already if it wasn't for the fact that unlike code, a JIT regime for memory can't be universally effective. So for the PLT part of it, maybe domain constrained languages? But that said, that all would bring into userland all the gymnastics that VM is doing with paging, etc. I think the more interesting question is what would an OS + language families that convey semantics/intent to the OS look like?

Re: Branchless Coding in Go

#40

Post by gnum4n »

ericbarrett wrote: post #11

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 the…

Author here. Thanks for the advice! That's a very good point.

Maybe it's worth doing a follow-up on this? I originally thought of doing unit tests to ensure it's actually running in constant time for different inputs, but I'm not sure they would run well on anything that wasn't bare-metal (probably too inconsistent).

Have you done this with Go or any other compiled language? I remember a colleague of mine was looking into C++ assembly generation rules a few years ago, but I haven't heard how far he got.

Post reply on HN