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: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>
- To: Florian Weimer <fweimer at redhat dot com>
- Cc: 'GNU C Library' <libc-alpha at sourceware dot org>, Szabolcs Nagy <Szabolcs dot Nagy at arm dot com>
- Date: Mon, 18 Nov 2019 21:57:16 +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=oNUgeKPhHmDZP2Y5kPpuiD2LqyykKIrqDVn9MsPISbQ=; b=dq0N/ijzE9RSZt9uqgsVOIddUI2iI2lcC2f6lqRZeXajk185r7EAKzBmt5PpW9Opzx9trvgaDs+Ap+xw7LoytQr8ufR0wpKLUzVHqD3FB3nsIfVDRKCR+vRFqt7Z0w1ILWMGsDIgmLswH3YSYALTQQWud853plRgkFCmSNsHI1honXC9EoNmbl3lcKls5dsmw9lixtP9+2QbwYiq7CirZCwF8V4UOfCI8fKadORgxaLVI/IN1nVfNmWXB4V6fcgjtXMpf+mX9nXegdaEjldhWaaVrs5K5TKxo4hNS6KsiYKhjvuCzCad+RSHbxxkPHeh1aWVVIv/stPc1gRHJLypWQ==
- Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Lwq6CEVw1c+RaUQ4xMgrGXhp1Cuw6LEcdbPgPcVbLutPexnuoSdfjT+nP1xkAM4USborP5bKK6cLJo7r4SgfbjbRuaRSO/9PONHCZ9XJLbm15sXT44HKjzRQFhHZJ7F4U4pki0YqOr+jOBFKoWpOhlL3Jj9FrADkh/Byu9NcXAKr2zN0m5PO15/TCC4KRt1AoTTQOdq2ePIwSMEHQCRcGfq3YYAFA/EjqJ0z1Cg/wOM3PQ/wqbkPTqGN19kKflY1GatQd6PxqfEjolnsfF+MC0htXrpyQUX8Irm2dxwfaNeCHBt/FxYl/SLC4SfK0nEYLxhVgZNfbt92dKon4OWkNA==
- Original-authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco dot Dijkstra at arm dot com;
Hi Florian,
Hashtables should be powers of 2 - this not only gives very efficient
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