From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 47398 invoked by alias); 7 Mar 2018 17:56:23 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Received: (qmail 47387 invoked by uid 89); 7 Mar 2018 17:56:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,SPF_NEUTRAL autolearn=no version=3.3.2 spammy=HContent-Transfer-Encoding:8bit X-HELO: popelka.ms.mff.cuni.cz Date: Wed, 07 Mar 2018 17:56:00 -0000 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: Wilco Dijkstra Cc: "libc-alpha@sourceware.org" , nd Subject: Re: best-fit algorithm with bitmap heap Message-ID: <20180307175615.GA31412@domone> References: <20180307072755.GA31543@domone> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) X-SW-Source: 2018-03/txt/msg00183.txt.bz2 On Wed, Mar 07, 2018 at 02:43:19PM +0000, Wilco Dijkstra wrote: > 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. > No, that is pretty easy to do if you know data structures. Well I thought that I also send mail with how I do best fit but didn't so I do that now. If there are 64 bins then one just needs bitmap bin_map which bins are empty and which not. Getting first nonempty bin is just three instructions. int best_fit_bin(int bin) { return __builtin_ctzl (bin_map & (-1L << bin)); } For 64*64 bins you need two-level structure with 64 individual bitmaps and one high bitmap if lower bitmaps are nonzero. Same idea, only done in two levels. int best_fit_bin(int bin) { int bin_hi = bin / 64; bin = bin % 64; if (bin_map[bin_hi] & (-1L << bin)) return 64*bin_hi + __builtin_ctzl (bin_map[bin_hi] & (-1L << bin)) else { bin_hi = __builtin_ctzl (high_bin_map & (-1L << (bin_hi+1))); return 64*bin_hi + __builtin_ctzl (bin_map[bin_hi]); } }