This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Don't reallocate small almost empty hashtabs on every htab_traverse call


htab_traverse unnecessarily reallocates small hash tables on every call.
The problem is that htab_expand is called whenever
htab_elements * 8 < htab_size,
but htab_expand doesn't change hash table size at all if not growing
and size is 7, 13 or 31.  So it just allocates new entries array
of the same size as before and refills it in.  If there are deleted entries,
it will change at least something (but nothing htab_traverse_noresize
cares about, as it ignores both NULL and deleted entries); if there
are no deleted entries, it just means a copy to a new same sized
buffer, with no changes whatsoever, and, on the new htab_traverse it
will be reallocated again if no entries have been added to change
the condition.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2009-06-19  Jakub Jelinek  <>

	* hashtab.c (htab_traverse): Don't call htab_expand for
	nearly empty hashtabs with sizes 7, 13 or 31.

--- libiberty/hashtab.c.jj	2008-09-30 16:57:39.000000000 +0200
+++ libiberty/hashtab.c	2009-06-19 14:16:52.000000000 +0200
@@ -1,5 +1,5 @@
 /* An expandable hash tables datatype.  
-   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009
    Free Software Foundation, Inc.
    Contributed by Vladimir Makarov (
@@ -759,7 +759,8 @@ htab_traverse_noresize (htab_t htab, hta
 htab_traverse (htab_t htab, htab_trav callback, PTR info)
-  if (htab_elements (htab) * 8 < htab_size (htab))
+  size_t size = htab_size (htab);
+  if (htab_elements (htab) * 8 < size && size > 32)
     htab_expand (htab);
   htab_traverse_noresize (htab, callback, info);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]