PATCH: Speed up ELF section merge

PATCH: Speed up ELF section merge

[H. J. Lu]

The default BFD hash table size is too small for ELF section merge.
This patch speeds up sec_merge_hash_lookup by 50% in average.


H.J.
---
2005-04-30  H.J. Lu  <hongjiu.lu@intel.com>

	* hash.c (hash_size_primes): Add 65537.

	* merge.c (sec_merge_init): Call bfd_hash_set_default_size to
	set hash table size to 16699.

--- bfd/hash.c.hash	2005-03-22 17:25:46.000000000 -0800
+++ bfd/hash.c	2005-04-30 12:25:59.000000000 -0700
@@ -492,7 +492,7 @@ bfd_hash_set_default_size (bfd_size_type
   /* Extend this prime list if you want more granularity of hash table size.  */
   static const bfd_size_type hash_size_primes[] =
     {
-      1021, 4051, 8599, 16699
+      1021, 4051, 8599, 16699, 65537
     };
   size_t index;
 
--- bfd/merge.c.hash	2005-04-14 10:51:43.000000000 -0700
+++ bfd/merge.c	2005-04-30 12:31:22.000000000 -0700
@@ -241,6 +241,8 @@ sec_merge_init (unsigned int entsize, bf
   if (table == NULL)
     return NULL;
 
+  bfd_hash_set_default_size (16699);
+
   if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
     {
       free (table);

Re: PATCH: Speed up ELF section merge

[Alan Modra]

On Sat, Apr 30, 2005 at 12:40:30PM -0700, H. J. Lu wrote:
> +  bfd_hash_set_default_size (16699);
> +

This changes the default for all hash tables created after this point.
I don't think that is wise, and in any case doesn't match your stated
aim of increasing the merge hash table.

>    if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))

Instead use bfd_hash_table_init_n here.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: PATCH: Speed up ELF section merge

[H. J. Lu]

On Mon, May 02, 2005 at 11:47:28AM +0930, Alan Modra wrote:
> On Sat, Apr 30, 2005 at 12:40:30PM -0700, H. J. Lu wrote:
> > +  bfd_hash_set_default_size (16699);
> > +
> 
> This changes the default for all hash tables created after this point.
> I don't think that is wise, and in any case doesn't match your stated
> aim of increasing the merge hash table.
> 
> >    if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
> 
> Instead use bfd_hash_table_init_n here.
> 

Here is the new one.


H.J.
----
2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>

	* merge.c (sec_merge_init): Call bfd_hash_table_init_n with
	hash table size 16699 instead of bfd_hash_table_init.

--- bfd/merge.c.hash	2005-04-15 18:51:49.000000000 -0700
+++ bfd/merge.c	2005-05-01 19:25:42.000000000 -0700
@@ -241,7 +241,8 @@ sec_merge_init (unsigned int entsize, bf
   if (table == NULL)
     return NULL;
 
-  if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
+  if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc,
+			       16699))
     {
       free (table);
       return NULL;

Re: PATCH: Speed up ELF section merge

[Alan Modra]

On Sun, May 01, 2005 at 07:28:39PM -0700, H. J. Lu wrote:
> 	* merge.c (sec_merge_init): Call bfd_hash_table_init_n with
> 	hash table size 16699 instead of bfd_hash_table_init.

OK.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

RE: PATCH: Speed up ELF section merge

[Dave Korn]

----Original Message----
>From: H. J. Lu
>Sent: 02 May 2005 03:29

> Here is the new one.
> 
> 
> H.J.
> ----
> 2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>
> 
> 	* merge.c (sec_merge_init): Call bfd_hash_table_init_n with
> 	hash table size 16699 instead of bfd_hash_table_init.
> 
> --- bfd/merge.c.hash	2005-04-15 18:51:49.000000000 -0700
> +++ bfd/merge.c	2005-05-01 19:25:42.000000000 -0700
> @@ -241,7 +241,8 @@ sec_merge_init (unsigned int entsize, bf
>    if (table == NULL)
>      return NULL;
> 
> -  if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
> +  if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc,
> +			       16699))
>      {
>        free (table);
>        return NULL;



  H.J., IIUIC this patch can't do anything to support the ld command line
options --hash-size=<NUMBER> and --reduce-memory-overheads; wouldn't it be
worthwhile providing a means of controlling whether it uses a large hash
table or not?


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: PATCH: Speed up ELF section merge

[H. J. Lu]

On Fri, May 06, 2005 at 03:38:57PM +0100, Dave Korn wrote:
> ----Original Message----
> >From: H. J. Lu
> >Sent: 02 May 2005 03:29
> 
> > Here is the new one.
> > 
> > 
> > H.J.
> > ----
> > 2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>
> > 
> > 	* merge.c (sec_merge_init): Call bfd_hash_table_init_n with
> > 	hash table size 16699 instead of bfd_hash_table_init.
> > 
> > --- bfd/merge.c.hash	2005-04-15 18:51:49.000000000 -0700
> > +++ bfd/merge.c	2005-05-01 19:25:42.000000000 -0700
> > @@ -241,7 +241,8 @@ sec_merge_init (unsigned int entsize, bf
> >    if (table == NULL)
> >      return NULL;
> > 
> > -  if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
> > +  if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc,
> > +			       16699))
> >      {
> >        free (table);
> >        return NULL;
> 
> 
> 
>   H.J., IIUIC this patch can't do anything to support the ld command line
> options --hash-size=<NUMBER> and --reduce-memory-overheads; wouldn't it be
> worthwhile providing a means of controlling whether it uses a large hash
> table or not?
> 

I am full on my plate.  A patch is more than welcome.  Thanks.


H.J.

RE: PATCH: Speed up ELF section merge

[Dave Korn]

----Original Message----
>From: H. J. Lu
>Sent: 06 May 2005 15:57

>>   H.J., IIUIC this patch can't do anything to support the ld command line
>> options --hash-size=<NUMBER> and --reduce-memory-overheads; wouldn't it
>> be worthwhile providing a means of controlling whether it uses a large
>> hash table or not? 
>> 
> 
> I am full on my plate.  A patch is more than welcome.  Thanks.
 

  I will look at it over the weekend (if I can get --enable-targets=all
working on cygwin....).

  Do you think it would be a reasonable approach to define a global flag
variable for the entire bfd library that indicates minimal memory usage is
desired, and a function such as bfd_set_memory_usage_policy() to set it?  It
would allow us to make other functions small-memory friendly as we went
along, without changing any existing behaviour.

  The only other approach I can think of immediately would be to pass a
parameter all the way down from the bfd_XXX interface function until it
arrives at sec_merge_init, but that seems like a long way down the call
stack to me, so I think it's probably not the right approach.


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: PATCH: Speed up ELF section merge

[H. J. Lu]

On Fri, May 06, 2005 at 04:04:27PM +0100, Dave Korn wrote:
> ----Original Message----
> >From: H. J. Lu
> >Sent: 06 May 2005 15:57
> 
> >>   H.J., IIUIC this patch can't do anything to support the ld command line
> >> options --hash-size=<NUMBER> and --reduce-memory-overheads; wouldn't it
> >> be worthwhile providing a means of controlling whether it uses a large
> >> hash table or not? 
> >> 
> > 
> > I am full on my plate.  A patch is more than welcome.  Thanks.
>  
> 
>   I will look at it over the weekend (if I can get --enable-targets=all
> working on cygwin....).
> 
>   Do you think it would be a reasonable approach to define a global flag
> variable for the entire bfd library that indicates minimal memory usage is
> desired, and a function such as bfd_set_memory_usage_policy() to set it?  It
> would allow us to make other functions small-memory friendly as we went
> along, without changing any existing behaviour.

It isn't a bad idear.  We already have

  --no-keep-memory            Use less memory and more disk I/O
  --reduce-memory-overheads   Reduce memory overheads, possibly taking
much long
  --hash-size=<NUMBER>        Set default hash table size close to
<NUMBER>

Can we consolidate them?


H.J.

Re: PATCH: Speed up ELF section merge

[Nick Clifton]

Hi H. J.,
  Hi Dave,

> On Fri, May 06, 2005 at 04:04:27PM +0100, Dave Korn wrote:

>>  Do you think it would be a reasonable approach to define a global flag
>>variable for the entire bfd library that indicates minimal memory usage is
>>desired, and a function such as bfd_set_memory_usage_policy() to set it?  It
>>would allow us to make other functions small-memory friendly as we went
>>along, without changing any existing behaviour.

> It isn't a bad idear.  We already have
> 
>   --no-keep-memory            Use less memory and more disk I/O
>   --reduce-memory-overheads   Reduce memory overheads, possibly taking
> much long
>   --hash-size=<NUMBER>        Set default hash table size close to
> <NUMBER>
> 
> Can we consolidate them?

Yes certainly.  A tidy up in this area would be a good idea.

Cheers
   Nick