[RFC] malloc: add random offset to mmapped memory

[Maarten Bosmans <mkbosmans at gmail dot com>]

When the current malloc implementation uses mmap to directly fulfil an
allocation request, it returns an address that is always aligned to a
page boundary + 16 bytes. When multiple such arrays are accessed in
the same order, like in the following example code, performance is
suboptimal due to cache conflicts.

static void mmap_alignment_test(unsigned n_arr, size_t length) {
  /* allocate [n_arr] arrays of [length] integers */
  int16_t *arr[n_arr];
  for (unsigned a = 0; a < n_arr; a++) {
    arr[a] = malloc(length * sizeof(int16_t));
  }
  /* fill the arrays, interleaving writes to each array */
  for (size_t i = 0; i < length; i++) {
    for (unsigned a = 0; a < n_arr; a++) {
      arr[a][i] = i;
    }
  }
}

The performance impact can be seen in this graph[1], where the
results are shown for executing this code with n_arr=1 to 20 and
length=50000. By default glibc satisfies these small (100kB) requests
from its heap, but by setting MALLOC_MMAP_THRESHOLD_ to a suitably
small value, they can be forced to come directly from the mmap system
call. You can see quite clearly that the code is run on a cpu with an
8-way associative cache, as that is the point where the similarly
aligned mmapped arrays start conflicting.

My proposal is to use the extra (unused) space that we get from mmap
anyway (because it is page-aligned) to add an offset to the returned
pointer. This would improve the performance of this example test case
when the arrays are large enough to be mmapped directly.

I would like to get some feedback whether glibc developers think this
is a worthwhile goal to pursue, before I start working on a patch.

Maarten


[1] http://www.bosmans.ch/share/malloc-mmap-alignment-test.png