[Python-Dev] Re: radix tree arena map for obmalloc
[Tim]
>> At the start, obmalloc never returned arenas to the system. The vast
>> majority of users were fine with that.
[Neil]
> Yeah, I was totally fine with that back in the day. However, I
> wonder now if there is a stronger reason to try to free memory back
> to the OS. Years ago, people would typically have swap space that
> was as large or larger than their real RAM. So, if the OS had to
> swap out unused pages, it wasn't a big deal. Now that disks are
> relatively so much slower and RAM is larger, people don't have as
> much swap. Some Linux systems get setup without any. Freeing
> arenas seems more important than it used to be.
See my earlier "right thing to do ... anticipating" ;-) It was clear
enough then that processor speeds were going to continue to increase
much faster than disk speeds, although the _primary_ driver at the
time was the then-small but increasing number of long-running Python
programs running big (for the time) data-crunching problems that
repeatedly went through stages of low and high memory need.
> OTOH, I don't think obmalloc should try too hard. The whole point of
> the small object allocator is to be really fast. Anti-fragmentation
> heuristics are going to slow it down. As far as I'm concerned, it
> works well enough as it is.
Freeing arenas _already_ slowed it down. All the cruft to keep arenas
sorted by number of free pools was far from free. Before that, free
pools for a given size class were singly-linked together directly
(regardless of which arenas they were in), and we just used the head
of that list. Arenas weren't involved at all. Indeed, pools didn't
even point back to their arenas.
So major code and data changes were needed to implement the "take from
the non-full pool in the most heavily populated arena" heuristic. The
other heuristic worth considering is "take from the non-full pool with
the smallest arena address", which directly strives to let the
higher-addressed arenas free up.
Since they're both just poke-&-hope, it's hard to out-think them. But
it's possible one would consistently work better than the other, and
that even _which_ one could change depending on arena and pool sizes.
And should note that "poke-&-hope" is the best that can be hoped for,
since it's impossible to predict the lifetime of an object when space
for it is requested, and we can't move the object after its address is
returned to the caller.
More amusing: address_in_range() didn't exist either at first.
Instead a pool header contained its own address and a "magic"
constant. So, e.g.,
if (pool->pooladdr != pool || pool->magic != POOL_MAGIC) {
// This ain't ours! Pass it to the system malloc family instead.
}
That was unlikely to believe something that _had_ come from the system
malloc really belonged to obmalloc, but proved very easy to trick into
making that error, even from pure Python code.
Good times ;-)
___
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/GLE6UC7EKGZLBTFJVHUMMCKYXRRWU5GB/
[Python-Dev] Re: radix tree arena map for obmalloc
On 2019-06-15, Tim Peters wrote: > At the start, obmalloc never returned arenas to the system. The vast > majority of users were fine with that. Yeah, I was totally fine with that back in the day. However, I wonder now if there is a stronger reason to try to free memory back to the OS. Years ago, people would typically have swap space that was as large or larger than their real RAM. So, if the OS had to swap out unused pages, it wasn't a big deal. Now that disks are relatively so much slower and RAM is larger, people don't have as much swap. Some Linux systems get setup without any. Freeing arenas seems more important than it used to be. OTOH, I don't think obmalloc should try too hard. The whole point of the small object allocator is to be really fast. Anti-fragmentation heuristics are going to slow it down. As far as I'm concerned, it works well enough as it is. ___ 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/Z6O5HPSLQXNUHTY6GY7WN4KUB43J6QGV/
[Python-Dev] Re: radix tree arena map for obmalloc
On 2019-06-15, Antoine Pitrou wrote: > We should evaluate what problem we are trying to solve here, instead > of staring at micro-benchmark numbers on an idle system. I think a change to obmalloc is not going to get accepted unless we can show it doesn't hurt these micro-benchmarks. To displace the status quo, it has to give other advantages as well. I don't have any agenda or "problem to solve". After Tim made a PR to allow obmalloc to use larger pools, I thought it would be interesting to see if a arena mapping scheme based on radix trees should be performance competitive. I'm not proposing any changes to CPython at this point. I'm sharing the results of an experiment. I thought it was interesting. I guess you don't. ___ 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/6PZU7UYGG5VCZTC4PAYDDU456SS3YTGT/
[Python-Dev] Re: radix tree arena map for obmalloc
[Tim. to Neil] >> Moving to bigger pools and bigger arenas are pretty much no-brainers >> for us, [...] [Antoine] > Why "no-brainers"? We're running tests, benchmarks, the Python programs we always run, Python programs that are important to us, staring at obmalloc stats ... and seeing nothing bad, nothing mysterious, only neutral-to-good results. So what's to think about? ;-) These are 64-bit boxes, with terabytes of virtual address space. Asking for a meg of that is just reserving less than a thousandth of a thousandth of that range of integers, not actual physical RAM. > Bigger pools sound ok, They're not necessarily independent choices. Increase pool size without increasing arena size, and the number of pools per arena falls. At the extreme, if pools were made the same size as arenas, we'd need at least 32 arenas just to start Python (which uses at least one pool of _every_ possible size class before you hit the prompt - note that, on 64-bit boxes, the number of possible size classes is falling from 64 (3.7) to 32 (3.8), due to some desire to make everything aligned to 16 bytes - which I've already seen account for some programs needing 100s of MB of more RAM). > but bigger arenas will make Python less likely to return memory to the system. I know that gets repeated a lot, and I usually play along - but why do people believe that? Where's the evidence? At the start, obmalloc never returned arenas to the system. The vast majority of users were fine with that. A relative few weren't. Evan Jones wrote all the (considerable!) code to change that, and I massaged it and checked it in - not because there was "scientific proof" that it was more beneficial than harmful (it certainly added new expenses!) overall, but because it seemed like a right thing to do, _anticipating_ that the issue would become more important in coming years. I'm still glad it was done, but no tests were checked in to _quantify_ its presumed benefits - or even to verify that it ever returned arenas to the system. Best I can tell, nobody actually has any informed idea how well it does. Evan stared at programs that were important to him, and fiddled things until he was "happy enough". Not everyone was. About five years ago, Kristján Valur Jónsson opened this report: https://bugs.python.org/issue21220 suggesting a very different heuristic to try to free arenas. The "memcrunch..py" in his patch is the only time I've ever seen anyone write code trying to measure whether obmalloc's arena-freeing is effective. I can verify that if you increase the number of objects in his script by a factor of 100, my PR _never_ returns an arena to the system. But it's clear as mud to me whether his heuristic would either (with the 100x smaller number of objects in the original script, the PR branch does recycle arenas). So that's the only objective evidence I have :-) I've looked at obmalloc stats in other programs at various stages, and saw nothing concerning. memchunk.py appears to model object lifetimes as coming from a uniform distribution, but in real life they appear to be strongly multi-modal (with high peaks at the "way less than an eye blink" and "effectively immortal" ends). > We should evaluate what problem we are trying to solve here, I'm not trying to solve a problem. This is a "right thing to do" thing, anticipating that slinging a massive number of objects on massive machines will become ever more important, and that changing 20-year-old constants will allow obmalloc to spend more time in its fastest paths instead of its slowest. We haven't been especially pro-active about giant machines, and are suffering from it: https://metarabbit.wordpress.com/2018/02/05/pythons-weak-performance-matters/ """ Update: Here is a “fun” Python performance bug that I ran into the other day: deleting a set of 1 billion strings takes >12 hours. Obviously, this particular instance can be fixed, but this exactly the sort of thing that I would never have done a few years ago. A billion strings seemed like a lot back then, but now we regularly discuss multiple Terabytes of input data as “not a big deal”. This may not apply for your settings, but it does for mine. """ That was _probably_ due to obmalloc's move-one-at-a-time way of keeping its usable arenas list sorted, which sat un-diagnosed for over a year. https://bugs.python.org/issue32846 Fixing the underlying cause put giant machines on my radar, and getting rid of obmalloc's pool size limit was the next obvious thing that would help them (although not in the same universe as cutting quadratic time to linear). > instead of staring at micro-benchmark numbers on an idle system. My only interest in those is that they're not slowing down, because that's important too. The aim here is much more to make life better for programs slinging millions - even billions - of objects. obmalloc's internal overheads are frugal, but not free. For example, it has to allocate at least 5
[Python-Dev] Re: radix tree arena map for obmalloc
On Sat, 15 Jun 2019 01:15:11 -0500 Tim Peters wrote: > > > ... > > My feeling right now is that Tim's obmalloc-big-pool is the best > > design at this point. Using 8 KB or 16 KB pools seems to be better > > than 4 KB. The extra complexity added by Tim's change is not so > > nice. obmalloc is already extremely subtle and obmalloc-big-pool > > makes it more so. > > Moving to bigger pools and bigger arenas are pretty much no-brainers > for us, [...] Why "no-brainers"? Bigger pools sound ok, but bigger arenas will make Python less likely to return memory to the system. We should evaluate what problem we are trying to solve here, instead of staring at micro-benchmark numbers on an idle system. Micro-benchmarks don't tell you what happens on a loaded system with many processes, lots of I/O happening. If the problem is the cost of mmap() and munmap() calls, then the solution more or less exists at the system level: jemalloc and other allocators use madvise() with MADV_FREE (see here: https://lwn.net/Articles/593564/). A possible design is a free list of arenas on which you use MADV_FREE to let the system know the memory *can* be reclaimed. When the free list overflows, call munmap() on extraneous arenas. Regards Antoine. ___ 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/MJC274FJJMAD3C25XV5S6UOKNPAZ5A3R/
