Improving the memory allocator

On Mon, Apr 25, 2011 at 5:45 PM, Andres Freund <andres@anarazel.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

Andres Freund <andres@anarazel.de> writes:

So after all this my question basically is: How important do we think the
mctx.c abstraction is?

I think it's pretty important. As a specific example, a new context
type in which pfree() is a no-op would be fine with me. A new context
type in which pfree() dumps core will be useless, or close enough to
useless. That means you can't get rid of the per-chunk back-link to the
context, but you might be able to get rid of the other overhead such as
per-chunk size data. (It might be practical to not support
GetMemoryChunkSize for such contexts, or if it's a slab allocator then
you could possibly know that all the chunks in a given block have size X.)

Another point worth making is that it's a nonstarter to propose running
any large part of the system in memory context types that are incapable
of supporting all the debugging options we rely on (freed-memory-reuse
detection and write-past-end-of-chunk in particular). It's okay if a
production build hasn't got that support, not okay for debug builds.
Perhaps you'll propose using completely different context
implementations in the two cases, but I'd be suspicious of that because
it'd mean the "fast" context code doesn't get any developer testing.

Especially as I hope its possible to write a single allocator
which is "good enough" for everything.

I'll lay a side bet that that approach is a dead end. If one size fits
all were good enough, we'd not be having this conversation at all. The
point of the mctx interface layer from the beginning was to support
multiple allocator policies, and that's the direction I think we want to
go to improve this.

BTW, what your numbers actually suggest to me is not that we need a
better allocator, but that we need a better implementation of List.
We speculated back when Neil redid List the first time about aggregating
list cells to reduce palloc traffic, but it was left out to keep the
patch complexity down. Now that the bugs have been shaken out it might
be time to have another go at that. In particular, teaching List to
allocate the list head and first cell together would alone remove a
third of your runtime ...

regards, tom lane

On Tuesday, April 26, 2011 01:39:37 AM Tom Lane wrote:

Andres Freund <andres@anarazel.de> writes:

So after all this my question basically is: How important do we think the
mctx.c abstraction is?

I think it's pretty important. As a specific example, a new context
type in which pfree() is a no-op would be fine with me. A new context
type in which pfree() dumps core will be useless, or close enough to
useless.

Well, what I suggested for that would be using a different api for such small
+ static size allocations.
But as I said, I would prefer to exhaust other possibilities first.

That means you can't get rid of the per-chunk back-link to the
context, but you might be able to get rid of the other overhead such as
per-chunk size data. (It might be practical to not support
GetMemoryChunkSize for such contexts, or if it's a slab allocator then
you could possibly know that all the chunks in a given block have size X.)

For the slab allocator design I have in mind I would need to have a back
pointer to the block, not the context... Thats one other reason why I started
thinking about removing the abstraction.
So far I couldn't envision a clean design where you can intermix two
implementations with such a different interpretations. One could have the
blocks and contexts have a 'allocator' node tag in the first element and
switch over that but I don't really like that.

And I don't see a way with that abstraction to let the compiler do expensive
stuff like the index offset determination at compile time instead of run time
with that abstraction. And I think pulling such computations out of runtime is
quite an important part of improvements in that area.

Another point worth making is that it's a nonstarter to propose running
any large part of the system in memory context types that are incapable
of supporting all the debugging options we rely on (freed-memory-reuse
detection and write-past-end-of-chunk in particular). It's okay if a
production build hasn't got that support, not okay for debug builds.

Totally with you. I have absolutely no problem of enlarging the chunkheader
for debug builds and I can't envision a design where that would be a major
problem.

Perhaps you'll propose using completely different context
implementations in the two cases, but I'd be suspicious of that because
it'd mean the "fast" context code doesn't get any developer testing.

I don't like that option either. Its *way* to easy to screw up slightly in
that area.

Especially as I hope its possible to write a single allocator
which is "good enough" for everything.

I'll lay a side bet that that approach is a dead end. If one size fits
all were good enough, we'd not be having this conversation at all. The
point of the mctx interface layer from the beginning was to support
multiple allocator policies, and that's the direction I think we want to
go to improve this.

I don't think I am with you here. I am not around that long so I might be
missing something but I haven't found much evidence of somebody trying to
improve the allocator on a whole instead of improving currently problematic
pieces for 10+ years. So I don't see there is enough evidence proving that
there isn't a possibility to envision an allocator thats good enough for all
needs.

I quite much fear having to figure out which allocator to use where. I don't
see that working very well.

BTW, what your numbers actually suggest to me is not that we need a
better allocator, but that we need a better implementation of List.
We speculated back when Neil redid List the first time about aggregating
list cells to reduce palloc traffic, but it was left out to keep the
patch complexity down. Now that the bugs have been shaken out it might
be time to have another go at that. In particular, teaching List to
allocate the list head and first cell together would alone remove a
third of your runtime ...

Thats certainly true for that workload. The hotspot is somewhere else entirely
though if you start doing even mildly more complex statements than the default
readonly statements from pgbench.
Its actually not totally easy finding any workload thats not totally IO bound
where memory allocation is not in the top 5 in a profile...

But sure. Improving that point is a good idea independent from the allocator.
One less allocation won't hurt any allocator ;)

Greetings,

Andres

Robert Haas <robertmhaas@gmail.com> writes:

On Mon, Apr 25, 2011 at 5:45 PM, Andres Freund <andres@anarazel.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.

The reason it shows as a hotspot is that parsing and planning happen in
that context for the simple-Query code path. You'd get different
answers if you were using extended-query protocol, or running prepared
statements, or doing the bulk of your work in plpgsql, etc etc.

It would be interesting if Andres could dig down another level or so in
the call stack to see where the list creations etc are called from, but
I'll bet quite a bit that what we're looking at is mostly parse/plan
activity. (The high showing of bitmapset activity is a dead tipoff for
planner, in particular, since that datatype is hardly used at all
elsewhere.)

regards, tom lane

On Tuesday, April 26, 2011 01:24:20 AM Robert Haas wrote:

On Mon, Apr 25, 2011 at 5:45 PM, Andres Freund <andres@anarazel.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.

Yes, I was surprised as well. I haven't checked yet what the callsites for
that are.
As I just wrote to TOm the hotspots are wildly different if you use slightly
more complex statements. Which doesn't mean its not worthy of improvement ;)

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:
...

While I aggree that that might be beneficial I think in this case nearly all
of the lists are of 1 element length because its callers seem to look mostly
like:
{{{
List *
lappend(List *list, void *datum)
{
Assert(IsPointerList(list));

if (list == NIL)
list = new_list(T_List);
else
new_tail_cell(list);

lfirst(list->tail) = datum;
check_list_invariants(list);
return list;
}
}}}

Hm. Seems worthy of some further investigation...

Thanks,

Andres

On Tuesday, April 26, 2011 02:22:34 AM Tom Lane wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Mon, Apr 25, 2011 at 5:45 PM, Andres Freund <andres@anarazel.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.

The reason it shows as a hotspot is that parsing and planning happen in
that context for the simple-Query code path. You'd get different
answers if you were using extended-query protocol, or running prepared
statements, or doing the bulk of your work in plpgsql, etc etc.

It would be interesting if Andres could dig down another level or so in
the call stack to see where the list creations etc are called from, but
I'll bet quite a bit that what we're looking at is mostly parse/plan
activity. (The high showing of bitmapset activity is a dead tipoff for
planner, in particular, since that datatype is hardly used at all
elsewhere.)

Currently thats just output via

#define MemoryContextAlloc(context, size) \
TraceMemoryContextAlloc(context, size, __FILE__, __FUNCTION__, __LINE__, \
__builtin_constant_p(size))
which in turn then calls the ordinary MemoryContextAlloc (yes, ugly I know).
But I guess it shouldn't be a problem to get more information...

Andres

I didn't followed this topic carefully, so sorry If I wrote something
that was written, but I thought about following approach at least for
message sending, etc.:

1. When initializing MemoryContext (pool) give one parameter that will
be stack size. Stack is addition to normal operations.
2. Operations on stack are only allocations, so alloc will be just
pointer bump.
3. When allocating memory for messages, internally set size to be 1/3
greater (or 2/3 I don't remember well) for realloc, may help when
encoding change occurs.
3. free is no op (as it was pointed), stack will be released or pointer
resetted, when context is released

From one point of view this may waste some memory (no free), but for
messages should not happen, and even giving 100kb of memory for stack
may be quite enough, depending ofcourse how many data you send.

Regards,
Radek

On Tuesday, April 26, 2011 01:59:45 PM Radosław Smogura wrote:

I didn't followed this topic carefully, so sorry If I wrote something
that was written, but I thought about following approach at least for
message sending, etc.:

1. When initializing MemoryContext (pool) give one parameter that will
be stack size. Stack is addition to normal operations.

You can't allocate memory on the stack and return that.

Andres

On Tue, 26 Apr 2011 14:25:10 +0200, Andres Freund wrote:

On Tuesday, April 26, 2011 01:59:45 PM Radosław Smogura wrote:

I didn't followed this topic carefully, so sorry If I wrote
something
that was written, but I thought about following approach at least
for
message sending, etc.:

1. When initializing MemoryContext (pool) give one parameter that
will
be stack size. Stack is addition to normal operations.

You can't allocate memory on the stack and return that.

Andres

I didn't wrote allocate on stack. I thought about preallocate n bytes
chunk for stack-like memory but without popping.

Regards,
Radek

On Tuesday, April 26, 2011 03:21:05 PM Radosław Smogura wrote:

On Tue, 26 Apr 2011 14:25:10 +0200, Andres Freund wrote:

On Tuesday, April 26, 2011 01:59:45 PM Radosław Smogura wrote:

I didn't followed this topic carefully, so sorry If I wrote

something

that was written, but I thought about following approach at least

for

message sending, etc.:

1. When initializing MemoryContext (pool) give one parameter that

will

be stack size. Stack is addition to normal operations.

You can't allocate memory on the stack and return that.

Andres

I didn't wrote allocate on stack. I thought about preallocate n bytes
chunk for stack-like memory but without popping.

The implementation already does something like that.

On 04/25/2011 05:45 PM, Andres Freund wrote:

The profile I used in this case was:

pgbench -h /tmp/ -p5433 -s 30 pgbench -S -T 20

I'd suggest collecting data from running this with "-M prepared" at some
point too, so that you can get a basic idea which of these allocations
are avoided when using prepared statements.

--
Greg Smith 2ndQuadrant US greg@2ndQuadrant.com Baltimore, MD