g'day Oh welcome to another video we're
going to be talking about x64 classes
today for a few videos these videos are
going to be about performance
programming in x86 and x64 assembly
language mostly but I think the
information is useful no matter what
language you program in so we're going
to be using C++ mostly for today but
eventually we will get into assembly
it'll just take a few videos I think
this information is going to be helpful
to people that program in higher-level
languages too but I don't know so cool
group okay so the topics for today first
of all I'm going to go through what
Akash is then we're going to talk about
the basic architecture of a computer
then a bit of basic cache terminology
that then we'll have a look at x64
caches in particular and then a bit of a
demonstration of something that I found
really counterintuitive when I first saw
it it's really weird it's really weird
so I'll have a look at a demonstration
at the end in C++ okay so what is it
cache first of all a cache is a small
area of on tip memory on the CPU itself
and it's used whenever we make a request
to or from system memory so Ram what
happens when you request a variable from
Ram the CPU first checks to see if the
data is actually in its cache and if the
data is in the cache then the CPU will
just use that version because reading
and writing to cache is much faster if
the data is not in cache then it'll go
all the way to D Ram it will bring the
data into the CPU from memory and it'll
store it in cache and then next time
when you want the same data it can just
use the cached version yeah so that's
pretty much what we're talking about
just a small area of on tip memory it's
used to speed up read and write accesses
and avoid reading from system memory
I guess so a little bit about computer
architecture this will start to give us
an idea of why caches are so fast
so the CPU up here has the cache on tip
it's actually part of the silicon and
the CPU is connected to the memory
controller which is also connected to
the PCIe or PCI Express which is your
graphics card and it's also connected to
system memory
here so whenever you need to get a
variable if it's not in cash then you
can see that it's there's a long way to
go I mean just distance-wise in the
words of the computer there's a long way
to go your request has to go through the
memory controller off to system ram the
ram chips have to say yep there's the
data mate they send it back to the
memory controller and send it back to
the cpu so it takes a long time that all
takes a very very long time and down
here we have even slower types of memory
USB your keyboard and mouse your IDE
drives santur drives parallel ports
they're all really really slow because
not only have they got to go through the
Northbridge the memory controller but
i've also got to go through the i/o
controller
well the Southbridge okay but that's not
the only reason why caches are faster
another reason why caches are fast is
because they are fundamentally a
different mechanism of sawing
information so D Ram which is system
memory I don't know I've got plus posea
memory plus plus zero D Ram is
constructed from a few transistors maybe
a couple of transistors and a capacitor
and the capacitor fills up with charge
and empties its charge whenever the
capacitor is full it's read as a1 and
whenever the capacitor is empty it's
read as a0 but when you want to read
from a DRAM cell the capacitor has to
empty its charge and that takes time so
SRAM works differently SRAM I think it's
I think it's six I think it's six
transistors in a fascinating
configuration but the six transistors
are connected together such that if you
want to read a 1 or a 0 the SRAM cell
has it immediately it doesn't have to
empty any capacitors or anything like
that you can just read and write the
value immediately SRAM has like 6
transistors per bit so it's much more
expensive than DRAM which is just a
couple of transistors and a capacitor
yes so Cash's use SRAM which is really
really fast but expensive and main
memory is slower DRAM but it's less
expensive okay a little bit of
terminology we talk about cache hits a
cache hit is if we request data from RAM
and the CPU Texas cache and the data is
already in cast that's what we want this
is what we want with one cache hits a
cache miss is what we don't want a cache
miss is when we request a variable from
Ram the CPU Texas cache and it finds out
that the variable is not cast and it has
to go all the way to RAM and get the
variable from then a data cache is cache
that's used for storing data or your
variables your arrays and all that sort
of stuff and instruction cache is the
cache that's used for storing executable
instructions a unified cache is the
cache that can be used for instructions
and/or data a clock cycle is the
smallest time measurement available to
the CPU so if you've got if you've got a
CPU that runs at 1 gigahertz then
there's a clock in the CPU that's
ticking by 1 billion times a second and
there is no smaller amount of time that
exists for the CPU that's the smallest
possible amount of time for the CPU so
you've got a 3 gigahertz CPU that clock
ticks by 3 billion times per second nice
and easy but latency is often measured
in clock cycles the latency of an
activity for the CPU is the number of
clock cycles that it takes to perform
that activity yeah so really what we
want to do when we're performance
programming is we want to reduce the
number of clock cycles that our code
takes to run that's what we're trying to
do
all right a little bit about x86 and x64
caches in particular and they call l1 l2
and l3 the L stands for level and the
smaller is better
so l1 is the smallest but the fastest
cache many x86 x64 CPUs have data and
instruction l ones separately and I want
to also mention that if you've got a
multi-core CPU the L ones are per course
so each core has its own l1 and they've
also got their own l2 l2 is medium-sized
and medium speed and l3 which is usually
the largest casts in an x64 machine l3
is the largest cast but it's also the
slowest and another thing about l3 is
that it's shared amongst the cause so
you only get one l3 whereas if you get a
quad core you'll get 4 L ones white
actually because you get instruction and
data and you also get 4 l 2 s ok so a
lot of budget CPUs don't actually have
an L 3 they stopped at l2 but yeah a lot
of this stuff is Hardware specific and
there's ways to figure out exactly what
sort of cache your CPU has and we might
look at that in a future video but l1 l2
and l3
okay so here's some real cash numbers
from hardware that's available at the
moment we've got Intel i7 6950 X's is a
crazy CPU crazy price too huge
instruction cache 320 kilobytes huge
data cache 320 kilobytes the l2 is 2 and
a half Megan the l3 is 20 Meg's
something interesting that you'll notice
here is just how small caches are so if
you think about the system RAM of a
computer it could easily be 8 gigabytes
of DRAM in your system memory the cache
is 320 kilobytes on a $2,000 CPU so
caches are tiny they're just tiny tiny
things this is interesting too so a few
months ago probably getting on to a year
now
AMD started releasing Rises these Rison
chips and they're really taking a market
share out of Intel for the first time
and I think a really long time I mean
Intel has really dominated the market
for a really long time but these rising
chips are performing really really well
and you often hear people saying that
it's because of the core count and they
certainly do have a higher core count
but I think it's more than that I think
you can also look at these caches
because for the price these caches are
enormous this is a risin 718 hundred x
it's not a teep tip by any chance that's
cheaper than the i7 here though this l1
instruction cache 512 K that's huge data
cache again 256 K is a huge l1 data
cache so I think one of the reasons why
these rising chips are doing so well is
not only their core count but also
they've got the cast to back these calls
up amazing it'll be interesting to see
what happens if you're watching this in
the future you probably know how this
all turns out yeah I'd like to see
Intel's response to this they got coffee
late coming out soon we'll see what they
do with coffee Lake now one of the
interesting things that Intel used to do
this was back in the Broadwell days so
going back maybe three or four
generations they had these Broadwell
chips and the broadband chips had an elf
forecast which was quite cool it wasn't
Sam it wasn't
SRAM though it was edy Ram what they
call the EDR and
it was really just embedded dynamic Ram
so it was that capacitor Ram yeah so was
it was slower than SRAM caches yeah l1
l2 and l3 but it was on tip so it was
faster than going out to memory they
stopped doing it after Broadwell so I
think a lot of people were confused and
a bit annoyed that they stopped doing it
because apparently this l4 added a lot
to their gaming experience
I don't have a game a lot but now a lot
of gamers we're annoyed that they
reduced this so got rid of itself for so
we'll see what they do in the future in
response to Rison it should be
interesting Intel there you go another
few chips here the yam rise in five to
see even even the rise in five as it has
a pretty decent sized cache and pretty
decent cast they're all good ships there
are all good ships and the prices are an
AUD from you Mart as of yesterday
all right here's a bit of a memory speed
comparison so this table shows some
timings of latency register access is
about one clock cycle you can't really
access any memory faster than registers
registers they even faster than cache l1
cache hit is going to cost about three
clock cycles l2 cache it's about 15
clock cycles three cache about 60 clock
cycles if we miss all of the caches then
we're going to get all the way to main
memory we'll talk about how data gets
stored in the l1 then L 2 then l3 at a
different point but if we miss all of
these caches if the done is not in the
cache that we want we've got to go all
the way to main memory and that's going
to cost something like 150 upwards
cycles so main memory very very slow and
then hard drives if we haven't got to
get something from the hard drive all we
might as well just go to sleep for a
million years now so that will give you
a bit of an idea there of the speeds of
memory and now we're going to talk about
matrix multiplication so I wanted to
show an example of something that I
found really counterintuitive and we'll
jump over to C++ and we'll see you there
coffee's empty I'm going to get our way
back here in visual studio for a bit of
a demonstration this is weird this is so
so weird
just a little matrix product
demonstration so this is the frame just
here we set up two matrices with a
thousand by thousand each called a and B
and what we're going to do is multiply
them and store the product in the matrix
C it's all really testy and demo E and
there's no text or anything for if the
matrices are square or even the same
size so yeah it's at the demo now you
have to be more careful about that sort
of thing if you were coding this for
real but the a and B matrices are just
set up with random values to see R and
then we run through ten times
multiplying the a and B and storing that
product in C this is really the crux of
what we're talking about today there's
mole operation just here and we time
that each time using the clock method
from seat on and then just print out
some results here at the end so
basically we're just using the n cubed
nested for loop version of the matrix
pipe if you don't have a look about
matrix products on Wikipedia if you
familiar with them it's probably a good
idea but anyway let's just run this and
we'll see how quickly it goes I have
slowly as a case may be
I already know how long it takes we're
going to lie takes a very long time now
it's boring so let's not watch it let's
actually come over here to the matrix
class and have a bit of a talk about
that now we'll get back to that time in
a minute it's still on that in the
background so the matrix class is just a
bunch of doubles really with the
dimension just there and so we set up
dimension by dimension doubles and just
fill it up with random values delete
just gets rid of that data array set
lets you set an element get lets you get
an element moles just moves one matrix
to another and mol it's really what
we're concerned with you how do we
perform the products you want to be able
to perform matrix product really really
quickly so that's really what we're
talking about okay here's this set just
here the set method pretty boring here's
the get method just here the mold
methods is copies the data from one
matrix to another but the male method so
what we're doing here in the moment that
is literally the three nested for-loops
we count through the rows in one follow
the columns in another for loop and for
each of those we're computing the dot
product so this is literally just
textbook naive matrix multiplication now
let's have a bit of a look at these
times here we go look at this fourteen
point one five eight seconds thirteen
point eight oh seven seconds so it's
taken a long time a long time to compute
those products so let's just hit stop so
we've got a bit of an idea there if I
took like fourteen points what do we say
eight oh nine or something like that
I'll punch that into my calculator for
later use but now the trick so this I
think this is just bizarre this is just
bizarre but it's very very cool so what
we're going to do is actually define
this matrix twice we're going to define
an in ran twice in row major form and in
column major form so it's going to take
up twice the ran but silence to see what
happens we go cord got a col I'll call
this one got a row okay so data Col is
going to be storing it in a convenient
way to read the columns when they're
incrementing data row is going to be in
a convenient way to read them when the
data is
being read in contiguous rows I hope
that makes a bit of sense but we're
basically just doubling our RAM
footprint what is this going to do to
our performance or I didn't delete we
better delete both of them so please go
and delete coal we have to make a few
changes I'm sorry I'm going to make a
mistake actually try to record this a
minute ago it didn't work out it did not
work out so that's about all the times
we have to make there let's come over
here to the matrix of CBP file okay when
we set we want to set twice you want to
set once in column major form and you
want to set once in row major form so
this row major form just here is
actually the column major form but it's
rotated 90 degrees now that's what we're
doing we're storing the matrix like this
and then the sided summary and RAM we're
storing it on its side as well seems
crazy it seems crazy but I tell you what
it's not cool actually we're going to
write two of these get methods so we'll
just leave that for the time being and
we'll come down to moles okay we've got
to move twice as much data as well so
all of these operations will be much
slower now because we're using twice as
much RAM so the the marv and the set and
get they're going to be twice as slow or
half to speed these other I like a but
forget we can I two of these so one of
them is going to read the data in the
column major form and the other one's
going to read the data in the row major
form so we're now going to have to get
methods
let's call it get cold forget
column-major
and get Monroe forget row major so
that's collimated Giselle and row major
is going to be it's not it's not super
important
all of this fiddly stuff not super
important it's not really the point of
the demo the point of the demo is is
it'd be ending so if you're not really
following us you know it's all good but
data Cole
there's going to be data row okay and
they're not defined so we'll put them in
our header say yes call and get wrong
and we'll say that okay now down here in
our matrix product instead of just
reading the same which was column major
we're going to do a column major red for
this one but this one is going to be a
row major reason okay so what have we
done here
well we burn called we got errors is
probably what we've done
yeah there we go but we've got errors
get is not a member of matrix a good
stuff in the main method yeah mains
winds and hot a deal like that good
normally when you read in row major form
it means that the row parameter comes
first I didn't bother to change the
orders around there I just changed the
order that I used them in the method
which is probably the confusing I might
have done it a different way but let's
give it a run and see what happens ah
look at that
okay so that's about two point four
eight one seconds about two and a half
seconds
mrs. punch that into the calculator this
is about six times faster than it was a
second ago
so we've taken up twice as much RAM and
in theory that would mean that we're
really looking at a much slower
algorithm but the timing says it all
we're not actually performing anywhere
near as many RAM reads this second
version although it takes twice as much
RAM is actually using the cache much
much better and that's where the
performance is coming from that's where
it's coming from I hope that was
interesting
have a bit of a think about why that
might have happened and we'll talk again
more about caches in the future get into
a bit more bit more of the details it's
interesting stuff and I tell you why I
like this is that's a good that's a good
trick right there that's I found that
fascinating it's a good trick everyone