Re: [PATCH] optimize malloc0

[Rich Felker <dalias@libc.org>]

On Wed, Jul 05, 2017 at 02:09:21AM +0300, Alexander Monakov wrote:
> On Tue, 4 Jul 2017, Rich Felker wrote:
> > Overall I like this. Reviewing what was discussed on IRC, I called the
> > loop logic clever and nsz said maybe a bit too clever. On further
> > reading I think he's right.
> 
> Somehow raising this point in the context of the rest of src/malloc seems
> even worse than common bikeshed.

I don't think so -- I actually had to re-read the code a few times
before I understood what it was doing. Yes, maybe there's some
confusing code in malloc.c, and I'd like to avoid repeating that when
it's rewritten, but I think concern about making it worse is valid.

> > One additional concern was that the reverse-scanning may be bad for
> > performance.
> 
> Or it might be good for performance, because:
> 
> a) the caller is likely to use the lower addresses, in which case the
>    reverse scan is more likely to leave relevant lines in L1$
> 
> b) switching directions corresponds to switching access patterns:
>    reverse for reading, forward (in memset) for writing, and that
>    may help hardware more than it hurts
> 
> c) at least on intel cpus hardware prefetcher doesn't cross 4K boundaries
>    anyway, so discontiguous access on memset->scan transitions shouldn't
>    matter there
> 
> d) in practice the most frequent calls are probably less-than-pagesize,
>    and the patch handles those in the most efficient way

OK, these make sense.

> > A cheap way to avoid the scanning logic for the first and last partial
> > page, while not complicating the loop logic, would be just writing a
> > nonzero value to the first byte of each before the loop.
> 
> Nonsense.

I'm not sure what part is "nonsense". I was saying that, if we want to
do a simple, idiomatic forward loop like I described, the need for
special-casing the first and last partial pages could be avoided by
preloading nonzero data in 2 specific places, so that the same logic
that switches to memset for the interior pages would also work for the
boundary ones. However I think you have good reasons to claim your
current approach is better.

> This patch handles the common case (less than 4K) in the most efficient
> way, strikes a good size/speed tradeoff for the rest, and makes the
> mal0_clear interface such that it can be moved to a separate translation
> unit (to assist non-'--gc-sections' static linking, if desired) with
> minimal penalty.

That sounds nice, but do you have a proposal for how it would work?
Dummy weak mal0_clear in malloc.c with the working definition in
calloc.c? Just putting it in a separate TU wouldn't do anything to
help since malloc.c would still have a reference to it.

> I can rewrite it fully forward scanning without much trouble, but I
> think it wouldn't be for the better.

*nod* I'll re-check the version you submitted just to be sure I
understand and agree that it's doing what I think it is, with the plan
of going with it or something very similar. I might add some comments
as a follow-up patch.

Rich