Re: The direction of malloc?

[Torvald Riegel <triegel at redhat dot com>]

On Tue, 2013-12-10 at 00:04 -0500, Carlos O'Donell wrote:
> * Add new and required features.
>   - Add support for "have but don't need" kernel pages via vrange.

I think it would be useful if that would be driven or at least
accompanied by a design discussion and documentation.  IOW, a wiki page
as frequently suggested by Carlos :)

Patches are fine and eventually what really matters, but there is a vast
body of literature out there for example, and I would be surprised if
many of us would really have a exhaustive overview of it.  Thus, an
overview or collection of relevant existing work could be helpful
content in this wiki page, even if just to have a central place where we
can combine our knowledge about the state of the art.  For example, I
know that the ISMM conference has had lots of allocator stuff over the
years, but I wouldn't even know which of that is relevant for glibc's
allocator (IOW, on the short list).

Furthermore, the code we end up with in glibc is just one option we
picked.  If well-documented, it will say what it does and why, but it
won't document all the negative results that lead to us adopting this
solution eventually.  But we need to document the negative results too,
or we're prone to forgetting about them, and then we can't reconstruct
our decision process anymore.  This is especially true given that we'll
be dealing with a lot of performance-dependent trade-offs here, and
those will change over time (eg, when hardware changes).

To illustrate that, let me give a quick attempt at a table of contents:

* Literature overview (eg, the short list). Links to relevant libc-alpha
discussions.
* The workload model that we use
  * Allocation patterns (e.g., frequent allocation of small objects,
    long-lived vs. short-lived objects, ...)
  * Number of threads, allocation where in the threads, etc.
  * Access patterns of the program to the memory (eg, lots locality in
    when objects are allocated compared to when they are used, etc.).
    IOW, how access patterns relate to the allocation patterns.
* Our workload priority list (ie, how we weigh each aspect in terms of
  importance)
* The performance model we use
  * NUMA or not, caches, TLB, etc.
  * How our allocator affects the rest of the system (ie, how much
    memory do we not return to the system, and how much does this
    matter?)
* The performance priority list (e.g., we care more about tiny systems
  than large servers, or not)
* How the benchmarks that we have reflect the above.  Also, aspects not
  covered by the benchmarks (so that people know what won't be caught by
  any future automated performance regression testing, for example).
* Allocator design decisions
  * Negative results. Stuff that didn't work, and why.
  * Why we have what we have in glibc.  How it performs on the
    workload/performance priority list, and how it does on variations of
    this list.

Something like this should help us in the discussion.  For example, if
we have a documented model, we get clear names for things (e.g., it's
pattern X, or a trade-off between F and Y).  It also makes it easier for
future maintainers to make sense out of all of this.  Etc.