Reducing the chunk header sizes on all memory context types

Good day, David.

В Вт, 12/07/2022 в 17:01 +1200, David Rowley пишет:

Over on [1], I highlighted that 40af10b57 (Use Generation memory
contexts to store tuples in sorts) could cause some performance
regressions for sorts when the size of the tuple is exactly a power of
2. The reason for this is that the chunk header for generation.c
contexts is 8 bytes larger (on 64-bit machines) than the aset.c chunk
header. This means that we can store fewer tuples per work_mem during
the sort and that results in more batches being required.

As I write this, this regression is still marked as an open item for
PG15 in [2]. So I've been working on this to try to assist the
discussion about if we need to do anything about that for PG15.

Over on [3], I mentioned that Andres came up with an idea and a
prototype patch to reduce the chunk header size across the board by
storing the context type in the 3 least significant bits in a uint64
header.

I've taken Andres' patch and made some quite significant changes to
it. In the patch's current state, the sort performance regression in
PG15 vs PG14 is fixed. The generation.c context chunk header has been
reduced to 8 bytes from the previous 24 bytes as it is in master.
aset.c context chunk header is now 8 bytes instead of 16 bytes.

We can use this 8-byte chunk header by using the remaining 61-bits of
the uint64 header to encode 2 30-bit values to store the chunk size
and also the number of bytes we must subtract from the given pointer
to find the block that the chunk is stored on. Once we have the
block, we can find the owning context by having a pointer back to the
context from the block. For memory allocations that are larger than
what can be stored in 30 bits, the chunk header gets an additional two
Size fields to store the chunk_size and the block offset. We can tell
the difference between the 2 chunk sizes by looking at the spare 1-bit
the uint64 portion of the header.

I don't get, why "large chunk" needs additional fields for size and
offset.
Large allocation sizes are certainly rounded to page size.
And allocations which doesn't fit 1GB we could easily round to 1MB.
Then we could simply store `size>>20`.
It will limit MaxAllocHugeSize to `(1<<(30+20))-1` - 1PB. Doubdfully we
will deal with such huge allocations in near future.

And to limit block offset, we just have to limit maxBlockSize to 1GB,
which is quite reasonable limitation.
Chunks that are larger than maxBlockSize goes to separate blocks anyway,
therefore they have small block offset.

Aside from speeding up the sort case, this also seems to have a good
positive performance impact on pgbench read-only workload with -M
simple. I'm seeing about a 17% performance increase on my AMD
Threadripper machine.

master + Reduced Memory Context Chunk Overhead
drowley@amd3990x:~$ pgbench -S -T 60 -j 156 -c 156 -M simple postgres
tps = 1876841.953096 (without initial connection time)
tps = 1919605.408254 (without initial connection time)
tps = 1891734.480141 (without initial connection time)

Master
drowley@amd3990x:~$ pgbench -S -T 60 -j 156 -c 156 -M simple postgres
tps = 1632248.236962 (without initial connection time)
tps = 1615663.151604 (without initial connection time)
tps = 1602004.146259 (without initial connection time)

Trick with 3bit context type is great.

The attached .png file shows the same results for PG14 and PG15 as I
showed in the blog [4] where I discovered the regression and adds the
results from current master + the attached patch. See bars in orange.
You can see that the regression at 64MB work_mem is fixed. Adding some
tracing to the sort shows that we're now doing 671745 tuples per batch
instead of 576845 tuples. This reduces the number of batches from 245
down to 210.

Drawbacks:

There is at least one. It might be major; to reduce the AllocSet chunk
header from 16 bytes down to 8 bytes I had to get rid of the freelist
pointer that was reusing the "aset" field in the chunk header struct.
This works now by storing that pointer in the actual palloc'd memory.
This could lead to pretty hard-to-trace bugs if we have any code that
accidentally writes to memory after pfree. The slab.c context already
does this, but that's far less commonly used. If we decided this was
unacceptable then it does not change anything for the generation.c
context. The chunk header will still be 8 bytes instead of 24 there.
So the sort performance regression will still be fixed.

At least we can still mark free list pointer as VALGRIND_MAKE_MEM_NOACCESS
and do VALGRIND_MAKE_MEM_DEFINED on fetching from free list, can we?

Hi,

On 2022-07-12 17:01:18 +1200, David Rowley wrote:

I've taken Andres' patch and made some quite significant changes to
it. In the patch's current state, the sort performance regression in
PG15 vs PG14 is fixed. The generation.c context chunk header has been
reduced to 8 bytes from the previous 24 bytes as it is in master.
aset.c context chunk header is now 8 bytes instead of 16 bytes.

I think this is *very* cool. But I might be biased :)

There is at least one. It might be major; to reduce the AllocSet chunk
header from 16 bytes down to 8 bytes I had to get rid of the freelist
pointer that was reusing the "aset" field in the chunk header struct.
This works now by storing that pointer in the actual palloc'd memory.
This could lead to pretty hard-to-trace bugs if we have any code that
accidentally writes to memory after pfree.

Can't we use the same trick for allcations in the freelist as we do for the
header in a live allocation? I.e. split the 8 byte header into two and use
part of it to point to the next element in the list using the offset from the
start of the block, and part of it to indicate the size?

Greetings,

Andres Freund

Hi,

On 2022-07-12 20:22:57 +0300, Yura Sokolov wrote:

I don't get, why "large chunk" needs additional fields for size and
offset.
Large allocation sizes are certainly rounded to page size.
And allocations which doesn't fit 1GB we could easily round to 1MB.
Then we could simply store `size>>20`.
It will limit MaxAllocHugeSize to `(1<<(30+20))-1` - 1PB. Doubdfully we
will deal with such huge allocations in near future.

What would gain by doing something like this? The storage density loss of
storing an exact size is smaller than what you propose here.

Greetings,

Andres Freund

On Wed, 13 Jul 2022 at 05:44, Andres Freund <andres@anarazel.de> wrote:

On 2022-07-12 20:22:57 +0300, Yura Sokolov wrote:

I don't get, why "large chunk" needs additional fields for size and
offset.
Large allocation sizes are certainly rounded to page size.
And allocations which doesn't fit 1GB we could easily round to 1MB.
Then we could simply store `size>>20`.
It will limit MaxAllocHugeSize to `(1<<(30+20))-1` - 1PB. Doubdfully we
will deal with such huge allocations in near future.

What would gain by doing something like this? The storage density loss of
storing an exact size is smaller than what you propose here.

I do agree that the 16-byte additional header size overhead for
allocations >= 1GB are not really worth troubling too much over.
However, if there was some way to make it so we always had an 8-byte
header, it would simplify some of the code in places such as
AllocSetFree(). For example, (ALLOC_BLOCKHDRSZ + hdrsize +
chunksize) could be simplified at compile time if hdrsize was a known
constant.

I did consider that in all cases where the allocations are above
allocChunkLimit that the chunk is put on a dedicated block and in
fact, the blockoffset is always the same for those. I wondered if we
could use the full 60 bits for the chunksize for those cases. The
reason I didn't pursue that is because:

#define MaxAllocHugeSize (SIZE_MAX / 2)

That's 63-bits, so 60 isn't enough.

Yeah, we likely could reduce that without upsetting anyone. It feels
like it'll be a while before not being able to allocate a chunk of
memory more than 1024 petabytes will be an issue, although, I do hope
to grow old enough to one day come back here at laugh at that.

David

On Wed, 13 Jul 2022 at 05:42, Andres Freund <andres@anarazel.de> wrote:

There is at least one. It might be major; to reduce the AllocSet chunk
header from 16 bytes down to 8 bytes I had to get rid of the freelist
pointer that was reusing the "aset" field in the chunk header struct.
This works now by storing that pointer in the actual palloc'd memory.
This could lead to pretty hard-to-trace bugs if we have any code that
accidentally writes to memory after pfree.

Can't we use the same trick for allcations in the freelist as we do for the
header in a live allocation? I.e. split the 8 byte header into two and use
part of it to point to the next element in the list using the offset from the
start of the block, and part of it to indicate the size?

That can't work as the next freelist item might be on some other block.

David

Hi,

On 2022-07-12 10:42:07 -0700, Andres Freund wrote:

On 2022-07-12 17:01:18 +1200, David Rowley wrote:

There is at least one. It might be major; to reduce the AllocSet chunk
header from 16 bytes down to 8 bytes I had to get rid of the freelist
pointer that was reusing the "aset" field in the chunk header struct.
This works now by storing that pointer in the actual palloc'd memory.
This could lead to pretty hard-to-trace bugs if we have any code that
accidentally writes to memory after pfree.

Can't we use the same trick for allcations in the freelist as we do for the
header in a live allocation? I.e. split the 8 byte header into two and use
part of it to point to the next element in the list using the offset from the
start of the block, and part of it to indicate the size?

So that doesn't work because the members in the freelist can be in different
blocks and those can be further away from each other.

Perhaps that could still made work somehow: To point to a block we don't
actually need 64bit pointers, they're always at least of some certain size -
assuming we can allocate them suitably aligned. And chunks are always 8 byte
aligned. Unfortunately that doesn't quite get us far enough - assuming a 4kB
minimum block size (larger than now, but potentially sensible as a common OS
page size), we still only get to 2^12*8 = 32kB.

It'd easily work if we made each context have an array of allocated non-huge
blocks, so that the blocks can be addressed with a small index. The overhead
of that could be reduced in the common case by embedding a small constant
sized array in the Aset. That might actually be worth trying out.

Greetings,

Andres Freund

В Вт, 12/07/2022 в 22:41 -0700, Andres Freund пишет:

Hi,

On 2022-07-12 10:42:07 -0700, Andres Freund wrote:

On 2022-07-12 17:01:18 +1200, David Rowley wrote:

There is at least one. It might be major; to reduce the AllocSet chunk
header from 16 bytes down to 8 bytes I had to get rid of the freelist
pointer that was reusing the "aset" field in the chunk header struct.
This works now by storing that pointer in the actual palloc'd memory.
This could lead to pretty hard-to-trace bugs if we have any code that
accidentally writes to memory after pfree.

Can't we use the same trick for allcations in the freelist as we do for the
header in a live allocation? I.e. split the 8 byte header into two and use
part of it to point to the next element in the list using the offset from the
start of the block, and part of it to indicate the size?

So that doesn't work because the members in the freelist can be in different
blocks and those can be further away from each other.

Perhaps that could still made work somehow: To point to a block we don't
actually need 64bit pointers, they're always at least of some certain size -
assuming we can allocate them suitably aligned. And chunks are always 8 byte
aligned. Unfortunately that doesn't quite get us far enough - assuming a 4kB
minimum block size (larger than now, but potentially sensible as a common OS
page size), we still only get to 2^12*8 = 32kB.

Well, we actually have freelists for 11 size classes.
It is just 11 pointers.
We could embed this 88 bytes in every ASet block and then link blocks.
And then in every block have 44 bytes for in-block free lists.
Total overhead is 132 bytes per-block.
Or 110 if we limit block size to 65k*8b=512kb.

With double-linked block lists (176bytes per block + 44bytes for in-block lists
= 220bytes), we could track block fullness and deallocate it if it doesn't
contain any alive alocation. Therefore "generational" and "slab" allocators
will be less useful.

But CPU overhead will be noticeable.

On Wed, 13 Jul 2022 at 17:20, David Rowley <dgrowleyml@gmail.com> wrote:

I did consider that in all cases where the allocations are above
allocChunkLimit that the chunk is put on a dedicated block and in
fact, the blockoffset is always the same for those. I wondered if we
could use the full 60 bits for the chunksize for those cases. The
reason I didn't pursue that is because:

As it turns out, we don't really need to explicitly store the chunk
size for chunks which are on dedicated blocks. We can just calculate
this by subtracting the pointer to the memory from the block's endptr.
The block offset is always fixed too, like I mentioned above.

I've now revised the patch to completely get rid of the concept of
"large" chunks and instead memory chunks are always 8 bytes in size.
I've created a struct to this effect and named it MemoryChunk. All
memory contexts make use of this new struct. The header bit which I
was previously using to denote a "large" chunk now marks if the chunk
is "external", meaning that the MemoryChunk does not have knowledge of
the chunk size and/or block offset. The MemoryContext itself is
expected to manage this when the chunk is external. I've coded up
aset.c and generation.c to always use these external chunks when size

set->allocChunkLimit. There is now a coding pattern like the

following (taken from AllocSetRealloc:

if (MemoryChunkIsExternal(chunk))
{
block = ExternalChunkGetBlock(chunk);
oldsize = block->endptr - (char *) pointer;
}
else
{
block = MemoryChunkGetBlock(chunk);
oldsize = MemoryChunkGetSize(chunk);
}

Here the ExternalChunkGetBlock() macro is just subtracting the
ALLOC_BLOCKHDRSZ from the chunk pointer to obtain the block pointer,
whereas MemoryChunkGetBlock() is subtracting the blockoffset as is
stored in the 30-bits of the chunk header.

Andres and I had a conversation off-list about the storage of freelist
pointers. Currently I have these stored in the actual allocated
memory. The minimum allocation size is 8-bytes, which is big enough
for storing sizeof(void *). Andres suggested that it might be safer to
store this link at the end of the chunk rather than at the start.
I've not quite done that in the attached, but doing this should just
be a matter of adjusting the GetFreeListLink() macro to add the
chunksize - sizeof(AllocFreelistLink).

I did a little bit of benchmarking of the attached with a scale 1 pgbench.

master = 0b039e3a8

master
drowley@amd3990x:~$ pgbench -c 156 -j 156 -T 60 -S postgres
tps = 1638436.367793 (without initial connection time)
tps = 1652688.009579 (without initial connection time)
tps = 1671281.281856 (without initial connection time)

master + v2 patch
drowley@amd3990x:~$ pgbench -c 156 -j 156 -T 60 -S postgres
tps = 1825346.734486 (without initial connection time)
tps = 1824539.294142 (without initial connection time)
tps = 1807359.758822 (without initial connection time)

~10% faster.

There are a couple of things to note that might require discussion:

1. I've added a new restriction that block sizes cannot be above 1GB.
This is because the 30-bits in the MemoryChunk used for storing the
offset between the chunk and the block wouldn't be able to store the
offset if the chunk was offset more than 1GB from the block. I used
debian code search to see if I could find any user code that used
blocks this big. I found nothing.
2. slab.c has a new restriction that the chunk size cannot be >= 1GB.
I'm not at all concerned about this. I think if someone needed chunks
that big there'd be no benefits from slab context over an aset
context.
3. As mentioned above, aset.c now stores freelist pointers in the
allocated chunk's memory. This allows us to get the header down to 8
bytes instead of today's 16 bytes. There's an increased danger that
buggy code that writes to memory after a pfree could stomp on this.

I think the patch is now starting to take shape. I've added it to the
September commitfest [1]https://commitfest.postgresql.org/39/3810/.

David

[1]: https://commitfest.postgresql.org/39/3810/

On Tue, Aug 9, 2022 at 8:53 AM David Rowley <dgrowleyml@gmail.com> wrote:

I think the patch is now starting to take shape. I've added it to the
September commitfest [1].

This is extremely cool. The memory savings are really nice. And I also
like this:

# Additionally, this commit completely changes the rule that pointers must
# be directly prefixed by the owning memory context and instead, we now
# insist that they're directly prefixed by an 8-byte value where the least
# significant 3-bits are set to a value to indicate which type of memory
# context the pointer belongs to. Using those 3 bits as an index to a new
# array which stores the methods for each memory context type, we're now
# able to pass the pointer given to functions such as pfree and repalloc to
# the function specific to that context implementation to allow them to
# devise their own methods of finding the memory context which owns the
# given allocated chunk of memory.

That seems like a good system.

This part of the commit message might need to be clarified:

# We also add a restriction that block sizes for all 3 of the memory
# allocators cannot be 1GB or larger. We would be unable to store the
# number of bytes that the block is offset from the chunk stored beyond this
#1GB boundary on any block that was larger than 1GB.

Earlier in the commit message, you say that allocations of 1GB or more
are stored in dedicated blocks. But here you say that blocks can't be
more than 1GB. Those statements seem to contradict each other. I guess
you mean block sizes for blocks that contain chunks, or something like
that?

--
Robert Haas
EDB: http://www.enterprisedb.com

Hi,

On 2022-08-09 10:36:57 -0400, Robert Haas wrote:

On Tue, Aug 9, 2022 at 8:53 AM David Rowley <dgrowleyml@gmail.com> wrote:

I think the patch is now starting to take shape. I've added it to the
September commitfest [1].

This is extremely cool. The memory savings are really nice.

+1

And I also like this:

# Additionally, this commit completely changes the rule that pointers must
# be directly prefixed by the owning memory context and instead, we now
# insist that they're directly prefixed by an 8-byte value where the least
# significant 3-bits are set to a value to indicate which type of memory
# context the pointer belongs to. Using those 3 bits as an index to a new
# array which stores the methods for each memory context type, we're now
# able to pass the pointer given to functions such as pfree and repalloc to
# the function specific to that context implementation to allow them to
# devise their own methods of finding the memory context which owns the
# given allocated chunk of memory.

That seems like a good system.

I'm obviously biased, but I agree.

I think it's fine, given that we can change this at any time, but it's
probably worth to explicitly agree that this will for now restrict us to 8
context methods?

This part of the commit message might need to be clarified:

# We also add a restriction that block sizes for all 3 of the memory
# allocators cannot be 1GB or larger. We would be unable to store the
# number of bytes that the block is offset from the chunk stored beyond this
#1GB boundary on any block that was larger than 1GB.

Earlier in the commit message, you say that allocations of 1GB or more
are stored in dedicated blocks. But here you say that blocks can't be
more than 1GB. Those statements seem to contradict each other. I guess
you mean block sizes for blocks that contain chunks, or something like
that?

I would guess so as well.

diff --git a/src/include/utils/memutils_internal.h b/src/include/utils/memutils_internal.h
new file mode 100644
index 0000000000..2dcfdd7ec3
--- /dev/null
+++ b/src/include/utils/memutils_internal.h
@@ -0,0 +1,117 @@
+/*-------------------------------------------------------------------------
+ *
+ * memutils_internal.h
+ *	  This file contains declarations for memory allocation utility
+ *	  functions for internal use.
+ *
+ *
+ * Portions Copyright (c) 2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/memutils_internal.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef MEMUTILS_INTERNAL_H
+#define MEMUTILS_INTERNAL_H
+
+#include "utils/memutils.h"
+
+extern void *AllocSetAlloc(MemoryContext context, Size size);
+extern void AllocSetFree(void *pointer);
[much more]

I really wish I knew of a technique to avoid this kind of thing, allowing to
fill a constant array from different translation units... On the linker level
that should be trivial, but I don't think there's a C way to reach that.

+/*
+ * MemoryContextMethodID
+ *		A unique identifier for each MemoryContext implementation which
+ *		indicates the index into the mcxt_methods[] array. See mcxt.c.
+ */
+typedef enum MemoryContextMethodID
+{
+	MCTX_ASET_ID = 0,

Is there a reason to reserve 0 here? Practically speaking the 8-byte header
will always contain not just zeroes, but I don't think the patch currently
enforces that. It's probably not worth wasting a "valuable" entry here...

diff --git a/src/include/utils/memutils_memorychunk.h b/src/include/utils/memutils_memorychunk.h
new file mode 100644
index 0000000000..6239cf9008
--- /dev/null
+++ b/src/include/utils/memutils_memorychunk.h
@@ -0,0 +1,185 @@
+/*-------------------------------------------------------------------------
+ *
+ * memutils_memorychunk.h
+ *	  Here we define a struct named MemoryChunk which implementations of
+ *	  MemoryContexts may use as a header for chunks of memory they allocate.
+ *
+ * A MemoryChunk provides a lightweight header which a MemoryContext can use
+ * to store the size of an allocation and a reference back to the block which
+ * the given chunk is allocated on.
+ *
+ * Although MemoryChunks are used by each of our MemoryContexts, other
+ * implementations may choose to implement their own method for storing chunk
+ * headers.  The only requirement is that the header end with an 8-byte value
+ * which the least significant 3-bits of are set to the MemoryContextMethodID
+ * of the given context.

Well, there can't be other implementations other than ours. So maybe phrase it
as "future implementations"?

+ * By default, a MemoryChunk is 8 bytes in size, however when
+ * MEMORY_CONTEXT_CHECKING is defined the header becomes 16 bytes in size due
+ * to the additional requested_size field.  The MemoryContext may use this
+ * field for whatever they wish, but it is intended to be used for additional
+ * checks which are only done in MEMORY_CONTEXT_CHECKING builds.
+ *
+ * The MemoryChunk contains a uint64 field named 'hdrmask'.  This field is
+ * used to encode 4 separate pieces of information.  Starting with the least
+ * significant bits of 'hdrmask', the bits of this field as used as follows:
+ *
+ * 1.	3-bits to indicate the MemoryContextMethodID
+ * 2.	1-bit to indicate if the chunk is externally managed (see below)
+ * 3.	30-bits for the amount of memory which was reserved for the chunk
+ * 4.	30-bits for the number of bytes that must be subtracted from the chunk
+ *		to obtain the address of the block that the chunk is stored on.
+ *
+ * Because we're limited to a block offset and chunk size of 1GB (30-bits),
+ * any allocation which exceeds this amount must call MemoryChunkSetExternal()
+ * and the MemoryContext must devise its own method for storing the offset for
+ * the block and size of the chunk.

Hm. So really only the first four bits have eactly that layout, correct?
Perhaps that could be clarified somehow?

+ /*
+  * The maximum size for a memory chunk before it must be externally managed.
+  */
+#define MEMORYCHUNK_MAX_SIZE 0x3FFFFFFF
+
+ /*
+  * The value to AND onto the hdrmask to determine if it's an externally
+  * managed memory chunk.
+  */
+#define MEMORYCHUNK_EXTERNAL_BIT (1 << 3)

We should probably have a define for the three bits reserved for the context
id, likely in _internal.h

@@ -109,6 +112,25 @@ typedef struct AllocChunkData *AllocChunk;
*/
typedef void *AllocPointer;

+/*
+ * AllocFreelistLink
+ *		When pfreeing memory, if we maintain a freelist for the given chunk's
+ *		size then we use a AllocFreelistLink to point to the current item in
+ *		the AllocSetContext's freelist and then set the given freelist element
+ *		to point to the chunk being freed.
+ */
+typedef struct AllocFreelistLink
+{
+	MemoryChunk *next;
+}			AllocFreelistLink;

I know we have no agreement on that, but I personally would add
AllocFreelistLink to typedefs.list and then re-pgindent ;)

/*
* AllocSetGetChunkSpace
*		Given a currently-allocated chunk, determine the total space
*		it occupies (including all memory-allocation overhead).
*/
-static Size
-AllocSetGetChunkSpace(MemoryContext context, void *pointer)
+Size
+AllocSetGetChunkSpace(void *pointer)
{
-	AllocChunk	chunk = AllocPointerGetChunk(pointer);
-	Size		result;
+	MemoryChunk *chunk = PointerGetMemoryChunk(pointer);

-	VALGRIND_MAKE_MEM_DEFINED(chunk, ALLOCCHUNK_PRIVATE_LEN);
-	result = chunk->size + ALLOC_CHUNKHDRSZ;
-	VALGRIND_MAKE_MEM_NOACCESS(chunk, ALLOCCHUNK_PRIVATE_LEN);
-	return result;
+	if (MemoryChunkIsExternal(chunk))
+	{

Hm. We don't mark the chunk header as noaccess anymore? If so, why? I realize
it'd be a bit annoying because there's plenty places that look at it, but I
think it's also a good way to catch errors.

+static const MemoryContextMethods mcxt_methods[] = {
+	[MCTX_ASET_ID] = {
+		AllocSetAlloc,
+		AllocSetFree,
+		AllocSetRealloc,
+		AllocSetReset,
+		AllocSetDelete,
+		AllocSetGetChunkContext,
+		AllocSetGetChunkSpace,
+		AllocSetIsEmpty,
+		AllocSetStats
+#ifdef MEMORY_CONTEXT_CHECKING
+		,AllocSetCheck
+#endif
+	},
+
+	[MCTX_GENERATION_ID] = {
+		GenerationAlloc,
+		GenerationFree,
+		GenerationRealloc,
+		GenerationReset,
+		GenerationDelete,
+		GenerationGetChunkContext,
+		GenerationGetChunkSpace,
+		GenerationIsEmpty,
+		GenerationStats
+#ifdef MEMORY_CONTEXT_CHECKING
+		,GenerationCheck
+#endif
+	},
+
+	[MCTX_SLAB_ID] = {
+		SlabAlloc,
+		SlabFree,
+		SlabRealloc,
+		SlabReset,
+		SlabDelete,
+		SlabGetChunkContext,
+		SlabGetChunkSpace,
+		SlabIsEmpty,
+		SlabStats
+#ifdef MEMORY_CONTEXT_CHECKING
+		,SlabCheck
+#endif
+	},
+};

Mildly wondering whether we ought to use designated initializers instead,
given we're whacking it around already. Too easy to get the order wrong when
adding new members, and we might want to have optional callbacks too.

Greetings,

Andres Freund

Andres Freund <andres@anarazel.de> writes:

I think it's fine, given that we can change this at any time, but it's
probably worth to explicitly agree that this will for now restrict us to 8
context methods?

Do we really need it to be that tight? I know we only have 3 methods today,
but 8 doesn't seem that far away. If there were six bits reserved for
this I'd be happier.

# We also add a restriction that block sizes for all 3 of the memory
# allocators cannot be 1GB or larger. We would be unable to store the
# number of bytes that the block is offset from the chunk stored beyond this
#1GB boundary on any block that was larger than 1GB.

Losing MemoryContextAllocHuge would be very bad, so I assume this comment
is not telling the full truth.

regards, tom lane

On 2022-Aug-09, Andres Freund wrote:

Mildly wondering whether we ought to use designated initializers instead,
given we're whacking it around already. Too easy to get the order wrong when
adding new members, and we might want to have optional callbacks too.

Strong +1. It makes code much easier to navigate (see XmlTableRoutine
and compare with heapam_methods, for example).

--
Álvaro Herrera 48°01'N 7°57'E — https://www.EnterpriseDB.com/
Subversion to GIT: the shortest path to happiness I've ever heard of
(Alexey Klyukin)

Hi,

On 2022-08-09 15:21:57 -0400, Tom Lane wrote:

Andres Freund <andres@anarazel.de> writes:

I think it's fine, given that we can change this at any time, but it's
probably worth to explicitly agree that this will for now restrict us to 8
context methods?

Do we really need it to be that tight? I know we only have 3 methods today,
but 8 doesn't seem that far away. If there were six bits reserved for
this I'd be happier.

We only have so many bits available, so that'd have to come from some other
resource. The current division is:

+ * 1.	3-bits to indicate the MemoryContextMethodID
+ * 2.	1-bit to indicate if the chunk is externally managed (see below)
+ * 3.	30-bits for the amount of memory which was reserved for the chunk
+ * 4.	30-bits for the number of bytes that must be subtracted from the chunk
+ *		to obtain the address of the block that the chunk is stored on.

I suspect we could reduce 3) here a bit, which I think would end up with slab
context's max chunkSize shrinking further. Which should still be fine.

But also, we could defer that to later, this is a limit that we can easily
change.

# We also add a restriction that block sizes for all 3 of the memory
# allocators cannot be 1GB or larger. We would be unable to store the
# number of bytes that the block is offset from the chunk stored beyond this
#1GB boundary on any block that was larger than 1GB.

Losing MemoryContextAllocHuge would be very bad, so I assume this comment
is not telling the full truth.

It's just talking about chunked allocation (except for slab, which doesn't
have anything else, but as David pointed out, it makes no sense to use slab
for that large allocations). I.e. it's the max you can pass to
AllocSetContextCreate()'s and GenerationContextCreate()'s maxBlockSize, and to
SlabContextCreate()'s chunkSize. I don't think we have any code that
currently sets a bigger limit than 8MB.

Greetings,

Andres Freund

Andres Freund <andres@anarazel.de> writes:

On 2022-08-09 15:21:57 -0400, Tom Lane wrote:

Do we really need it to be that tight? I know we only have 3 methods today,
but 8 doesn't seem that far away. If there were six bits reserved for
this I'd be happier.

We only have so many bits available, so that'd have to come from some other
resource. The current division is:

+ * 1.	3-bits to indicate the MemoryContextMethodID
+ * 2.	1-bit to indicate if the chunk is externally managed (see below)
+ * 3.	30-bits for the amount of memory which was reserved for the chunk
+ * 4.	30-bits for the number of bytes that must be subtracted from the chunk
+ *		to obtain the address of the block that the chunk is stored on.

I suspect we could reduce 3) here a bit, which I think would end up with slab
context's max chunkSize shrinking further. Which should still be fine.

Hmm, I suppose you mean we could reduce 4) if we needed to. Yeah, that
seems like a reasonable place to buy more bits later if we run out of
MemoryContextMethodIDs. Should be fine then.

regards, tom lane

On Wed, 10 Aug 2022 at 09:23, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Andres Freund <andres@anarazel.de> writes:

On 2022-08-09 15:21:57 -0400, Tom Lane wrote:

Do we really need it to be that tight? I know we only have 3 methods today,
but 8 doesn't seem that far away. If there were six bits reserved for
this I'd be happier.

We only have so many bits available, so that'd have to come from some other
resource. The current division is:

+ * 1.        3-bits to indicate the MemoryContextMethodID
+ * 2.        1-bit to indicate if the chunk is externally managed (see below)
+ * 3.        30-bits for the amount of memory which was reserved for the chunk
+ * 4.        30-bits for the number of bytes that must be subtracted from the chunk
+ *           to obtain the address of the block that the chunk is stored on.

I suspect we could reduce 3) here a bit, which I think would end up with slab
context's max chunkSize shrinking further. Which should still be fine.

Hmm, I suppose you mean we could reduce 4) if we needed to. Yeah, that
seems like a reasonable place to buy more bits later if we run out of
MemoryContextMethodIDs. Should be fine then.

I think he means 3). If 4) was reduced then that would further reduce
the maxBlockSize we could pass when creating a context. At least for
aset.c and generation.c, we don't really need 3) to be 30-bits wide as
the set->allocChunkLimit is almost certainly much smaller than that.
Allocations bigger than allocChunkLimit use a dedicated block with an
external chunk. External chunks don't use 3) or 4).

David

David Rowley <dgrowleyml@gmail.com> writes:

On Wed, 10 Aug 2022 at 09:23, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Hmm, I suppose you mean we could reduce 4) if we needed to. Yeah, that
seems like a reasonable place to buy more bits later if we run out of
MemoryContextMethodIDs. Should be fine then.

I think he means 3). If 4) was reduced then that would further reduce
the maxBlockSize we could pass when creating a context. At least for
aset.c and generation.c, we don't really need 3) to be 30-bits wide as
the set->allocChunkLimit is almost certainly much smaller than that.

Oh, I see: we'd just be further constraining the size of chunk that
has to be pushed out as an "external" chunk. Got it.

regards, tom lane

Thanks for giving this a look.

On Wed, 10 Aug 2022 at 02:37, Robert Haas <robertmhaas@gmail.com> wrote:

# We also add a restriction that block sizes for all 3 of the memory
# allocators cannot be 1GB or larger. We would be unable to store the
# number of bytes that the block is offset from the chunk stored beyond this
#1GB boundary on any block that was larger than 1GB.

Earlier in the commit message, you say that allocations of 1GB or more
are stored in dedicated blocks. But here you say that blocks can't be
more than 1GB. Those statements seem to contradict each other. I guess
you mean block sizes for blocks that contain chunks, or something like
that?

I'll update that so it's more clear.

But, just to clarify here first, the 1GB restriction is just in
regards to the maxBlockSize parameter when creating a context.
Anything over set->allocChunkLimit goes on a dedicated block and there
is no 1GB size restriction on those dedicated blocks.

David

On Wed, 10 Aug 2022 at 06:44, Andres Freund <andres@anarazel.de> wrote:

I think it's fine, given that we can change this at any time, but it's
probably worth to explicitly agree that this will for now restrict us to 8
context methods?

I know there was some discussion about this elsewhere in this thread
about 8 possibly not being enough, but that seems to have concluded
with we'll just make more space if we ever need to.

To make that easier, I've adapted the code in memutils_memorychunk.h
to separate out the max values for the block offset from the max value
for the chunk size. The chunk size is the one we'd likely want to
lower if we ever needed more bits. I think this also helps document
the maxBlockSize limitations in aset.c and generation.c.

+/*
+ * MemoryContextMethodID
+ *           A unique identifier for each MemoryContext implementation which
+ *           indicates the index into the mcxt_methods[] array. See mcxt.c.
+ */
+typedef enum MemoryContextMethodID
+{
+     MCTX_ASET_ID = 0,

Is there a reason to reserve 0 here? Practically speaking the 8-byte header
will always contain not just zeroes, but I don't think the patch currently
enforces that. It's probably not worth wasting a "valuable" entry here...

The code was just being explicit about that being set to 0. I'm not
really sure I see this as reserving 0. I've removed the = 0 anyway
since it wasn't really doing anything useful.

+ * Although MemoryChunks are used by each of our MemoryContexts, other
+ * implementations may choose to implement their own method for storing chunk

Well, there can't be other implementations other than ours. So maybe phrase it
as "future implementations"?

Yeah, that seems better.

+ * 1.        3-bits to indicate the MemoryContextMethodID
+ * 2.        1-bit to indicate if the chunk is externally managed (see below)
+ * 3.        30-bits for the amount of memory which was reserved for the chunk
+ * 4.        30-bits for the number of bytes that must be subtracted from the chunk
+ *           to obtain the address of the block that the chunk is stored on.

Hm. So really only the first four bits have eactly that layout, correct?
Perhaps that could be clarified somehow?

I've clarified that #3 and #4 are unused in external chunks.

+#define MEMORYCHUNK_EXTERNAL_BIT (1 << 3)

We should probably have a define for the three bits reserved for the context
id, likely in _internal.h

I've added both MEMORY_CONTEXT_METHODID_BITS and
MEMORY_CONTEXT_METHODID_MASK and tidied up the defines in
memutils_memorychunk.h so that they'll follow on from whatever
MEMORY_CONTEXT_METHODID_BITS is set to.

+typedef struct AllocFreelistLink
+{
+     MemoryChunk *next;
+}                    AllocFreelistLink;

I know we have no agreement on that, but I personally would add
AllocFreelistLink to typedefs.list and then re-pgindent ;)

I tend to leave that up to the build farm to generate. I really wasn't
sure which should sort first out of the following:

MemoryContextMethods
MemoryContextMethodID

The correct answer depends on if the sort is case-sensitive or not. I
imagine it is since it is in C, but don't really know if the buildfarm
will generate the same.

I've added them in the above order now.

Hm. We don't mark the chunk header as noaccess anymore? If so, why? I realize
it'd be a bit annoying because there's plenty places that look at it, but I
think it's also a good way to catch errors.

I don't think I've really changed anything here. If I understand
correctly the pointer to the MemoryContext was not marked as NOACCESS
before. I guessed that's because it's accessed outside of aset.c. I've
kept that due to how the 3 lower bits are still accessed outside of
aset.c. It's just that we're stuffing more information into that
8-byte variable now.

+static const MemoryContextMethods mcxt_methods[] = {

...

Mildly wondering whether we ought to use designated initializers instead,
given we're whacking it around already. Too easy to get the order wrong when
adding new members, and we might want to have optional callbacks too.

I've adjusted how this array is initialized now.

I've attached version 3 of the patch.

Thanks for having a look at this.

David

I've spent a bit more time hacking on this patch.

Changes:

1. Changed GetFreeListLink() so that it stores the AllocFreelistLink
at the end of the chunk rather than at the start.
2. Made it so MemoryChunk stores a magic number in the spare 60 bits
of the hdrmask when the chunk is "external". This is always set but
only verified in assert builds.
3. In aset.c, I'm no longer storing the chunk_size in the hdrmask. I'm
now instead storing the freelist index. I'll explain this below.
4. Various other cleanups.

For #3, I was doing some benchmarking of the patch with a function I
wrote to heavily exercise palloc() and pfree(). When this function is
called to only allocate a small amount of memory at once, I saw a
small regression in the palloc() / pfree() performance for aset.c. On
looking at profiles, I saw that the code in AllocSetFreeIndex() was
standing out AllocSetFree(). That function uses the __builtin_clz()
intrinsic function which I see on x86-64 uses the "bsr" instruction.
Going by page 104 of [1]https://www.agner.org/optimize/instruction_tables.pdf, it tells me the latency of that instruction
is 4 for my Zen 2 CPU. I'm not yet sure why the v3 patch appeared
slower than master for this workload.

To make AllocSetFree() faster, I've now changed things so that instead
of storing the chunk size in the hdrmask of the MemoryChunk, I'm now
just storing the freelist index. The chunk size is always a power of
2 for non-external chunks. It's very cheap to obtain the chunk size
from the freelist index when we need to. That's just a "sal" or "shl"
instruction, effectively 8 << freelist_idx, both of which have a
latency of 1. This means that AllocSetFreeIndex() is only called in
AllocSetAlloc now.

This changes the performance as follows:

Master:
postgres=# select pg_allocate_memory_test(64, 1024,
20::bigint*1024*1024*1024, 'aset');
Time: 2524.438 ms (00:02.524)

Old patch (v3):
postgres=# select pg_allocate_memory_test(64, 1024,
20::bigint*1024*1024*1024, 'aset');
Time: 2646.438 ms (00:02.646)

New patch (v4):
postgres=# select pg_allocate_memory_test(64, 1024,
20::bigint*1024*1024*1024, 'aset');
Time: 2296.228 ms (00:02.296)

(about ~10% faster than master)

This function is allocating 64-byte chunks and keeping 1k of them
around at once, but allocating a total of 20GBs of them. I've attached
another patch with that function in it for anyone who wants to check
the performance.

I also tried another round of the pgbench -S workload that I ran
upthread [2]/messages/by-id/CAApHDvrrYfcCXfuc_bZ0xsqBP8U62Y0i27agr9Qt-2geE_rv0Q@mail.gmail.com on the v2 patch. Confusingly, even when testing on
0b039e3a8 as I was last week, I'm unable to see that same 10%
performance increase.

Does anyone else want to have a go at taking v4 for a spin to see how
it performs?

David

[1]: https://www.agner.org/optimize/instruction_tables.pdf
[2]: /messages/by-id/CAApHDvrrYfcCXfuc_bZ0xsqBP8U62Y0i27agr9Qt-2geE_rv0Q@mail.gmail.com