Re: Memory fragmentation?

[email protected] wrote:
> 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.)  

I am using leak-gauge.pl (and previously the leak detector extension) 
because my father tried to make me understand leaks years ago, and that 
it was important to locate leaks because they hold a reference to memory 
that could otherwise be free'ed (which is probably the wrong word) up.

For extension developers, with little to no knowledge of C/C++ it is 
hard to understand what is going on, but David Baron made it clear (at 
least to me) that leaks are bad and that we need to check our code. 
Which I do on a regular basis, especially when I add new code.

Finding leaks in XPCOM components is a little harder, and all I can 
really do is look at other people's code to see what I am looking for.

I am not blaming anyone, but maybe MoCo could do more to make us 
extension developers understand what to do.  To me right now it is about 
removing observers on shutdown, that was step one, and null'ing the 
timer objects I'm using to prevent leaks, but that is about it.

> 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!

No, you made it amazingly simple to understand.  Thank you so much!

-- 
Michael Vincent van Rantwijk
- MultiZilla Project Team Lead
- XUL Boot Camp Staff member (ActiveState Training Partner)
- iPhone Application Developer