This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Don't reallocate small almost empty hashtabs on every htab_traverse call
- From: Jakub Jelinek <jakub at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 19 Jun 2009 16:18:03 +0200
- Subject: [PATCH] Don't reallocate small almost empty hashtabs on every htab_traverse call
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
Hi!
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 <jakub@redhat.com>
* 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 (vmakarov@cygnus.com).
@@ -759,7 +759,8 @@ htab_traverse_noresize (htab_t htab, hta
void
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);
Jakub