From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 80499 invoked by alias); 6 Mar 2018 23:25:38 -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 80484 invoked by uid 89); 6 Mar 2018 23:25:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 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: EUR02-VE1-obe.outbound.protection.outlook.com From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: Re: best-fit algorithm with bitmap heap Date: Tue, 06 Mar 2018 23:25:00 -0000 Message-ID: References: In-Reply-To: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;DB6PR0801MB1397;7:sUGt8vWQjD1KPY7v67MMOw9nmQS49Q9j1CTgSfD0WQNadh2W0eBTT/g2UQTVgh9dHGq8eptQKUzYMHLwFCFyjjQSGe/DLGVmOiMSXm+jS+zZMv/J0kRBOFF6320APi/FvNWttDZXRzkC7B5/4RCeqLQFAdbKGGzWUpEQpXhY7P10YnlR3RqnsagyGnynIdeeU2AHwWDQWpDdpu8LEpaOoj1EkgR0ent4JdRt5Ku3SvyqQbqol7Qo6Bal2xsH7Qgy x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-ht: Tenant x-ms-office365-filtering-correlation-id: f8570688-6d8c-47c1-9ebc-08d583b98e13 x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(7020095)(4652020)(48565401081)(5600026)(4604075)(3008032)(2017052603328)(7153060)(7193020);SRVR:DB6PR0801MB1397; x-ms-traffictypediagnostic: DB6PR0801MB1397: 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)(10201501046)(93006095)(93001095)(3002001)(3231220)(944501244)(52105095)(6055026)(6041288)(20161123560045)(20161123562045)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(6072148)(201708071742011);SRVR:DB6PR0801MB1397;BCL:0;PCL:0;RULEID:;SRVR:DB6PR0801MB1397; x-forefront-prvs: 06036BD506 x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(979002)(376002)(396003)(366004)(39380400002)(346002)(39840400004)(199004)(189003)(2351001)(72206003)(8936002)(478600001)(99286004)(2940100002)(106356001)(105586002)(14454004)(5660300001)(6506007)(6246003)(2501003)(2900100001)(5250100002)(4326008)(316002)(25786009)(26005)(86362001)(102836004)(53936002)(2906002)(3280700002)(8676002)(81166006)(81156014)(6436002)(68736007)(9686003)(3846002)(229853002)(55016002)(6116002)(6916009)(5640700003)(3660700001)(2950100002)(33656002)(97736004)(66066001)(74316002)(305945005)(7736002)(76176011)(7696005)(969003)(989001)(999001)(1009001)(1019001);DIR:OUT;SFP:1101;SCL:1;SRVR:DB6PR0801MB1397;H:DB6PR0801MB2053.eurprd08.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: mutHTuOwzNyFIqjYtKgGw3Tgx5KyaSkyOykgJfSGu9xEfI/4HJnO5fa519I3Mt67nxnFQmPtY9fsmwQE2C/jrnzz0X8vnY5gGhXkIgzwXVrkhl2LYL2BFQSOLLQ2wjRMPFWlKLZlJ4/556q7cjCI8+TrSK2L05c0oi62oGx+TgWQT6xq2Qb8FE6/vVqp8/Gs7Fk01s39zRSa+6bHhUqkG1aArk+EAry91UCDzaxoXNprgZXWyzLKSg1rFqGqMGRy+oFlVY2XIbKq9TrcFzAsqTRI7Iq2trKn7r0YhrqTXAYXoFoTDqiBKoCNmSmF4Xodc0DF1QR3cjTA3jz+gjjDQA== spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: f8570688-6d8c-47c1-9ebc-08d583b98e13 X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Mar 2018 23:25:31.7694 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR0801MB1397 X-SW-Source: 2018-03/txt/msg00163.txt.bz2 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 w= hich has its own bitmap. If say we have 100MBytes worth of data allocated, you w= ill 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 k= ey bottleneck - so it's essential to sort out the overall allocation strategy = first. Wilco =20=20=20=20=20