This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: best-fit algorithm with bitmap heap
- From: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>
- To: Ondřej Bílka <neleai at seznam dot cz>
- Cc: "libc-alpha at sourceware dot org" <libc-alpha at sourceware dot org>, nd <nd at arm dot com>
- Date: Wed, 7 Mar 2018 14:43:19 +0000
- Subject: Re: best-fit algorithm with bitmap heap
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco dot Dijkstra at arm dot com;
- Nodisclaimer: True
- References: <DB6PR0801MB2053B88AEF84C7772505072B83D90@DB6PR0801MB2053.eurprd08.prod.outlook.com> <DB6PR0801MB205340FDEB79C61E7461D55983D90@DB6PR0801MB2053.eurprd08.prod.outlook.com>,<20180307072755.GA31543@domone>
- Spamdiagnosticmetadata: NSPM
- Spamdiagnosticoutput: 1:99
Ondřej Bílka wrote:
> No, there is no searching and as I described it is really easy.
There is always a search here and that is completely unavoidable.
If you have a free list which contains multiple different sizes, you need
to walk it until you get a block that fits. This could be slow if there are
thousands of entries in that free list. If you use individual free lists for
every supported allocation size (only practical for small sizes), and the
free list for the requested size is empty, you now need to search all larger
free lists until you find one which isn't empty (if you cache which sizes
have free blocks then that's yet another data structure to keep up to date).
I think bitmaps are a good choice for allocation of small fixed size blocks,
but for medium sized blocks it's less clear.
Wilco