You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Use doubly-linked block lists in aset.c to reduce large-chunk overhead.
Large chunks (those too large for any palloc freelist) are managed asseparate blocks. Formerly, realloc'ing or pfree'ing such a chunk requiredO(N) time in a context with N blocks, since we had to traipse down thesingly-linked block list to locate the block's predecessor before we couldfix the list links. This can result in O(N^2) runtime in situations wherelarge numbers of such chunks are manipulated within one context. Caseslike that were not foreseen in the original design of aset.c, and indeeddidn't arise until fairly recently. But such problems can now occur inreorderbuffer.c and in hash joining, both of which make repeated largerequests without scaling up their request size as they do so, and whichwill 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'tseem like unacceptable overhead, since aset.c's blocks are normally8K or more, and never less than 1K in current practice.In passing, get rid of some redundant AllocChunkGetPointer() calls inAllocSetRealloc (the compiler might be smart enough to optimize theseaway anyway, but no need to assume that) and improve AllocSetCheck'schecking of block header fields.Back-patch to 9.4 where reorderbuffer.c appeared. We could take thisfurther back, but currently there's no evidence that it would be useful.Discussion:https://postgr.es/m/CAMkU=1x1hvue1XYrZoWk_omG0Ja5nBvTdvgrOeVkkeqs71CV8g@mail.gmail.com