Re: [PATCH v2] Add malloc micro benchmark

[Carlos O'Donell <carlos at redhat dot com>]

On 01/05/2018 08:28 AM, Joseph Myers wrote:
> On Fri, 5 Jan 2018, Carlos O'Donell wrote:
> 
>> I think that for blocks smaller than the fundamental language types 
>> (which require malloc to have 16-byte alignment) we do not have to 
>> return sufficiently aligned memory. For example if you allocate a 3-byte 
>> block or a 13-byte block, you cannot possibly put a 16-byte long double 
>> there, nor can you use that for a stack block, so it's a waste to 
>> guarantee alignment.
> 
> As per DR#075, the memory needs to be aligned for any type of object (with 
> a fundamental alignment requirement, in C11 and later), not just those 
> that will fit in the block.  (This in turn allows for applications using 
> low bits for tagged pointers.)

Thanks for the reference to DR#075, I had not considered the cast equality
issue.

> This does not of course rule out having another allocation API that 
> supports smaller alignment requirements.
Agreed.

It would still be a win if we did not have co-located metadata (something
Florian whispered into my ear years ago now) for small constant sized blocks.

We would go from this:

N * 1-byte allocations => N * (32-byte header 
                               + 1-byte allocation
                               + 15-bytes alignment)
                          [97% constant waste]

To this:

N * 1-byte allocations => N * (1-byte allocation
                               + 15-bytes alignment) 
                          + (N/8)-bytes in-use-bit + 16-bytes header
                          [96% waste for 1-byte]
			  [94% waste for 100*1-byte]
                          ... towards a 93.75% constant waste (limit of the alignment e.g. 15/16)

This is a gain of 5% RSS efficiency for a structural change.

For a 13-byte allocation:

N * 1-byte allocations => N * (32-byte header 
                               + 13-byte allocation
                               + 3-bytes alignment)
                          [73% constant waste]

To this:

N * 1-byte allocations => N * (13-byte allocation
                               + 3-bytes alignment) 
                          + (N/8)-bytes in-use-bit + 16-bytes header
                          [60% waste for 13-bytes]
			  [20% waste for 100*13-bytes]
			  [19% waste for 1000*13-bytes]
			  ... towards a 18.75% constant waste (limit of the alignment e.g. 3/16)

Note: We never reach the constant limit because the in-use bit-array still grows quickly.


-- 
Cheers,
Carlos.