This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Simple malloc benchtest.


On Mon, Dec 23, 2013 at 07:22:51PM +0530, Siddhesh Poyarekar wrote:
>    On 23-Dec-2013 7:02 pm, "OndÅej BÃlka" <[1]neleai@seznam.cz> wrote:
>    >
>    > On Mon, Dec 23, 2013 at 04:39:12PM +0530, Siddhesh Poyarekar wrote:
>    > > On Mon, Dec 23, 2013 at 10:50:34AM +0100, OndÅej BÃlka wrote:
>    > > > You cannot do that, you would repeat same mistake that plagued
>    allocator
>    > > > research in seventies, allocation patterns are simply different than
>    > > > simulations and all that you would get from that measurement is is
>    meaningles garbage,
>    > > > see following link:
>    > > >
>    > > >
>    [2]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.5185&rep=rep1&type=pdf
>    > >
>    > > I don't think the conclusions of that paper are valid because their
>    > > measurements are tweaked to give the most optimistic number possible.
>    > > They do pretend to use a more pessimistic measurement as well, but its
>    > > higher numbers are simply ignored in their conclusion, stating that
>    > > they're 'misleading'.
>    > >
>    > Please justify your opinion, a relevant metric was:
>    >
>    > "3. The maximum amount of memory used by the allocator
>    > relative to the amount of memory requested by the pro-
>    > gram at the point of maximal memory usage."
>    >
>    > If that metric is valid you have a severe problem with fragmentation on
>    > following program;
> 
>    I did not imply that measurement 3 is valid. I meant that it only pretends
>    to use measurement 3 but only uses 4. IMO measurement 1, i.e. average of
>    difference over time is a better measurement despite the fact that spikes
>    are not accounted for. Measurement 4 certainly isn't.
> 
You are reinventing the wheel. What you described is measurement 1:

1. The amount of memory used by the allocator relative to the amount of memory requested by the program,
averaged across all points in time . In Figure 1, this is
equivalent to averaging the fragmentation for each corresponding point on the upper and lower lines for the
entire run of the program. For the GCC program using the simple seg allocator, this measure yields 258%
fragmentation. The problem with this measure of fragmentation is that it tends to hide the spikes in memory
usage, and it is at these spikes where fragmentation is most likely to be a problem.

and you criticize:

4. The maximum amount of memory used by the allocator relative to the maximum amount of live memory.
These two points do not necessarily occur at the same point in the run of the program
. In Figure 1 this corresponds to the amount of memory at point 3 relative
to the amount of memory at point 2. For the GCC program using the simple seg
allocator, this measure yields 100% fragmentation. The problem with this
measure of fragmentation is that it can yield a number that is too low if the point of maximal memory usage is
a point with a small amount of live memory and is also the point where the amount of memory used becomes
problematic.


You need to know limits of measurements, and that they could fail badly
in certain circumstances. In papers a 4. is common as authors know that
other measurements are more misleading.

There are more problems with taking averages than hiding spikes.

1. Not really measuring fragmentation, when you have program that
previously needed twice of live memory depending on allocator free
memory could form either continuous chunk or be fragmented on many
islands. With that amount of resources even bad allocator could likely
satisfy all requests and when average consists mostly of these
contributions then results will turn inconclusive.

2. A number you get could be chaotic depending on tiny detail. Imagine a
program that in start does lot of small allocations, then frees everything 
but last allocation. Then it does long computation that is not memory intensive.

In that program amount of memory used is depends only on address of last
allocating which will vary wildly even for most innocent change of how
chunks are ordered.

A variant of this problem is that you have program that is mostly stable
except of periodic peaks. 

A good allocator could fit 80% of peak usage and need to place only 20%
into new area. A bad allocator would place 80% of peak data into new
area.

Bad allocator would come as winner as when freeing peak data it crosses
a trim treshold but good allocator does not.

3. Problems with stability. Unless you are measuring a long running process
with mostly flat profile then numbers you get could vary wildly
depending on input. Allocation pattern could stay same but if majority
of time is spend in routine that does not allocate memory but time
varies by input you get different percentages.

4. That by averaging a live memory versus used memory does not measure
fragmentation but how effectively we return memory to system.

You could get better numbers by simply choosing a smaller trim treshold
and triggering trim more often.

We currently do not return memory to system well, see bug 11261 and it
is common that users like this one complain that we use 50% more memory
than alternatives.
http://juliank.wordpress.com/2012/05/31/memory-allocators/

You would get more realistic estimate by actually unmapping unused pages
and dealing with holes, but that would change how long program spends on
various parts which would change average.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]