You may well have used the P prof. Tool to profile the amount of memory
your program is using but it can also be used to profile the amount of
CPU to find out which of the slowest piles, what you should be going about.
Optimizing use it with the runtime pprof package and there are a couple of
functions to start CPU profiling and then stop it and save out a
file for use with people off the illustrate. How this works. I have
implemented an lru least recently used cash rather
badly in go.
And I'm going to use it and use the profiler to actually
figure out where why it's slow, why I'm about programmer in this case. So let's just
take a look at the package is the lru package here.
And the idea is it creates some sort of cash of items. It has a
certain size this capacity, that's the number of items it can store
and the implementation is a map mapping strings to
things. And those things are Keys, the values that are
stored along with them.
And the last time they were accessed and we need the last time to do the lru thing. Once it
reaches capacity, we need to start a victim things. When you put something
in the cache, if it's full, if it's at capacity, then you have to make
space and whatever happens. You insert something into the cache.
When you retrieve something that's fairly simple. You just look up the item in the
cache set the time to now because it's been used. So you want to bump it up, to be
something that shouldn't be evicted and then return the actual item. And
if it's not there,
It's nil and the making space function here.
What it does is it iterates through the things that are in the cash, looks for the oldest item
to remove and then we'll actually remove it. So this is what it does. Here it goes.
It says are you older than the oldest thing I've seen. If so
then you'll keep that key around and eventually will delete it using the delete
key word from from the map. So,
fairly simple. Allow you implementation and I've got a small program and what it
As it reads in something on standard. In actually words
and chops off the first letter of each word, just takes the next
three letters. So I just generate some data here. So the cash gets exercised
and I'm actually going to feed it. The entirety of War and Peace word by word
and we're going to take all those words and cash them. And I've
set the cache size to be up to a maximum of a thousand of these word
fragments and I'll store the last word I saw that, that
particular fragment in it this.
Be any realistic data using lru cache. This is just some handy textual data that I
have lying around.
So in order to profile, this I'm going to use pprof
here and I'm going to Output a file called Liu test or CPU profile
and to start profiling. As soon as the program begins and when it terminates, stop it, which will write the
file out before it terminates. So this will give me a complete view of what happened
inside the cache. So let's just make sure this
builds
And that's great. And I've got War and Peace here, which I think is
there you go over half a million words so we can feed that in and I'll just take
that and feed it into lru. Test as always going to be going
through, filling up this cash with a maximum of a thousand items
so there it's run. So you can see that, you know, there were
24,000 mrs. Or 24,000 times when the thing wasn't already in
cash and so we had to obviously go ahead and evict something and I can
then
Is the profiler to look at the performance of that. Now, in this
case there's not very rarely misses for the total number of items. And so it's probably the
case that it's not that interesting. I'm going to try this. Another thing I can use which is the
dictionary.
And I can pie that in.
And now I've got a large number of Misses here. So either of these, I think we will be good
techniques. We can use files, we can use to look at it. So let's look at the profile file. It should be here.
There it is. And I can feed that into the P prof. Tool like this.
So it's just we just saying this people off to on the program is a CPU
profile and I can take a look at where the time went. And what we
find is very quickly that these two things at the top here, if you
notice 75% of the time,
Being spent in this runtime map. It's a next is iterating a map. So
somewhere in my code there's a map iteration that's happening and in fact you can kind of see
that make space, whatever that function was that was where it seems to be happening.
Now it looks like it's in lru one so I can
do a couple of things. One is I can use list and I can go and I can just list
out here and I'm going to see that. Here's that call. You see 200 milliseconds
on that call to make space and of that, a hundred 90
milliseconds here. So
This is this, this is where the problem is is the iteration of the sea data which
if you recall is the map, which we're using to
store the cash in with the times. That's what happens is when you try and
evict something, it's going to run through this make space function as to
iterate. Everything's okay. Measures iterating, iterating, iterating over that map. Which is a bit
silly. And that's where the time has gone. Another way to view. This, of course, would be the
webview. So if I go in and do web and I'm going to get a view like
this, and you can quickly see
That here's the main program. It takes two hundred twenty milliseconds
to run and of that, tune 20 milliseconds, 200, milliseconds,
almost, all of it was in the put function. So
adding something to the cash and of that, almost all of it was in make
space and almost all of that was in that map. Iteration. So, quite clearly,
this is the branch that we need to optimize to make this lru cache
more efficient. As a what I'm going to do is I'm going to go ahead and do that and we'll
look at the
Affect this house. So obviously iterating, a map like that every time you want to do
insert something into the cache when it was full, was a bad idea because it would create,
you know, a thousand iterations or depending on the map size, it could have been even larger.
What we need is a different kind of data structure. And what I've done here is I've changed the way things are
working to use a list and then using a list moved
front operate operation to keep the least recently used element. So the
idea is I've got rid of time completely and within my cash structure now.
I've got data right here, it is, that's the map I had before, but it's pointing to
a list element, which is something that comes from container list. And I've also got a
list pointing to the same elements. So I'm keeping two places pointing to the
same data. And so now when I get something,
what I do is, I move the item that we're getting to
the front of the list, we find it by looking in the map. So we find
the list element and then we say to the list, okay, move that to the front. That's what we get. The least
recently used from
and then we return the actual item that's in there. This is the syntax for doing that.
So the although the list contains an interface and empty interface,
we use this type of session here to say, it's actually contains a pointer to an
item when you're putting something. If we're at capacity then we just
delete whatever as at the back. So the thing at the back will be the least recently used on the
list and we remove it from the actual list of data.
And then we push on the new thing on the front because that's obviously the most recently used. So this
is a
Much more efficient way of doing this, because it doesn't require any iteration where there are two
different data structures. There's no change to the original program. So
let's go build that and let's just put through
the same thing again. Okay. There we go. And it seemed like it was a bit snappier
and stats will have the same profile there. So let's run to profile tool
and now we've got a totally different view of things. Now all the time that's being spent, first of all, it only took 10
milliseconds, not a hundreds and all of the time is being spent doing
This thing sis calling here. So let's just bring up the webview. It's
got a hell of a lot simpler now. And you can see that in fact,
all of the time is being spent actually reading the file. So, if I was going to spend
any time on this, it would be bulk reading perhaps and then doing the
splitting of lines myself. But right now, this program is pretty fast
compared to where it was before and you can continue down this. We could then start looking at
different operations in here of your programs, try and optimize it even
further. But for this,
Casual think it's pretty efficient for what it is, for the moment.