Re: [PATCH] optimize malloc0

[Alexander Monakov <amonakov@ispras.ru>]

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.

> 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

> 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.

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.

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

Alexander