[Autogenerated] here's a breakdown of what's going on inside the processor.
The differences we've seen we've seen earlier with the metric
example has to do with something called the cash.
And the basic idea is that memory RAM physical memory
is much slower than processors.
If we connect a processor directly to RAM, it will be mostly stalled.
Waiting for memory to actually acknowledge and get data or set data.
So instead we have this idea of caches.
Every processor today is built with caches within the hydro itself.
So here's the socket and the second example and we have a
bunch of course as in the previous example we have let's say
we have four cores on this system.
Now every core has these two hardware threads which are the ones
that are the smallest independent pieces that can run code and
there are cash is the first level of cash is known as level one
which is the smallest cash.
But but the fastest and we have two types of cash is here.
One of them is called the D cash for data and the other one
is called an eye cash for instructions.
So instructions are also cash as needed.
Because instructions also initially they reside in memory.
So the fastest accesses to this cash.
But the cash is relatively small and we'll see the numbers are very soon.
The second level of cash is bigger but it is also slower and you can see here's
something interesting that the level two cache is actually being shared by the
core by the two hardware threads which are part of the same core and this is
why they are not totally independent,
which means that if they're working on different data level
two cache could be thrashed and that would require reloading
the cash with new data from memory.
And memory is slow.
And this is exactly the problem that we've seen in the example
with the matrices When we're doing row major,
we're actually walking through memory in a contagious fashion.
So it goes to the next integer or value in line and it's likely for
these values to be in the cash and I'll talk about that in a moment
in the next slide in some greater detail.
Finally there is a level three cache which is the biggest in terms of
size but it is shared with the entire socket with all the how do the
threads and coarse part of the same socket.
And this is the thing that is connected to main memory.
So you might be wondering, what are the sizes are we talking about here?
Really?
What are the sizes of the caches compared to main memory?
We know that main memory at least today is in the gigabytes?
We have 64 gigabytes, 128 gigabytes.
And big service might even have several terabytes of RAM.
What's the sizes of these caches really?
And so the caches are fairly small.
Here are some examples Level one could be 64 kilobytes of memory.
I mean kilobytes.
What is that really?
It's almost nothing.
Level two is also not much bigger.
512 k bytes this is a far cry from the main memory sizes which
is gigabytes or sometimes terabytes in size.
Level three is bigger with 16 megabytes still very
small compared to the actual RAM.
And this is why usage of cash in practice in an
efficient way is super important.
And this is why some cases where computer science says that
is exactly the same thing as the metric example is not
really the same thing in practice,
even though we're apparently doing the same work,
that's not really the case.
And when we actually work with these caches which is
something CPU does all the time.
They're not working on a single by entity.
When we try to read an integer, it doesn't mean you read just four bytes,
it always works in a chunk called cache lines and the normal size of a
cache line or at least the most common one is 64 bytes,
which means that every time you read the bite,
you actually read 64 bytes that are just uh 64 63
more bites after that single bite,
which means that if you next need to read the next bite,
there's no need to go to memory,
you can just grab a bit off the cash and this is why caches are so important
because they're so fast and this is exactly the reason we got different results
with the matrix example because when we had to move into different locations in
memory that were very far from one another,
when the code was doing a column major work,
then the trash,
the cash had to be trashed and removed and new items had to
be pulled out from RAM and RAM is slow.
So essentially when you're accessing memory continuously
you're going to get the fastest performance.
And essentially it means that arrays are usually the fastest to work
with because the rays are contagious in memory.
And in general if you think about writing programs,
sometimes you need to select a data structure to work with.
For example,
if you need to search fast into something you might
be thinking if I use in the rain, that's an O.
N complexity you have to perhaps move over every item your until you
find what you're looking for or fail finding it.
Maybe you should be using something else like a map that is built
like maybe a binary search tree which provides a faster search at
least in theory being based on log two of n.
So in the general case, yes,
that seems to be faster but if the number of elements are not too great in
fact and the way would be actually faster because of the contagious memory
there and the notes in a binary tree could be spread around in memory
which would cause cache thrashing, which is not ideal.
And and so the conclusion from that, if you're writing performance,
critical application is is not to to count on your
intuition or in computer science all the time,
you always have to use the number number one rule in performance,
which is measure, never assume anything,
just measure and see what works best.