This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v2] Add malloc micro benchmark
- From: Ondřej Bílka <neleai at seznam dot cz>
- To: Florian Weimer <fweimer at redhat dot com>
- Cc: Carlos O'Donell <carlos at redhat dot com>, Joseph Myers <joseph at codesourcery dot com>, Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>, "libc-alpha at sourceware dot org" <libc-alpha at sourceware dot org>, nd <nd at arm dot com>
- Date: Wed, 28 Feb 2018 15:11:26 +0100
- Subject: Re: [PATCH v2] Add malloc micro benchmark
- Authentication-results: sourceware.org; auth=none
- References: <DB6PR0801MB205334E9F59632F30A17202683390@DB6PR0801MB2053.eurprd08.prod.outlook.com> <bcc3af78-c1ac-2d24-6a6a-c14d6ca7dc96@redhat.com> <DB6PR0801MB20538A414F1659748E703918833C0@DB6PR0801MB2053.eurprd08.prod.outlook.com> <6ad98d83-d49b-25a3-ef01-e93e18f4740b@redhat.com> <DB6PR0801MB2053641333453CE91496266E83190@DB6PR0801MB2053.eurprd08.prod.outlook.com> <96b76d58-d2f0-2176-51e5-f6338ed079e1@redhat.com> <alpine.DEB.2.20.1801051621180.14880@digraph.polyomino.org.uk> <a55c0575-f89d-0a05-7269-e38653b2b16e@redhat.com> <165192eb-d815-867f-e1ba-0f9972eb19cd@redhat.com>
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