[Tim]
> The radix tree generally appears to be a little more memory-frugal
> than my PR (presumably because my need to break "big pools" into 4K
> chunks, while the tree branch doesn't, buys the tree more space to
> actually store objects than it costs for the new tree).
It depends a whole lot on the size classes of the most popular
objects. A program below to compute it all. For a 64-bit box using
3.8 alignment, and 16 KiB pools:
pages per pool 4
pool size 16,384
alignment 16
The first output block:
size 16
SQ 1012 1.2%
PR 1018 0.6%
RT 1021 0.3%
SQ is the status quo: we have to use four separate 4 KiB pools, and
each burns 48 bytes for a pool header.
PR: my PR. There's one pool spanning 4 pages, with 48 bytes for a
pool header in the first page, and 16 bytes to store the arena index
in each of the other 3 pages.
RT: the radix tree. One 16 KiB block that only "wastes" 48 bytes for
the pool header.
The first number on each line is the number of objects we can get from
a "big pool" under that scheme. The second number is the % of total
pool space that cannot be use for client objects.
So, in the above, PR is a substantial improvement over SQ, and RT a
less substantial improvement over PR. Regardless of size class, PR
never does worse than SQ, and RT never worse than PR.
The most dramatic difference is in the largest size class:
size 512
SQ 28 12.5%
PR 28 12.5%
RT 31 3.1%
RT is a huge win there. And while it's generally true that RT's
advantages are more striking in the larger size classes, it doesn't
always crush. For example, in the 2nd-largest size class, it doesn't
matter at all which scheme is used:
size 496
SQ 32 3.1%
PR 32 3.1%
RT 32 3.1%
However, in the 3rd-largest size class, RT crushes it again:
size 480
SQ 32 6.2%
PR 32 6.2%
RT 34 0.4%
I trust the general principle at work here is too obvious to need
explanation ;-)
Anyway, these differences can really add up when there are millions of
objects passed out from a size class where RT has an advantage.
That's very attractive to me.
On the other hand, this _effectively_ make arenas even larger (they
can contain more objects), which apparently makes it even less likely
that arenas can eventually be returned to the system.
But, on the third hand, I've seen no evidence yet that increasing
arena size matters much at all to that after hitting 128 KiB arenas
(smaller than what we already use). "Uncooperative" programs
essentially recycle nothing regardless, and "happy" programs
essentially recycle almost as many arena bytes with 1 MiB arenas as
with 8 KiB arenas.
Here's the code:
PAGES_PER_POOL = 4
ALIGNMENT = 16 # change to 8 for < Python 3.8
PAGE_SIZE = 2**12
POOL_SIZE = PAGE_SIZE * PAGES_PER_POOL
POOL_HEADER_SIZE = 48
def from_block(size, blocksize, overhead):
return (blocksize - overhead) // size
def from_first_page(size, *, pagesize=PAGE_SIZE):
return from_block(size, pagesize, POOL_HEADER_SIZE)
# using multiple 4K one-page pools - status quo
def nobj_4K(size):
return from_first_page(size) * PAGES_PER_POOL
# using the PR
def nobj_PR(size):
return (from_first_page(size) +
from_block(size, PAGE_SIZE, ALIGNMENT)
* (PAGES_PER_POOL - 1))
# using the radix tree branch
def nobj_RT(size):
return from_first_page(size, pagesize=POOL_SIZE)
print("pages per pool", PAGES_PER_POOL)
print(f"pool size {POOL_SIZE:,}")
print("alignment", ALIGNMENT)
for size in range(ALIGNMENT, 512 + 1, ALIGNMENT):
print("size", size)
for tag, f in (("SQ", nobj_4K),
("PR", nobj_PR),
("RT", nobj_RT),
):
nobj = f(size)
waste = POOL_SIZE - nobj * size
print(f" {tag} {nobj:4} {waste/POOL_SIZE:5.1%}")
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/S5KMU6M6GZACRNFCF3TNPE7NKDCMQD5E/
