Welcome to the Lounge

Randor 5-Jan-21 0:35

Randor

5-Jan-21 0:35

honey the codewitch wrote:
That's sort of unfortunate though, because there are many cases in a codepath where an if will be evaluated most often true with one use case, and most often false

I mean... some of this is just common sense. Imagine that you have a switch statement with 100 cases. 99 of those cases occur 0.1% of the time, the other case occurs 99.9% of the time. In the old days (on old hardware before pipelining and branch prediction) we had to remember to optimize our switch statements so the most common case is at the top.

It's not as relevant today because the address of the most used case will most likely be present in the instruction pipeline. In fact it will have probably already been fetched and speculatively executed.

honey the codewitch5-Jan-21 0:45

5-Jan-21 0:45

Ah, that makes sense. There's sure a lot of thinking around corners required when it comes to understanding what the CPU is doing with your instructions on a superscalar architecture.

Real programmers use butterflies

Randor 5-Jan-21 0:56

Randor

5-Jan-21 0:56

honey the codewitch wrote:
Ah, that makes sense.

Can you tell me why the most used case will already be present in the instruction pipeline? And also why that address will most likely have been speculatively executed? (The 100 case switch statement)

Yes, this is a quiz to check if you really understood. Poke tongue | ;-P

honey the codewitch5-Jan-21 1:06

5-Jan-21 1:06

If I understand your question, and the problem correctly, then because of locality. The code would be in the cache. And based on what you said before, it uses history to predict, but most recently you also said it would rely on branch order - i am a little unclear on that, but right now I'm assuming you mean it uses both, which seems likely.

Real programmers use butterflies

Randor 5-Jan-21 1:24

Randor

5-Jan-21 1:24

honey the codewitch wrote:
it uses history to predict

Yeah, the 'jump table' would most likely have that address with a weighted score.

honey the codewitch wrote:
but most recently you also said it would rely on branch order - i am a little unclear on that

I think looking at executables as a visual graph[^] make it easier to understand. The cpu does not have any control over branch ordering. Your compiler/linker controls this. This entire conversation was about how likely and unlikely keywords affect that ordering. And how that influences branch prediction.

Anyway, I am falling behind in my work, gotta go

honey the codewitch5-Jan-21 1:35

5-Jan-21 1:35

Randor wrote:
The cpu does not have any control over branch ordering. Your compiler/linker controls this.

Yeah, I understand that. What I'm saying is you seemed to be saying that the CPU relies on the order those branches appear in the instruction stream in order to predict. I heard you as saying it would favor the first one it encountered. Maybe I misunderstood you.

Randor wrote:
Anyway, I am falling behind in my work, gotta go

Don't work too hard. Smile | :)

Real programmers use butterflies

Randor 4-Jan-21 19:37

Randor

4-Jan-21 19:37

Stuart,

We are discussing jump tables in the CPU related to branch prediction. There are two address locations in the example you have given that would be added to the jump table. Both the je and jne would result in a jump table entry. It's actually extremely easy to understand:

Branch prediction basically works like this: (note that this is a simplification and each vendor does it differently)
- As your program is executing the CPU tracks each and every time a jump instruction has executed. It keeps a table of the address of these jumps and increments an internal counter each time that jump instruction is executed.
- As executable code is being loaded and cached, the cpu attempts to predict which path will be executed. It uses that internal counter as a 'weight'. In other words previous taken paths have a higher probability of being chosen. If it incorrectly predicts a path... this is known as a branch misprediction. After a misprediction the cpu has to throw away everything it just computed and go back and predict the path again until it gets it right.(This is actually the core problem with the spectre vulnerability[^]) as you can look at the timing and use very small intervals of time to know what is inside the cpu cache.

The likely and unlikely keywords effect the ordering of the jump instructions in such a way so that branch prediction will be more accurate.

Best Wishes,
-David Delaune

modified 5-Jan-21 3:48am.

honey the codewitch4-Jan-21 23:39

4-Jan-21 23:39

Randor wrote:
This is actually the core problem with the spectre vulnerability[^]

I just read about that now, thanks to your comment. I don't know whether to be impressed by the hack, or appalled at the amount of time the creator of it must have had on their hands. Laugh | :laugh:

Real programmers use butterflies

honey the codewitch4-Jan-21 7:14

4-Jan-21 7:14

cool. i'll check it out

Real programmers use butterflies

Rick York3-Jan-21 11:34

Rick York

3-Jan-21 11:34

For something a little bit different, try programming GPUs. You have to think in terms of using a few thousand processors that can all work at once. The challenge is to arrange your algorithm and data so they actually can all work at once. It's really quite fun.

"They have a consciousness, they have a life, they have a soul! Damn you! Let the rabbits wear glasses! Save our brothers! Can I get an amen?"

honey the codewitch3-Jan-21 11:59

3-Jan-21 11:59

I've played a little bit with that, enough to at least have a general feel for the landscape. It dovetails with this kind of coding actually, because branchless coding tends to be parallelizable. It's not always true of course, but it just tends to lend itself to it.

Real programmers use butterflies

Greg Utas3-Jan-21 12:39

Greg Utas

3-Jan-21 12:39

No offense intended, but I can think of some things that are a lot more fun, and less contrived. Big Grin | :-D

Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.

Face Recognition App

Kevin Marois3-Jan-21 7:59

Kevin Marois

3-Jan-21 7:59

Anyone worked on Face Recognition projects? I'm looking to write an app and would like some guidance.

If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.

Re: Face Recognition App

Nelek3-Jan-21 10:15

Nelek

3-Jan-21 10:15

CP Search[^] is a good place to start

M.D.V.

If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.

Local Polymorphism

Gerry Schmitz3-Jan-21 4:50

Gerry Schmitz

3-Jan-21 4:50

I've been porting large chunks of C code to C#.

Some routines are quite long and deal with a lot of C "math.h", etc.

In some case, I'll do a straight c "cos" to c# "Math.Cos", for example.

In other cases, a "local delegate" avoids having to make a lot of changes or adding a method with the same name. e.g.

Func<double, double> cos = Math.Cos;

// "C" code.
double cosX = cos(x);
double cosY = cos(y).
...
...

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

PIEBALDconsult3-Jan-21 5:28

PIEBALDconsult

3-Jan-21 5:28

Would this be better as a Tip?

Daniel Pfeffer3-Jan-21 6:07

Daniel Pfeffer

3-Jan-21 6:07

This brings to mind pre-processor games that attempted to make C more "Pascal-like" by replacing '{' with 'begin', '}' with 'end', etc. This is of limited utility, and only confuses those who expect to see native C# code.

Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.

OriginalGriff3-Jan-21 7:38

OriginalGriff

3-Jan-21 7:38

C++

#define while if

C++

#define true ((__LINE__&31)!=31)

Always fun to work with ... Big Grin | :-D

"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!

honey the codewitch3-Jan-21 7:53