From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6543 invoked by alias); 3 Jul 2006 14:46:15 -0000 Received: (qmail 6519 invoked by uid 22791); 3 Jul 2006 14:46:15 -0000 X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 03 Jul 2006 14:46:13 +0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11.20060308/8.12.11) with ESMTP id k63EkBrY018602; Mon, 3 Jul 2006 10:46:11 -0400 Received: from lacrosse.corp.redhat.com (lacrosse.corp.redhat.com [172.16.52.154]) by int-mx1.corp.redhat.com (8.12.11.20060308/8.12.11) with ESMTP id k63EkBMx002594; Mon, 3 Jul 2006 10:46:11 -0400 Received: from [192.168.7.71] (vpn50-130.rdu.redhat.com [172.16.50.130]) by lacrosse.corp.redhat.com (8.12.11.20060308/8.11.6) with ESMTP id k63EjWbP002332; Mon, 3 Jul 2006 10:45:37 -0400 Message-ID: <44A92DBB.6030308@redhat.com> Date: Mon, 03 Jul 2006 14:46:00 -0000 From: Ulrich Drepper User-Agent: Thunderbird 1.5.0.4 (X11/20060614) MIME-Version: 1.0 To: djamel anonymous CC: jakub@redhat.com, binutils@sources.redhat.com, libc-alpha@sources.redhat.com Subject: Re: DT_GNU_HASH: ~ 50% dynamic linking improvement References: In-Reply-To: Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig23F0FF110DBD5B139002FD65" Mailing-List: contact binutils-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sourceware.org X-SW-Source: 2006-07/txt/msg00015.txt.bz2 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig23F0FF110DBD5B139002FD65 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-length: 1468 djamel anonymous wrote: > Hello, i am writing again for a small suggestion that may reduce the > space occupied by the hash > table and reduce cache fills probability. I see absolutely no benefit at all in any of this. The second hash table with the required second memory load would kill all the performance advantage. It's sole purpose would be to not compare the chain list elements at all. But: - it has to be pessimistic. I.e., for the first table there are also collisions and when they happen, the search must be made - we limit the hash chain to a single cache line whenever possible and this is as I showed before almost always the case. The operations all work on L1 cache and even 8 or 10 memory loads are cheaper than loading another cache line. And that number of loads is just a worst case behavior, usually there are fewer. - each element in your second hash table must point to the beginning of a chain. So here the huge overhead in the hash table sizing is costing a lot. Furthermore, the division is nowadays no problem at all anymore. It's fast. If you really care, modify your linker to size the hash table with a power of two and change the dynamic linker to optimize that case. It's easy enough to do. The linker already has a function to size the table more intelligently if requested. --=20 =E2=9E=A7 Ulrich Drepper =E2=9E=A7 Red Hat, Inc. =E2=9E=A7 444 Castro St = =E2=9E=A7 Mountain View, CA =E2=9D=96 --------------enig23F0FF110DBD5B139002FD65 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" Content-length: 251 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.4 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org iD8DBQFEqS272ijCOnn/RHQRAg1EAJkBoOCWRwp0Sx52/R+Dwzdwk+TxVQCeK4Vj U8RSiBADlOPllQl1RguE9uw= =tJAH -----END PGP SIGNATURE----- --------------enig23F0FF110DBD5B139002FD65--