From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 104419 invoked by alias); 7 Mar 2018 14:43:25 -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 104126 invoked by uid 89); 7 Mar 2018 14:43:25 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.7 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: EUR01-HE1-obe.outbound.protection.outlook.com From: Wilco Dijkstra To: =?iso-8859-2?Q?Ond=F8ej_B=EDlka?= CC: "libc-alpha@sourceware.org" , nd Subject: Re: best-fit algorithm with bitmap heap Date: Wed, 07 Mar 2018 14:43:00 -0000 Message-ID: References: ,<20180307072755.GA31543@domone> In-Reply-To: <20180307072755.GA31543@domone> authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;DB6PR0801MB1880;7:PyK5Vd1R2LHth+bXY7tU8s/jBzrwFVQuusa3dmGBd9cXwtRkjwX1F4cPMVYZV1wIcGyuDBm7K6tI6b6BTM562IHjVLur7FDWtm7Vxvp7HH5vC/4J0HCsoPBmtdNJvYGPiMF2lp4MfdtcmOjAD0gSQc3NBZkijk1T9ka1ryQ8/a2cZ5Xl4h3bdbu2QZTO5EiYHtdju7z1rxSL+cSSs48ZF6eZtFgdIKq5+hX9NlILF9fpQ+5H9APqCxJoeyqBXidj x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-ht: Tenant x-ms-office365-filtering-correlation-id: 0e168373-20a4-46c4-858e-08d58439c4e9 x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(7020095)(4652020)(48565401081)(5600026)(4604075)(3008032)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020);SRVR:DB6PR0801MB1880; x-ms-traffictypediagnostic: DB6PR0801MB1880: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(8211001083)(6040501)(2401047)(5005006)(8121501046)(3231220)(944501244)(52105095)(10201501046)(93006095)(93001095)(3002001)(6055026)(6041288)(20161123558120)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123564045)(6072148)(201708071742011);SRVR:DB6PR0801MB1880;BCL:0;PCL:0;RULEID:;SRVR:DB6PR0801MB1880; x-forefront-prvs: 0604AFA86B x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(346002)(396003)(39380400002)(39860400002)(366004)(376002)(189003)(199004)(72206003)(186003)(53936002)(3280700002)(54906003)(5660300001)(478600001)(14454004)(5250100002)(316002)(68736007)(6246003)(2906002)(3660700001)(229853002)(4326008)(6506007)(33656002)(86362001)(25786009)(55016002)(106356001)(6916009)(26005)(2950100002)(6436002)(9686003)(102836004)(66066001)(105586002)(2900100001)(81156014)(81166006)(8676002)(7696005)(76176011)(8936002)(97736004)(7736002)(6116002)(74316002)(99286004)(3846002)(8656006)(305945005);DIR:OUT;SFP:1101;SCL:1;SRVR:DB6PR0801MB1880;H:DB6PR0801MB2053.eurprd08.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: TnEUpeVzAMl7moQ4IZPIhrJh4HRPiY8esXMD/888qF8+0D1WYEkWnyPgrt/ss+M4JrFNI6JTfMLuVsCWJSy195NNC5OoBnOkcHsw8wIRZpiBJdyxi5AVvgSEFY621/WTtssVeG7321KprdPMxSsSMAm3MprXz9EJlfx4FE88j84gySBfhGeW/5Jrz/TWCFYITIX4DzIC0r87j1WeFpqsTof4T2PZpNP/XBbxuTeuiEXAQW9Xi1QHqYPqVHgFNhZlLaspSNa4fiNMxm83AQrHsncNSVHFLE+1QVQCnJs1Fy3g0UokjBaweyMnly5OUE1n1/i7WryHuU9mfkE8o6xBqA== spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="iso-8859-2" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 0e168373-20a4-46c4-858e-08d58439c4e9 X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Mar 2018 14:43:19.3965 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR0801MB1880 X-SW-Source: 2018-03/txt/msg00170.txt.bz2 Ond=F8ej B=EDlka 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 =20=20=20=20