From: Rich Felker <dalias@libc.org>
To: musl@lists.openwall.com
Subject: Re: [musl] When to reclaim pages in __bin_chunk?
Date: Fri, 31 Jul 2020 15:23:45 -0400 [thread overview]
Message-ID: <20200731192339.GV6949@brightrain.aerifal.cx> (raw)
In-Reply-To: <20200731172216.GB2076@voyager>
On Fri, Jul 31, 2020 at 07:22:16PM +0200, Markus Wichmann wrote:
> On Fri, Jul 31, 2020 at 08:17:02AM +0800, Zhao Zhengyu wrote:
> > Hello,
> >
> > When chunks are merged, we use "(curr_size + pre_size) ^ pre_size >
> > pre_size" to decide whether to reclaim. I think this may be something
> > related to performance, but I can’t prove it. I want to know the
> > reason.
> >
> > Thank you!
> >
> > Zhengyu
>
> I asked that same question a while ago. For one, this was in the old
> malloc code, which is now usually no longer used. For two, this tries to
> figure out if adding current size to previous size rolls over into a new
> power of two. Usually, curr_size will be small and pre_size will be
> large. Therefore, adding the two will not change much about the high
> bits of pre_size, so due to the XOR operator, those bits will cancel out
> and the result will be smaller than pre_size. However, if the sum does
> roll over, then the sum has one bit set that isn't in pre_size and is
> larger than all the ones in pre_size. So the XOR can't cancel that bit,
> and the result of the XOR is greater than pre_size.
>
> Fundamentally, it is an optimized version of (a_clz(curr_size +
> pre_size) < a_clz(pre_size)).
Yes, it's a heuristic at least approximately equivalent to "crossed
the next power of two size boundary" to limit the frequency of madvise
syscalls when a large free zone keeps getting expanded by adjacent
tiny frees. However it does not work very well in practice, and
doesn't even mitigate the possibility of continuous syscall load when
a repeated malloc/free cycle occurs right at a power-of-two boundary.
mallocng handles this kind of thing much better by grouping same-sized
allocations and returning them as a group when all are freed, only
holding back from doing so if it's observed allocations of this size
"bouncing" (repeatedly creating and destroying the same group).
Rich
next prev parent reply other threads:[~2020-07-31 19:24 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-07-31 0:17 Zhao Zhengyu
2020-07-31 17:22 ` Markus Wichmann
2020-07-31 19:23 ` Rich Felker [this message]
2020-08-02 16:22 ` Zhao Zhengyu
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200731192339.GV6949@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).