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

Bypassing the Branch Predictor

nicula.xyz

Post reply on HN
Print view View original

31–40 of 40 posts

Re: Bypassing the Branch Predictor

#31

Post by kronks »

bluGill wrote: post #12

Do cpus really track that much about branches? I know JIT does but where does a cpu find the needed memory to store those counters - and them how does reading those not result in a different miss because the cpu can't speculate until it does the if prediction? last time I checked a cpu documentation they had a simple rule that branches are always taken, that would be easy for the compiler to code order first. However…

All of the side channel attacks for CPUs has been from in depth use of branch prediction techniques that make up a significant part of every modern processor’s performance. It’s one of the main things we can do aside from just clocking them higher.

Re: Bypassing the Branch Predictor

#32

Post by [deleted] »

nneonneo wrote: post #5

What a fun problem to think about. My first instinct, knowing less about this domain than maybe I should, would be to abuse the return address predictor. I believe CPUs will generally predict the target of a “ret” instruction using an internal stack of return addresses; some ARM flavours even make this explicit ( https://developer.arm.com/documentation/den0042/0100/Unified... ). The way to abuse this would be to put…

[deleted]

Re: Bypassing the Branch Predictor

#33

Post by ack_complete »

tehjoker wrote: post #29
sparkie wrote: post #14

Earlier quoted context omitted.

The branch taken hint (3EH) was re-added in Redwood Cove (2023), but it's only for static prediction where the branch predictor has not yet encountered the branch - ie, useful for things you would only use once or twice but would likely take the branch. Once the branch predictor has some information the static prediction hint is ignored, so it's best to omit it for anything that will eventually have dynamic branch pr…

if the branch is only taken once how can you realize a significant performance benefit more than a few ns?

Cold branch comes to mind -- something like a interrupt handler, that is run often enough but not in high enough bursts.

Re: Bypassing the Branch Predictor

#34

Post by bluGill »

School-Cotton wrote: post #19
bluGill wrote: post #17

Earlier quoted context omitted.

over the 15 million lines of code I maintain there are a lot of branches. the cpu can track the most common ones but as soon as the code spills out of cache where does that memory come from?

It doesn’t track all of them, it’s a cache. The ones that were hit long enough ago get evicted, and then if you ever hit them again the processor will indeed have to fall back to a naive static prediction strategy with a high miss probability.

Thanks, that makes sense now

Re: Bypassing the Branch Predictor

#35

Post by m4nu3l »

I remember reading about this or a similar problem before. I think it was posted on HN, but the solution was much different. They entirely removed the branch and instead marked the requests in such a way that the packets would be discarded by the network adapter. I can't remember the details. That only works for that kind of network transactions, though.

Re: Bypassing the Branch Predictor

#36

Post by dooglius »

monocasa wrote: post #25
kklisura wrote: post #7

> I asked Claude if there is such a way to basically hard-code branch prediction rules into the machine code, and the answer was that there’s no way to do this on x86, but there is a way on ARM: the BEQP (predict branch taken) and BEQNP (predict branch not taken) instructions. > Those ARM instructions are just hallucinated, and the reality is actually the other way around: ARM doesn’t have a way of hard-coding ‘predi…

To be fair, on the x86 side those branch prediction hint prefixes have been functionally ignored by pretty much all cores for about two decades.

They've been brought back in recent uarches

Re: Bypassing the Branch Predictor

#37

Post by 113245 »

Arcuru wrote: post #30

I love the `[[likely]]` and `[[unlikely]]` tags since they nicely encapsulate the Modern C++ philosophy. 1. They don't work that well. 2. The intended use case is that you'd label an unlikely branch that you want to speed up as `[[likely]]`, which is confusing. They are certainly motivated by good intentions (like the HFT use-case as mentioned in TFA, I remember that talk too, I think I was a volunteer that year for…

1 - Can you elaborate? To what standard do you hold "work well"?

2 - Can you back that up? Generally [[likely]] is for the codepath that you want to be faster, where common path = fast path. It is a specific HFT use case to desire the fast path to be the uncommon path. [[likely]] is definitely intended to be the fast path per https://en.cppreference.com/w/cpp/language/attributes/likely

Re: Bypassing the Branch Predictor

#38

Post by yeoyeo42 »

5 microseconds is a whole lot of time for just a branch misprediction, which is on the order of a few nanoseconds. probably a lot more important stuff going on and focusing on the wrong thing.

for example, predicting a different branch can lead to different memory access patterns. maybe you can get rid of most of the real world cost of the misprediction by just forcefully prefetching the memory the send() path is going to use.

Re: Bypassing the Branch Predictor

#39

Post by jcul »

andrepd wrote: post #11
jcul wrote: post #6

Why not just make all the abandon transactions into fake discarded transactions, discard them at the send later. E.g. by poisoning the frame checksum or setting something invalid on them, so they get discarded. Seems you'd be doing this anyway with the dummy transactions. Then you have no branch, though may want to add dummy transactions anyway to keep the code in cache.

This is literally what is says in TFA lol

I don't believe that's true.

The article suggests flooding the system with dummy "should send" transactions so that they become the majority.

Quote:

> One such solution that I know of is one that Carl Cook talked about during his CppCon 17 talk2: we can fill our system with mocked transaction data for which should_send(t) returns true. We have to do this enough times such that the mocked transaction data becomes the vast majority over the real data, so the branch predictor will be primed to assume that the send() path will be executed practically on every resolve() call. Overall, this may actually be a better approach than hard-coding prediction rules, because those rules wouldn’t really guarantee us that the whole send() path would get executed (the assumption may just lead to partial execution, until the should_send(t) condition is actually evaluated and the pipeline is flushed; so at the end we may still have important stuff not placed in the instruction/data cache).

What I am suggesting is to remove the branch entirely, and instead poison the "should abandon" transactions so they get dropped or null routed on the NIC. This is the kind of thing that low latency cut through L1 switches do.

Thereby removing the CPU branch predictor from the equation entirely.

Re: Bypassing the Branch Predictor

#40

Post by thatSteveFan »

113245 wrote: post #37
Arcuru wrote: post #30

I love the `[[likely]]` and `[[unlikely]]` tags since they nicely encapsulate the Modern C++ philosophy. 1. They don't work that well. 2. The intended use case is that you'd label an unlikely branch that you want to speed up as `[[likely]]`, which is confusing. They are certainly motivated by good intentions (like the HFT use-case as mentioned in TFA, I remember that talk too, I think I was a volunteer that year for…

1 - Can you elaborate? To what standard do you hold "work well"? 2 - Can you back that up? Generally [[likely]] is for the codepath that you want to be faster, where common path = fast path. It is a specific HFT use case to desire the fast path to be the un common path. [[likely]] is definitely intended to be the fast path per https://en.cppreference.com/w/cpp/language/attributes/likely

Not the parent, but wanting the rare case to be fast is definitely not a HFT exclusive thing.

I write software packet processors for a living, and it's common to have requirements stated as "process X packets per second, no matter what", ie youre judged by the worst case kind of packets. Also common is optimization of 99.9th percentile latency.

There's also just cases like if (being ddosed) or if (overloaded) where you definitely want the rare case to be faster.

As to point 1, there's.... a significant doubt as to whether these actually change performance. I have never personally managed to confirm a performance gain from them, and not for lack of trying. CPUs also seem to not give them a ton of weight, and will probably override you if they see a way more common other path.

Post reply on HN