This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
RE: changing the default hash table size (was improving ldperformance)
- From: Nick Clifton <nickc at redhat dot com>
- To: achittenden at bluearc dot com
- Cc: binutils at sources dot redhat dot com
- Date: Fri, 21 May 2004 16:20:08 +0100
- Subject: RE: changing the default hash table size (was improving ldperformance)
Hi Andy,
I am very sorry for forgetting about this patch. :-(
I have now had a chance to review it and I am going to apply it,
albeit in a slightly different version. I made the following
changes:
* I create ChangeLog entries for the bfd/ and ld/ directories.
* I added documentation of the new switch to ld/ld.texinfo and
ld/NEWS.
* I added support for setting the default hash table size to the
new --reduce-memory-overheads linker switch. I also added an
entry for 1021 to the hash_size_primes[] array which is used by
this switch.
* I removed the debugging fprintf() from
bfd_hash_set_default_size().
* I fixed up the formatting to conform to the GNU Coding
Standard.
* I simplified the code in bfd_hash_set_default_size in order to
eliminate the new_hash_size and nhash_size_primes variables. I
also moved the hash_size_primes[] array into this function since
it is only used here.
Incidentally whilst checking this patch I noticed that if the
default hash table size is set to 8599 quite a few linker tests
fail. I did not investigate this fully, but I suspect that this is
because the tests have certain values inappropriately hardwired into
their expected results. You might like to investigate this
yourself.
Cheers
Nick
PS. Here is the patch that I applied.
bfd/ChangeLog
2004-05-21 Nick Clifton <nickc@redhat.com>
* hash.c (bfd_default_hash_table_size): New variable.
(bfd_hash_table_init): Use new variable instead of DEFAULT_SIZE.
(bfd_hash_set_default_size): New function. Set the default size
to a selected prime number close to the argument. Document new
function.
* bfd-in.h: Add prototype for bfd_hash_set_default_size.
* bfd-in2.h: Regenerate.
* Makefile.am (hash.lo): Add dependency upon libiberty.h.
* Makefile.in: Regenerate.
ld/ChangeLog
2004-05-21 Nick Clifton <nickc@redhat.com>
* ld.h (ld_config_type): Add new field: hash_table_size.
* ldmain.c: Initialise the new field to zero. If it is non-zero
after parsing the linker's command line call
bfd_hash_set_default_size.
* lexsup.c (option_values): Add OPTION_HASH_SIZE.
(ld_options): Add hash-size.
(parse_args): Parse --hash-size option. Allow
--reduce-memory-overheads to set the default hash table size as
well.
* ld.texinfo: Document the new switch. Also mention that
--reduce-memory-overheads can affect the hash table size.
* NEWS: Mention the new feature.
Index: bfd/Makefile.am
===================================================================
RCS file: /cvs/src/src/bfd/Makefile.am,v
retrieving revision 1.131
diff -c -3 -p -r1.131 Makefile.am
*** bfd/Makefile.am 8 Apr 2004 15:17:35 -0000 1.131
--- bfd/Makefile.am 21 May 2004 14:54:03 -0000
*************** syms.lo: syms.c $(INCDIR)/filenames.h $(
*** 894,900 ****
$(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def
targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \
targmatch.h
! hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h
linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \
genlink.h
srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
--- 894,900 ----
$(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def
targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \
targmatch.h
! hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h $(INCDIR)/libiberty.h
linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \
genlink.h
srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
Index: bfd/Makefile.in
===================================================================
RCS file: /cvs/src/src/bfd/Makefile.in,v
retrieving revision 1.144
diff -c -3 -p -r1.144 Makefile.in
*** bfd/Makefile.in 8 Apr 2004 15:17:35 -0000 1.144
--- bfd/Makefile.in 21 May 2004 14:54:04 -0000
*************** syms.lo: syms.c $(INCDIR)/filenames.h $(
*** 1431,1437 ****
$(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def
targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \
targmatch.h
! hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h
linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \
genlink.h
srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
--- 1431,1437 ----
$(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def
targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \
targmatch.h
! hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h $(INCDIR)/libiberty.h
linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \
genlink.h
srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
Index: bfd/bfd-in.h
===================================================================
RCS file: /cvs/src/src/bfd/bfd-in.h,v
retrieving revision 1.79
diff -c -3 -p -r1.79 bfd-in.h
*** bfd/bfd-in.h 21 Apr 2004 20:52:25 -0000 1.79
--- bfd/bfd-in.h 21 May 2004 14:54:06 -0000
*************** extern void bfd_hash_traverse
*** 433,438 ****
--- 433,443 ----
bfd_boolean (*) (struct bfd_hash_entry *, void *),
void *info);
+ /* Allows the default size of a hash table to be configured. New hash
+ tables allocated using bfd_hash_table_init will be created with
+ this size. */
+ extern void bfd_hash_set_default_size (bfd_size_type);
+
#define COFF_SWAP_TABLE (void *) &bfd_coff_std_swap_table
/* User program access to BFD facilities. */
Index: bfd/bfd-in2.h
===================================================================
RCS file: /cvs/src/src/bfd/bfd-in2.h,v
retrieving revision 1.277
diff -c -3 -p -r1.277 bfd-in2.h
*** bfd/bfd-in2.h 17 May 2004 16:40:01 -0000 1.277
--- bfd/bfd-in2.h 21 May 2004 14:54:10 -0000
*************** extern void bfd_hash_traverse
*** 440,445 ****
--- 440,450 ----
bfd_boolean (*) (struct bfd_hash_entry *, void *),
void *info);
+ /* Allows the default size of a hash table to be configured. New hash
+ tables allocated using bfd_hash_table_init will be created with
+ this size. */
+ extern void bfd_hash_set_default_size (bfd_size_type);
+
#define COFF_SWAP_TABLE (void *) &bfd_coff_std_swap_table
/* User program access to BFD facilities. */
Index: bfd/hash.c
===================================================================
RCS file: /cvs/src/src/bfd/hash.c,v
retrieving revision 1.11
diff -c -3 -p -r1.11 hash.c
*** bfd/hash.c 1 Dec 2003 06:33:01 -0000 1.11
--- bfd/hash.c 21 May 2004 14:54:11 -0000
***************
*** 1,28 ****
/* hash.c -- hash table routines for BFD
! Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003
Free Software Foundation, Inc.
Written by Steve Chamberlain <sac@cygnus.com>
! This file is part of BFD, the Binary File Descriptor library.
! This program is free software; you can redistribute it and/or modify
! it under the terms of the GNU General Public License as published by
! the Free Software Foundation; either version 2 of the License, or
! (at your option) any later version.
!
! This program is distributed in the hope that it will be useful,
! but WITHOUT ANY WARRANTY; without even the implied warranty of
! MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
! GNU General Public License for more details.
!
! You should have received a copy of the GNU General Public License
! along with this program; if not, write to the Free Software
! Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#include "bfd.h"
#include "sysdep.h"
#include "libbfd.h"
#include "objalloc.h"
/*
SECTION
--- 1,29 ----
/* hash.c -- hash table routines for BFD
! Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
Written by Steve Chamberlain <sac@cygnus.com>
! This file is part of BFD, the Binary File Descriptor library.
! This program is free software; you can redistribute it and/or modify
! it under the terms of the GNU General Public License as published by
! the Free Software Foundation; either version 2 of the License, or
! (at your option) any later version.
!
! This program is distributed in the hope that it will be useful,
! but WITHOUT ANY WARRANTY; without even the implied warranty of
! MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
! GNU General Public License for more details.
!
! You should have received a copy of the GNU General Public License
! along with this program; if not, write to the Free Software
! Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#include "bfd.h"
#include "sysdep.h"
#include "libbfd.h"
#include "objalloc.h"
+ #include "libiberty.h"
/*
SECTION
*************** SECTION
*** 53,58 ****
--- 54,60 ----
@* Looking Up or Entering a String::
@* Traversing a Hash Table::
@* Deriving a New Hash Table Type::
+ @* Changing the default Hash Table Size::
@end menu
INODE
*************** SUBSECTION
*** 87,92 ****
--- 89,98 ----
been allocated for a hash table. This will not free up the
<<struct bfd_hash_table>> itself, which you must provide.
+ @findex bfd_hash_set_default_size
+ Use <<bfd_hash_set_default_size>> to set the default size of
+ hash table to use.
+
INODE
Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
SUBSECTION
*************** SUBSUBSECTION
*** 295,301 ****
*/
/* The default number of entries to use when creating a hash table. */
! #define DEFAULT_SIZE (4051)
/* Create a new hash table, given a number of entries. */
--- 301,308 ----
*/
/* The default number of entries to use when creating a hash table. */
! #define DEFAULT_SIZE 4051
! static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
/* Create a new hash table, given a number of entries. */
*************** bfd_hash_table_init (table, newfunc)
*** 339,345 ****
struct bfd_hash_table *,
const char *));
{
! return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE);
}
/* Free a hash table. */
--- 346,352 ----
struct bfd_hash_table *,
const char *));
{
! return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size);
}
/* Free a hash table. */
*************** bfd_hash_traverse (table, func, info)
*** 493,498 ****
--- 500,523 ----
return;
}
}
+ }
+
+ void
+ bfd_hash_set_default_size (bfd_size_type hash_size)
+ {
+ int index;
+ /* Extend this prime list if you want more granularity of hash table size. */
+ static bfd_size_type hash_size_primes[] =
+ {
+ 1021, 4051, 8599, 16699
+ };
+
+ /* Work out best prime number near the hash_size. */
+ for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
+ if (hash_size <= hash_size_primes[index])
+ break;
+
+ bfd_default_hash_table_size = hash_size_primes[index];
}
/* A few different object file formats (a.out, COFF, ELF) use a string
Index: ld/NEWS
===================================================================
RCS file: /cvs/src/src/ld/NEWS,v
retrieving revision 1.46
diff -c -3 -p -r1.46 NEWS
*** ld/NEWS 19 May 2004 14:15:55 -0000 1.46
--- ld/NEWS 21 May 2004 14:54:12 -0000
***************
*** 1,11 ****
--- 1,19 ----
-*- text -*-
+ * A new linker command line switch has been added which allows the hash table
+ size to be set to a suitable prime value near to its argument. This switch
+ is --hash-size=<NUMBER>. Also if the switch --reduce-memory-overheads is
+ used, and --hash-size has not been used, then the default value will be set
+ to 1021.
+
* Linker map files are now generated with an O(N) algorithm for finding symbols
that are defined in each section. This uses about 40% more memory for
symbols than the old O(N^2) algorithm. You can use the new
--reduce-memory-overheads option to select the old algorithm; this option
might also be used in the future to select similar tradeoffs.
+ Changes in 2.15:
+
* New PE --large-address-aware option to indicate executables support virtual
addresses greater than 2 gigabytes.
Index: ld/ld.h
===================================================================
RCS file: /cvs/src/src/ld/ld.h,v
retrieving revision 1.22
diff -c -3 -p -r1.22 ld.h
*** ld/ld.h 19 May 2004 14:15:55 -0000 1.22
--- ld/ld.h 21 May 2004 14:54:12 -0000
***************
*** 1,5 ****
/* ld.h -- general linker header file
! Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2002
Free Software Foundation, Inc.
This file is part of GLD, the Gnu Linker.
--- 1,5 ----
/* ld.h -- general linker header file
! Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2002, 2004
Free Software Foundation, Inc.
This file is part of GLD, the Gnu Linker.
*************** typedef struct {
*** 241,246 ****
--- 241,249 ----
/* If set, only search library directories explicitly selected
on the command line. */
bfd_boolean only_cmd_line_lib_dirs;
+
+ /* The size of the hash table to use. */
+ bfd_size_type hash_table_size;
} ld_config_type;
extern ld_config_type config;
Index: ld/ld.texinfo
===================================================================
RCS file: /cvs/src/src/ld/ld.texinfo,v
retrieving revision 1.115
diff -c -3 -p -r1.115 ld.texinfo
*** ld/ld.texinfo 19 May 2004 14:15:55 -0000 1.115
--- ld/ld.texinfo 21 May 2004 14:54:21 -0000
*************** If you specify @option{--disable-new-dta
*** 1734,1746 ****
created. By default, the new dynamic tags are not created. Note that
those options are only available for ELF systems.
@kindex --reduce-memory-overheads
@item --reduce-memory-overheads
This option reduces memory requirements at ld runtime, at the expense of
linking speed. This was introduced to to select the old O(n^2) algorithm
for link map file generation, rather than the new O(n) algorithm which uses
! about 40% more memory for symbol storage. It may be also be used for
! similar such tradeoffs in the future.
@end table
--- 1734,1760 ----
created. By default, the new dynamic tags are not created. Note that
those options are only available for ELF systems.
+ @kindex --hash-size=@var{number}
+ Set the default size of the linker's hash tables to a prime number
+ close to @var{number}. Increasing this value can reduce the length of
+ time it takes the linker to perform its tasks, at the expense of
+ increasing the linker's memory requirements. Similarly reducing this
+ value can reduce the memory requirements at the expense of speed.
+
@kindex --reduce-memory-overheads
@item --reduce-memory-overheads
This option reduces memory requirements at ld runtime, at the expense of
linking speed. This was introduced to to select the old O(n^2) algorithm
for link map file generation, rather than the new O(n) algorithm which uses
! about 40% more memory for symbol storage.
!
! Another affect of the switch is to set the default hash table size to
! 1021, which again saves memory at the cost of lengthening the linker's
! run time. This is not done however if the *option{--hash-size} switch
! has been used.
!
! The @option{--reduce-memory-overheads} switch may be also be used to
! enable other tradeoffs in future versions of the linker.
@end table
Index: ld/ldmain.c
===================================================================
RCS file: /cvs/src/src/ld/ldmain.c,v
retrieving revision 1.81
diff -c -3 -p -r1.81 ldmain.c
*** ld/ldmain.c 19 May 2004 14:15:55 -0000 1.81
--- ld/ldmain.c 21 May 2004 14:54:22 -0000
*************** main (int argc, char **argv)
*** 267,272 ****
--- 267,273 ----
config.has_shared = FALSE;
config.split_by_reloc = (unsigned) -1;
config.split_by_file = (bfd_size_type) -1;
+ config.hash_table_size = 0;
command_line.force_common_definition = FALSE;
command_line.inhibit_common_definition = FALSE;
command_line.interpreter = NULL;
*************** main (int argc, char **argv)
*** 343,348 ****
--- 344,352 ----
ldemul_before_parse ();
lang_has_input_file = FALSE;
parse_args (argc, argv);
+
+ if (config.hash_table_size != 0)
+ bfd_hash_set_default_size (config.hash_table_size);
ldemul_set_symbols ();
Index: ld/lexsup.c
===================================================================
RCS file: /cvs/src/src/ld/lexsup.c,v
retrieving revision 1.73
diff -c -3 -p -r1.73 lexsup.c
*** ld/lexsup.c 19 May 2004 14:15:55 -0000 1.73
--- ld/lexsup.c 21 May 2004 14:54:24 -0000
*************** enum option_values
*** 118,123 ****
--- 118,124 ----
OPTION_FORCE_EXE_SUFFIX,
OPTION_GC_SECTIONS,
OPTION_NO_GC_SECTIONS,
+ OPTION_HASH_SIZE,
OPTION_CHECK_SECTIONS,
OPTION_NO_CHECK_SECTIONS,
OPTION_NO_UNDEFINED,
*************** static const struct ld_option ld_options
*** 328,333 ****
--- 329,336 ----
{ {"no-gc-sections", no_argument, NULL, OPTION_NO_GC_SECTIONS},
'\0', NULL, N_("Don't remove unused sections (default)"),
TWO_DASHES },
+ { {"hash-size=<NUMBER>", required_argument, NULL, OPTION_HASH_SIZE},
+ '\0', NULL, N_("Set default hash table size close to <NUMBER>"), TWO_DASHES },
{ {"help", no_argument, NULL, OPTION_HELP},
'\0', NULL, N_("Print option help"), TWO_DASHES },
{ {"init", required_argument, NULL, OPTION_INIT},
*************** static const struct ld_option ld_options
*** 364,369 ****
--- 367,374 ----
'\0', N_("TARGET"), N_("Specify target of output file"), EXACTLY_TWO_DASHES },
{ {"qmagic", no_argument, NULL, OPTION_IGNORE},
'\0', NULL, N_("Ignored for Linux compatibility"), ONE_DASH },
+ { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS},
+ '\0', NULL, N_("Reduce memory overheads, possibly taking much longer"), TWO_DASHES },
{ {"relax", no_argument, NULL, OPTION_RELAX},
'\0', NULL, N_("Relax branches on certain targets"), TWO_DASHES },
{ {"retain-symbols-file", required_argument, NULL,
*************** static const struct ld_option ld_options
*** 447,454 ****
'\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES },
{ {"wrap", required_argument, NULL, OPTION_WRAP},
'\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES },
- { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS},
- '\0', NULL, N_("reduce memory overheads, possibly taking much longer"), TWO_DASHES },
};
#define OPTION_COUNT ARRAY_SIZE (ld_options)
--- 452,457 ----
*************** parse_args (unsigned argc, char **argv)
*** 1224,1232 ****
--- 1227,1242 ----
case OPTION_FINI:
link_info.fini_function = optarg;
break;
+
case OPTION_REDUCE_MEMORY_OVERHEADS:
command_line.reduce_memory_overheads = TRUE;
+ if (config.hash_table_size == 0)
+ config.hash_table_size = 1021;
break;
+
+ case OPTION_HASH_SIZE:
+ config.hash_table_size = strtoul (optarg, NULL, 0);
+ break;
}
}