Oh, my CPU is sometimes slow, and I don't know why, maybe because it's too low power,
maybe because my code is hardly inefficient.
So I actually invited an old colleague of mine, which is nothing to do with why he was
accepted.
But with an amazing talk, he's working on databases in his main life of Grafana, and
it's now going to talk about this, why CPU is a slow and how to fix this?
Right, let's talk last.
Yeah, thank you, everyone.
So yeah, thank you, Mark, for the introduction.
So I'm going to want to show you some research I've done, at some point, started computer
science and forgot everything about it, so it's always good to, I guess, remember some
of the principles, how the CPU is run, and right now I'm working on Grafana Power
scope, which is a database for profiling data.
So it is kind of related to the topic here, so we obviously know Go has P-Prof, and we collect
CPU usage there, and this kind of just shows that we can go deeper if we have to.
I'm not saying that I have to do this a lot, or maybe, ever, but I always had on my list,
to basically figure out a bit more out from the CPU performance metrics, it gives.
So quick overview, over today, so first, we're going to look at how CPUs kind of evolved
over the last couple of years, and basically, I'd like to look at the cache architecture.
I think it fits quite well with the green tea, got a bunch of collected talk a few here
for longer, and then I want to take a look how branch prediction happens in your CPU,
and why sometimes that might happen to you, and finally I want to show how you could
measure this, and what kind of tools are available, and hopefully, a quick demo on something
benchmark that I run remotely, it's going to see it, probably.
Here's maybe just a quick history, so I actually own the two on the left side in my laptops.
So, 20 years ago, a core to do, had two cores, and if we now kind of look over the years,
we are now more at the 20 core mark, if you buy a new laptop this year, so that's very
other metrics I put on, I guess the summary is maybe we have roughly 10x most strengths
in those 20 years until now, so I guess something notable, the kind of frequency seemed to
hit some ceiling, so we're still talking about a base frequency of trigger heads, but it
can obviously go a lot higher, and also the cache become bigger, so you can see that in the
kind of very recently the level 1 has increased from 64 kB to 192, I think, so basically all
in all CPUs are faster than 20 years ago, what I would say has not really changed,
it's that kind of like how they relate to each other different timings in how the CPU
access its memory, so I guess if I go to the level 1 cache, we are in the kind of area of
one nanosecond, so I don't know the cycle is maybe 0.2 nanoseconds, and so basically like
over that time it might have gotten smaller, but what didn't really change is that roughly 10x
is like what the last level cache has in terms of latency, and then if you go to RAM, you probably
are the 100 x of the level 1 cache latency time, and then obviously the further you go away from
from your CPU, the longer this latency will take, I guess an NVME is more in 10 microseconds like
milliseconds for HDDs, I don't know, I put a confiner dashboard to put it in perspective,
it's maybe more 10 seconds that you want to auto reload it, and I guess if you want to get
at first term, it's probably some outside of this room, so let's look at this CPU cache architecture
a bit more in detail, so like when you look at a very simple 2 core machine, you will find
that each core has its dedicated cache in level 1 and level 2, and then the last level cache
is typically shared, so you might have very beefy instances where it's not shared across all
cores with different sockets of CPU, but that is really typical in the kind of consume CPUs,
and also in the architecture that we mostly work with, or I mostly work with a cache line would be
64 bytes long, so I guess no matter what you read one byte, you read at least the 64
of the cache line, so that's the minimum unit, and so the way I guess the CPU operates on those
cache, the CPU tries to figure out what you're up to, and tries to pre-fetch the data, so it's
ready in the cache, so that it doesn't have to go through this, like long cycle of 100 nanoseconds
to get it from memory, and so in order for your code to kind of help the CPU, I guess CPUs are
optimized for this locality, so it's either the temporal locality, you access a variable now,
it's very likely you're going to come back to this variable, and add another one to it, or add a
like, yeah, store some intermediate results and access them very soon after, but then it's also
very likely when you read, I guess in a memory it offset zero, you likely go through that array
and go to the next element or with an offset of 10 to the one after, so basically like as long as
you allow your code to kind of move in these ways, I guess you're going to help the CPU to kind of
predict and allow the CPU to pre-fetch the memory, which will make it easier to not have to
have that latency penalties, yeah, at the time when you want to access memory, so this is obviously
very important for your data structures, I guess we sort of have kind of example, like if you have
either linked list or a tree with a lot of pointers that are very randomly jumping memory space,
then you will face this penalty heavily, because obviously there's no way for the CPU to predict
where the layout of your tree, and therefore you need to kind of think a bit harder about how
you can organize this, and like I guess one very common example where I face that a bit, it's like
I guess go maps when you iterate over them, they come back very randomly and so it might be really
worth I guess considering to sort them, if you have indexes for example coming out of a map,
like I guess another very typical I guess go example is this kind of, I don't know, you treat
a struct a bit like, I don't know, object oriented, so you have, in this example I have a
person database, you might have like millions of persons in your database, and obviously if you're
application and your access pattern is only ever one person, then this kind of array slice of
structs, I guess a person each is ideal, because obviously you only operate on one person,
it's where we local, but if your database is more kind of comparing names with each other, and
I guess never really reading the whole person, it's a lot better to actually design a struct
with a lot of arrays in there, so the data is tightly together, I guess this, obviously it has
a lot to do with a cash line length, I guess I think I had a from in 64 or in 64, but it's
we have the 8 bytes, and then obviously the cash line has 56 bytes, you lose, so if you read through
the, I guess, slice struct, you have a lot of overhead and waste a lot of memory and with off your,
when you when you can run that application, like something CPUs have to do as well,
is they need to kind of understand where your code goes, so when you have a branch, like an if
condition, I guess it is something where basically the CPU wants to understand which branch you're
going to take next, and in order to kind of understand how that works, I'm going to repeat,
I guess some of a very kind of old CPU design, but it's pretty much unchanged with a lot more extra
complexities, but what CPUs do, they do pipelining, and the reason for that is, there obviously
have a lot of different circuits that do different things, and you want to make best use of them,
and I guess what you also need to think about, one instruction is an obron in one cycle, so you run
part of an instruction in one cycle, and I guess to order or like to to make best use of your circuits,
that you have in hardware, you do some kind of pipelining, I guess, it's a bit like a car manufacturing
assembly lines, so you basically have like this pattern where you, so an instruction first step
is usually like fetching the instruction, obviously you have the circuit for it, and in cycle one,
I guess you use it here for the first instruction, and then in cycle two, the first instruction
obviously goes into the next stage, which is the instruction decoding, and then if you also want to
use your circuit for fetching, you can do that with the next instruction, and basically like this
gives this kind of pipelining, and rather than having five cycles per instruction, you can kind of
do four instructions in eight cycles, seven cycles, and when you now look at more modern CPUs,
they have more like a stage depth of like I think 10 to 20, so obviously this becomes a lot
longer, and also modern CPUs are super scalears, so like they would have multiple instruction
fetch circuits, so they could fetch for at the time or six, and so you can see how this kind of
gets a lot more complex to build up that pipeline and start the pipeline, and now when you
think about a branch, obviously like I tried to kind of annotate the same graph here,
so obviously if this would be your kind of if condition, then obviously you like by that point
where you want to start the next instruction, you actually don't know that I would come
off the if condition yet, and so you need to know kind of what your best guess is what your most
likely outcome that is, and so I guess in this case the CPU was predicting the true branch
to be the one that that is the likelyest outcome, and therefore started running it before even
knowing if it acts as really true, and then I guess in the best case somewhere here, it turns out
it true, it's true, and so the CPU kind of won and was able through the branch prediction to save some
time and have more efficiency, I guess at worst it needs to basically stop and kind of go back
replant the work and start the pipeline again, in order to I guess continue at the force
side of things, so that more than CPUs can get quite complex in how they do this prediction,
so I guess most of the time there is like a similar kind of structure of level one level two,
but it's still branches that they've taken, so obviously like you might have code that branches
quite a lot, and so you add a lot of pressure to that, and so you might forget this decisions,
therefore like this if you were not able to kind of get this prediction right or wrong,
I'm having a kind of simple go code as well, and by the way all my examples they should have a link
in the PDF and you can run them yourself and maybe figure out that the benchmark showed that as well,
so in this case we have an input of int and we want to decide if the negative of positive
and count up how many positives we've seen, how many negatives we've seen, so you can see the
code is obviously very simple and straightforward, and depending on your input, your input could
be very kind of ordered, so you might just have all the minuses first and then at some point,
your kind of number switch from minus one to one, or whatever the kind of bit this way of jumps,
you might have a branch mistake, but everything else is just straight pipeline being very
tied and a lot of instructions around, if you don't have random numbers, obviously you
I guess at worst will face like 50% of branch misses because it could happen for any of the
the conditions that I guess the CPU made the wrong choice, I guess when we're creating that example,
I actually spend a bit of time looking at the assembly because sometimes the compiler does
small things, I think the go compiler is maybe a bit less liable to do this, but if you want to
figure out if there's a branch, it's the easiest to look into the assembly and see the
kind of instructions that it generates, and so if you want now want to avoid those branch misses,
I guess the main two ways are either making the data predictable, so we have very good prediction
or getting rid of the branch encode, so in this case, because it is a very simple example,
I guess somewhat straightforward to think of an solution that will basically like do with the other
metrics, the same thing that the branch would achieve, so in this case we do some shifting of the
negative bits, and if the negative bit is obviously one, the negative bit is one, when it's
a negative number, so we add that to the negative count, and if not, then we added to the positive,
so we kind of swapped our branching for a bit more algorithmistics, and therefore I guess the code
can run somewhat straightforward. Also, I think there's been a lot of research, I went researching that
at the talk, I had to really stop myself a lot to not read this paper, about whatever neural
network for our prediction, and so I think it's a very interesting thing to dive a bit more into,
but modern like Ryzen CPUs for example, they use a second stage where they have a neural network
that I think a lot of that is not very open, but people kind of were able to prove from looking
running code on those CPUs, so obviously now we come to the more what I wanted to do in this talk,
so how can I actually use that, and measure that proof that this is actually what happens,
and so CPUs have ways to tell you, so there's a performance monitoring unit that has counters,
and you are able to read those out, so very typical counters are how many cycles are run,
how many instructions have been run, then there's a really detailed information about the cache
misses and hits, do you read or write from cache, and the branching has, as well,
like it counts the branches, it counts the branch misses, and it always is a bit CPU vendor,
depending when you want to go more into customer events, so you can give it a hex code,
and you can basically find in the manual of your CPU vendor what you use,
like obviously one thing to do that is just get the counter for your test, and you have an idea,
I guess how it performs to maybe another test case or a benchmark where they code change,
but it's also possible to profile and actually get the instruction that kind of
was very close to that point branch miss happened, that can be some timing issues,
so it might be that the instruction that that shows up there is actually a bit after when it
really happened, it's just CPUs are not getting that timing right, especially the more consumer ones,
and there's also methods to kind of reduce that in accuracy, but yeah it was really very CPU
dependency, you need to check kind of, so don't be surprised when an instruction that
that is seemingly not related as some high counters, you basically just need to look very close to
when the execution apps are there. I guess probably the biggest problem around PMUs is
for virtual machines, it's kind of tricky to emulate them, because I guess they are in hardware, and if you're
having very small non-dediated course in your VMs, it is kind of impossible to
create that data in the kind of hypervisor level, so in Grafana we kind of run on the big cloud providers,
and the bigger the instances, the more likely you get those PMUs, in GCP, you need to see
set a special flag, and I found we run quite a lot of workloads on ARM, and they seem to have
like even the smaller instances have pretty good PMU pass through, these are links,
so you can kind of read which instance types are kind of providing that data for you.
So I guess one of the biggest problems when I'm doing benchmark, the benchmark loop, changing
code, run benchmark, compared to results, my name files really badly, and I lose all the code all
the time and to get stash and whatever, and so I kind of lost November, I think I was fed up,
and I wrote a little too much basic stores to benchmark results while I run, and some kind of
gets committed to code together, and as I always wanted to kind of go a bit more into those
PMUs and kind of actually like basically measure the benchmark in understand better,
why something is better or not, and if my assumptions are right, I used the opportunity to just
submit this talk, and then for the typical way for me to get something done is to submit a talk,
and then I forced myself to kind of implement this. So I basically wrote a little wrapper around
go tests, and the Perth tool on Linux, which is able to get the information out of the PMUs
of your CPU, present them, and it also fixes that problem of storing the benchmark together with
the code changes and what I've run. So I guess one additional problem for me, so you can see
the MacBook, so there's no Perth available, I think there's some Mac based solution which
fits a lot of XML, which wasn't really easy to kind of make sense of, and so when I tried to do
this before, I always had to compile and ship into Linux instance, and so I also integrated the way to
do an SSH remote run off of benchmark, and like one of the other goals was I want to use PProph to
look at the profiles that Perth generates. Yeah, I can navigate Perth's report, but like I'm
definitely a less proficient as in looking at Flamerafs and using PProph for that.
And so yeah, you will find it on GitHub, the link should be on the on the speak information.
I mostly have two modes, the test mode, which runs, there's a go test with a wrapper around it
to collect those metrics, and the other one is a touch mode where you can run a port,
given you are able to create a privilege port, you basically are able to run that in your Kubernetes
cluster. You then still need to have access to the PMU from your cloud provider that we
end problem now mentioned, but yeah, no, that's basically like a pretty useful, I guess, to look
in how things are running in production. And so I know attempting a demo, so think is crossed.
So I kind of know that type of movement.
So I kind of know the typing and the sentence is not super easy, so I kind of
automate it a little bit, and so I'm going to run the Perhance prediction example from
earlier, and I guess as a start let's maybe look quickly, remember the kind of implementation,
so we had that example with negative numbers counting up, with here with the branch first,
and then in varying two, it is the branchless approach with the additional arrow matrix.
So now if I want to run a benchmark I guess this is kind of roughly how I run benchmarks
and go, I have four benchmarks, first of branch version with predictable data and with random
data and then the branchless with those two data variants, so I guess I run it here on my
MacBook for now, so you can see or not see, you can see the four benchmarks and I guess the
fastest one is the one with a branch and with predictable data. Then in the second line you
can see the one with random data, so which is like slower, but maybe not as slow as you would
expect, so this has to do with arm and the the the less deep kind of complexity of the CPU and
therefore less stages in the pipeline and so the cost is not as high, but it is still a penalty
of I guess around 50% extra, and then we have the branchless version which is not as good as the
branch version, but it is a very static I guess for both of the random and the predictable data
can put, and so if I now want to run the same thing with that perf go tool, you basically
just need to run perf in front of go, I try to keep the variables everything kind of gets past through
and this runs on my machine and basically does just the same thing, what do you get from here?
We are can be able to list all the runs you did and get the kibbit hash and it also saves the
test binary, if you ever wanted to run it again, you could really run it fairly easily.
So now in order to do kind of the first assessment of those metrics from the CPU,
perf has the static command and that gives you the counters for the whole of the process you run
or for everything running on the note, depending on the flux you give it. In this case we just run
this kind of the worst case, the one with branch and random data and we run it with stat,
and so you can't configure it or I'm on a MacBook there's no perf basically. So my desktop computer
at home is hopefully online, so I kind of added remote holes and that could be just any
SSH like target as long as it's kind of connectable, it basically will do exactly the same
it will compile it for the correct target, so we are connected, kind of figures out yeah this is Linux
in D64 and basically send the right binary rapid with perf, run the perf command and that's
kind of the perf command output. So you can kind of see the metrics it shows by default I guess
pretty wants to start with, so I'm not super familiar with any more beyond this and I definitely
think you find quite a lot of stack overflow information or even the agents know quite a lot
about how to interpret it but also perf gives you an indication of the color, so you can see that
the front end of the CPU I guess is that bit with the instruction fetch instruction decode and you
can see that's kind of where the stalls happen but what you also see is branch with the 14% and that's
kind of the highest I could generate a benchmark for, so definitely like naively you would expect
50% as the worst you would get, but there's a lot of smartness going on that you can't get that far,
so typically you would see more like in the low zero point branch misses whenever I profile
something running so this is really obviously the absolute worst case where we don't nothing else
than just this loop and so obviously this is the obvious next thing to look into from this output
and now you can basically like profile to get the functions the line numbers I guess everything
that is related so what I changed here is I did profile and I added the event type branch misses
so you can collect multiple events but there are hardware limitations and then purple kind of
switch out the events and as you run it typically I think there's like six in the CPU six event
types that you can collect and so yeah it can only obviously do six at a time if you give it more
than six but in this case I also decided to run the whole benchmark suite so I'm no longer filtering
on this one benchmark just so you can see the comparison in the profile so I run the the same
command just I guess been profile and you can see also a bit how this one takes a lot longer
on the horizon CPU because it's an AMD 64 versus the arm and now we should have the profile already
so it basically passes the profile could generate the p-prof and I need to see
I'm going
so I guess this is the p-prof that I don't know what's going on
it's easy to kind of go so you can kind of see the unit we collect should be branch misses I
can't really read it but and then you can see that 100% should be close to 100% maybe not
but a very huge part goes to this bent smart branch with random and if you would want to
look into the source curve you can kind of see this actually muted here I guess in those lines you
get the instructions I guess although the goodies you get from p-prof you haven't and or you can
upload them to the same tools yeah I don't know if you can see the better of benchmark time
I think time is over one minute and you know I think maybe done a quick jump back to the
and just showing that all the mode quickly so with attach this is a Kubernetes cluster that I'm
hopefully also connected to so you can select the port can tell it collect me branch misses for this port
and it kind of does the same obviously it doesn't have to compile a test the port is already running
it finds out the PIDs attached just now to the perfect command collect the profile runs it back
gets steals the binary from the remote so it it also makes a lot of this manual work that I had before
and yeah I guess you can take a look it's not a bit take a bit longer depending on internet speed but
it basically runs for 10 seconds collect the branch misses and and for me if you would then see
depending on what you're running maybe a query iterators have a lot of branch misses and yeah
I guess you can then decide if this is both optimizing or not okay
while we're waiting across
and wow not only live them away but also trusting the first them why far to work amazing