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

41–50 of 56 posts

Re: Branchless Coding in Go

#41

Post by slimsag »

gnum4n wrote: post #40
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…

You could perhaps just have the Go compiler generate the assembler for your code:

go tool compile -S file.go > file_amd64.s

Then you could verify it doesn't change over time, and choose to begin maintaining by hand if it makes sense.

If you do want to go the route of rolling it yourself, I'd suggest looking into something like Avo: https://github.com/mmcloughlin/avo

Re: Branchless Coding in Go

#42

Post by slver »

Thoughts in my head:

- Go was designed with simple compiler, because the purpose of it wasn't best performance at all costs, but simple code and fast compilation.

- Instead we watch as people try to second-guess their processor and alter their code to optimize the machine code produced. Defeating the purpose of Go?

- I've actually seen cases where removing the branches slows down code. People have learned that branching is interesting to the CPU, and have decided that no branching means "faster". Actually branching is perfectly fast, when the predictor is right (most of the time). You only want to avoid branching where the predictor does poorly.

Anyway, I think only do these tricks in very hot spots of your code, and backed by a solid benchmark to confirm improvement.

Re: Branchless Coding in Go

#43

Post by glangdale »

WillAbides wrote: post #8

I wrote a mostly branchless json parser in go using ragel to generate most of the code. https://github.com/WillAbides/rjson The generated code isn't much to look at, but it is certainly fast. https://github.com/WillAbides/rjson/blob/main/object_handler...

This must be some strange new definition of "branchless" with which I'm not previously familiar; the generated code is full of branches, conditional or otherwise. I don't think invoking some other tool to put branches into your code qualifies you as branchless.

Have you compared your parser to simdjson-go? I haven't looked specifically at the go rewrite, but I hear it's decent.

I was very excited to do branch free coding to parse JSON, but really only handled the 'lexing' portion of the task in branch free fashion. Certainly more of the task could be done branch free, especially if you are working on SIMD or GPGPU.

Re: Branchless Coding in Go

#44

Post by Buttons840 »

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?

Here's a secret number plus or minus 10: 98, 104, 101, 110, 93...

You'll never guess what the secret number is. /s

The entire purpose of statistics is to uncover that secret number, and it works if you have enough data. Changing the random plus or minus won't save you.

Re: Branchless Coding in Go

#45

Post by miscmask »

logicchains wrote: post #37
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 ?

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

> and separately the y,z,w triples are contiguous ([y1,z1,w1,y2,z2,w2,y3,z3,w3...]).

Wouldn't having ys, zs and ws occupying different cache lines be good enough? After all, the CPU only wants fast access to these data. Or maybe it's a hard thing to do for CPUs to fetch from 4 different lines at a time (+1 for the instructions)?

Re: Branchless Coding in Go

#46

Post by WillAbides »

glangdale wrote: post #43
WillAbides wrote: post #8

I wrote a mostly branchless json parser in go using ragel to generate most of the code. https://github.com/WillAbides/rjson The generated code isn't much to look at, but it is certainly fast. https://github.com/WillAbides/rjson/blob/main/object_handler...

This must be some strange new definition of "branchless" with which I'm not previously familiar; the generated code is full of branches, conditional or otherwise. I don't think invoking some other tool to put branches into your code qualifies you as branchless. Have you compared your parser to simdjson-go? I haven't looked specifically at the go rewrite, but I hear it's decent. I was very excited to do branch free co…

I apparently had a fundamental misunderstanding of the meaning of branchless. That's embarrassing.

As for simdjson-go, I did benchmark it. rjson outperformed simdjson-go in most benchmarks, but simdjson-go was about 3% faster reading citm_catalog.json.

https://github.com/WillAbides/rjson#simdjson

Edit:

I see on your bio that you are one of the simdjson authors. I hope you will indulge a question about it. I am generally more interested parsing a large volume of json documents efficiently than I am in doing it quickly. Since simdjson uses parallel instructions, would that mean that the speedup comes at the expense of being able to process more documents in parallel on the same hardware?

Re: Branchless Coding in Go

#47

Post by slver »

nemo1618 wrote: post #32
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…

How likely is this attack over the Internet (rather than locally or intranet) you think? Realistically?

Also wouldn't other mitigations stop it, like slowing down retry after 3 attempts, blocking after 10 or so.

Re: Branchless Coding in Go

#49

Post by ericbarrett »

gnum4n wrote: post #40
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…

So I looked into this and Go doesn't exactly make it easy.

The process would be to break out the hand-reviewed (but not necessarily hand-written) assembler for this function into a separate source file for each supported architecture (probably x86-64 and ARMv? nowadays), compile from assembler source into an object file, then link the final Go binary together using the object file and the rest of your app's Go source.

However the Go toolchain doesn't make this particularly easy. I think it might be necessary to use the cgo package[0] and import these objects as C-style functions, even if they originally came from Go source. (If somebody has a simpler way, I'd love to know!)

I think calling conventions for pure Go functions differ somewhat from the C ABI, so you might have to tweak the assembly code to follow C calling conventions as well—with the caveat that I haven't dived deeply into this, and could be all wet.

This method would be "fragile" in the sense that toolchain changes would risk breakage with every Go revision, but at least it would be your build that breaks and not your code's timing-attack security.

[0] https://golang.org/cmd/cgo/

Re: Branchless Coding in Go

#50

Post by ericbarrett »

slimsag wrote: post #41
gnum4n wrote: post #40

Earlier quoted context omitted.

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…

You could perhaps just have the Go compiler generate the assembler for your code: go tool compile -S file.go > file_amd64.s Then you could verify it doesn't change over time, and choose to begin maintaining by hand if it makes sense. If you do want to go the route of rolling it yourself, I'd suggest looking into something like Avo: https://github.com/mmcloughlin/avo

avo looks like would be a great route for this, though I haven't personally used it.
Post reply on HN