[personal/website.git] / source / blog / posts / 2010 / 08 / 14-memory-allocation-patterns.rst

Title: Memory allocation patterns
Tags: en, d, gc, dgc, cdgc, memory, allocation, pattern, dil, benchmark

.. note::

   Tango__ 0.99.9 has a bug__ in its runtime, which sometimes makes the GC scan
   memory that should not be scanned. It only affects Dil and Voronoi programs,
   but in a significant way. The tests in this post are done using a patched
   runtime, with the bug fixed.

__ http://www.dsource.org/projects/tango
__ http://www.dsource.org/projects/tango/ticket/1971


.. admonition:: Update

   The results for the unpublished programs are now available__. You can find
   the graphic results, the detailed summary and the source code for all the
   programs (except dil, which can be downloaded from its home site).

__ ##POST_URL##/14-memory-allocation/


After seeing some weird behaviours and how different benchmarks are more or less
affected by changes like `memory addresses returned by the OS`__ or by
`different ways to store the type information pointer`__, I decided to gather
some information about how much and what kind of memory are requested by the
different benchmarks.

__ http://www.llucax.com.ar/blog/blog/post/-7a56a111
__ http://www.llucax.com.ar/blog/blog/post/1490c03e

I used the information provided by the ``malloc_stats_file`` CDGC__ option, and
generated some stats.

__ http://www.llucax.com.ar/blog/blog/post/-2c067531

The analysis is done on the allocations requested by the program (calls to
``gc_malloc()``) and contrasting that with the real memory allocated by the GC.
Note that only the GC heap memory (that is, memory dedicated to the program,
which the GC scans in the collections) is counted (internal GC memory used for
bookkeeping is not).

Also note that in this post I generally refer to object meaning a block of
memory, it doesn't mean they are actually instance of a class or anything.
Finally bear in mind that all the figures shown here are the sum of all the
allocations done in the life of a program. If the collected data says a program
requested 1GiB of memory, that doesn't mean the program had a residency of 1GiB,
the program could had a working set of a few KiB and recycled memory like hell.

When analyzing the real memory allocated by the GC, there are two modes being
analyzed, one is the classic conservative mode and the other is the precise mode
(as it is in the original patch, storing the type information pointer at the end
of the blocks). So the idea here is to measure two major things:

* The amount of memory wasted by the GC because of `how it arranges memory`__ as
  fixed-size blocks (*bins*) and large objects that uses whole pages.
* The extra amount of memory wasted by the GC when using precise mode because it
  stores the type information pointer at the end of the blocks.

__ http://www.llucax.com.ar/blog/blog/post/250bf643

I've selected a few representative benchmarks. Here are the results:


bh allocation pattern
---------------------

This is a translation__ by `Leonardo Maffi`__ from the `Olden Benchmark`__ that
does a `Barnes–Hut simulation`__.  The program is CPU intensive an does a lot of
allocation of about 5 different small objects.

__ http://www.fantascienza.net/leonardo/js/dolden_bh.zip
__ http://www.fantascienza.net/leonardo/
__ http://www.irisa.fr/caps/people/truong/M2COct99/Benchmarks/Olden/Welcome.html
__ http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation

Here is a graphic summary of the allocation requests and real allocated memory
for a run with ``-b 4000``:

.. container::
   :align: center

   .. image:: ##POST_URL##/14-memory-allocation/bh.rq.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/bh.rq.bin.png

   .. image:: ##POST_URL##/14-memory-allocation/bh.ws.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/bh.ws.bin.png

We can easily see here how the space wasted by the GC memory organization is
significant (about 15% wasted), and how the type information pointer is adding
an even more significant overhead (about 36% of the memory is wasted). This
means that this program will be 15% more subject to false pointers (and will
have to scan some extra memory too, but fortunately the majority of the memory
doesn't need to be scanned) than it should in conservative mode and that the
precise mode makes things 25% worse.

You can also see how the extra overhead in the precise mode is because some
objects that should fit in a 16 bin now need a 32 bytes bin to hold the extra
pointer. See how there were no waste at all in the conservative mode for objects
that should fit a 16 bytes bin. **117MiB are wasted because of that**.

Here is a more detailed (but textual) summary of the memory requested and
allocated:

.. include:: ##POST_DIR##/14-memory-allocation/bh.txt


bigarr allocation pattern
-------------------------

This is a extremely simple program that just allocate a big array of
small-medium objects (all of the same size) `I found in the D NG`__.

__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=54084

Here is the graphic summary:

.. container::
   :align: center

   .. image:: ##POST_URL##/14-memory-allocation/bigarr.rq.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/bigarr.rq.bin.png

   .. image:: ##POST_URL##/14-memory-allocation/bigarr.ws.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/bigarr.ws.bin.png

The only interesting part of this test is how many space is wasted because of
the memory organization, which in this case goes up to 30% for the conservative
mode (and have no change for the precise mode).

Here is the detailed summary:

.. include:: ##POST_DIR##/14-memory-allocation/bigarr.txt


mcore allocation pattern
------------------------

This is program that test the contention produced by the GC when appending to
(thread-specific) arrays in several threads concurrently (again, `found at the
D NG`__). For this analysis the concurrency doesn't play any role though, is
just a program that do a lot of appending to a few arrays.

__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103563

Here are the graphic results:

.. container::
   :align: center

   .. image:: ##POST_URL##/14-memory-allocation/mcore.rq.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/mcore.rq.bin.png

   .. image:: ##POST_URL##/14-memory-allocation/mcore.ws.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/mcore.ws.bin.png

This is the most boring of the examples, as everything works as expected =)

You can clearly see how the arrays grow, passing through each bin size and
finally becoming big objects which take most of the allocated space. Almost
nothing need to be scanned (they are int arrays), and practically there is no
waste. That's a good decision by the array allocation algorithm, which seems to
exploit the bin sizes to the maximum. Since almost all the data is doesn't need
to be scanned, there is no need to store the type information pointers, so there
is no waste either for the precise mode (the story would be totally different if
the arrays were of objects that should be scanned, as probably each array
allocation would waste about 50% of the memory to store the type information
pointer).

Here is the detailed summary:

.. include:: ##POST_DIR##/14-memory-allocation/mcore.txt


voronoi allocation pattern
--------------------------

This is one of my favourites, because is always problematic. It "computes the
`voronoi diagram`__ of a set of points recursively on the tree" and is also
taken from the Olden Benchmark and translated__ by Leonardo Maffi to D.

__ http://en.wikipedia.org/wiki/Voronoi_diagram
__ http://codepad.org/xGDCS3KO

Here are the graphic results for a run with ``-n 30000``:

.. container::
   :align: center

   .. image:: ##POST_URL##/14-memory-allocation/voronoi.rq.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/voronoi.rq.bin.png

   .. image:: ##POST_URL##/14-memory-allocation/voronoi.ws.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/voronoi.ws.bin.png

This have a little from all the previous examples. Practically all the heap
should be scanned (as in **bigarr**), it wastes a considerably portion of the
heap because of the fixed-size blocks (as all but **mcore**), it wastes just
a very little more because of type information (as all but **bh**) but that
waste comes from objects that should fit in a 16 bytes bin but is stored in a 32
bytes bin instead (as in **bh**).

Maybe that's why it's problematic, it touches a little mostly all the GC flaws.

Here is the detailed summary:

.. include:: ##POST_DIR##/14-memory-allocation/voronoi.txt


Dil allocation pattern
----------------------

Finally, this is by far my favourite, the only real-life program, and the most
colorful example (literally =).

Dil__ is a D compiler, and as such, it works a lot with strings, a lot of big
chunks of memory, a lot of small objects, it has it **all**! String manipulation
stress the GC a lot, because it uses objects (blocks) of all possible sizes
ever, specially extremely small objects (less than 8 bytes, even a lot of blocks
of just **one byte**!).

__ http://code.google.com/p/dil/


Here are the results of a run of Dil to generate Tango documentation (around 555
source files are processed):

.. container::
   :align: center

   .. image:: ##POST_URL##/14-memory-allocation/dil.rq.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/dil.rq.bin.png

   .. image:: ##POST_URL##/14-memory-allocation/dil.ws.tot.png

   .. image:: ##POST_URL##/14-memory-allocation/dil.ws.bin.png

Didn't I say it was colorful?

This is like the voronoi but taken to the extreme, it really have it all, it
allocates all types of objects in significant quantities, it wastes a lot of
memory (23%) and much more when used in precise mode (33%).

Here is the detailed summary:

.. include:: ##POST_DIR##/14-memory-allocation/dil.txt


Conclusion
----------

I've analyzed other small fabricated benchmarks, but all of them had results
very similar to the ones shown here.

I think the overallocation problem is more serious than what one might think at
first sight. Bear in mind this is not GC overhead, is not because of internal GC
data. Is memory the GC or the mutator cannot use. Is memory wasted because of
fragmentation (planned fragmentation, but fragmentation at least). And I don't
think this is the worse problem. The worse problem is, this memory will need to
be scanned in most cases (Dil needs to scan 70% of the total memory requested),
and maybe the worse of all is that is subject to false pointer. A false pointer
to a memory location that is not actually being used by the program will keep
the block alive! If is a large object (several pages) that could be pretty
nasty.

This problems can be addressed in several ways. One is mitigate the problem by
checking (when type information is available) what portions of the memory is
really used and what is wasted, and don't keep things alive when they are only
pointed to wasted memory. This is not free though, it will consume more CPU
cycles so the solution could be worse than the problem.

I think it worth experimenting with other heap organizations, for example,
I would experiment with one free list for object size instead of
pre-fixed-sizes. I would even experiment with a free list for each **type** when
type information is available, that would save a lot of space (internal GC
space) when storing type information. Some specialization for strings could be
useful too.

Unfortunately I don't think I'll have the time to do this, at least for the
thesis, but I think is a very rich and interesting ground to experiment.


.. vim: set et sw=3 sts=3 :