Re: use radix tree for bitmap heap scan

>>> This is because today, a major cost of large BitmapIndexScans is
>>> repeatedly growing the simplehash.h-based hash table backing TIDBitmap
>>> from initially 128 elements to its final size.
>>
>> How much of a major cost?
>
> The "actual time" of the BIS in my test query dropped from 193 ms to 139
> ms when reserving all memory of the final hash table upfront by passing
> its final size to pagetable_create() in tbm_create_pagetable().
>
> Part of that time is spent on page faults because the allocations are
> big enough for ASET to call malloc() and for malloc() to call sbrk(),
> and then in the other direction for free() to call systrim() which calls
> sbrk() to shrink the heap again.
>
> This can be seen also from the perf stat output:
>
> 3,034 page-faults # 5114.8 faults/sec page_faults_per_second
>
> vs when reserving enough memory to avoid resizing
>
> 0 page-faults # 0.0 faults/sec page_faults_per_second
>
> I'm not entirely sure why it has 0 page faults for successive calls when
> I reserve a big hash table. It should still have to fault when writing
> to the pages of the initially reserved hash map. It seems to cache the
> allocation somehow as I no longer see calls to sbrk().
>
> My take away beyond the radix tree effort is that it would be useful if
> we could allocate anonymous and shared memory backed by 2 MiB huge
> pages. That would help for TIDBitmap but also for large sort buffers or
> large hash join hash tables. Shared allocations can end up in the main
> memory segment if dynamic_shared_memory_size is picked appropriately
> but, FWIR, anonymous memory is always 4k-backed.
Closer inspection revealed that all allocation functions that return
zeroed memory, such as palloc0(), palloc_extended(MCXT_ALLOC_ZERO),
repalloc0(), MemoryContextAllocZero(), etc., unconditionally call
memset() in the wrapper around the memory context, rather than leaving
that to the memory context.

Leaving the zeroing to the memory context would have the advantage of
the memory context being able to skip it, if it knows that the memory
it's going to return is already zeroed.

It would know that, for example, if we used calloc() to serve big zeroed
allocations. On Linux, calloc() skips zeroing the memory if it comes
fresh from sbrk or mmap (via the zero-fill-on-demand technique using a
zero page).

Performance is only one aspect here. The other aspect is memory
consumption: large zeroed allocations that is only sparsely written to
will unnecessarily get all pages faulted in which makes a difference
with vm.memory_overcommit = 0/1.

It could also prevent OOM situations: say we create a large simplehash.h
map, created based on estimated row count, but actual row count is much
lower.

--
David Geier