Memory usage minimization

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

(I am not on sounder)

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.

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRPfYGws1xW0HCTEFAQJFtA//WQk1Y2KBfbHp0Nr6iNGR3Q/jyZ5n5G0f
+UiYURjTmUUpQFVD4P+Hvakj5FIzSZgUK7/jULZ+FTkwoTTosiXWgSLMbseqsJIO
kkc0Cx4PHAietjomBUUJOkZ8VurUcSAvCebal1tGj/PkgR39xcrCtoKrx3aERVZK
bEuH8FFPtiH7gEYkJIH+4ifxZm3/GC0ckBCR2+qJM+peCotzlalE9xidno/2PMUp
zxXwuhpXYS/HVScMzYz655gox0um7DjIQgmGdoT0qbHCd6teLi77QcECGhS4T+6P
wH5Gn7FPPB2Cp7nBMFWm8PT025taLdbQJliucNhjfXDDKXdYgwUf8f7iHFV/WuKZ
XHro0TSgZDUIgOBCI0xpTPIppoNe3/GZcCau40pzroOgXSzYj8dIrnxb60SWWTiZ
PFzGjcWQ1NMv2mpaSMBrOlFKuPQjHj3c+aG1E+OpxoBpPgFI8diadToG7g7ezX5c
luGH5fseT1DdMNx80ei+0BXlpRijnEUJgA9ThQvcqMdtvU0AfmfAD7UbDIUeLvVB
OueArAb2rjWQJHNsYmC4XdkR78z9wqBUQP26olu8M53YEBCNw/zm7A9p+jzhwFIo
fut9ck+tFxT4IIQiRyIkwTPhFt2cCZd/lz9X659eXupOxeZ5WJKaotihq+NS5sdL
2jElbw1V4xk=
=PS1O
-----END PGP SIGNATURE-----