[PATCH v2] Add malloc micro benchmark

[Ondřej Bílka]

On Wed, Feb 28, 2018 at 01:40:28PM +0100, Florian Weimer wrote:
> On 01/05/2018 06:26 PM, Carlos O'Donell wrote:
> >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]
> 
> Actually, we have an 8-byte header, a 16-byte alignment requirement,
> and a 24-byte minimum allocation size.  (i386: 4-byte header,
> 16-byte alignment, 12-byte minimum size.)
> 
> The non-main arenas actually need only a four-byte chunk header (or
> even fewer bits) because there, the chunk size is very limited.
> 
> The alignment is non-negotiable, considering our current stance
> regarding fundamental alignment, even for smaller allocations.
>
Thats rather ineffective, it is easier to start fresh than try to
maintain rather obsolete allocator. Most of other are faster and more
space effective because of their layout.

I have several ideas based on that all allocations on a page of size P must 
have same capacity(say upto 256 bytes), options where metadata for pointer x are due 
to possibilitity of bigger alignment requirements following

1. End of previous page, easiest to implement. formula P*(x/P)-16

2. Page map, on 64-bit systems its possible on mmap also allocate pages
for mapping 16*(x/P). On 32-bit its possible add constant and rezerve
pages to map entire address space with same formula.

3. Encode size to address to table lookup in free for say size<=256. This trick is
probably applicable only for 64-bit systems as it could cause problems
with virtual address space. First calculate size by formula 16*((x-start)/(1<<25))
if its less than 257 we got correct size, otherwise use option 1/2