This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: Optimizing hash table lookup in symbol binding
- From: Szabolcs Nagy <Szabolcs dot Nagy at arm dot com>
- To: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>, Florian Weimer <fweimer at redhat dot com>
- Cc: nd <nd at arm dot com>, 'GNU C Library' <libc-alpha at sourceware dot org>
- Date: Tue, 19 Nov 2019 09:15:10 +0000
- Subject: Re: Optimizing hash table lookup in symbol binding
- Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Np5698ctzqRov54VTHudzKxqNET/UXhtWN9L164jZis=; b=NvZbXbtJ4VQv/srOr8ZkkyCCFpSFw2VPwzmYLcq55O8y4yaK6PTplSo6weR4WaPMabVq9GPV/CA8fPqOAWY8Kbg2TqCJjzX2htsucJ+MbLyPk+usMtsjW0lkX9bstJa28mbQdZ018ZXmJBIYTO4pxgQuFIhg/ZA43PACMf0ejEIe/P7MvmR6cmmKJkqi+1AApZSqCZB8k9rLAMtn++Ok96poGNmMta772CqEtzDmcbg5w2ZXTh/fVFtM1DrS8flmZVgoDK8wocMrEwsXXbYTuX/TmVV7QWxLjU7odel8YeMgI+vfpcI/eMEREVm9PlEYJgxx/u44gRcezq50eGa2gA==
- Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=bGCv6euGh31dfm4SCEqBcQhcMi69yk0rlmYCAXWDuCuTRt9N70XU3aWrQ5WXzN3t8cClwv1QJ53GaXIDztUOHWHRqX/I7qQ6UG9MYH15htjiv1+r8vH+57FB6svPOWypo6F8UZn5AOC9d+NiZyI1eeemutf3ZFQ/N6DcnqTpv9nb+hNCPtc/yeTOipppfUPg6icCbU6TOzsUhYGmtbRQ5NT5yDI1Rn75McKFy6v5fDjSUTsDknjakCb1jm5thpZzPUQUexPZDndR6MnW80Ov23trtI1BK5Jb864GwZT5V4QlzZeRcZSkqMpVSFfW6Aa38+poU4SyJgFzVuLGXysmOA==
- Original-authentication-results: spf=none (sender IP is ) smtp.mailfrom=Szabolcs dot Nagy at arm dot com;
- References: <VI1PR0801MB2127AD448C920F3F0AE63A47834D0@VI1PR0801MB2127.eurprd08.prod.outlook.com>
On 18/11/2019 21:57, Wilco Dijkstra wrote:
> Hi Florian,
>
> Hashtables should be powers of 2 - this not only gives very efficient
this hash table is in the elf binary,
so we are not in control of the size and other details.
> lookups but also enables double hashing without ever needing to use
> multiply or division. If you're worried about the entropy of the low bits
> you can do (x ^ (x >> 16)) & mask to mix bits before masking.
>
> If you're looking to get the best possible speedup, this will do it.
>
> Cheers,
> Wilco
>