[OLPC-devel] [Fwd: Memory usage minimization]

[Ivan Krstić]

FYI...


-------- Original Message --------
Subject: Memory usage minimization
Date: Fri, 01 Sep 2006 02:50:04 -0400
From: John Richard Moser <nigelenki at comcast.net>
To: ubuntu-devel <ubuntu-devel at lists.ubuntu.com>

As part of an on-going effort to reduce memory usage, I theorized based
entirely on conjecture that the heap allocator was inefficient.  This
was a long time ago, due to a quirk in Nautilus that peaked its memory
usage at 300MB and then dropped back down to 30MB (or at least I had
assumed it reduced to 30MB again; I repeated the causing condition and
it didn't increase memory again); it continued to retain 300MB from the
system even though it apparently didn't need it.

New research has shown that my conjecture was correct.  Not only have I
been able to test for the existence of a flaw using a micro-test that I
had written; but I found some other supporting study that indicated the
efficiency of a number of different allocators.  URL below.

http://www.dent.med.uni-muenchen.de/~wmglo/malloc-slides.html

ftp://ftp.dent.med.uni-muenchen.de/pub/wmglo/

Using the tools at the above FTP (specifically mtrace) I have been able
to make my own measurements, with limited success; often the mtrace
trace file corrupts and cannot be used.  Tests on Thunderbird have
indicated basic 10% memory waste just after start-up; 25% seems normal
for a few minutes of use, but I have seen peak over 60%.  Firefox
behaves similarly, as do a bunch of other programs; short-lived shell
programs that allocate and free a small amount of memory rapidly (i.e.
find, grep, pwd) can reach 90-95% waste but their working set is only a
few megabytes so this is insignificant.

The problem is conjectured (by me) to be that peak memory usage is
retained due to heap fragmentation.  I can measure peak and current
memory usage and extract the memory waste at peak (typically under 8%)
and the average memory waste (typically 20%-70%) but I cannot see the
layout of the heap to confirm the exact cause in real code.  I can force
the flaw to manifest in a micro-test and prove that it does in fact
exist, however.

I am currently working myself on correcting the problem.  I have an
allocator design with a theoretical maximum waste amortized to 3.125%.
Predictably, it is possible to create more waste than this with the same
fragmentation that causes the current problem; however, the design is
such that it requires even distribution of fragments for this to be
possible, and that certain characteristics of thread safety will no
longer cause a problem.  There is also room for more advanced design
tactics which are even more efficient, but do not need to be gone into
at this time.

I would enjoy the chance to do much more testing; although in theory I
should be able to produce something much more efficient than we
currently have, the fact is I need some solid numbers to really lay that
claim down.  If anyone wants to help, the mtrace tool is slightly
broken; as noted before, it often corrupts the output file preventing
'trace-test' from returning statistics.  If it's convenient for anyone,
I'd like to see that fixed so I can gather some solid numbers,
especially on Firefox.