Use generation context to speed up tuplesorts
Hackers,
While reviewing and benchmarking 91e9e89dc (Make nodeSort.c use Datum
sorts for single column sorts), I noticed that we use a separate
memory context to store tuple data and we just reset when we're done
if the sort fits in memory, or we dump the tuples to disk in the same
order they're added and reset the context when it does not. There is
a little pfree() work going on via writetup_heap() which I think
possibly could just be removed to get some additional gains.
Anyway, this context that stores tuples uses the standard aset.c
allocator which has the usual power of 2 wastage and additional
overheads of freelists etc. I wondered how much faster it would go if
I set it to use a generation context instead of an aset.c one.
After running make installcheck to make the tenk1 table, running the
attached tuplesortbench script, I get this:
Master:
work_mem = '4MB';
Sort Method: external merge Disk: 2496kB
work_mem = '4GB';
Sort Method: quicksort Memory: 5541kB
Patched:
work_mem = '4MB';
Sort Method: quicksort Memory: 3197kB
So it seems to save quite a bit of memory getting away from rounding
up allocations to the next power of 2.
Performance-wise, there's some pretty good gains. (Results in TPS)
work_mem = '4GB';
Test master gen sort compare
Test1 317.2 665.6 210%
Test2 228.6 388.9 170%
Test3 207.4 330.7 159%
Test4 185.5 279.4 151%
Test5 292.2 563.9 193%
If I drop the work_mem down to standard the unpatched version does to
disk, but the patched version does not. The gains get a little
bigger.
work_mem = '4MB';
Test master gen sort compare
Test1 177.5 658.2 371%
Test2 149.7 385.2 257%
Test3 137.5 330.0 240%
Test4 129.0 275.1 213%
Test5 161.7 546.4 338%
The patch is just a simple 1-liner at the moment. I likely do need to
adjust what I'm passing as the blockSize to GenerationContextCreate().
Maybe a better number would be something that's calculated from
work_mem, e.g Min(ALLOCSET_DEFAULT_MAXSIZE, ((Size) work_mem) * 64))
so that we just allocate at most a 16th of work_mem per chunk, but not
bigger than 8MB. I don't think changing this will affect the
performance of the above very much.
David
Attachments:
generation_tuplesort.patchapplication/octet-stream; name=generation_tuplesort.patchDownload
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index b17347b214..09cb73657e 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -845,9 +845,9 @@ tuplesort_begin_batch(Tuplesortstate *state)
* in the parent context, not this context, because there is no need to
* free memtuples early.
*/
- state->tuplecontext = AllocSetContextCreate(state->sortcontext,
- "Caller tuples",
- ALLOCSET_DEFAULT_SIZES);
+ state->tuplecontext = GenerationContextCreate(state->sortcontext,
+ "Caller tuples",
+ ALLOCSET_DEFAULT_MAXSIZE);
state->status = TSS_INITIAL;
state->bounded = false;
On Fri, Jul 30, 2021 at 2:42 AM David Rowley <dgrowleyml@gmail.com> wrote:
Master:
Sort Method: quicksort Memory: 5541kB
Patched:
Sort Method: quicksort Memory: 3197kB
Whoa.
work_mem = '4GB';
Test master gen sort compare
Test1 317.2 665.6 210%
Test2 228.6 388.9 170%
Test3 207.4 330.7 159%
Test4 185.5 279.4 151%
Test5 292.2 563.9 193%
Very impressive.
An early version of what eventually became DSA worked with
backend-local memory and I saw very substantial memory usage
improvements on large sorts, similar to what you show here. I am not
sure I saw the same CPU improvements, and in any case I abandoned the
idea of using that infrastructure to manage backend-local memory at
some point, since the whole thing had lots of problems that I didn't
know how to solve. What you've done here looks like a much more
promising approach.
--
Robert Haas
EDB: http://www.enterprisedb.com
Hi,
On 2021-07-30 18:42:18 +1200, David Rowley wrote:
While reviewing and benchmarking 91e9e89dc (Make nodeSort.c use Datum
sorts for single column sorts), I noticed that we use a separate
memory context to store tuple data and we just reset when we're done
if the sort fits in memory, or we dump the tuples to disk in the same
order they're added and reset the context when it does not. There is
a little pfree() work going on via writetup_heap() which I think
possibly could just be removed to get some additional gains.Anyway, this context that stores tuples uses the standard aset.c
allocator which has the usual power of 2 wastage and additional
overheads of freelists etc. I wondered how much faster it would go if
I set it to use a generation context instead of an aset.c one.After running make installcheck to make the tenk1 table, running the
attached tuplesortbench script, I get this:
So it seems to save quite a bit of memory getting away from rounding
up allocations to the next power of 2.Performance-wise, there's some pretty good gains. (Results in TPS)
Very nice!
I wonder if there's cases where generation.c would regress performance
over aset.c due to not having an initial / "keeper" block?
The patch is just a simple 1-liner at the moment. I likely do need to
adjust what I'm passing as the blockSize to GenerationContextCreate().
Maybe a better number would be something that's calculated from
work_mem, e.g Min(ALLOCSET_DEFAULT_MAXSIZE, ((Size) work_mem) * 64))
so that we just allocate at most a 16th of work_mem per chunk, but not
bigger than 8MB. I don't think changing this will affect the
performance of the above very much.
I think it's bad that both genereration and slab don't have internal
handling of block sizes. Needing to err on the size of too big blocks to
handle large amounts of memory well, just so the contexts don't need to
deal with variably sized blocks isn't a sensible tradeoff.
I don't think it's acceptable to use ALLOCSET_DEFAULT_MAXSIZE or
Min(ALLOCSET_DEFAULT_MAXSIZE, ((Size) work_mem) * 64) for
tuplesort.c. There's plenty cases where we'll just sort a handful of
tuples, and increasing the memory usage of those by a factor of 1024
isn't good. The Min() won't do any good if a larger work_mem is used.
Nor will it be good to use thousands of small allocations for a large
in-memory tuplesort just because we're concerned about the initial
allocation size. Both because of the allocation overhead, but
importantly also because that will make context resets more expensive.
To me this says that we should transplant aset.c's block size growing
into generation.c.
There is at least one path using tuplecontext that reaches code that
could end up freeing memory to a significant enough degree to care about
generation.c effectively not using that memory:
tuplesort_putdatum()->datumCopy()->EOH_flatten_into()
On a quick look I didn't find any expanded record user that frees
nontrivial amounts of memory, but I didn't look all that carefully.
Greetings,
Andres Freund
On 7/30/21 10:38 PM, Andres Freund wrote:
Hi,
On 2021-07-30 18:42:18 +1200, David Rowley wrote:
While reviewing and benchmarking 91e9e89dc (Make nodeSort.c use Datum
sorts for single column sorts), I noticed that we use a separate
memory context to store tuple data and we just reset when we're done
if the sort fits in memory, or we dump the tuples to disk in the same
order they're added and reset the context when it does not. There is
a little pfree() work going on via writetup_heap() which I think
possibly could just be removed to get some additional gains.Anyway, this context that stores tuples uses the standard aset.c
allocator which has the usual power of 2 wastage and additional
overheads of freelists etc. I wondered how much faster it would go if
I set it to use a generation context instead of an aset.c one.After running make installcheck to make the tenk1 table, running the
attached tuplesortbench script, I get this:So it seems to save quite a bit of memory getting away from rounding
up allocations to the next power of 2.Performance-wise, there's some pretty good gains. (Results in TPS)
Very nice!
Yes, very nice. I wouldn't have expected such significant difference,
particularly in CPU usage. It's pretty interesting that it both reduces
memory and CPU usage, I'd have guessed it's either one of the other.
I wonder if there's cases where generation.c would regress performance
over aset.c due to not having an initial / "keeper" block?
Not sure. I guess such workload would need to allocate and free a single
block (so very little memory) very often. I guess that's possible, but
I'm not aware of a place doing that very often. Although, maybe decoding
could do that for simple (serial) workload.
I'm not opposed to adding a keeper block to Generation, similarly to
what was discussed for Slab not too long ago.
The patch is just a simple 1-liner at the moment. I likely do need to
adjust what I'm passing as the blockSize to GenerationContextCreate().
Maybe a better number would be something that's calculated from
work_mem, e.g Min(ALLOCSET_DEFAULT_MAXSIZE, ((Size) work_mem) * 64))
so that we just allocate at most a 16th of work_mem per chunk, but not
bigger than 8MB. I don't think changing this will affect the
performance of the above very much.I think it's bad that both genereration and slab don't have internal
handling of block sizes. Needing to err on the size of too big blocks to
handle large amounts of memory well, just so the contexts don't need to
deal with variably sized blocks isn't a sensible tradeoff.
Well, back then it seemed like a sensible trade off to me, but I agree
it may have negative consequences. I'm not opposed to revisiting this.
I don't think it's acceptable to use ALLOCSET_DEFAULT_MAXSIZE or
Min(ALLOCSET_DEFAULT_MAXSIZE, ((Size) work_mem) * 64) for
tuplesort.c. There's plenty cases where we'll just sort a handful of
tuples, and increasing the memory usage of those by a factor of 1024
isn't good. The Min() won't do any good if a larger work_mem is used.Nor will it be good to use thousands of small allocations for a large
in-memory tuplesort just because we're concerned about the initial
allocation size. Both because of the allocation overhead, but
importantly also because that will make context resets more expensive.
True.
To me this says that we should transplant aset.c's block size growing
into generation.c.
Yeah, maybe.
There is at least one path using tuplecontext that reaches code that
could end up freeing memory to a significant enough degree to care about
generation.c effectively not using that memory:
tuplesort_putdatum()->datumCopy()->EOH_flatten_into()
On a quick look I didn't find any expanded record user that frees
nontrivial amounts of memory, but I didn't look all that carefully.
Not sure, I'm not familiar with EOH_flatten_into or expanded records.
But I wonder if there's some sort of metric that we could track in
Generation and use it to identify "interesting" places.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Hi,
I spent a bit of time hacking on the Generation context, adding the two
improvements discussed in this thread:
1) internal handling of block sizes, similar to what AllocSet does (it
pretty much just copies parts of it)
2) keeper block (we keep one empry block instead of freeing it)
3) I've also added allocChunkLimit, which makes it look a bit more like
AllocSet (instead of using just blockSize/8, which does not work too
well with dynamic blockSize)
I haven't done any extensive tests on it, but it does pass check-world
with asserts etc. I haven't touched the comments, those need updating.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Attachments:
0001-Generation-grow-blocks.patchtext/x-patch; charset=UTF-8; name=0001-Generation-grow-blocks.patchDownload
From 6ca0ae674964157c1f2d2ae446cb415c9be509b6 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Fri, 30 Jul 2021 23:53:52 +0200
Subject: [PATCH 1/3] Generation: grow blocks
---
src/backend/access/gist/gistvacuum.c | 2 +-
.../replication/logical/reorderbuffer.c | 2 +-
src/backend/utils/mmgr/generation.c | 53 ++++++++++++++-----
src/include/utils/memutils.h | 4 +-
4 files changed, 44 insertions(+), 17 deletions(-)
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.c
index 0663193531..1818ed06fc 100644
--- a/src/backend/access/gist/gistvacuum.c
+++ b/src/backend/access/gist/gistvacuum.c
@@ -161,7 +161,7 @@ gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
*/
vstate.page_set_context = GenerationContextCreate(CurrentMemoryContext,
"GiST VACUUM page set context",
- 16 * 1024);
+ ALLOCSET_DEFAULT_SIZES);
oldctx = MemoryContextSwitchTo(vstate.page_set_context);
vstate.internal_page_set = intset_create();
vstate.empty_leaf_set = intset_create();
diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c
index f99e45f22d..89018dc99d 100644
--- a/src/backend/replication/logical/reorderbuffer.c
+++ b/src/backend/replication/logical/reorderbuffer.c
@@ -336,7 +336,7 @@ ReorderBufferAllocate(void)
buffer->tup_context = GenerationContextCreate(new_ctx,
"Tuples",
- SLAB_LARGE_BLOCK_SIZE);
+ ALLOCSET_DEFAULT_SIZES);
hash_ctl.keysize = sizeof(TransactionId);
hash_ctl.entrysize = sizeof(ReorderBufferTXNByIdEnt);
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 584cd614da..771a2525ca 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -60,7 +60,9 @@ typedef struct GenerationContext
MemoryContextData header; /* Standard memory-context fields */
/* Generational context parameters */
- Size blockSize; /* standard block size */
+ Size initBlockSize; /* initial block size */
+ Size maxBlockSize; /* maximum block size */
+ Size nextBlockSize; /* next block size to allocate */
GenerationBlock *block; /* current (most recently allocated) block */
dlist_head blocks; /* list of blocks */
@@ -196,7 +198,9 @@ static const MemoryContextMethods GenerationMethods = {
MemoryContext
GenerationContextCreate(MemoryContext parent,
const char *name,
- Size blockSize)
+ Size minContextSize,
+ Size initBlockSize,
+ Size maxBlockSize)
{
GenerationContext *set;
@@ -208,16 +212,20 @@ GenerationContextCreate(MemoryContext parent,
"padding calculation in GenerationChunk is wrong");
/*
- * First, validate allocation parameters. (If we're going to throw an
- * error, we should do so before the context is created, not after.) We
- * somewhat arbitrarily enforce a minimum 1K block size, mostly because
- * that's what AllocSet does.
+ * First, validate allocation parameters. Once these were regular runtime
+ * test and elog's, but in practice Asserts seem sufficient because nobody
+ * varies their parameters at runtime. We somewhat arbitrarily enforce a
+ * minimum 1K block size.
*/
- if (blockSize != MAXALIGN(blockSize) ||
- blockSize < 1024 ||
- !AllocHugeSizeIsValid(blockSize))
- elog(ERROR, "invalid blockSize for memory context: %zu",
- blockSize);
+ Assert(initBlockSize == MAXALIGN(initBlockSize) &&
+ initBlockSize >= 1024);
+ Assert(maxBlockSize == MAXALIGN(maxBlockSize) &&
+ maxBlockSize >= initBlockSize &&
+ AllocHugeSizeIsValid(maxBlockSize)); /* must be safe to double */
+ Assert(minContextSize == 0 ||
+ (minContextSize == MAXALIGN(minContextSize) &&
+ minContextSize >= 1024 &&
+ minContextSize <= maxBlockSize));
/*
* Allocate the context header. Unlike aset.c, we never try to combine
@@ -242,7 +250,9 @@ GenerationContextCreate(MemoryContext parent,
*/
/* Fill in GenerationContext-specific header fields */
- set->blockSize = blockSize;
+ set->initBlockSize = initBlockSize;
+ set->maxBlockSize = maxBlockSize;
+ set->nextBlockSize = initBlockSize;
set->block = NULL;
dlist_init(&set->blocks);
@@ -293,6 +303,9 @@ GenerationReset(MemoryContext context)
set->block = NULL;
+ /* Reset block size allocation sequence, too */
+ set->nextBlockSize = set->initBlockSize;
+
Assert(dlist_is_empty(&set->blocks));
}
@@ -329,9 +342,12 @@ GenerationAlloc(MemoryContext context, Size size)
GenerationBlock *block;
GenerationChunk *chunk;
Size chunk_size = MAXALIGN(size);
+ Size blockSize;
+
+ blockSize = (set->block) ? set->block->blksize : set->nextBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
- if (chunk_size > set->blockSize / 8)
+ if (chunk_size > (blockSize / 8))
{
Size blksize = chunk_size + Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
@@ -387,7 +403,16 @@ GenerationAlloc(MemoryContext context, Size size)
if ((block == NULL) ||
(block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
{
- Size blksize = set->blockSize;
+ Size blksize;
+
+ /*
+ * The first such block has size initBlockSize, and we double the
+ * space in each succeeding block, but not more than maxBlockSize.
+ */
+ blksize = set->nextBlockSize;
+ set->nextBlockSize <<= 1;
+ if (set->nextBlockSize > set->maxBlockSize)
+ set->nextBlockSize = set->maxBlockSize;
block = (GenerationBlock *) malloc(blksize);
diff --git a/src/include/utils/memutils.h b/src/include/utils/memutils.h
index ff872274d4..514c0bf75b 100644
--- a/src/include/utils/memutils.h
+++ b/src/include/utils/memutils.h
@@ -183,7 +183,9 @@ extern MemoryContext SlabContextCreate(MemoryContext parent,
/* generation.c */
extern MemoryContext GenerationContextCreate(MemoryContext parent,
const char *name,
- Size blockSize);
+ Size minContextSize,
+ Size initBlockSize,
+ Size maxBlockSize);
/*
* Recommended default alloc parameters, suitable for "ordinary" contexts
--
2.31.1
0002-Generation-keeper-block.patchtext/x-patch; charset=UTF-8; name=0002-Generation-keeper-block.patchDownload
From 952bd3b480f2a76bb802a6e0433b14dde5f3f461 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sat, 31 Jul 2021 02:54:36 +0200
Subject: [PATCH 2/3] Generation: keeper block
---
src/backend/utils/mmgr/generation.c | 61 +++++++++++++++++++++++++----
1 file changed, 54 insertions(+), 7 deletions(-)
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 771a2525ca..6c90416e27 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -65,6 +65,7 @@ typedef struct GenerationContext
Size nextBlockSize; /* next block size to allocate */
GenerationBlock *block; /* current (most recently allocated) block */
+ GenerationBlock *keeper; /* keeper block */
dlist_head blocks; /* list of blocks */
} GenerationContext;
@@ -254,6 +255,7 @@ GenerationContextCreate(MemoryContext parent,
set->maxBlockSize = maxBlockSize;
set->nextBlockSize = initBlockSize;
set->block = NULL;
+ set->keeper = NULL;
dlist_init(&set->blocks);
/* Finally, do the type-independent part of context creation */
@@ -302,6 +304,7 @@ GenerationReset(MemoryContext context)
}
set->block = NULL;
+ set->keeper = NULL;
/* Reset block size allocation sequence, too */
set->nextBlockSize = set->initBlockSize;
@@ -344,7 +347,7 @@ GenerationAlloc(MemoryContext context, Size size)
Size chunk_size = MAXALIGN(size);
Size blockSize;
- blockSize = (set->block) ? set->block->blksize : set->nextBlockSize;
+ blockSize = set->initBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
if (chunk_size > (blockSize / 8))
@@ -400,6 +403,26 @@ GenerationAlloc(MemoryContext context, Size size)
*/
block = set->block;
+ /*
+ * If we can't use the current block, and we have a keeper block with
+ * enough free space in it, use it as the block.
+ *
+ * XXX We don't want to do this when there's not enough free space
+ * (although the keeper block should be empty, so not sure if checking
+ * the space in the keeper block is necessary).
+ */
+ if (((block == NULL) ||
+ (block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size) &&
+ (set->keeper != NULL) &&
+ (set->keeper->endptr - set->keeper->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
+ {
+ block = set->keeper;
+ set->keeper = NULL;
+
+ /* keeper block was not counted as allocated, so add it back */
+ context->mem_allocated += block->blksize;
+ }
+
if ((block == NULL) ||
(block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
{
@@ -524,16 +547,34 @@ GenerationFree(MemoryContext context, void *pointer)
if (block->nfree < block->nchunks)
return;
+ /* Also make sure the block is not marked as the current block. */
+ if (set->block == block)
+ set->block = NULL;
+
+ /* Keep the block for reuse, if we don't have one already. */
+ if (!set->keeper && block->blksize <= set->maxBlockSize)
+ {
+ /* reset the pointers before we use it as keeper block */
+ block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
+ block->endptr = ((char *) block) + block->blksize;
+
+ block->nfree = 0;
+ block->nchunks = 0;
+
+ set->keeper = block;
+
+ /* keeper block is not counted as allocated */
+ context->mem_allocated -= block->blksize;
+
+ return;
+ }
+
/*
* The block is empty, so let's get rid of it. First remove it from the
* list of blocks, then return it to malloc().
*/
dlist_delete(&block->node);
- /* Also make sure the block is not marked as the current block. */
- if (set->block == block)
- set->block = NULL;
-
context->mem_allocated -= block->blksize;
free(block);
}
@@ -770,13 +811,19 @@ GenerationCheck(MemoryContext context)
nchunks;
char *ptr;
- total_allocated += block->blksize;
+ /*
+ * The keeper block in the list of blocks, but we don't consider it
+ * as allocated in memory accounting. So don't include it in the sum.
+ */
+ if (block != gen->keeper)
+ total_allocated += block->blksize;
/*
* nfree > nchunks is surely wrong, and we don't expect to see
* equality either, because such a block should have gotten freed.
*/
- if (block->nfree >= block->nchunks)
+ if ((block->nfree > block->nchunks) &&
+ ((block != gen->keeper) && (block->nfree == block->nchunks)))
elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p exceeds %d allocated",
name, block->nfree, block, block->nchunks);
--
2.31.1
0003-Generation-allocChunkLimit.patchtext/x-patch; charset=UTF-8; name=0003-Generation-allocChunkLimit.patchDownload
From ad420a220e67480cbb94a4b60845423ea34c31c1 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sat, 31 Jul 2021 03:20:56 +0200
Subject: [PATCH 3/3] Generation: allocChunkLimit
---
src/backend/utils/mmgr/generation.c | 19 +++++++++++++++----
1 file changed, 15 insertions(+), 4 deletions(-)
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 6c90416e27..2465598762 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -46,6 +46,8 @@
#define Generation_BLOCKHDRSZ MAXALIGN(sizeof(GenerationBlock))
#define Generation_CHUNKHDRSZ sizeof(GenerationChunk)
+#define Generation_CHUNK_FRACTION 8
+
typedef struct GenerationBlock GenerationBlock; /* forward reference */
typedef struct GenerationChunk GenerationChunk;
@@ -63,6 +65,7 @@ typedef struct GenerationContext
Size initBlockSize; /* initial block size */
Size maxBlockSize; /* maximum block size */
Size nextBlockSize; /* next block size to allocate */
+ Size allocChunkLimit; /* effective chunk size limit */
GenerationBlock *block; /* current (most recently allocated) block */
GenerationBlock *keeper; /* keeper block */
@@ -254,6 +257,17 @@ GenerationContextCreate(MemoryContext parent,
set->initBlockSize = initBlockSize;
set->maxBlockSize = maxBlockSize;
set->nextBlockSize = initBlockSize;
+
+ /*
+ * Compute the allocation chunk size limit for this context.
+ *
+ * Follows similar ideas as AllocSet, see aset.c for details ...
+ */
+ set->allocChunkLimit = 1;
+ while ((Size) (set->allocChunkLimit + Generation_CHUNKHDRSZ) >
+ (Size) ((Size) (maxBlockSize - Generation_BLOCKHDRSZ) / Generation_CHUNK_FRACTION))
+ set->allocChunkLimit >>= 1;
+
set->block = NULL;
set->keeper = NULL;
dlist_init(&set->blocks);
@@ -345,12 +359,9 @@ GenerationAlloc(MemoryContext context, Size size)
GenerationBlock *block;
GenerationChunk *chunk;
Size chunk_size = MAXALIGN(size);
- Size blockSize;
-
- blockSize = set->initBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
- if (chunk_size > (blockSize / 8))
+ if (chunk_size > set->allocChunkLimit)
{
Size blksize = chunk_size + Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
--
2.31.1
On Sat, 31 Jul 2021 at 14:34, Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:
I spent a bit of time hacking on the Generation context, adding the two
improvements discussed in this thread:1) internal handling of block sizes, similar to what AllocSet does (it
pretty much just copies parts of it)2) keeper block (we keep one empry block instead of freeing it)
3) I've also added allocChunkLimit, which makes it look a bit more like
AllocSet (instead of using just blockSize/8, which does not work too
well with dynamic blockSize)I haven't done any extensive tests on it, but it does pass check-world
with asserts etc. I haven't touched the comments, those need updating.
regards
Thanks for starting work on that. I've only had a quick look, but I
can have a more detailed look once you've got it more complete.
For now it does not really look like the keeper block stuff is wired
up the same way as in aset.c. I'd expect you to be allocating that in
the same malloc as you're using to allocate the context struct itself
in GenerationContextCreate().
Also, likely as a result of the above, minContextSize does not seem to
be wired up to anything apart from an Assert().
David
On Sat, 31 Jul 2021 at 08:38, Andres Freund <andres@anarazel.de> wrote:
There is at least one path using tuplecontext that reaches code that
could end up freeing memory to a significant enough degree to care about
generation.c effectively not using that memory:
tuplesort_putdatum()->datumCopy()->EOH_flatten_into()
On a quick look I didn't find any expanded record user that frees
nontrivial amounts of memory, but I didn't look all that carefully.
I guess we could just use a normal context for datum sorts if we
thought that might be a problem.
I'm not too familiar with the expanded object code, but I'm struggling
to imagine why anything would need to do a pfree in there. We just do
EOH_get_flat_size() to determine how big to make the allocation then
allocate some memory for EOH_flatten_into() to use to expand the
object into.
David
On 8/2/21 1:17 PM, David Rowley wrote:
On Sat, 31 Jul 2021 at 14:34, Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:I spent a bit of time hacking on the Generation context, adding the two
improvements discussed in this thread:1) internal handling of block sizes, similar to what AllocSet does (it
pretty much just copies parts of it)2) keeper block (we keep one empry block instead of freeing it)
3) I've also added allocChunkLimit, which makes it look a bit more like
AllocSet (instead of using just blockSize/8, which does not work too
well with dynamic blockSize)I haven't done any extensive tests on it, but it does pass check-world
with asserts etc. I haven't touched the comments, those need updating.
regardsThanks for starting work on that. I've only had a quick look, but I
can have a more detailed look once you've got it more complete.
A review would be nice, although it can wait - It'd be interesting to
know if those patches help with the workload(s) you've been looking at.
For now it does not really look like the keeper block stuff is wired
up the same way as in aset.c. I'd expect you to be allocating that in
the same malloc as you're using to allocate the context struct itself
in GenerationContextCreate().
Yes, that difference is natural. The AllocSet works a bit differently,
as it does not release the blocks (except during reset), while the
Generation context frees the blocks. So it seems pointless to use the
same "keeper" block as AllocSet - instead my intention was to keep one
"allocated" block as a cache, which should help with tight pfree/palloc
cycles. Maybe we should not call that "keeper" block?
Also, likely as a result of the above, minContextSize does not seem to
be wired up to anything apart from an Assert().
Hmm, yeah. This is probably due to copying some of the block-growth and
keeper block code from AllocSet. There should be just init/max block
size, I think.
I did run the same set of benchmarks as for Slab, measuring some usual
allocation patterns. The results for i5-2500k machine are attached (for
the xeon it's almost exactly the same behavior). While running those
tests I realized the last patch is wrong and sets allocChunkLimit=1,
which is bogus and causes significant regression. So here's an updated
version of the patch series too.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Attachments:
0001-generation-bench-v2.patchtext/x-patch; charset=UTF-8; name=0001-generation-bench-v2.patchDownload
From bf127426d5ad7add41a49cc80348233aa49e7d4e Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sat, 31 Jul 2021 22:55:36 +0200
Subject: [PATCH 1/4] generation bench
---
contrib/generation_bench/.gitignore | 4 +
contrib/generation_bench/Makefile | 21 +
contrib/generation_bench/bench.sql | 40 ++
.../generation_bench--1.0.sql | 16 +
contrib/generation_bench/generation_bench.c | 438 ++++++++++++++++++
.../generation_bench/generation_bench.control | 4 +
6 files changed, 523 insertions(+)
create mode 100644 contrib/generation_bench/.gitignore
create mode 100644 contrib/generation_bench/Makefile
create mode 100644 contrib/generation_bench/bench.sql
create mode 100644 contrib/generation_bench/generation_bench--1.0.sql
create mode 100644 contrib/generation_bench/generation_bench.c
create mode 100644 contrib/generation_bench/generation_bench.control
diff --git a/contrib/generation_bench/.gitignore b/contrib/generation_bench/.gitignore
new file mode 100644
index 0000000000..5dcb3ff972
--- /dev/null
+++ b/contrib/generation_bench/.gitignore
@@ -0,0 +1,4 @@
+# Generated subdirectories
+/log/
+/results/
+/tmp_check/
diff --git a/contrib/generation_bench/Makefile b/contrib/generation_bench/Makefile
new file mode 100644
index 0000000000..0fee5b84db
--- /dev/null
+++ b/contrib/generation_bench/Makefile
@@ -0,0 +1,21 @@
+# contrib/generation_bench/Makefile
+
+MODULE_big = generation_bench
+OBJS = generation_bench.o
+
+EXTENSION = generation_bench
+DATA = generation_bench--1.0.sql
+PGFILEDESC = "generation_bench - slab context benchmarking functions"
+
+REGRESS = generation_bench
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/generation_bench
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/generation_bench/bench.sql b/contrib/generation_bench/bench.sql
new file mode 100644
index 0000000000..abf3511047
--- /dev/null
+++ b/contrib/generation_bench/bench.sql
@@ -0,0 +1,40 @@
+CREATE EXTENSION generation_bench;
+
+\o fifo-no-loops.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_fifo(1000000, block_size, chunk_size, 2*chunk_size, 0, 0, 0) x;
+
+\o lifo-no-loops.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_lifo(1000000, block_size, chunk_size, 2*chunk_size, 0, 0, 0) x;
+
+\o random-no-loops.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_random(1000000, block_size, chunk_size, 2*chunk_size, 0, 0, 0) x;
+
+
+\o fifo-increase.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_fifo(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 15000) x;
+
+\o lifo-increase.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_lifo(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 15000) x;
+
+\o random-increase.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_random(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 15000) x;
+
+
+\o fifo-decrease.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_fifo(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 5000) x;
+
+\o lifo-decrease.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_lifo(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 5000) x;
+
+\o random-decrease.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_random(1000000, block_size, chunk_size, 2*chunk_size, 100, 10000, 5000) x;
+
+
+\o fifo-cycle.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_fifo(1000, block_size, chunk_size, 2*chunk_size, 10000, 1000, 1000) x;
+
+\o lifo-cycle.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_lifo(1000, block_size, chunk_size, 2*chunk_size, 10000, 1000, 1000) x;
+
+\o random-cycle.data
+select run, block_size, chunk_size, 2*chunk_size, 1000000 * chunk_size, x.* from generate_series(1,5) r(run), generate_series(32,512,32) a(chunk_size), (values (1024), (2048), (4096), (8192), (16384), (32768)) AS b(block_size), lateral generation_bench_random(1000, block_size, chunk_size, 2*chunk_size, 10000, 1000, 1000) x;
diff --git a/contrib/generation_bench/generation_bench--1.0.sql b/contrib/generation_bench/generation_bench--1.0.sql
new file mode 100644
index 0000000000..5f7c46eef2
--- /dev/null
+++ b/contrib/generation_bench/generation_bench--1.0.sql
@@ -0,0 +1,16 @@
+/* generation_bench--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION generation_bench" to load this file. \quit
+
+CREATE FUNCTION generation_bench_random(nallocs bigint, block_size bigint, min_alloc_size bigint, max_alloc_size bigint, loops int, free_cnt int, alloc_cnt int, out mem_allocated bigint, out alloc_ms bigint, out free_ms bigint)
+AS 'MODULE_PATHNAME', 'generation_bench_random'
+LANGUAGE C VOLATILE STRICT;
+
+CREATE FUNCTION generation_bench_fifo(nallocs bigint, block_size bigint, min_alloc_size bigint, max_alloc_size bigint, loops int, free_cnt int, alloc_cnt int, out mem_allocated bigint, out alloc_ms bigint, out free_ms bigint)
+AS 'MODULE_PATHNAME', 'generation_bench_fifo'
+LANGUAGE C VOLATILE STRICT;
+
+CREATE FUNCTION generation_bench_lifo(nallocs bigint, block_size bigint, min_alloc_size bigint, max_alloc_size bigint, loops int, free_cnt int, alloc_cnt int, out mem_allocated bigint, out alloc_ms bigint, out free_ms bigint)
+AS 'MODULE_PATHNAME', 'generation_bench_lifo'
+LANGUAGE C VOLATILE STRICT;
diff --git a/contrib/generation_bench/generation_bench.c b/contrib/generation_bench/generation_bench.c
new file mode 100644
index 0000000000..1cff55b751
--- /dev/null
+++ b/contrib/generation_bench/generation_bench.c
@@ -0,0 +1,438 @@
+/*-------------------------------------------------------------------------
+ *
+ * generation_bench.c
+ *
+ * helper functions to benchmark generation context with different workloads
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include <sys/time.h>
+
+#include "funcapi.h"
+#include "miscadmin.h"
+
+PG_MODULE_MAGIC;
+
+PG_FUNCTION_INFO_V1(generation_bench_random);
+PG_FUNCTION_INFO_V1(generation_bench_fifo);
+PG_FUNCTION_INFO_V1(generation_bench_lifo);
+
+typedef struct Chunk {
+ int random;
+ void *ptr;
+} Chunk;
+
+static int
+chunk_index_cmp(const void *a, const void *b)
+{
+ Chunk *ca = (Chunk *) a;
+ Chunk *cb = (Chunk *) b;
+
+ if (ca->random < cb->random)
+ return -1;
+ else if (ca->random > cb->random)
+ return 1;
+
+ return 0;
+}
+
+Datum
+generation_bench_random(PG_FUNCTION_ARGS)
+{
+ MemoryContext cxt,
+ oldcxt;
+ Chunk *chunks;
+ int64 i, j;
+ int64 nallocs = PG_GETARG_INT64(0);
+ int64 blockSize = PG_GETARG_INT64(1);
+ int64 minChunkSize = PG_GETARG_INT64(2);
+ int64 maxChunkSize = PG_GETARG_INT64(3);
+
+ int nloops = PG_GETARG_INT32(4);
+ int free_cnt = PG_GETARG_INT32(5);
+ int alloc_cnt = PG_GETARG_INT32(6);
+
+ struct timeval start_time,
+ end_time;
+ int64 alloc_time = 0,
+ free_time = 0;
+ int64 mem_allocated;
+
+ TupleDesc tupdesc;
+ Datum result;
+ HeapTuple tuple;
+ Datum values[9];
+ bool nulls[9];
+
+ int maxchunks;
+
+ maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
+
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+
+ chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
+
+ /* allocate the chunks in random order */
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ gettimeofday(&start_time, NULL);
+
+ for (i = 0; i < nallocs; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = MemoryContextMemAllocated(cxt, true);
+
+ /* do the requested number of free/alloc loops */
+ for (j = 0; j < nloops; j++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ /* randomize the indexes */
+ for (i = 0; i < nallocs; i++)
+ chunks[i].random = random();
+
+ qsort(chunks, nallocs, sizeof(Chunk), chunk_index_cmp);
+
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 0; i < Min(nallocs, free_cnt); i++)
+ pfree(chunks[i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs -= Min(nallocs, free_cnt);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ memmove(chunks, &chunks[free_cnt], nallocs * sizeof(Chunk));
+
+
+ /* allocate alloc_cnt chunks at the end */
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 0; i < alloc_cnt; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[nallocs + i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs += alloc_cnt;
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = Max(mem_allocated, MemoryContextMemAllocated(cxt, true));
+ }
+
+ /* release the chunks in random order */
+ for (i = 0; i < nallocs; i++)
+ chunks[i].random = random();
+
+ qsort(chunks, nallocs, sizeof(Chunk), chunk_index_cmp);
+
+ gettimeofday(&start_time, NULL);
+
+ for (i = 0; i < nallocs; i++)
+ pfree(chunks[i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ /* Build a tuple descriptor for our result type */
+ if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
+ elog(ERROR, "return type must be a row type");
+
+ values[0] = Int64GetDatum(mem_allocated);
+ values[1] = Int64GetDatum(alloc_time);
+ values[2] = Int64GetDatum(free_time);
+
+ memset(nulls, 0, sizeof(nulls));
+
+ tuple = heap_form_tuple(tupdesc, values, nulls);
+ result = HeapTupleGetDatum(tuple);
+
+ PG_RETURN_DATUM(result);
+}
+
+Datum
+generation_bench_fifo(PG_FUNCTION_ARGS)
+{
+ MemoryContext cxt,
+ oldcxt;
+ Chunk *chunks;
+ int64 i, j;
+ int64 nallocs = PG_GETARG_INT64(0);
+ int64 blockSize = PG_GETARG_INT64(1);
+ int64 minChunkSize = PG_GETARG_INT64(2);
+ int64 maxChunkSize = PG_GETARG_INT64(3);
+
+ int nloops = PG_GETARG_INT32(4);
+ int free_cnt = PG_GETARG_INT32(5);
+ int alloc_cnt = PG_GETARG_INT32(6);
+
+ struct timeval start_time,
+ end_time;
+ int64 alloc_time = 0,
+ free_time = 0;
+ int64 mem_allocated;
+
+ TupleDesc tupdesc;
+ Datum result;
+ HeapTuple tuple;
+ Datum values[9];
+ bool nulls[9];
+
+ int maxchunks;
+
+ maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
+
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+
+ chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
+
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ gettimeofday(&start_time, NULL);
+
+ for (i = 0; i < nallocs; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = MemoryContextMemAllocated(cxt, true);
+
+
+ /* do the requested number of free/alloc loops */
+ for (j = 0; j < nloops; j++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 0; i < Min(nallocs, free_cnt); i++)
+ pfree(chunks[i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs -= Min(nallocs, free_cnt);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ memmove(chunks, &chunks[free_cnt], nallocs * sizeof(Chunk));
+
+ /* allocate alloc_cnt chunks at the end */
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 0; i < alloc_cnt; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[nallocs + i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs += alloc_cnt;
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = Max(mem_allocated, MemoryContextMemAllocated(cxt, true));
+ }
+
+
+ gettimeofday(&start_time, NULL);
+
+ for (i = 0; i < nallocs; i++)
+ pfree(chunks[i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ /* Build a tuple descriptor for our result type */
+ if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
+ elog(ERROR, "return type must be a row type");
+
+ values[0] = Int64GetDatum(mem_allocated);
+ values[1] = Int64GetDatum(alloc_time);
+ values[2] = Int64GetDatum(free_time);
+
+ memset(nulls, 0, sizeof(nulls));
+
+ tuple = heap_form_tuple(tupdesc, values, nulls);
+ result = HeapTupleGetDatum(tuple);
+
+ PG_RETURN_DATUM(result);
+}
+
+Datum
+generation_bench_lifo(PG_FUNCTION_ARGS)
+{
+ MemoryContext cxt,
+ oldcxt;
+ Chunk *chunks;
+ int64 i, j;
+ int64 nallocs = PG_GETARG_INT64(0);
+ int64 blockSize = PG_GETARG_INT64(1);
+ int64 minChunkSize = PG_GETARG_INT64(2);
+ int64 maxChunkSize = PG_GETARG_INT64(3);
+
+ int nloops = PG_GETARG_INT32(4);
+ int free_cnt = PG_GETARG_INT32(5);
+ int alloc_cnt = PG_GETARG_INT32(6);
+
+ struct timeval start_time,
+ end_time;
+ int64 alloc_time = 0,
+ free_time = 0;
+ int64 mem_allocated;
+
+ TupleDesc tupdesc;
+ Datum result;
+ HeapTuple tuple;
+ Datum values[9];
+ bool nulls[9];
+
+ int maxchunks;
+
+ maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
+
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+
+ chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
+
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ /* palloc benchmark */
+ gettimeofday(&start_time, NULL);
+
+ for (i = 0; i < nallocs; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = MemoryContextMemAllocated(cxt, true);
+
+
+ /* do the requested number of free/alloc loops */
+ for (j = 0; j < nloops; j++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ oldcxt = MemoryContextSwitchTo(cxt);
+
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 1; i <= Min(nallocs, free_cnt); i++)
+ pfree(chunks[nallocs - i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs -= Min(nallocs, free_cnt);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ /* allocate alloc_cnt chunks at the end */
+ gettimeofday(&start_time, NULL);
+
+ /* free the first free_cnt chunks */
+ for (i = 0; i < alloc_cnt; i++)
+ {
+ int chunkSize = minChunkSize + random() % (maxChunkSize - minChunkSize);
+
+ chunks[nallocs + i].ptr = palloc(chunkSize);
+ }
+
+ gettimeofday(&end_time, NULL);
+
+ nallocs += alloc_cnt;
+
+ alloc_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ mem_allocated = Max(mem_allocated, MemoryContextMemAllocated(cxt, true));
+ }
+
+
+ gettimeofday(&start_time, NULL);
+
+ for (i = (nallocs - 1); i >= 0; i--)
+ pfree(chunks[i].ptr);
+
+ gettimeofday(&end_time, NULL);
+
+ free_time += (end_time.tv_sec - start_time.tv_sec) * 1000000L +
+ (end_time.tv_usec - start_time.tv_usec);
+
+ /* Build a tuple descriptor for our result type */
+ if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
+ elog(ERROR, "return type must be a row type");
+
+ values[0] = Int64GetDatum(mem_allocated);
+ values[1] = Int64GetDatum(alloc_time);
+ values[2] = Int64GetDatum(free_time);
+
+ memset(nulls, 0, sizeof(nulls));
+
+ tuple = heap_form_tuple(tupdesc, values, nulls);
+ result = HeapTupleGetDatum(tuple);
+
+ MemoryContextDelete(cxt);
+
+ PG_RETURN_DATUM(result);
+}
diff --git a/contrib/generation_bench/generation_bench.control b/contrib/generation_bench/generation_bench.control
new file mode 100644
index 0000000000..8c81e22e6b
--- /dev/null
+++ b/contrib/generation_bench/generation_bench.control
@@ -0,0 +1,4 @@
+# generation_bench extension
+comment = 'functions for benchmarking generation context'
+default_version = '1.0'
+module_pathname = '$libdir/generation_bench'
--
2.31.1
0002-Generation-grow-blocks-v2.patchtext/x-patch; charset=UTF-8; name=0002-Generation-grow-blocks-v2.patchDownload
From 3f858dfa27bd4faca7898d5edda1be5e60bb60cc Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Fri, 30 Jul 2021 23:53:52 +0200
Subject: [PATCH 2/4] Generation: grow blocks
---
contrib/generation_bench/generation_bench.c | 6 +--
src/backend/access/gist/gistvacuum.c | 2 +-
.../replication/logical/reorderbuffer.c | 2 +-
src/backend/utils/mmgr/generation.c | 53 ++++++++++++++-----
src/include/utils/memutils.h | 4 +-
5 files changed, 47 insertions(+), 20 deletions(-)
diff --git a/contrib/generation_bench/generation_bench.c b/contrib/generation_bench/generation_bench.c
index 1cff55b751..bc3d631205 100644
--- a/contrib/generation_bench/generation_bench.c
+++ b/contrib/generation_bench/generation_bench.c
@@ -69,7 +69,7 @@ generation_bench_random(PG_FUNCTION_ARGS)
maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
- cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize, blockSize, 1024L * 1024L);
chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
@@ -210,7 +210,7 @@ generation_bench_fifo(PG_FUNCTION_ARGS)
maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
- cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize, blockSize, 1024L * 1024L);
chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
@@ -339,7 +339,7 @@ generation_bench_lifo(PG_FUNCTION_ARGS)
maxchunks = nallocs + nloops * Max(0, alloc_cnt - free_cnt);
- cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize);
+ cxt = GenerationContextCreate(CurrentMemoryContext, "generation_bench", blockSize, blockSize, 1024L * 1024L);
chunks = (Chunk *) palloc(maxchunks * sizeof(Chunk));
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.c
index 0663193531..1818ed06fc 100644
--- a/src/backend/access/gist/gistvacuum.c
+++ b/src/backend/access/gist/gistvacuum.c
@@ -161,7 +161,7 @@ gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
*/
vstate.page_set_context = GenerationContextCreate(CurrentMemoryContext,
"GiST VACUUM page set context",
- 16 * 1024);
+ ALLOCSET_DEFAULT_SIZES);
oldctx = MemoryContextSwitchTo(vstate.page_set_context);
vstate.internal_page_set = intset_create();
vstate.empty_leaf_set = intset_create();
diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c
index 7378beb684..308d833292 100644
--- a/src/backend/replication/logical/reorderbuffer.c
+++ b/src/backend/replication/logical/reorderbuffer.c
@@ -329,7 +329,7 @@ ReorderBufferAllocate(void)
buffer->tup_context = GenerationContextCreate(new_ctx,
"Tuples",
- SLAB_LARGE_BLOCK_SIZE);
+ ALLOCSET_DEFAULT_SIZES);
hash_ctl.keysize = sizeof(TransactionId);
hash_ctl.entrysize = sizeof(ReorderBufferTXNByIdEnt);
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 584cd614da..771a2525ca 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -60,7 +60,9 @@ typedef struct GenerationContext
MemoryContextData header; /* Standard memory-context fields */
/* Generational context parameters */
- Size blockSize; /* standard block size */
+ Size initBlockSize; /* initial block size */
+ Size maxBlockSize; /* maximum block size */
+ Size nextBlockSize; /* next block size to allocate */
GenerationBlock *block; /* current (most recently allocated) block */
dlist_head blocks; /* list of blocks */
@@ -196,7 +198,9 @@ static const MemoryContextMethods GenerationMethods = {
MemoryContext
GenerationContextCreate(MemoryContext parent,
const char *name,
- Size blockSize)
+ Size minContextSize,
+ Size initBlockSize,
+ Size maxBlockSize)
{
GenerationContext *set;
@@ -208,16 +212,20 @@ GenerationContextCreate(MemoryContext parent,
"padding calculation in GenerationChunk is wrong");
/*
- * First, validate allocation parameters. (If we're going to throw an
- * error, we should do so before the context is created, not after.) We
- * somewhat arbitrarily enforce a minimum 1K block size, mostly because
- * that's what AllocSet does.
+ * First, validate allocation parameters. Once these were regular runtime
+ * test and elog's, but in practice Asserts seem sufficient because nobody
+ * varies their parameters at runtime. We somewhat arbitrarily enforce a
+ * minimum 1K block size.
*/
- if (blockSize != MAXALIGN(blockSize) ||
- blockSize < 1024 ||
- !AllocHugeSizeIsValid(blockSize))
- elog(ERROR, "invalid blockSize for memory context: %zu",
- blockSize);
+ Assert(initBlockSize == MAXALIGN(initBlockSize) &&
+ initBlockSize >= 1024);
+ Assert(maxBlockSize == MAXALIGN(maxBlockSize) &&
+ maxBlockSize >= initBlockSize &&
+ AllocHugeSizeIsValid(maxBlockSize)); /* must be safe to double */
+ Assert(minContextSize == 0 ||
+ (minContextSize == MAXALIGN(minContextSize) &&
+ minContextSize >= 1024 &&
+ minContextSize <= maxBlockSize));
/*
* Allocate the context header. Unlike aset.c, we never try to combine
@@ -242,7 +250,9 @@ GenerationContextCreate(MemoryContext parent,
*/
/* Fill in GenerationContext-specific header fields */
- set->blockSize = blockSize;
+ set->initBlockSize = initBlockSize;
+ set->maxBlockSize = maxBlockSize;
+ set->nextBlockSize = initBlockSize;
set->block = NULL;
dlist_init(&set->blocks);
@@ -293,6 +303,9 @@ GenerationReset(MemoryContext context)
set->block = NULL;
+ /* Reset block size allocation sequence, too */
+ set->nextBlockSize = set->initBlockSize;
+
Assert(dlist_is_empty(&set->blocks));
}
@@ -329,9 +342,12 @@ GenerationAlloc(MemoryContext context, Size size)
GenerationBlock *block;
GenerationChunk *chunk;
Size chunk_size = MAXALIGN(size);
+ Size blockSize;
+
+ blockSize = (set->block) ? set->block->blksize : set->nextBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
- if (chunk_size > set->blockSize / 8)
+ if (chunk_size > (blockSize / 8))
{
Size blksize = chunk_size + Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
@@ -387,7 +403,16 @@ GenerationAlloc(MemoryContext context, Size size)
if ((block == NULL) ||
(block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
{
- Size blksize = set->blockSize;
+ Size blksize;
+
+ /*
+ * The first such block has size initBlockSize, and we double the
+ * space in each succeeding block, but not more than maxBlockSize.
+ */
+ blksize = set->nextBlockSize;
+ set->nextBlockSize <<= 1;
+ if (set->nextBlockSize > set->maxBlockSize)
+ set->nextBlockSize = set->maxBlockSize;
block = (GenerationBlock *) malloc(blksize);
diff --git a/src/include/utils/memutils.h b/src/include/utils/memutils.h
index ff872274d4..514c0bf75b 100644
--- a/src/include/utils/memutils.h
+++ b/src/include/utils/memutils.h
@@ -183,7 +183,9 @@ extern MemoryContext SlabContextCreate(MemoryContext parent,
/* generation.c */
extern MemoryContext GenerationContextCreate(MemoryContext parent,
const char *name,
- Size blockSize);
+ Size minContextSize,
+ Size initBlockSize,
+ Size maxBlockSize);
/*
* Recommended default alloc parameters, suitable for "ordinary" contexts
--
2.31.1
0003-Generation-keeper-block-v2.patchtext/x-patch; charset=UTF-8; name=0003-Generation-keeper-block-v2.patchDownload
From e27b30bfb7b179b6a1b47c4907e562521e6fb5cd Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sat, 31 Jul 2021 02:54:36 +0200
Subject: [PATCH 3/4] Generation: keeper block
---
src/backend/utils/mmgr/generation.c | 61 +++++++++++++++++++++++++----
1 file changed, 54 insertions(+), 7 deletions(-)
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 771a2525ca..6c90416e27 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -65,6 +65,7 @@ typedef struct GenerationContext
Size nextBlockSize; /* next block size to allocate */
GenerationBlock *block; /* current (most recently allocated) block */
+ GenerationBlock *keeper; /* keeper block */
dlist_head blocks; /* list of blocks */
} GenerationContext;
@@ -254,6 +255,7 @@ GenerationContextCreate(MemoryContext parent,
set->maxBlockSize = maxBlockSize;
set->nextBlockSize = initBlockSize;
set->block = NULL;
+ set->keeper = NULL;
dlist_init(&set->blocks);
/* Finally, do the type-independent part of context creation */
@@ -302,6 +304,7 @@ GenerationReset(MemoryContext context)
}
set->block = NULL;
+ set->keeper = NULL;
/* Reset block size allocation sequence, too */
set->nextBlockSize = set->initBlockSize;
@@ -344,7 +347,7 @@ GenerationAlloc(MemoryContext context, Size size)
Size chunk_size = MAXALIGN(size);
Size blockSize;
- blockSize = (set->block) ? set->block->blksize : set->nextBlockSize;
+ blockSize = set->initBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
if (chunk_size > (blockSize / 8))
@@ -400,6 +403,26 @@ GenerationAlloc(MemoryContext context, Size size)
*/
block = set->block;
+ /*
+ * If we can't use the current block, and we have a keeper block with
+ * enough free space in it, use it as the block.
+ *
+ * XXX We don't want to do this when there's not enough free space
+ * (although the keeper block should be empty, so not sure if checking
+ * the space in the keeper block is necessary).
+ */
+ if (((block == NULL) ||
+ (block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size) &&
+ (set->keeper != NULL) &&
+ (set->keeper->endptr - set->keeper->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
+ {
+ block = set->keeper;
+ set->keeper = NULL;
+
+ /* keeper block was not counted as allocated, so add it back */
+ context->mem_allocated += block->blksize;
+ }
+
if ((block == NULL) ||
(block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
{
@@ -524,16 +547,34 @@ GenerationFree(MemoryContext context, void *pointer)
if (block->nfree < block->nchunks)
return;
+ /* Also make sure the block is not marked as the current block. */
+ if (set->block == block)
+ set->block = NULL;
+
+ /* Keep the block for reuse, if we don't have one already. */
+ if (!set->keeper && block->blksize <= set->maxBlockSize)
+ {
+ /* reset the pointers before we use it as keeper block */
+ block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
+ block->endptr = ((char *) block) + block->blksize;
+
+ block->nfree = 0;
+ block->nchunks = 0;
+
+ set->keeper = block;
+
+ /* keeper block is not counted as allocated */
+ context->mem_allocated -= block->blksize;
+
+ return;
+ }
+
/*
* The block is empty, so let's get rid of it. First remove it from the
* list of blocks, then return it to malloc().
*/
dlist_delete(&block->node);
- /* Also make sure the block is not marked as the current block. */
- if (set->block == block)
- set->block = NULL;
-
context->mem_allocated -= block->blksize;
free(block);
}
@@ -770,13 +811,19 @@ GenerationCheck(MemoryContext context)
nchunks;
char *ptr;
- total_allocated += block->blksize;
+ /*
+ * The keeper block in the list of blocks, but we don't consider it
+ * as allocated in memory accounting. So don't include it in the sum.
+ */
+ if (block != gen->keeper)
+ total_allocated += block->blksize;
/*
* nfree > nchunks is surely wrong, and we don't expect to see
* equality either, because such a block should have gotten freed.
*/
- if (block->nfree >= block->nchunks)
+ if ((block->nfree > block->nchunks) &&
+ ((block != gen->keeper) && (block->nfree == block->nchunks)))
elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p exceeds %d allocated",
name, block->nfree, block, block->nchunks);
--
2.31.1
0004-Generation-allocChunkLimit-v2.patchtext/x-patch; charset=UTF-8; name=0004-Generation-allocChunkLimit-v2.patchDownload
From 5de9bdbb42874a8b2706a80f4977c6009dfabbbf Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sat, 31 Jul 2021 03:20:56 +0200
Subject: [PATCH 4/4] Generation: allocChunkLimit
---
src/backend/utils/mmgr/generation.c | 28 ++++++++++++++++++++++++----
1 file changed, 24 insertions(+), 4 deletions(-)
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index 6c90416e27..2c98877953 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -46,6 +46,8 @@
#define Generation_BLOCKHDRSZ MAXALIGN(sizeof(GenerationBlock))
#define Generation_CHUNKHDRSZ sizeof(GenerationChunk)
+#define Generation_CHUNK_FRACTION 8
+
typedef struct GenerationBlock GenerationBlock; /* forward reference */
typedef struct GenerationChunk GenerationChunk;
@@ -63,6 +65,7 @@ typedef struct GenerationContext
Size initBlockSize; /* initial block size */
Size maxBlockSize; /* maximum block size */
Size nextBlockSize; /* next block size to allocate */
+ Size allocChunkLimit; /* effective chunk size limit */
GenerationBlock *block; /* current (most recently allocated) block */
GenerationBlock *keeper; /* keeper block */
@@ -254,6 +257,17 @@ GenerationContextCreate(MemoryContext parent,
set->initBlockSize = initBlockSize;
set->maxBlockSize = maxBlockSize;
set->nextBlockSize = initBlockSize;
+
+ /*
+ * Compute the allocation chunk size limit for this context.
+ *
+ * Follows similar ideas as AllocSet, see aset.c for details ...
+ */
+ set->allocChunkLimit = maxBlockSize;
+ while ((Size) (set->allocChunkLimit + Generation_CHUNKHDRSZ) >
+ (Size) ((Size) (maxBlockSize - Generation_BLOCKHDRSZ) / Generation_CHUNK_FRACTION))
+ set->allocChunkLimit >>= 1;
+
set->block = NULL;
set->keeper = NULL;
dlist_init(&set->blocks);
@@ -345,12 +359,9 @@ GenerationAlloc(MemoryContext context, Size size)
GenerationBlock *block;
GenerationChunk *chunk;
Size chunk_size = MAXALIGN(size);
- Size blockSize;
-
- blockSize = set->initBlockSize;
/* is it an over-sized chunk? if yes, allocate special block */
- if (chunk_size > (blockSize / 8))
+ if (chunk_size > set->allocChunkLimit)
{
Size blksize = chunk_size + Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
@@ -427,6 +438,7 @@ GenerationAlloc(MemoryContext context, Size size)
(block->endptr - block->freeptr) < Generation_CHUNKHDRSZ + chunk_size)
{
Size blksize;
+ Size required_size;
/*
* The first such block has size initBlockSize, and we double the
@@ -437,6 +449,14 @@ GenerationAlloc(MemoryContext context, Size size)
if (set->nextBlockSize > set->maxBlockSize)
set->nextBlockSize = set->maxBlockSize;
+ /*
+ * If initBlockSize is less than ALLOC_CHUNK_LIMIT, we could need more
+ * space... but try to keep it a power of 2.
+ */
+ required_size = chunk_size + Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
+ while (blksize < required_size)
+ blksize <<= 1;
+
block = (GenerationBlock *) malloc(blksize);
if (block == NULL)
--
2.31.1
generation i5.odsapplication/vnd.oasis.opendocument.spreadsheet; name="generation i5.ods"Download
PK �nS�l9�. . mimetypeapplication/vnd.oasis.opendocument.spreadsheetPK �nS�+ Thumbnails/thumbnail.png�PNG
IHDR � � *��- ZPLTE""")))555<<<DDDKKKSSSZZZbbbkkksss{{{������������������������������������������������ ������ tIDATx��]�����L���o����n ;������3�������T�*�������D�}�&��J��F�u�������`r�_�'��=��o:�~�g��aYg����E7�i�y���Z$���B�r�2�gg0�e�7o�+u���M��oi��n��k�����x#k�25y��)q��nA�������h�����E��@;7ev��Z8�X�vn��iG���kK.�C��h�_�^@i�SAM�h�`���y����v�m�-^���"[���;Z��`yRW/����*"o���%BK�k��i��������pmS��8o*7�_���-���fe���S+u;Z�L�N%��e;����D
Li�>[���h�]0V����U���+��V���"aM^������3~H�?��b��-
���yh�J����=��`S���m�x�����O����/ W9W�g�5fs�o�9s��S��Z����S����@�� 0^6Y�I�,\1,�Uh��pgF[��&m��
h���FmZy���he�W��U�@�r��-�)���AKB�����r���N�9��t+�[]���Oo~X���YCU�U��@n~��n>f��UT5�'_2��
*��f+PB�_��F���E
� ��O�/D��A4�������o����6��" f�-�Zci��u����yk�b)=�����2�Pb�yGdsd��,1Vs���&I�i�s����k@���`�j�� :x2V�x�D�o|8�i~p�:����%p[��p�&�6�TF-mg������3G�[��b���������
,��2[����(sA-�]�q.Pn,8��{���nJ������2qJ0C!_a(����t)C�-� Z�{x2�(D�h����_?���9��w�.��s���CJ_B,U���.N�'����7L���Q���:;d]�>]Y���Y��92�
�{��
{���(����
����3�n�o��Hm����P�e�J^����.��@1L���<0`uZ�5s��9V`��#,yj��\��� za���[3�|�����*��MtN��+cnS�5���j���&6�C�����fY����TX���-I�-��O�^��"M��q�����m������iV%��V*%i�_s7Y��m��l/����B�'��q+S$����tnb�]��\��a�� ��O�/D�a0�����(�~G���m�P`^�Dk�XW�)�S��*����C�1��8CW}�_���9�G���@Z��N=�)PZJ����=���bJ��>��:iv ������GX
�X�a�i*VM<"�;b��s�:��c�44l{���Cf�>��<Ejk���VFX{�1?a�.�-zU�����woS��}�E��V*O&b���#��r>�[*�N���UN����y�?����)��!���T����b4pK���������g "�h.h�j��o�o�8���K�hO���A���m�9�����\�������1��8�X��d�hZ����R��������f6zuT��rf��JX��z��~jX
�S�z�[�yDX�bk��a�U�6�~���8��8O�SaZ�9r;�x���a6YO�
J�����"�]�>EX#E��]�Z��Uv
�T�&
k��C��9�V��,���E9@�Z����U}�jJD�E����u�kZJ
#q
t�N�B���S�4��?@@eg��+�����9�h_�vmUB����7���OI/h�>5_Z���*�mZ1e\�>�k�eic��p�������R����?5����f�����<[��0'�E��fC6�A�����
��j������HOq)x�,��r��c��K���>�#P��s�K��c�F;�y.��p�7��w��
~FXK��c$w
�4�ry�yDX��&�|��u�dhQ�;h<�d�����
�c���+����w�'?���r��;�=����k�f�����[�����n��f���i������cn�
��h��
{�$)�b�����(��a%�@����$Be�WE�����R�2`63�u���(�V��;�������C���K��a���n��p����k������X�%���y��OEXa�>kX����h{�u������D�a����r���]A(�=�kD��z�Q�����/���k����X���
�����ZT�-���-�����u��������&�T;]�r+�
��O��C��%@���#.vA�k��8����nPV(I�-�t�-�h\����% ����Jj��S�#\�#.%���jXP&=�?+].vv��$�|}?�d,��.����a�j�=����|�K@�9:{�1���Si�v V�Dz���A���K@
e��U}�K�|�p�5�w V���D� �������L����T��_���nu��X��t���8Cwt����3�_���.'�:�~;�%�0���h�����.����s��%@5M�p
���*�*�*�������.��D����4WJubP�c\�g� ����D
�Q�#�{]�C��}X�����)��%�M6..F����5�oq ���y�:��j��u�{]\�kX�Z��@<�� ��|��Y\�L*h�d��6����.p���`[HU�^�]\�H�H��8`�j���J���N����v'�
�U
Q��sT�� �!��f��{hv��m\�('_l��X�v6Pc��]�q�!�R�[*q@���.�nj��0y�,.�'��?��z�s�������(�K���S��)\���GX
�,�������O�iX
��iX%>d��7���M��84�y��5����j�xhXy���&M��@
+n^5Tg&�8�)p�3_3l%���L��<2nZ�)c*���
��������a��-�����R'��A��k�i*��bN��m��a
�����wjX��%e}�G���F���dU��'���E���%1*��m�����������au���g`�i�R�5C�'������i?=�u.5��5�e��5����T��iX������gw4Z���8j��fG��K���B{�/�(Ka�sun1�z7��.n��]��[���>�te�o�4����[�;xm��#����-�[@z��6cN���[�VhO�x�}�
LPY��.���?]J�k&j_�������1������L/�������C��g�
G����Ub��'����O��@�BH�p �;2]]�%Sd���q����4}�K������
���a��`��h��@��^��]vkXo%��3]��]��(&�]�iX�P"�Xq_�+�I�0�,� �r x���t ���t 8��h�G�}h��)�����p �����z}���%���tE%p5�$%�������.z�K .qq @�t� Je"P�=��sy��t�#��0�]���h�>��g�K���l�=��?\���Y�6����os ��Q"�t xC��8+���t��k����#3~d�*0������G�����3]�/Ng<G:e�������g�R���=�U�f�U]-�N�H�oI��7�I1����n;]N�'�}h7tv\����"�whX�X��`�N���d������`�b���~���[���)�'?|j�7����<�R��05�5��t���Y^��P��)��+d�����9<�.P�9��#��OV`YV�A��\�T�;sTX�G���ce[��a�����E�y]Ft�
PP u`����H�LR��2�>�k������:���f\$#�{���8�aNw���\���n�~'�'�:�~
� ��<=Ee�a������g�S������k���� ��F�\EY\�kF��+�n�����������a�h��T����$����S���Kbg�[`i�bC��}����q�����5�J#�g�e��V3��a�vC�q���y�S�kX�A�P�]�p33���8�����MQ;T&�'K>T&� M��$^`���^����hcOU[�:���#���l�+����/�HO[������xT����k'O>�������u��D�z{�s|��T}���G���v��5us���s����\m��UK���y����WT<d-�1����p�+�M����
���vq+zs��|��c��9RG�:�h�)�x����#���L���J�&��*��a���Fq�� )��O���1����������qk�9R�22��D��������Ri��W���M���s��Bf������#��z��I �����J�NhO�x����{�%�=m������*�W��7`}��$��S\�Y\�HxEWEX����>� T��<���@���m}�K����<'��%`~�%��V�r���0/.�
.�B6��pS�}.<��D(��LWy�����7x��
������)�kK��E���5���r ���]��jm.&��#+ZS_��e���j���j�Pn0%Z6\�d������8]N�'�}h7����:=a%������^e ]N7����[J�A���n%}(k.>�N�N�V�J�ON�V���mI�~Bz����;<����u����H����S*R���\3_"���_.�J��_�s2�kX��BlhX)��r����#Gj��j���Pab]�9�7�~����
+[��au�DXhp�Fa� JKA�'�PkF]��������������#�F��>I��9.���9~�V�wB{r������T���f�!g�����[����a��r�)�W��(�V�����#�:��Q�l�=�����������Y8�����W~���,�|D��+T>�a}p�����a��S'�WjX;���5t�H��lF����v�%,�4�������wi�K�SnZ��aM��V����aU�aE\�"RxK�+�vd��<Y1�����l�(^4vE_o�����n�'Pn�gU�����Z#|��n�p��z��l�R[J����-�E�39���J�o�o#?���]�hO����y����:;�T�=������ ����yn�cv�5���f�*
��������e>�����U2�%���+�Sx���I�������
��\�a�S5�u������#��o����v
k8V��#�0*���ae��3G���y�q:�p ���:4�s�q��u{Ht0G�=z^,�v�+���r����Oo~X���YC�T�U��i�X���b�_EU�-���lP�4����/���a=��hG�m�iu�{�����h���n�����.�����"1 J��P��LW�\f6e�����!a���f�pD����uDX]�v��%`B��t��K�
��i�BY����tev =�j�-zq 0&�K��dD�]�Ao�te���8���->����]:OB/.p������ ����eq �% ��/Z._*��*^�_����v�!�iH��|�Yw���]�h�����o�<�p�� IEND�B`�PK �nS settings.xml�W�r�@}���xO0����2f�q�MRb���Z��0M�Et�~�T���<)s9�9s���^-"����y�:9nZ
�>��z����������tJ}p�u\IP�,�
��K'��YZp����$�(���f��q��"�F����*;��$�q�>F1�O:�����,��O�lW�l�G*D|'J7d���Z����=[�u��iY�����w���U��4��ih=�P:s
��jV�����RI=d����T��LR��~�ko�|
�����4Pat��i�t��:;o^^�3�G��!fZe,���t�\����Y?�i.r�0�_T�e$o��wC" ��{���S�$T�x@������c�<m�w������X��I^��(�M ���x�����������(5(�5� �E�d
�#�rOpL�QA<�L��*��'����"����wD�!���T�},��?XPi��
��o���������\���V������)�GTPG�d�Y��C��4K���T�!2��-�|�:���2ul����Z��*Q�x4�:��o������2]���C&]�W���|%L�����fU�[Zd5���)������Y9�����1�3U�����l�Aq��0h�C�|]O_;��R�;o�H8?�����.F�1[�H7D��G:4�M�C�b2zb���XR�J�b{�k�.���PK��/� I PK �nS
styles.xml�]�s�6�~�F��$3�HI~H��L/mz�I<�&�}��$H�% Yv��[��� �mG��&�X��v�X�|���s{�����������oR���m��/��I���_7����g5����'�=h�������d�����3y8�qsF�'�fy���**��T�K�|k��jcA[h���{����C+���0�7��j����l���'%)]��s�_p�t}�Z
V�e�>�N���M6S�`�\Ie�:v��,������z�#U�m^$��c�
��b���H@]��j��m
���({��� ��@L��$q�U������|[�E�}'�G���}����T���LFe5#�|{Ji*�h
v)��0.��9G�j%_1�1�����&r�q���tC(4� \>�fB�F��:�e<�Vv��(����CU�&���ZRg����A�=�zU�e��OuI��_�
��.h�! �f��9�t`��oE�.?�Q�\�lV����v`�!9��J����T�Z6�j^����\����1�3��?tQ��Y�f�On2����iS�5mdb����o�����g!�m�gFx���#�SR��7�@ �J�z�����4��D�{��^s����W$�&��� �Z#�/�o���]���HO!��62} ���'������Z +Q�L>��I��(�J�����n��%�cI���L����<@9- '�C�U5p��f��#_�p���g� ��6�b68�Mg.��%r�������H���~��!�e��4 ����"��&���l�$���v�)���Y�U��I�@?����8�)�#B�����z��G|vhg�������g��C���f8f�%[��qr�R��N`��,�M>&u!6�o51�+�(�3`B����8���Q��+R �!�TX�%��=Em��1FR��x��"G��jov���"=4 ���V��j�h
N]S����Z���/V����sZ#����8����V�8$��3�v<�K�`��T���������B��K����X���������{��
����������2�+�����J�����Zpd���G����$p���t.�--`�e������m�S(�F��u��f}���mN}�$�����+�6�S���g��������6�N����� ��|w������@;�}�n~����X�5X���+{��_���-b�'5�'�R�4,�25�4���YU\�aU+ ��j�b�Sg�B���]O��O���~An�# ��D���H9@������1��^�}����e��3|:������l��tKhwI�<�)x��]�&�E��p�e���pq�!�*.�Kh��~��q)o�`���9�W`]p9Ug=�E�t����j����K�)����j�����1�hJ�'Zv��W��'��Y�����&��F&�`��]wcR=�#�}�fP���u�*�`
�\fC5fk�p�|���@u�q|��,��b����s�m��;�����,Crg�� ,�4������e���b��.c���b������.L�.>����Y��GX4n�������*;;K���F:��>�eX��,�O�N���)?��� �_H*~�)��i�0?���R��{���3���3�;�3��sF��j�_��9�i��CQYQ�x��b
��(�O}��0Ai���u��s�5����0��rR)=��5����K�[�(�ch1m��kI��ClI}z���VU���Ev�j����������qM�Xza�Vt�
��'$����"��2�D� ��v\a�,�p��X��#�k:�Z$�0��(z�N�'�u�}8�@������v�GG�~�G���4[9�����r����=l�����Gd=��e/wm�43+"��8�]��bPM�8T�u�+e��G�\�����%V���_J1w,?#{4�{J������!P��p����'�#�Ld���1��F����2��FzL��X�^
�����I��~��b�k��F���w,V�1n�r���?WW5�t�C�/9��%|*�L��?��^"�P�4kg�}�?����d��R�W�(;|DH~�k-$��l�f���� �g��w�ZVA�CZ_��8�/l:<2��1l�V[��A~{T�����
�%?��|"T��Et"~xG��Y�V��'I{E�]�qU��;f��*��_������R��/�;��C���K���-��r���B-�K&nY��c��� �t�7�
'����& SX�p�x�����Q��X�x�SK*���Tt��a����^(�B($���m_�E��-��~�li����4~������^��lXU��"b����p0������U.���(���Tm�����4�CY'R,���4���(�^1���Gj>��w�F��i�s�K�dEw���a��&�5�W�N��x�T�Q*���'�&^;����WC���=���w�qF �SF�Kh�
�������%�U��.���U����� R��FF�z�
M3�"-4����q�m���-{��olB�7��&���'8��[��'���Ca�"���B����h~T���2��j���{��8���}��F/�%A�%�r����D���������I��� ���"��A�G|Ap��
�I����B�M��
����'N��'���T )�X(��[�B��M�����;X�DQX��b���1������K!�?��A�����unT��x�� ������O��Q�Q|Q��Y<������k�B)U���q�%�]���vP"�+F�u�)~��uXE����f��%)_:\�r�����t��(���i�8��/����&�����W
g�j���d�62�s�q�����L�w$�������7�z�:X���U��PK�z�2[ �j PK �nS meta.xml��?o�0��~
�v���S��,U�H]Z�[��ukld���� 1�U��~��{�N�v�Zg4Vh��$�I���R�*'�o/�����L�N�#-5okT.������,K9i���Ya�b5Z�8�
*�B�4�F�"�����s
��.���6$i��P�h�'�i���J�,$Q���7T��#i�'�Cv�8^���te�R�[��.���9�v�$��?;����}�"�L���9a����;v�r�*����"G)����:^�
�����RL�6�B��9m��8|����(����i/T{9|l7��*�1���~$d�gP���{��PK8a�(: n PK �nS manifest.rdf���n�0��<�e��@/r(��j��5�X/������VQ�������F3�����a�����T4c)%�Hh��+:�.���:���+��j���*�wn*9_��-7l���(x��<O�"��8qH��� �Bi��|9�� fWQt���y� =��:���
a�R��� ��@� L��t��NK�3��Q9�����`����<`�+�������^����\��|�hz�czu����#�`�2�O��;y���.�����vDl@��g�����UG�PK��h� � PK �nS Configurations2/toolpanel/PK �nS Configurations2/statusbar/PK �nS Configurations2/progressbar/PK �nS Configurations2/toolbar/PK �nS Configurations2/popupmenu/PK �nS Configurations2/floater/PK �nS Configurations2/menubar/PK �nS META-INF/manifest.xml��Mn� ��9���2�YU(N�z�� �O�����WU�X��a���`�;;�� &��#��4��+�}G�_�'�mW'�hH�O����t;R"r/�I�����>