[PATCH] Fix compute_bucket_count

[PATCH] Fix compute_bucket_count

[Jakub Jelinek]

Hi!

I believe this hasn't been updated since (most of) 64-bit targets
started using 4 byte .hash sh_entsize (as required by ELF).
Certainly max = (2 + nsyms) * (bed->s->arch_size / 8);
looks very much like an attempt to compute the size of the .hash
section except the nbuckets part.  But
1) on most 64-bit targets .hash entsize is not 8
2) the chains part of .hash section is really dynsymcount entries large
   (corresponds 1:1 to .dymsym entries), while nsyms can be smaller number
   (STT_SECTION symbols, symbol 0)
On the other side, when not optimizing, compute_bucket_count was looking
at dynsymcount, but in that case the interesting number really is the number
of dynamic symbols that are entered into the .hash table.

What do you think about this?

2006-06-23  Jakub Jelinek  <jakub@redhat.com>

	* elflink.c (compute_bucket_count): Use bed->s->sizeof_hash_entry
	instead of bed->s->arch_size / 8.  Fix .hash size estimation.
	When not optimizing, use the number of hashed symbols rather than
	dynsymcount.

--- bfd/elflink.c.jj	2006-06-20 18:34:53.000000000 +0200
+++ bfd/elflink.c	2006-06-23 17:48:01.000000000 +0200
@@ -4913,9 +4913,9 @@ compute_bucket_count (struct bfd_link_in
 #  define BFD_TARGET_PAGESIZE	(4096)
 # endif
 
-	  /* We in any case need 2 + NSYMS entries for the size values and
-	     the chains.  */
-	  max = (2 + nsyms) * (bed->s->arch_size / 8);
+	  /* We in any case need 2 + DYNSYMCOUNTS entries for the size values
+	     and the chains.  */
+	  max = (2 + dynsymcount) * bed->s->sizeof_hash_entry;
 
 # if 1
 	  /* Variant 1: optimize for short chains.  We add the squares
@@ -4925,7 +4925,7 @@ compute_bucket_count (struct bfd_link_in
 	    max += counts[j] * counts[j];
 
 	  /* This adds penalties for the overall size of the table.  */
-	  fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1;
+	  fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1;
 	  max *= fact * fact;
 # else
 	  /* Variant 2: Optimize a lot more for small table.  Here we
@@ -4936,7 +4936,7 @@ compute_bucket_count (struct bfd_link_in
 
 	  /* The overall size of the table is considered, but not as
 	     strong as in variant 1, where it is squared.  */
-	  fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1;
+	  fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1;
 	  max *= fact;
 # endif
 
@@ -4959,7 +4959,7 @@ compute_bucket_count (struct bfd_link_in
       for (i = 0; elf_buckets[i] != 0; i++)
 	{
 	  best_size = elf_buckets[i];
-	  if (dynsymcount < elf_buckets[i + 1])
+	  if ((hashcodesp - hashcodes) < elf_buckets[i + 1])
 	    break;
 	}
     }

 

	Jakub

Re: [PATCH] Fix compute_bucket_count

[Alan Modra]

On Fri, Jun 23, 2006 at 05:55:02PM +0200, Jakub Jelinek wrote:
> I believe this hasn't been updated since (most of) 64-bit targets
> started using 4 byte .hash sh_entsize (as required by ELF).
> Certainly max = (2 + nsyms) * (bed->s->arch_size / 8);
> looks very much like an attempt to compute the size of the .hash
> section except the nbuckets part.  But
> 1) on most 64-bit targets .hash entsize is not 8

Of course using the "wrong" sizes just tweaks the weighting given to
short chains vs. overall table size.  Still, we may as well be using the
same algorithm for 64-bit vs. 32-bit.  Changing (bed->s->arch_size / 8)
to bed->s->sizeof_hash_entry is OK to commit.

> 2) the chains part of .hash section is really dynsymcount entries large
>    (corresponds 1:1 to .dymsym entries), while nsyms can be smaller number
>    (STT_SECTION symbols, symbol 0)
> On the other side, when not optimizing, compute_bucket_count was looking
> at dynsymcount, but in that case the interesting number really is the number
> of dynamic symbols that are entered into the .hash table.

I'm not so sure about this change, which affects both 32-bit and
64-bit.  If I've analysed the change correctly, it will tend to result
in smaller hash tables at the expense of possibly longer chains, in both
the optimising and non-optimising cases.  Do we really want that?

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: [PATCH] Fix compute_bucket_count

[Jakub Jelinek]

On Mon, Jul 03, 2006 at 03:43:52PM +0930, Alan Modra wrote:
> > 2) the chains part of .hash section is really dynsymcount entries large
> >    (corresponds 1:1 to .dymsym entries), while nsyms can be smaller number
> >    (STT_SECTION symbols, symbol 0)
> > On the other side, when not optimizing, compute_bucket_count was looking
> > at dynsymcount, but in that case the interesting number really is the number
> > of dynamic symbols that are entered into the .hash table.
> 
> I'm not so sure about this change, which affects both 32-bit and
> 64-bit.  If I've analysed the change correctly, it will tend to result
> in smaller hash tables at the expense of possibly longer chains, in both
> the optimising and non-optimising cases.  Do we really want that?

Well, if we want to use a bigger number, we certainly can, not sure if
we want some multiply of (hashcodesp - hashcodes) or just add some constant
(i.e. say (hashcodesp - hashcodes) * 1.1 < elf_buckets[i + 1] or
(hashcodesp - hashcodes) + 20 < elf_buckets[i + 1]).  What I'm just trying
to say that the heuristics should have nothing to do with dynsymcount,
it really shouldn't care how many special symbols you have in .dynsym that
are not added to the hash table.

But if you want, we can keep it as is and only change the heuristics
for the new .gnu.hash section.

	Jakub

Re: [PATCH] Fix compute_bucket_count

[Alan Modra]

On Mon, Jul 03, 2006 at 10:42:31AM +0200, Jakub Jelinek wrote:
> On Mon, Jul 03, 2006 at 03:43:52PM +0930, Alan Modra wrote:
> > I'm not so sure about this change, which affects both 32-bit and
> > 64-bit.  If I've analysed the change correctly, it will tend to result
> > in smaller hash tables at the expense of possibly longer chains, in both
> > the optimising and non-optimising cases.  Do we really want that?
> 
> Well, if we want to use a bigger number, we certainly can, not sure if
> we want some multiply of (hashcodesp - hashcodes) or just add some constant
> (i.e. say (hashcodesp - hashcodes) * 1.1 < elf_buckets[i + 1] or
> (hashcodesp - hashcodes) + 20 < elf_buckets[i + 1]).

No, I don't want to see fudge factors like this!

>  What I'm just trying
> to say that the heuristics should have nothing to do with dynsymcount,
> it really shouldn't care how many special symbols you have in .dynsym that
> are not added to the hash table.

Yes, I agree with your change from a logical perspective.  I wasn't
saying that I disliked the new heuristic, just noting that your change
potentially causes longer chains.  Have you done any tests to see
whether there is in fact any real world effect?

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: [PATCH] Fix compute_bucket_count

[Jakub Jelinek]

[-- Attachment #1: Type: text/plain, Size: 2258 bytes --]

On Tue, Jul 04, 2006 at 10:36:35AM +0930, Alan Modra wrote:
> On Mon, Jul 03, 2006 at 10:42:31AM +0200, Jakub Jelinek wrote:
> > On Mon, Jul 03, 2006 at 03:43:52PM +0930, Alan Modra wrote:
> > > I'm not so sure about this change, which affects both 32-bit and
> > > 64-bit.  If I've analysed the change correctly, it will tend to result
> > > in smaller hash tables at the expense of possibly longer chains, in both
> > > the optimising and non-optimising cases.  Do we really want that?
> > 
> > Well, if we want to use a bigger number, we certainly can, not sure if
> > we want some multiply of (hashcodesp - hashcodes) or just add some constant
> > (i.e. say (hashcodesp - hashcodes) * 1.1 < elf_buckets[i + 1] or
> > (hashcodesp - hashcodes) + 20 < elf_buckets[i + 1]).
> 
> No, I don't want to see fudge factors like this!
> 
> >  What I'm just trying
> > to say that the heuristics should have nothing to do with dynsymcount,
> > it really shouldn't care how many special symbols you have in .dynsym that
> > are not added to the hash table.
> 
> Yes, I agree with your change from a logical perspective.  I wasn't
> saying that I disliked the new heuristic, just noting that your change
> potentially causes longer chains.  Have you done any tests to see
> whether there is in fact any real world effect?

I have some raw data for the same binaries/libraries built without my first
DT_GNU_HASH patch and after it (that patch included also the arch_size / 8
-> bed->size_of_hash_entry change, nsyms -> dynsymcount in ld -O1 code
and dynsymcount -> (hashcodesp - hashcodes) in non-optimizing compute_bucket_count).
For .gnu.hash, one shouldn't look at the st_size of .gnu.hash section,
that was decreased by (2 * nchains - 1) * 4 with the patch from yesterday.

Apparently very few packages use -Wl,-O1 (glibc is a notable exception)
and for non-optimizing linking the dynsymcount -> (hashcodesp - hashcodes)
change in many cases decreases the bucket counts.  It is just itching me
because the heuristics uses completely unrelated value, a fudge factor would
be ugly, but at least would make some sense.

In any case, I can live with that for .hash section, for .gnu.hash
we don't mind slightly longer chains as long as they aren't much longer.

	Jakub

[-- Attachment #2: ppc.before.bz2 --]
[-- Type: application/x-bzip2, Size: 19609 bytes --]

[-- Attachment #3: ppc.after.bz2 --]
[-- Type: application/x-bzip2, Size: 34641 bytes --]

[-- Attachment #4: ia64.before.bz2 --]
[-- Type: application/x-bzip2, Size: 12460 bytes --]

[-- Attachment #5: ia64.after.bz2 --]
[-- Type: application/x-bzip2, Size: 17787 bytes --]

Re: [PATCH] Fix compute_bucket_count

[Jakub Jelinek]

On Tue, Jul 04, 2006 at 12:01:19PM +0200, Jakub Jelinek wrote:
> I have some raw data for the same binaries/libraries built without my first
> DT_GNU_HASH patch and after it (that patch included also the arch_size / 8
> -> bed->size_of_hash_entry change, nsyms -> dynsymcount in ld -O1 code
> and dynsymcount -> (hashcodesp - hashcodes) in non-optimizing compute_bucket_count).
> For .gnu.hash, one shouldn't look at the st_size of .gnu.hash section,
> that was decreased by (2 * nchains - 1) * 4 with the patch from yesterday.

Well, don't look at the histograms for .gnu.hash in that data either, just
for .hash.  I just realized I used readelf -I from binutils build with the
latest DT_GNU_HASH patch (i.e. the new, smaller .gnu.hash format) on the
binaries/libraries created by older binutils (the older, bigger .gnu.hash
format).  I was shocked to see e.g. chains with length 48 in there only
to figure later that they aren't that long.  If you are interested, will
repost new ppc.after.bz2 and ia64.after.bz2 data, created with the matching
readelf.  Sorry.

	Jakub

Re: [PATCH] Fix compute_bucket_count

[Jakub Jelinek]

[-- Attachment #1: Type: text/plain, Size: 750 bytes --]

On Tue, Jul 04, 2006 at 12:33:27PM +0200, Jakub Jelinek wrote:
> Well, don't look at the histograms for .gnu.hash in that data either, just
> for .hash.  I just realized I used readelf -I from binutils build with the
> latest DT_GNU_HASH patch (i.e. the new, smaller .gnu.hash format) on the
> binaries/libraries created by older binutils (the older, bigger .gnu.hash
> format).  I was shocked to see e.g. chains with length 48 in there only
> to figure later that they aren't that long.  If you are interested, will
> repost new ppc.after.bz2 and ia64.after.bz2 data, created with the matching
> readelf.  Sorry.

Attached are corrected ppc.after2.bz2 and ia64.after2.bz2 which use the
matching readelf, so .gnu.hash histograms are correct.

	Jakub

[-- Attachment #2: ppc.after2.bz2 --]
[-- Type: application/x-bzip2, Size: 29453 bytes --]

[-- Attachment #3: ia64.after2.bz2 --]
[-- Type: application/x-bzip2, Size: 16399 bytes --]

Re: [PATCH] Fix compute_bucket_count

[Alan Modra]

On Tue, Jul 04, 2006 at 12:01:19PM +0200, Jakub Jelinek wrote:
> Apparently very few packages use -Wl,-O1 (glibc is a notable exception)
> and for non-optimizing linking the dynsymcount -> (hashcodesp - hashcodes)
> change in many cases decreases the bucket counts.  It is just itching me
> because the heuristics uses completely unrelated value, a fudge factor would
> be ugly, but at least would make some sense.

Having looked at those results, I guess I'm fussing over nothing.  We
probably don't care too much about files with a small number of symbols,
and the effect of your changes ought to be less on files with a large
number of symbols.  So go ahead and commit.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre