Re: PG15 beta1 sort performance regression due to Generation context change

David Rowley <dgrowleyml@gmail.com> writes:
> On Tue, 24 May 2022 at 09:36, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I think probably that could be made to work, since a Generation
>> context should not contain all that many live blocks at any one time.

> I've done a rough cut implementation of this and attached it here.
> I've not done that much testing yet, but it does seem to fix the
> performance regression that I mentioned in the blog post that I linked
> in the initial post on this thread.

Here's a draft patch for the other way of doing it.  I'd first tried
to make the side-effects completely local to generation.c, but that
fails in view of code like

    MemoryContextAlloc(GetMemoryChunkContext(x), ...)

Thus we pretty much have to have some explicit awareness of this scheme
in GetMemoryChunkContext().  There's more than one way it could be
done, but I thought a clean way is to invent a separate NodeTag type
to identify the indirection case.

So this imposes a distributed overhead of one additional test-and-branch
per pfree or repalloc.  I'm inclined to think that that's negligible,
but I've not done performance testing to try to prove it.

For back-patching into v14, we could put the new NodeTag type at the
end of that enum list.  The change in the inline GetMemoryChunkContext
is probably an acceptable hazard.

            regards, tom lane

diff --git a/src/backend/utils/mmgr/README b/src/backend/utils/mmgr/README
index 221b4bd343..c932f88639 100644
--- a/src/backend/utils/mmgr/README
+++ b/src/backend/utils/mmgr/README
@@ -397,12 +397,14 @@ precede the MemoryContext.  This means the only overhead implied by
 the memory context mechanism is a pointer to its context, so we're not
 constraining context-type designers very much.

-Given this, routines like pfree determine their corresponding context
-with an operation like (although that is usually encapsulated in
-GetMemoryChunkContext())
-
-    MemoryContext context = *(MemoryContext*) (((char *) pointer) - sizeof(void *));
-
+Furthermore, context allocators can make the pointer preceding an
+allocated chunk be a pointer to a "MemoryContextLink" rather than
+directly to the owning context.  This allows chunks to be associated
+with a subsidiary data structure, such as a sub-group of allocations,
+at relatively low cost.
+
+Given this, routines like pfree determine their target context
+with GetMemoryChunkContext() or equivalent code,
 and then invoke the corresponding method for the context

     context->methods->free_p(pointer);
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index e530e272e0..bf1acc13c7 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -85,9 +85,15 @@ typedef struct GenerationContext
  *
  *        GenerationBlock is the header data for a block --- the usable space
  *        within the block begins at the next alignment boundary.
+ *
+ *        To make it cheap to identify the GenerationBlock containing a given
+ *        chunk, a GenerationBlock starts with a MemoryContextLink.  This
+ *        allows us to make GenerationChunk's required overhead pointer point to
+ *        the containing GenerationBlock rather than directly to the context.
  */
 struct GenerationBlock
 {
+    MemoryContextLink link;        /* link to owning context */
     dlist_node    node;            /* doubly-linked list of blocks */
     Size        blksize;        /* allocated size of this block */
     int            nchunks;        /* number of chunks in the block */
@@ -101,7 +107,7 @@ struct GenerationBlock
  *        The prefix of each piece of memory in a GenerationBlock
  *
  * Note: to meet the memory context APIs, the payload area of the chunk must
- * be maxaligned, and the "context" link must be immediately adjacent to the
+ * be maxaligned, and the "block" link must be immediately adjacent to the
  * payload area (cf. GetMemoryChunkContext).  We simplify matters for this
  * module by requiring sizeof(GenerationChunk) to be maxaligned, and then
  * we can ensure things work by adding any required alignment padding before
@@ -128,17 +134,16 @@ struct GenerationChunk
 #endif

     GenerationBlock *block;        /* block owning this chunk */
-    GenerationContext *context; /* owning context, or NULL if freed chunk */
     /* there must not be any padding to reach a MAXALIGN boundary here! */
 };

 /*
- * Only the "context" field should be accessed outside this module.
+ * Only the "block" field should be accessed outside this module.
  * We keep the rest of an allocated chunk's header marked NOACCESS when using
  * valgrind.  But note that freed chunk headers are kept accessible, for
  * simplicity.
  */
-#define GENERATIONCHUNK_PRIVATE_LEN    offsetof(GenerationChunk, context)
+#define GENERATIONCHUNK_PRIVATE_LEN    offsetof(GenerationChunk, block)

 /*
  * GenerationIsValid
@@ -152,7 +157,8 @@ struct GenerationChunk
     ((GenerationPointer *)(((char *)(chk)) + Generation_CHUNKHDRSZ))

 /* Inlined helper functions */
-static inline void GenerationBlockInit(GenerationBlock *block, Size blksize);
+static inline void GenerationBlockInit(GenerationBlock *block,
+                                       MemoryContext context, Size blksize);
 static inline bool GenerationBlockIsEmpty(GenerationBlock *block);
 static inline void GenerationBlockMarkEmpty(GenerationBlock *block);
 static inline Size GenerationBlockFreeBytes(GenerationBlock *block);
@@ -226,7 +232,7 @@ GenerationContextCreate(MemoryContext parent,
     /* Assert we padded GenerationChunk properly */
     StaticAssertStmt(Generation_CHUNKHDRSZ == MAXALIGN(Generation_CHUNKHDRSZ),
                      "sizeof(GenerationChunk) is not maxaligned");
-    StaticAssertStmt(offsetof(GenerationChunk, context) + sizeof(MemoryContext) ==
+    StaticAssertStmt(offsetof(GenerationChunk, block) + sizeof(void *) ==
                      Generation_CHUNKHDRSZ,
                      "padding calculation in GenerationChunk is wrong");

@@ -278,7 +284,7 @@ GenerationContextCreate(MemoryContext parent,
     block = (GenerationBlock *) (((char *) set) + MAXALIGN(sizeof(GenerationContext)));
     /* determine the block size and initialize it */
     firstBlockSize = allocSize - MAXALIGN(sizeof(GenerationContext));
-    GenerationBlockInit(block, firstBlockSize);
+    GenerationBlockInit(block, (MemoryContext) set, firstBlockSize);

     /* add it to the doubly-linked list of blocks */
     dlist_push_head(&set->blocks, &block->node);
@@ -413,6 +419,10 @@ GenerationAlloc(MemoryContext context, Size size)

         context->mem_allocated += blksize;

+        /* set up standard GenerationBlock header */
+        block->link.type = T_MemoryContextLink;
+        block->link.link = context;
+
         /* block with a single (used) chunk */
         block->blksize = blksize;
         block->nchunks = 1;
@@ -423,7 +433,6 @@ GenerationAlloc(MemoryContext context, Size size)

         chunk = (GenerationChunk *) (((char *) block) + Generation_BLOCKHDRSZ);
         chunk->block = block;
-        chunk->context = set;
         chunk->size = chunk_size;

 #ifdef MEMORY_CONTEXT_CHECKING
@@ -516,7 +525,7 @@ GenerationAlloc(MemoryContext context, Size size)
             context->mem_allocated += blksize;

             /* initialize the new block */
-            GenerationBlockInit(block, blksize);
+            GenerationBlockInit(block, context, blksize);

             /* add it to the doubly-linked list of blocks */
             dlist_push_head(&set->blocks, &block->node);
@@ -544,7 +553,6 @@ GenerationAlloc(MemoryContext context, Size size)
     Assert(block->freeptr <= block->endptr);

     chunk->block = block;
-    chunk->context = set;
     chunk->size = chunk_size;

 #ifdef MEMORY_CONTEXT_CHECKING
@@ -574,8 +582,11 @@ GenerationAlloc(MemoryContext context, Size size)
  *        mem_allocated field.
  */
 static inline void
-GenerationBlockInit(GenerationBlock *block, Size blksize)
+GenerationBlockInit(GenerationBlock *block, MemoryContext context, Size blksize)
 {
+    block->link.type = T_MemoryContextLink;
+    block->link.link = context;
+
     block->blksize = blksize;
     block->nchunks = 0;
     block->nfree = 0;
@@ -685,9 +696,6 @@ GenerationFree(MemoryContext context, void *pointer)
     wipe_mem(pointer, chunk->size);
 #endif

-    /* Reset context to NULL in freed chunks */
-    chunk->context = NULL;
-
 #ifdef MEMORY_CONTEXT_CHECKING
     /* Reset requested_size to 0 in freed chunks */
     chunk->requested_size = 0;
@@ -979,6 +987,12 @@ GenerationCheck(MemoryContext context)

         total_allocated += block->blksize;

+        /* Sanity-check the block header. */
+        if (block->link.type != T_MemoryContextLink ||
+            block->link.link != context)
+            elog(WARNING, "problem in Generation %s: invalid link in block %p",
+                 name, block);
+
         /*
          * nfree > nchunks is surely wrong.  Equality is allowed as the block
          * might completely empty if it's the freeblock.
@@ -1004,21 +1018,11 @@ GenerationCheck(MemoryContext context)

             nchunks += 1;

-            /* chunks have both block and context pointers, so check both */
+            /* verify the block pointer */
             if (chunk->block != block)
                 elog(WARNING, "problem in Generation %s: bogus block link in block %p, chunk %p",
                      name, block, chunk);

-            /*
-             * Check for valid context pointer.  Note this is an incomplete
-             * test, since palloc(0) produces an allocated chunk with
-             * requested_size == 0.
-             */
-            if ((chunk->requested_size > 0 && chunk->context != gen) ||
-                (chunk->context != gen && chunk->context != NULL))
-                elog(WARNING, "problem in Generation %s: bogus context link in block %p, chunk %p",
-                     name, block, chunk);
-
             /* now make sure the chunk size is correct */
             if (chunk->size < chunk->requested_size ||
                 chunk->size != MAXALIGN(chunk->size))
@@ -1026,7 +1030,7 @@ GenerationCheck(MemoryContext context)
                      name, block, chunk);

             /* is chunk allocated? */
-            if (chunk->context != NULL)
+            if (chunk->requested_size > 0)
             {
                 /* check sentinel, but only in allocated blocks */
                 if (chunk->requested_size < chunk->size &&
@@ -1041,7 +1045,7 @@ GenerationCheck(MemoryContext context)
              * If chunk is allocated, disallow external access to private part
              * of chunk header.
              */
-            if (chunk->context != NULL)
+            if (chunk->requested_size > 0)
                 VALGRIND_MAKE_MEM_NOACCESS(chunk, GENERATIONCHUNK_PRIVATE_LEN);
         }

diff --git a/src/include/nodes/memnodes.h b/src/include/nodes/memnodes.h
index bbbe151e39..e0f87a612e 100644
--- a/src/include/nodes/memnodes.h
+++ b/src/include/nodes/memnodes.h
@@ -95,6 +95,20 @@ typedef struct MemoryContextData
 /* utils/palloc.h contains typedef struct MemoryContextData *MemoryContext */


+/*
+ * MemoryContextLink
+ *        An indirect linkage to a MemoryContext.
+ *
+ * Some context types prefer to make the pointer preceding each chunk
+ * point to one of these, rather than directly to the owning MemoryContext.
+ */
+typedef struct MemoryContextLink
+{
+    NodeTag        type;            /* == T_MemoryContextLink */
+    MemoryContext link;            /* owning context */
+} MemoryContextLink;
+
+
 /*
  * MemoryContextIsValid
  *        True iff memory context is valid.
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index b3b407579b..f01ad58a20 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -301,6 +301,7 @@ typedef enum NodeTag
     T_AllocSetContext,
     T_SlabContext,
     T_GenerationContext,
+    T_MemoryContextLink,

     /*
      * TAGS FOR VALUE NODES (value.h)
diff --git a/src/include/utils/memutils.h b/src/include/utils/memutils.h
index 495d1af201..1a51fce193 100644
--- a/src/include/utils/memutils.h
+++ b/src/include/utils/memutils.h
@@ -105,9 +105,10 @@ extern bool MemoryContextContains(MemoryContext context, void *pointer);
  *
  * All chunks allocated by any memory context manager are required to be
  * preceded by the corresponding MemoryContext stored, without padding, in the
- * preceding sizeof(void*) bytes.  A currently-allocated chunk must contain a
- * backpointer to its owning context.  The backpointer is used by pfree() and
- * repalloc() to find the context to call.
+ * preceding sizeof(void*) bytes.  This pointer is used by pfree() and
+ * repalloc() to find the context to call.  The only exception is that the
+ * pointer might point to a MemoryContextLink rather than directly to the
+ * owning context.
  */
 #ifndef FRONTEND
 static inline MemoryContext
@@ -128,6 +129,12 @@ GetMemoryChunkContext(void *pointer)
      */
     context = *(MemoryContext *) (((char *) pointer) - sizeof(void *));

+    /*
+     * It might be a link rather than the context itself.
+     */
+    if (IsA(context, MemoryContextLink))
+        context = ((MemoryContextLink *) context)->link;
+
     AssertArg(MemoryContextIsValid(context));

     return context;