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: "libc-alpha at sourceware dot org" <libc-alpha at sourceware dot org>
- Cc: nd <nd at arm dot com>
- Date: Tue, 6 Mar 2018 23:25:31 +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>
- Spamdiagnosticmetadata: NSPM
- Spamdiagnosticoutput: 1:99
Hi,
I think before going into the details it is worth considering whether it is even
feasible to use a bitmap search for first-fit, let alone best-fit. What you seem
to be saying is there will be lots of small pages for allocation, each of which
has its own bitmap. If say we have 100MBytes worth of data allocated, you will
need to start searching every single bitmap that has free space. That would imply
adding a fast data structure that keeps track of all the free space across all
the bitmaps. Then this needs to be kept up to date by both malloc and free, as
well as supporting multiple threads. It seems to me this would become the key
bottleneck - so it's essential to sort out the overall allocation strategy first.
Wilco