Re: Memory fragmentation?

On Nov 15, 12:17 am, "Michael Vincent van Rantwijk, MultiZilla"
<[email protected]> wrote:
> So what happen in current Mozilla builds when the 'lifetime' is over?
> Will this memory be available for re-allocation?  Will is be re-used, or
> not?  I guess not.  I don't think that it works like this, but I thought
> it was worth to give it a shot to learn/understand what is going on
> right now.
>

Micahel -

The 'lifetime' question is really a way to approach the problem and
how to think about how objects live and die in the code.  It relates
to how memory is allocated in the application, but only indirectly.

So to answer your question, memory that's freed no matter what the
lifetime _should_ be available for allocation later.  The problem that
we're running into is that lots of small objects with short lifetimes
are causing us to end up with holes that are too small to fit new
requests.

Here's a metaphor for you.  Imagine computer memory as a huge pile of
cartons that can contain eggs.  Your program is made up of eggs.  The
operating system only provides cartons.  Each carton can contain up to
12 eggs.  When you're running your program you're taking cartons off
the shelf and putting eggs in them.  Any time that you want to put an
egg into a carton you can either find an empty carton that you already
have or you can pull a carton off the shelf and put your eggs in the
new carton.  The trick is finding the space for a set of eggs.
Sometimes you don't have an empty carton or you have 100 eggs that
have to be spread out over a huge number of cartons, but you can't
find enough cartons in a row that are empty to hold the eggs.  So you
have to get cartons off the shelf to hold them.  What you end up with
is a huge number of cartons in front of you, some of which are full
but many are only half-full.  That's what memory fragmentation looks
like.

Just about every program on the planet suffers from this.

There's an additional rule that I should mention because it's
important to understand why people are reporting huge memory sizes
growing over time.  The only time that you are allowed to take a
carton and put it back on the shelf is when it 1. does not have any
eggs in it and 2. it was the last one that you took off the shelf.
Cartons have to go back on the shelf in order, in reverse of the order
that they came off the shelf!  Because of this you can actually have a
pile of cartons that are completely empty in front of you that can't
be returned to the shelf because there is a single carton with an egg
in it that you pulled down off the shelf after all those other
cartons.  That's a huge gap in memory.  Now, can you as a program put
eggs in those gaps?  Sure!  And I think that's the answer to your
question right there.  The gaps that we create in the cartons can be
filled with eggs, just as if we had pulled a new carton off the
shelf.  But if the gaps are too small to fit what we need to put in
them, we end up with wasted space: fragmentation.

Now, the final bit of this metaphor, and probably the most important
one.  When you look at your system tool and it tells you how much
memory a program is using it is _only counting cartons_.  Since the
operating system only hands out cartons it has no idea how many eggs
you have.  Which means that while you might have 100 eggs in cartons
to run your program, you might have them spread out over 20 cartons so
your program _looks_ like it's actually using 240 eggs!  (That's 12
eggs times 20 cartons.)  So your program looks twice as big as it
actually is.

When we talk about leaks, we're only talking about eggs.  Stuart's
most recent post says that we have very few leaks at this point.
Which means we can account for every egg that's in those cartons.  We
know where they belong, we know who owns them and we know that we're
going to pick them up out of the cartons at some point in the future.

Detecting a leak (finding all your eggs) is a very different activity
than understanding how those eggs are arranged in the cartons.  (I
won't talk about finding leaks here as it would stretch this metaphor
too far.)  Examining the problem of fragmentation means understanding
how often you're taking cartons off the shelf, how many eggs you're
usually putting in them and then how often there's a chance to put the
cartons back on the shelf and if you're able to do so.  Once you know
that you can start to move code around and change the way that eggs
are put into cartons.

There are a couple of tricks you can play.  Let's say that a piece of
code is always putting 1-2 eggs in and out of cartons over and over
again.  If you were just pulling a carton down for each of those
little allocations it would get pretty wasteful.  So instead what you
can do is pull down a few cartons off the shelf all at once and take
those small allocations and put them all in the same cartons (i.e. 2
eggs per allocation, 6 per carton.)  Once you're done you can take
those cartons and give them back and the waste is pretty small.

There's another trick that you can play and that's that you can make
an entirely different pile of cartons.  (Why isn't this done in the
usual case, you ask?  Because if we did this for every place we
allocated memory it would be exceedingly slow and we would be pushing
the fragmentation problem up into the operating system instead of
handling it in your program.  But that's a discussion for another
metaphor and another day.)  This is where the lifetime question comes
in.  If you're doing a lot of localized computation with lots of small
numbers of eggs and you know that those will be mixed with a lot of
long-lived objects that use a lot of eggs it makes sense to try and
put all the small groups of eggs with a short lifetime into a pile of
its own cartons while the long lived large numbers of eggs into
another one.  When you're done with the short lived group of eggs and
cartons, you just hand them all back.  And then those cartons aren't
counted anymore while the long-lived cartons are still around.

Anyway, the real take away here is that the operating system counts
cartons, the code counts eggs, leaks are how many eggs we lost track
of and that fragmented memory is just half-empty cartons.  And
examining how many eggs per carton we have is what Stuart and Vlad are
doing.

Hope this isn't too confusing!