Re: Improving the memory allocator

On Mon, Apr 25, 2011 at 5:45 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> [ lots of awesome test results ]

Very interesting work. I think it's interesting that there is so much
allocation happening inside MessageContext; I barely knew that
existed, let alone that it was a hotspot for memory allocation. I
think it would be interesting to break out the calls to new_list() by
caller. It's been vaguely bothering me for a long time that we store
so many things in using List structures. That is not a particularly
efficient representation, because a List of N nodes requires 2N+1
memory allocations - N nodes, N ListCell objects, and the List object
itself. It might be worth experimenting with some kind of array/list
hybridy thing, like this:

typedef struct BunchOfThings {
NodeTag type;
int total_length;
int this_node_length;
struct BunchOfThings *next;
Thing data[1]; /* really variable-length */
};

This is probably a bit more of a pain to deal with than a plain old
List, and for many purposes it might not be suitable, but there might
be some hotspots where the performance gain is enough to justify the
trouble. In some cases you might be able to get even simpler - just
use a fixed array and, if it fills up, either reallocate-and-copy or
error out.

> The problem with that is obviously that it would violate the whole mctx.c
> abstraction as it has to be known at compile time which memory manager is
> used.
>
> Are we willing to reduce that abstraction?

I think it's definitely worth considering, if there is a significant
performance benefit.

> Given the frequentness of very small allocations the current space overhead
> of at least 16 bytes on 64bit Platforms seems quite high.

Yeah.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company