Re: Keep TIDBitmap pagetable memory across bitmap scans

On Tue, Nov 10, 2026, David Geier wrote:
> It's actually curious that it's that bad. All processes are independent
> so they have their own page tables, mm_struct lists, etc., all with
> their own locks. The kernel's page allocator should scale well enough to
> not cause that level of contention.

Hey David,

> I believe the folio_lruvec_lock_irqsave() stems from protecting the
> cgroup's memory accounting. Could you rerun your test without cgroups?

Sure, and guess what? It isn't the cgroup. Same host, same build, as
before and with glibc defaults, 96 clients, btree:

stock tps (faults/query) patched spinlock share
memcg on 2,746 (732) 4,284 29.5%
cgroup_disable=memory 2,874 (690) 4,273 27.4%

The memory controller costs about 5% here, but the contended lock is the
LRU list lock, and without memcg the lruvec is the node's. On a
one-socket host every backend still takes the same one, on every first
touch of a fresh page (lru_add) and again when brk trims the heap and
the pages are released.

To check that it isn't Linux-specific either, I ran the same test on
FreeBSD 14.5 on the same instance type. FreeBSD has no memcg. Its libc
malloc (jemalloc) keeps the memory and never stormed, so I forced the
same pattern with allocators that give memory back. With libumem
(4.3.2), which returns large frees with madvise(MADV_DONTNEED), DTrace
lockstat shows 87 s of spinning per 5 s on "vm active pagequeue", one
lock per memory domain, taken from madvise and from the fault path.
Stock btree there is 3,575 tps with 690 faults per query and 22% system
time; patched, 4,306 with 2. So it's a per-NUMA-node page queue lock
that every backend shares, on both kernels.

> glibc's malloc uses sbrk() by default. I haven't looked into why causes
> the documentation claims today it uses mmap().

Right, I should have been clearer: "a low mmap threshold" meant
MALLOC_MMAP_THRESHOLD_ set. With defaults, glibc's probes show brk: for
20 bitmap statements in one backend, 99 sbrk grows and 20 trims. The
mmap threshold starts at 128 kB but rises to the size of the largest
mmapped chunk freed, so by the time this matters, everything is on brk.

> It seems like there's a threshold that controls how aggressively malloc
> trims free memory that can be changed via mallopt(M_TRIM_THRESHOLD, -1).
> How about giving this a try and thinking about using it to our advantage.

On its own it doesn't help, and I didn't expect that. Setting
M_TRIM_THRESHOLD (or M_TOP_PAD, or M_MMAP_THRESHOLD) also turns off the
dynamic threshold, so the mmap threshold stays at 128 kB. Every array
over 128 kB then goes to mmap and munmap instead of brk, and faults the
same. 96 clients. btree: stock TPS (faults/query) [patched TPS]; the
other three: stock faults per query:

btree hash join sort hash agg
glibc defaults 2,758 (732) [4,278] 1,199 1,020 0
M_TRIM_THRESHOLD only 2,799 (726) [4,283] 0 620 600
M_TRIM + M_MMAP_THRESHOLD 4,040 (0) [4,272] 0 0 0
jemalloc 4,046 (7) [4,268] 350 12 3

Trim alone moves the faults around: hash join stops faulting and hash
aggregate starts. Setting both thresholds removes them everywhere and
matches jemalloc. (Our earlier "trim threshold" run had worked because it
also set a 64 MB top pad, which keeps malloc from ever reaching the code
that decides to mmap.)

> While I think the direction of keeping the memory around is the right
> one, I don't think we should do that at the Bitmap Index Scan (BIS)
> level for two reasons:
>
> 1. A database with lots of connections could quickly spent gigabytes on
> unused BIS buffers. Freeing the memory when unused quickly gets you
> into memory allocator territory.

The patch keeps at most work_mem per backend, and only in backends that
ran a large bitmap scan, so 800 MB for 200 such backends at the default.

For comparison, glibc with both thresholds set keeps whatever each
backend's high-water mark was, with no bound at all; jemalloc keeps
dirty pages for 10 s and then gives them back. But before you say it, I
agree the decay is better done by an allocator than by tidbitmap.c.

> 2. There are more places in the code where we double allocation sizes as
> we go and hence cause avalanches of page faults repeatedly. It would
> be good to fix them all in one go.

Yes. I added a hash join, a sort and a hash aggregate to the test.
With glibc defaults, the hash join faults 1,199 times per query and the
sort 1,020; the patch does nothing for either. They cost less in total
(4.5% and 9.7% system time against 33% for the bitmap scans), but it's
the same mechanism.

I agree a process-wide fix is the better target, and setting both glibc
thresholds at backend start would be a small one. The patch would still
be worth +5.5% to +11.8% on top of that, from skipping the rehash and
copy of the doubling, but that's a much smaller argument.

> Is anyone aware of an effort to change PostgreSQL to use e.g. jemalloc
> which better allows controlling when memory is returned?

One data point against just switching: mimalloc on FreeBSD gets 620 tps
on the btree query, against 3,982 with libc. mimalloc reserves its
arena in the postmaster, every backend inherits it, and on FreeBSD all
of them end up on one shared VM object. Every purge (madvise of 26 MB)
then takes that object's lock: 87% of all CPU time is spent spinning on
it. With MIMALLOC_PURGE_DELAY=-1 it gets 4,030. On Linux, mimalloc
behaves like glibc (724 faults per query). How an allocator interacts
with fork-without-exec is not something allocator benchmarks usually
measure and publicize.

On Tue, Nov 10, 2026, David Geier wrote in the radix tree thread:
> A shot into the dark: sbrk() can only shrink if there's no allocation
> sticking around after the freed memory. Maybe that causes the virtual
> memory to not be returned in some cases?

That's it. Twenty bitmaps inside one statement trim the heap once (788
faults); twenty separate statements trim it twenty times (14,659
faults). The heap only shrinks at statement end, when the query's other
memory above the freed arrays goes too.

> But it's curious that calloc() didn't help. Did you remove writing to the
> status byte after changing to calloc()?

Yes, that version used calloc() and wrote nothing itself. The inserts
touch every page anyway: 17k entries in 32,768 slots of 48 bytes, 85
slots per 4 kB page, so the chance of a page getting no entry is about
e^-44. Why calloc() faulted more than palloc0 (1,161 against 732 per
query) I still haven't tracked down.

> The more important part is that the radix tree grows incrementally while
> the hash map needs to double in size and then be rehashed. That lowers
> the number of page faults considerably.

The faults follow the memory touched per query, though, not the number
of grows. Presizing the table, so the final 1.5 MB is touched once,
took glibc with a low mmap threshold from 703 to 396 faults per query,
and musl from 768 to 424. I'd expect an incrementally grown tree whose
memory is given back after each query to land about there too: half the
faults, not none. That's inference; I haven't measured a radix tree.

So, where does all this digging this leave us? The kernel side is a
shared per-node lock, and memory given back per query hits it on both
Linux and FreeBSD. The fix probably belongs at the process level rather
than in tidbitmap.c, since hash join and sort have the same problem.

For glibc, setting M_MMAP_THRESHOLD and M_TRIM_THRESHOLD together is
enough; setting only one is not. I can look at what that would mean in
PostgreSQL (where to set it, and what bound to use) unless someone knows
a reason not to.

The setup: c7i.metal-24xl, Fedora 44 (kernel 7.3, glibc 2.43) and FreeBSD
14.5, stock and patched interleaved, two runs per side. libumem 4.3.2,
mimalloc 2.2.4 and jemalloc 5.3. The scripts and raw numbers are
available if anyone wants them.

best.

-greg