This is the mail archive of the
gdb-patches@sources.redhat.com
mailing list for the GDB project.
[intercu] Use a hash table for DIEs after all
- From: Daniel Jacobowitz <drow at false dot org>
- To: gdb-patches at sources dot redhat dot com
- Date: Sat, 21 Feb 2004 15:51:32 -0500
- Subject: [intercu] Use a hash table for DIEs after all
It turns out the splay tree was really not being efficient. For a mostly
sorted access pattern, and strictly sorted addition, trees are about your
worst-case data structure. The hash table seems to do much better.
Committed to the intercu branch.
--
Daniel Jacobowitz
MontaVista Software Debian GNU/Linux Developer
2004-02-21 Daniel Jacobowitz <drow@mvista.com>
* Makefile.in (hashtab_h): Add.
(dwarf2read.o): Update dependencies.
* dwarf2read.c: Include "hashtab.h".
(struct dwarf2_cu): Change partial_dies to an htab_t.
(hash_obstack_allocate, partial_die_hash, partial_die_eq): New
functions.
(dwarf2_build_psymtabs_hard): Call htab_create_alloc_ex.
(load_partial_dies): Call htab_find_slot_with_hash.
(find_partial_die): Call htab_find_with_hash.
Index: Makefile.in
===================================================================
RCS file: /cvs/src/src/gdb/Makefile.in,v
retrieving revision 1.512.2.1
diff -u -p -r1.512.2.1 Makefile.in
--- Makefile.in 21 Feb 2004 20:17:22 -0000 1.512.2.1
+++ Makefile.in 21 Feb 2004 20:47:59 -0000
@@ -583,6 +583,7 @@ gdb_sim_d10v_h = $(INCLUDE_DIR)/gdb/sim-
gdb_sim_frv_h = $(INCLUDE_DIR)/gdb/sim-frv.h
gdb_sim_sh_h = $(INCLUDE_DIR)/gdb/sim-sh.h
splay_tree_h = $(INCLUDE_DIR)/splay-tree.h
+hashtab_h = $(INCLUDE_DIR)/hashtab.h
readline_headers = \
$(READLINE_SRC)/chardefs.h \
@@ -1707,7 +1708,7 @@ dwarf2read.o: dwarf2read.c $(defs_h) $(b
$(expression_h) $(filenames_h) $(macrotab_h) $(language_h) \
$(complaints_h) $(bcache_h) $(dwarf2expr_h) $(dwarf2loc_h) \
$(cp_support_h) $(gdb_string_h) $(gdb_assert_h) \
- $(splay_tree_h)
+ $(splay_tree_h) $(hashtab_h)
dwarfread.o: dwarfread.c $(defs_h) $(symtab_h) $(gdbtypes_h) $(objfiles_h) \
$(elf_dwarf_h) $(buildsym_h) $(demangle_h) $(expression_h) \
$(language_h) $(complaints_h) $(gdb_string_h)
Index: dwarf2read.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarf2read.c,v
retrieving revision 1.135.2.5
diff -u -p -r1.135.2.5 dwarf2read.c
--- dwarf2read.c 21 Feb 2004 20:46:11 -0000 1.135.2.5
+++ dwarf2read.c 21 Feb 2004 20:48:00 -0000
@@ -45,6 +45,7 @@
#include "dwarf2loc.h"
#include "cp-support.h"
#include "splay-tree.h"
+#include "hashtab.h"
#include <fcntl.h>
#include "gdb_string.h"
@@ -260,7 +261,7 @@ struct dwarf2_cu
fundamental types gdb knows how to construct. */
struct type *ftypes[FT_NUM_MEMBERS]; /* Fundamental types */
- splay_tree partial_dies;
+ htab_t partial_dies;
struct obstack partial_die_obstack;
};
@@ -954,6 +955,30 @@ splay_tree_obstack_deallocate (void *obj
return;
}
+static void *
+hash_obstack_allocate (void *data, size_t size, size_t count)
+{
+ unsigned int total = size * count;
+ void *ptr = obstack_alloc ((struct obstack *) data, total);
+ memset (ptr, 0, total);
+ return ptr;
+}
+
+static hashval_t
+partial_die_hash (const void *item)
+{
+ const struct partial_die_info *part_die = item;
+ return part_die->offset;
+}
+
+static int
+partial_die_eq (const void *item_lhs, const void *item_rhs)
+{
+ const struct partial_die_info *part_die_lhs = item_lhs;
+ const struct partial_die_info *part_die_rhs = item_rhs;
+ return part_die_lhs->offset == part_die_rhs->offset;
+}
+
/* Try to locate the sections we need for DWARF 2 debugging
information and return true if we have enough to do something. */
@@ -1318,10 +1343,12 @@ dwarf2_build_psymtabs_hard (struct objfi
obstack_init (&cu.partial_die_obstack);
cu.partial_dies
- = splay_tree_new_with_allocator (splay_tree_compare_ints, NULL,
- NULL, splay_tree_obstack_allocate,
- splay_tree_obstack_deallocate,
- &cu.partial_die_obstack);
+ = htab_create_alloc_ex (29, partial_die_hash,
+ partial_die_eq,
+ NULL,
+ &cu.partial_die_obstack,
+ hash_obstack_allocate,
+ splay_tree_obstack_deallocate);
load_partial_dies (abfd, info_ptr, &cu);
@@ -4501,6 +4528,7 @@ load_partial_dies (bfd *abfd, char *info
struct partial_die_info *parent_die, *last_die;
struct abbrev_info *abbrev;
unsigned int bytes_read;
+ void **slot;
/* FIXME: Obviously we need a nesting level passed in for incremental use. */
int nesting_level = 1;
@@ -4559,8 +4587,10 @@ load_partial_dies (bfd *abfd, char *info
last_die = part_die;
// fprintf_unfiltered (gdb_stderr, "Inserting DIE %x\n", part_die->offset);
- splay_tree_insert (cu->partial_dies, part_die->offset,
- (splay_tree_value) part_die);
+ slot = htab_find_slot_with_hash (cu->partial_dies, part_die,
+ part_die->offset, INSERT);
+ // gdb_assert (*slot == NULL);
+ *slot = part_die;
part_die = obstack_alloc (&cu->partial_die_obstack,
sizeof (struct partial_die_info));
@@ -4714,14 +4744,16 @@ static struct partial_die_info *
find_partial_die (unsigned long offset, struct dwarf2_cu *cu)
{
struct partial_die_info *lookup_die = NULL;
- splay_tree_node node;
+ struct partial_die_info part_die;
- node = splay_tree_lookup (cu->partial_dies, offset);
- if (node == NULL)
+ part_die.offset = offset;
+ lookup_die = htab_find_with_hash (cu->partial_dies, &part_die, offset);
+
+ if (lookup_die == NULL)
internal_error (__FILE__, __LINE__,
"could not find partial DIE in cache\n");
- return (struct partial_die_info *) node->value;
+ return lookup_die;
}
static void