Questions tagged [branch-prediction]

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Filter by
Sorted by
Tagged with
2 votes
0 answers
32 views

problem occurred while designing an enhancement pipeline datapath for branches (MIPS)

i'm studying MIPS pipeline in Patterson and Hennesy TextBook this picture below shows the edits for beq instruction : The idea is to calculate branch target and detect if taken or not in decode stage,...
Abdalrahman Alshannaq's user avatar
0 votes
1 answer
77 views

Use branch prediction with no else statement

I am currently implementing selectionsort. Using the code below and the driver file to test it below. I am currently trying to do micro optimizations to see what speeds it up. public static void ...
Ooh Ben's user avatar
  • 11
0 votes
0 answers
34 views

How to implement the Gshare TAGE hybrid predictor combination on the RISC V BOOM core using Chisel

I am working on implementing hybrid branch predictors listed below Gshare + TAGE TAGE + Alpha Perceptron + TAGE Gshare + Alpha Perceptron + Gshare Perceptron + Alpha Perceptron + TAGE + Alpha I ...
albie_01's user avatar
0 votes
1 answer
28 views

If I want to observe the prediction accuracy of different branches of O3cpu in gem5, should I modify the O3 code? If so, do I need to rebuild gem5

In O3, only one algorithm, bpred_unit, is used, and gem5 also provides several other branch prediction algorithms. I want to compare the prediction accuracy of different algorithms, what should I do?...
Gdnxn Dhfjc's user avatar
1 vote
4 answers
285 views

Branch prediction and UB (undefined behavior)

I know a little something about branch prediction. This happens at the CPU and has nothing to do with compilation. Although you might be able to tell the compiler if one branch is more likely than the ...
Joel's user avatar
  • 885
1 vote
1 answer
81 views

I'd like to know why there's a two-fold difference in execution time between these two codes

In computer architecture class, I learned that when the "if" statement is executed in assembly language, it involves the use of branch prediction strategies. Furthermore, it was emphasized ...
이윤수's user avatar
1 vote
3 answers
114 views

How to avoid branching when finding runs of the same value and storing as a range (like run-length encoding)?

I have the following logic: struct Range { int start; int end; }; bool prev = false; Range range; std::vector<Range> result; for (int i = 0; i < n; i++) { bool curr = ...; // this is ...
ra1nsq's user avatar
  • 11
2 votes
1 answer
152 views

In c++ what is the importance in terms of performance of using 'else' in situations where it doesn't change the flow of the program? [duplicate]

There are cases where (logically at least) it makes no difference if I leave out the else keyword, for example: int func(int num) { if(num == 10) return 99999; **else** return -1; } Question ...
penguin2213's user avatar
0 votes
1 answer
101 views

How to replace nested IF/ELSE branches with SIMD (SSE or AVX)?

EDIT x 2 Added more comprehensive function which returns an abstract register class: the function outputs a register full of floats. I don't care the actual length - SSE, AVX... - because Google ...
stuckoverlow's user avatar
0 votes
0 answers
10 views

__builtin_expect_with_probability use in gcc [duplicate]

The use of builtin_expect_with_probability gcc function is for condition check with probability like in below example __builtin_expect_with_probability(!!(x),1,1.0) can someone tell me what is the ...
Naval's user avatar
  • 1
0 votes
1 answer
117 views

How much does a mispredicted conditional branch cost?

On x86-64 whatever micro architecture and ARM64 devices, how many clock cycles does a mispredicted conditional branch cost? And I suppose I should also ask what the figure is for a successfully ...
Cecil Ward's user avatar
0 votes
1 answer
100 views

How can I cause indirect (function pointer) call to be correctly jump/branch predicted?

let's say I have a function that accepts a callback argument (example given in rust and C) void foo(void (*bar)(int)) { // lots of computation bar(3); } fn foo(bar: fn(u32)) { // lots of ...
ajp's user avatar
  • 1,927
1 vote
0 answers
83 views

Does branchless programming make sense on very old x86 CPUs? (before 80486)

Modern CPUs since at least the 486 ¹) have a tightly-pipelined design, so conditional branches can cause "stalls" in which the pipeline has to be flushed and the code restarted on a ...
Coder's user avatar
  • 187
0 votes
0 answers
150 views

how do i get job id of batch prediction job on vertex AI?

i need to get the prediction details of batch prediction job which are stored on google cloud storage, however to get that i need to get JOB ID from BatchPredictionJob i tired to write the results to ...
krissy's user avatar
  • 11
1 vote
0 answers
124 views

Branch Prediction: What is the BTB eviction scheme used in modern CPUs (Intel skylake for example)?

For branch prediction, the BHT(Branch history table) is indexed by branch virtual address. Aliasing problem happens when two or more branches hash to the same entry in the BHT(Branch history table), ...
Changbin Du's user avatar
-1 votes
2 answers
262 views

Is 2-bit prediction always better than 1-bit?

Does 2-bit prediction always better than 1-bit? And from wikipedia, how ‘a loop-closing conditional jump is mispredicted once rather than twice.’ with 2-bit prediction? According to this answer, 2-bit ...
zg c's user avatar
  • 129
1 vote
0 answers
75 views

Why is there a connection between branch prediction failure and "rep ret" in the K8 processor?

I am currently looking for answers to why gcc generates strange instructions like "rep ret" in the generated assembly code. I came across a question on Stack Overflow where someone raised a ...
Michael Coleman's user avatar
3 votes
1 answer
204 views

Why do we need stalls even if branches can be determined?

I am learning about pipelining and was reading about control hazards from the book Computer Organization and Design: The Hardware/Software Interface (MIPS Edition). There is a paragraph in the book (...
Prithvidiamond's user avatar
0 votes
0 answers
30 views

What is the depth of CPU branch prediction? [duplicate]

If CPU is already in the path of a branch A speculatively, will it continue to speculatively execute the next branch B? or wait until branch A retire? if (A) { /* body of branch A */ if(B) { ...
Changbin Du's user avatar
0 votes
0 answers
42 views

Optimizing a branch like a jump table? [duplicate]

I was wondering if I have a branch bool condition = x > y; // just an example if(condition) { // do the thing... } else { // do the other thing... } It can be optimized to something like this ...
M.kazem Akhgary's user avatar
3 votes
0 answers
99 views

Branch predictor friendly tree traversal

I have an AVL tree and I need to traverse it in ascending and descending order. I implemented a simple algorithm, where knowing the tree size in advance, I allocate an array and assign 0 to a counter, ...
Serge Rogatch's user avatar
1 vote
0 answers
75 views

Influencing branchiness when branch behaviour is known

Before I begin, yes, I'm aware of the compiler built-ins __builtin_expect and __builtin_unpredictable (Clang). They do solve the issue to some extent, but my question is about something neither ...
Mona the Monad's user avatar
3 votes
1 answer
94 views

How to view branch predictor tables of a process using a debugger (gdb)?

I know that most modern processors maintain a branch prediction table (BPT). I have read the gdb documentation but I could not found any command that should give desired results. Based on this, I have ...
Taimoor Zaeem's user avatar
6 votes
3 answers
775 views

Is the if-branch faster than the else branch?

I came across this very nice infographic which gives a rough estimation about the CPU-cylces used for certain operations. While studying I noticed an entry "Right branch of if" which I ...
glades's user avatar
  • 3,915
-2 votes
1 answer
225 views

Is branch prediction purely cpu behavior, or will the compiler give some hints?

In go standard package src/sync/once.go, a recent revision change the snippets if atomic.LoadUint32(&o.done) == 1 { return } //otherwise ... to: //if atomic.LoadUint32(&o.done) == ...
agnes's user avatar
  • 11
7 votes
1 answer
405 views

How to handle branch mispredictions that seem to depend on machine code position?

While trying to benchmark implementations of a simple sparse unit lower triangular backward solve in CSC format, I observe strange behavior. The performance seems to vary drastically, depending on ...
mjacobse's user avatar
  • 365
0 votes
1 answer
267 views

How debuggers deal with out-of-order execution and branch prediction

I know that modern CPUs do OoO execution and got advanced branch predictors that may fail, how does the debugger deal with that? So, if the cpu fails in predicting a branch how does the debugger know ...
Ahmed Ehab's user avatar
3 votes
1 answer
828 views

Rust generic parameters and compile time if

Using C++ template and if constexpr I found a trick that I like a lot: suppose you have a function with some tunable option that are known compile-time, I can write something like template <bool ...
MaPo's user avatar
  • 633
0 votes
3 answers
326 views

How good is the Visual Studio compiler at branch-prediction for simple if-statements?

Here is some c++ pseudo-code as an example: bool importantFlag = false; for (SomeObject obj : arr) { if (obj.someBool) { importantFlag = true; } obj.doSomethingUnrelated(); } ...
Greg's user avatar
  • 61
2 votes
0 answers
1k views

Perf branch misses on non conditional instructions

I want to understand branch prediction behavior of a program I work on. For this, I use the perf tool. I recorded with: perf record -e branches,branch-misses and visualizing it with perf report --...
Konstantin Solomatov's user avatar
5 votes
0 answers
137 views

If a function was entered via a near call, can it do a far tail call without breaking return address prediction?

Consider this code: .globl _non_tail, _tail .text .code32 _non_tail: lcall $0x33, $_non_tail.heavensgate ret .code64 _non_tail.heavensgate: # do stuff. there's 12 bytes on the stack ...
Joseph Sible-Reinstate Monica's user avatar
3 votes
2 answers
331 views

Is there automatic L1i cache prefetching on x86?

I looked at the wiki article on branch target predictor; it's somewhat confusing: I thought the branch target predictor comes into play when a CPU decides which instruction(s) to fetch next (into the ...
ledonter's user avatar
  • 1,649
0 votes
0 answers
164 views

can you produce BEQL MIPS instruction with C code?

So I have this code snippet in C int unit_test_case08(int a, int b) { int success = 1336; if(a != b) { success = 1337; } else { success = -1; } return ...
BBBBBBBBBBBBBBBBBBBBBBBBB's user avatar
0 votes
1 answer
74 views

How to profile branch prediction hitrate in Java

Is there a tool available to profile java applications regarding branch (mis)prediction statistics for if statements? I know VisualVM and JDK Mission Control but did not find such functionality.
Mahatma_Fatal_Error's user avatar
7 votes
2 answers
1k views

RISCV branchless coding

On Intel AVX, there is a possibility of branchless code. Instead of branching for case0 or case1, you can compute both cases, and blend the results based on a condition. AVX does this 8 way for float ...
Bram's user avatar
  • 7,594
0 votes
0 answers
42 views

Branch prediction does not improve the performance [duplicate]

I executed the code from this famous topic Why is processing a sorted array faster than processing an unsorted array? On my Mac OS Mojave: //file test.cpp #include <algorithm> #include <ctime&...
Mikhail Genkin's user avatar
5 votes
1 answer
147 views

Emulate attribute "unpredictable"

There are [[likely]] and [[unlikely]] attributes in modern C++. There are corresponding __builtin_expect(x, 1) and __builtin_expect(x, 0) builtins in G++ and clang++. But also there are ...
Tomilov Anatoliy's user avatar
0 votes
0 answers
46 views

Optimize a loop for static predict-not-taken? Which prediction problems exist for that in a normal loop?

Which problems arise in the following assembly loop, if Predict Not Taken is chosen by default? Optimize the example to Predict not Taken. addi $s1, $zero, 1024 // s1 := 1024 loop: addi $s1, $s1, -1 //...
Iwan5050's user avatar
  • 165
0 votes
0 answers
126 views

Prefetch data-dependent branch to avoid mispredictions [duplicate]

In the following example, I assume that functions f1-f4 are slow, but short and inlined. It is clear to me on iteration i=j that the taken branch of iteration i=j+1 is dependent on the value of data[j+...
Curious's user avatar
  • 517
6 votes
1 answer
435 views

Why is rv32gc optimising branchless code with branches for RISC-V?

Let's attempt to define a function that returns the maximum of two values x and y. A sufficient condition for these formulas to be valid is that, for signed integers, –2^30 <= x, y <= 2^30 – 1, ...
Hugo Sereno Ferreira's user avatar
3 votes
1 answer
351 views

In CUDA kernels, __assume() or __builtin_assume()?

CUDA offers the kernel author two functions, __builtin_assume() and __assume(). Their signatures are the same: void __builtin_assume(bool exp); void __assume(bool exp); and so is their one-line ...
einpoklum's user avatar
  • 121k
0 votes
0 answers
377 views

understanding compiler optimization in gcc

Does gcc understand or lookahead branches and perform optimization. I wrote a code like this for (int i = 10;i < 20;i++) { long long sum = 1; for (int j = 0;j < 10000;j++) { sum ...
Manoj Kumar's user avatar
55 votes
9 answers
10k views

Is if(A | B) always faster than if(A || B)?

I am reading this book by Fedor Pikus and he has some very very interesting examples which for me were a surprise. Particularly this benchmark caught me, where the only difference is that in one of ...
Eduard Rostomyan's user avatar
3 votes
1 answer
2k views

Can I improve branch prediction with my code?

This is a naive general question open to any platform, language, or compiler. Though I am most curious about Aarch64, C++, GCC. When coding an unavoidable branch in program flow dependent on I/O ...
slomobile's user avatar
  • 122
3 votes
1 answer
270 views

BR/RET timing discrepancy when returning from contrived subroutine to a modified return address

In my adventures of experimenting around with the 64-bit ARM architecture, I noticed a peculiar speed difference depending on whether br or ret is used to return from a subroutine. ; Contrived for ...
Mona the Monad's user avatar
0 votes
0 answers
452 views

Branchless comparison in x86_64 [duplicate]

Recently I took the course of discrete math. The professor tells us that branching is slower than branchless. AFAIK modern CPUs use pipeline to increase the efficiency, so breaching in CPUs are ...
TNThung's user avatar
0 votes
1 answer
133 views

How to write a local branch predictor?

I am trying to use runspec test my local branch predictor, but only find a disappointing result. By now I have tried use a 64 terms LHT, and when the LHT is full, I use FIFO tactics replace a terms in ...
丁凌辉's user avatar
1 vote
0 answers
431 views

Optimizing std::clamp with favor for in-range input: is there a point for keeping cmov instead of a branch?

C++17 std::clamp is a template function that makes sure the input value is not less than the given minimum and less than the given maximum, and returns the input value; otherwise it returns the ...
Alex Guteniev's user avatar
1 vote
1 answer
152 views

Are Ada function arguments evaluated if the body is empty?

According to this statement : Trace.Debug("My String" & Integer'Image(x) & "is evaluated" & "or not" & "if my logger is disabled ?" & ...
LnlB's user avatar
  • 190
0 votes
1 answer
1k views

Branch-mispredictions versus cache misses [closed]

Consider the following two alternative pieces of code: Alternative 1: if (variable != new_val) // (1) variable = new_val; f(); // This function reads `variable`. Alternative 2: variable = ...
ABu's user avatar
  • 10.6k

1
2 3 4 5
8