Use doubly-linked block lists in aset.c to reduce large-chunk overhead.
authorTom Lane
Wed, 8 Mar 2017 17:21:12 +0000 (12:21 -0500)
committerTom Lane
Wed, 8 Mar 2017 17:21:12 +0000 (12:21 -0500)
commit8dd5c4171fb2c3b78e713c49f531ad8ff3b245ea
treeef8b6d89590288b4e58cbd73d2518ca222238cb5
parent9420ea88f95de86114f70460e7c86638330e7155
Use doubly-linked block lists in aset.c to reduce large-chunk overhead.

Large chunks (those too large for any palloc freelist) are managed as
separate blocks.  Formerly, realloc'ing or pfree'ing such a chunk required
O(N) time in a context with N blocks, since we had to traipse down the
singly-linked block list to locate the block's predecessor before we could
fix the list links.  This can result in O(N^2) runtime in situations where
large numbers of such chunks are manipulated within one context.  Cases
like that were not foreseen in the original design of aset.c, and indeed
didn't arise until fairly recently.  But such problems can now occur in
reorderbuffer.c and in hash joining, both of which make repeated large
requests without scaling up their request size as they do so, and which
will free their requests in not-necessarily-LIFO order.

To fix, change the block list from singly-linked to doubly-linked.
This adds another 4 or 8 bytes to ALLOC_BLOCKHDRSZ, but that doesn't
seem like unacceptable overhead, since aset.c's blocks are normally
8K or more, and never less than 1K in current practice.

In passing, get rid of some redundant AllocChunkGetPointer() calls in
AllocSetRealloc (the compiler might be smart enough to optimize these
away anyway, but no need to assume that) and improve AllocSetCheck's
checking of block header fields.

Back-patch to 9.4 where reorderbuffer.c appeared.  We could take this
further back, but currently there's no evidence that it would be useful.

Discussion: https://postgr.es/m/CAMkU=1x1hvue1XYrZoWk_omG0Ja5nBvTdvgrOeVkkeqs71CV8g@mail.gmail.com
src/backend/utils/mmgr/aset.c