However I also think that this is a very interesting topic that can show you some detailed in depth information about the wonders of how your CPU works and thinks.
I'm going to present it differently from my normal tutorials this time. Thats why this topic is inside the Tips and Tricks subforum despite relating to AutoHotkey.
Have you ever thought about if and else? Looking at if and else it is nothing but a decision between 2 possible actions.
If we don't look at the rest of the script and only at the if/else any if/else becomes very chaotic almost random - similar to a coin toss with a specific chance and pattern to turn heads or tails.
Code: Select all
if ( tossCoin() ) {
doSomething()
else
doSomethingElse()To showcase branch prediction and it's effect we are going to look at a strange sort of if/else.
We will look at an if/else where both branches do almost the same thing.
Additionally that if/else is executed a lot like it's inside a loop:
Code: Select all
Loop 10000000 ;repeat many times
Random, coinTossResult, 0.0, 1.0 ;toss the coin
if ( coinTossResult <= coinTossChance ) { ;get either heads or tails depending on the chance of the throw and then go either
continue ;do nothing loop version
else
continue ;do nothing loop version
}No matter what happens our Script will toss the coin decide the result depending on the chance get a result go to the correct line ( either if or else ) and do nothing.
If you execute this code in pratice with different chances you will see a difference though - specifically if we measure times.
If the chance is 50/50 it will often take longer than when the chance is 100% to be true.
How can that be. If our CPU is executing everything in the correct order as we programmed it the speeds should be exactly the same.
You have probably guessed it now - Your CPU does not execute things in order.
Your CPU - in order to get faster - will reorder things it has to execute to fit its needs.
For example it could delay a specific instruction that requires it to load a new piece of memory and do other instructions first where the memory is already there.
If and Else are not an exception there. The CPU can either go 2 ways - 2 branches of execution - and if it takes to long to get the true/false result for your if else it will just jump ahead and guess whether that if is true or false.
Then it will just execute the resulting code - if it was correct good job - if it was wrong it will have to undo all the stuff it did and go to the correct branch.
That takes time. Even if you do the exact same thing in your if or else branch your CPU isn't smart enough to notice that - it will still undo and redo.
This concept is called branch prediction - a wrong guess is called a branch misprediction.
In highly efficient algorithms branch prediction plays a role. A good example is the skewed pivot Quick Sort - it's a good example of this effect however it breaks the scale of this introduction.
Also this basic example might not be a good example for branch prediction since it seems like the branch prediction isn't always triggered.
AHK is also a very high level language where a lot things get executed between the if/else so it isn't affected that much by branch prediction.
Weird Benchmarks:
https://autohotkey.com/boards/viewtopic ... 36#p197936
From the topic "jeeswg's benchmark tests" we had some curious results since the first test is always faster than the latter test.
It makes no sense - however if we look at it from another perspective it seems that the benchmark is executed before the second.
Meaning that for the second benchmark the CPU will have had more branches and results meaning that it can predict the branches more correctly.
That leads to less mispredictions and a higher speed.
Letting the benchmark execute some time before measuring it should enhance the accuracy of the results.
Specter:
I hope that all of you have heard of Meltdown and Specter. I cannot explain Meltdown but it has to do with instruction reordering and bypassing specific tests of the CPU using that.
Specter however is closely related to Branch Predicition.
As I said before when a misprediction happens your CPU will run the code it shouldn't have run and undo the things it did.
However that cleaning up is not perfect. Some minor rests remain. Specter uses this idea to bypass an if that normally keeps it from reading data it shouldn't have access to.
A specter attack does that by actively making the CPU predict that the protecting if will let it access the data. Afterwards it will trigger a branch prediction and let the if mispredict.
Inside the if there will be a piece of code that will make the CPU leave traces even after the CPU undoes the operations.
Lastly the attack will then read the traces and get the data it normally doesn't have any access to.
In the example implementation that works the CPU was made to load a piece of data from the RAM inside the if. That data was still loaded after the CPU undid everything. Accessing that data is faster than accessing a piece of data that isn't loaded.
