This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PATCH: Speedup hashtables, ASM_OUTPUT_SECTION_NAME
- To: gcc-patches at gcc dot gnu dot org
- Subject: PATCH: Speedup hashtables, ASM_OUTPUT_SECTION_NAME
- From: Mark Mitchell <mark at codesourcery dot com>
- Date: Sun, 26 Nov 2000 20:23:02 -0800
- Organization: CodeSourcery, LLC
I've started attacking the low-hanging fruit for a test-case that
Gerald sent me. Using the profiler, I fould some surprising culprits
near the top of the chain:
- higher_prime_number in hashtab.c
This function used the seive of Erosthosthanes (sp?) to compute
prime numbers. If we really needed to do that, we should use
some probabilistic method (e.g., Rabin) but we don't -- we just
need a table.
- ASM_OUTPUT_SECTION_NAME
This function kept a linked list of all the sections that had
been output. In C++, when you can have *lots* of sections due
to how we implement templates, this was very bad. I switched
this to use a hashtable. (Also, thanks to the stringpool
stuff, we no longer have to copy the section name for the section
table, which makes for some memory savings, too.)
If your port doesn't use the elfos/config.h definition of
ASM_OUTPUT_SECTION_NAME, you should look at your
ASM_OUTPUT_SECTION_NAME to see if it wants optimizing, too.
That knocked the time from 57.35 to 52.84 seconds: a 7.9% improvement.
There's some more low-hanging fruit, and then we get into the good
stuff...
--
Mark Mitchell mark@codesourcery.com
CodeSourcery, LLC http://www.codesourcery.com
2000-11-26 Mark Mitchell <mark@codesourcery.com>
* hashtab.c (higher_prime_number): Use a table, rather than a
seive, to find the next prime.
2000-11-26 Mark Mitchell <mark@codesourcery.com>
* config/elfos.h (ASM_OUTPUT_SECTION_NAME): Use a hash table, not
a list, to keep track of the sections.
* tm.texi (ASM_OUTPUT_SECTION_NAME): Document the fact that the
parameter provided will always be a canonical string.
Index: libiberty/hashtab.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/hashtab.c,v
retrieving revision 1.18
diff -c -p -r1.18 hashtab.c
*** hashtab.c 2000/11/04 07:42:53 1.18
--- hashtab.c 2000/11/27 04:11:30
*************** static PTR *find_empty_slot_for_expand
*** 71,105 ****
htab_hash htab_hash_pointer = hash_pointer;
htab_eq htab_eq_pointer = eq_pointer;
! /* The following function returns the nearest prime number which is
! greater than a given source number, N. */
static unsigned long
higher_prime_number (n)
unsigned long n;
{
! unsigned long i;
! /* Ensure we have a larger number and then force to odd. */
! n++;
! n |= 0x01;
!
! /* All odd numbers < 9 are prime. */
! if (n < 9)
! return n;
!
! /* Otherwise find the next prime using a sieve. */
!
! next:
!
! for (i = 3; i * i <= n; i += 2)
! if (n % i == 0)
! {
! n += 2;
! goto next;
! }
!
! return n;
}
/* Returns a hash code for P. */
--- 71,139 ----
htab_hash htab_hash_pointer = hash_pointer;
htab_eq htab_eq_pointer = eq_pointer;
! /* The following function returns a nearest prime number which is
! greater than N, and near a power of two. */
static unsigned long
higher_prime_number (n)
unsigned long n;
{
! /* These are primes that are near, but slightly smaller than, a
! power of two. */
! static unsigned long primes[] = {
! 2,
! 7,
! 13,
! 31,
! 61,
! 127,
! 251,
! 509,
! 1021,
! 2039,
! 4093,
! 8191,
! 16381,
! 32749,
! 65521,
! 131071,
! 262139,
! 524287,
! 1048573,
! 2097143,
! 4194301,
! 8388593,
! 16777213,
! 33554393,
! 67108859,
! 134217689,
! 268435399,
! 536870909,
! 1073741789,
! 2147483647,
! 4294967291
! };
!
! unsigned long* low = &primes[0];
! unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
!
! while (low != high)
! {
! unsigned long* mid = low + (high - low) / 2;
! if (n > *mid)
! low = mid + 1;
! else
! high = mid;
! }
!
! /* If we've run out of primes, abort. */
! if (n > *low)
! {
! fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
! abort ();
! }
! return *low;
}
/* Returns a hash code for P. */
Index: gcc/config/elfos.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/elfos.h,v
retrieving revision 1.22
diff -c -p -r1.22 elfos.h
*** elfos.h 2000/10/09 23:55:50 1.22
--- elfos.h 2000/11/27 04:11:22
*************** dtors_section () \
*** 421,440 ****
#define ASM_OUTPUT_SECTION_NAME(FILE, DECL, NAME, RELOC) \
do \
{ \
! static struct section_info \
{ \
- struct section_info *next; \
- char *name; \
enum sect_enum {SECT_RW, SECT_RO, SECT_EXEC} type; \
! } *sections; \
struct section_info *s; \
const char *mode; \
! enum sect_enum type; \
! \
! for (s = sections; s; s = s->next) \
! if (!strcmp (NAME, s->name)) \
! break; \
! \
if (DECL && TREE_CODE (DECL) == FUNCTION_DECL) \
type = SECT_EXEC, mode = "ax"; \
else if (DECL && DECL_READONLY_SECTION (DECL, RELOC)) \
--- 421,447 ----
#define ASM_OUTPUT_SECTION_NAME(FILE, DECL, NAME, RELOC) \
do \
{ \
! static htab_t htab; \
! \
! struct section_info \
{ \
enum sect_enum {SECT_RW, SECT_RO, SECT_EXEC} type; \
! }; \
! \
struct section_info *s; \
const char *mode; \
! enum sect_enum type; \
! PTR* slot; \
! \
! /* The names we put in the hashtable will always be the unique \
! versions gived to us by the stringtable, so we can just use \
! their addresses as the keys. */ \
! if (!htab) \
! htab = htab_create (31, \
! htab_hash_pointer, \
! htab_eq_pointer, \
! NULL); \
! \
if (DECL && TREE_CODE (DECL) == FUNCTION_DECL) \
type = SECT_EXEC, mode = "ax"; \
else if (DECL && DECL_READONLY_SECTION (DECL, RELOC)) \
*************** dtors_section () \
*** 442,462 ****
else \
type = SECT_RW, mode = "aw"; \
\
! if (s == 0) \
! { \
s = (struct section_info *) xmalloc (sizeof (* s)); \
- s->name = xmalloc ((strlen (NAME) + 1) * sizeof (* NAME)); \
- strcpy (s->name, NAME); \
s->type = type; \
! s->next = sections; \
! sections = s; \
fprintf (FILE, "\t.section\t%s,\"%s\",@progbits\n", \
NAME, mode); \
} \
else \
{ \
if (DECL && s->type != type) \
! error_with_decl (DECL, "%s causes a section type conflict");\
\
fprintf (FILE, "\t.section\t%s\n", NAME); \
} \
--- 449,471 ----
else \
type = SECT_RW, mode = "aw"; \
\
! \
! /* See if we already have an entry for this section. */ \
! slot = htab_find_slot (htab, NAME, INSERT); \
! if (!*slot) \
! { \
s = (struct section_info *) xmalloc (sizeof (* s)); \
s->type = type; \
! *slot = s; \
fprintf (FILE, "\t.section\t%s,\"%s\",@progbits\n", \
NAME, mode); \
} \
else \
{ \
+ s = (struct section_info *) *slot; \
if (DECL && s->type != type) \
! error_with_decl (DECL, \
! "%s causes a section type conflict"); \
\
fprintf (FILE, "\t.section\t%s\n", NAME); \
} \
Index: tm.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tm.texi,v
retrieving revision 1.153
diff -c -p -r1.153 tm.texi
*** tm.texi 2000/11/25 00:33:04 1.153
--- tm.texi 2000/11/27 04:13:45
*************** A C statement to output something to the
*** 5439,5446 ****
@var{name} for object @var{decl} which is either a @code{FUNCTION_DECL}, a
@code{VAR_DECL} or @code{NULL_TREE}. @var{reloc}
indicates whether the initial value of @var{exp} requires link-time
! relocations. Some target formats do not support
! arbitrary sections. Do not define this macro in such cases.
At present this macro is only used to support section attributes.
When this macro is undefined, section attributes are disabled.
--- 5439,5449 ----
@var{name} for object @var{decl} which is either a @code{FUNCTION_DECL}, a
@code{VAR_DECL} or @code{NULL_TREE}. @var{reloc}
indicates whether the initial value of @var{exp} requires link-time
! relocations. The string given by @var{name} will always be the
! canonical version stored in the global stringpool.
!
! Some target formats do not support arbitrary sections. Do not define
! this macro in such cases.
At present this macro is only used to support section attributes.
When this macro is undefined, section attributes are disabled.