From: "Martin Liška" <mliska@suse.cz>
To: binutils@sourceware.org
Subject: [PATCH] add splay tree for info_ptr -> CU mapping
Date: Sun, 7 Aug 2022 20:05:13 +0200 [thread overview]
Message-ID: <5101c1e0-e121-b897-03a2-0be6c1387d41@suse.cz> (raw)
While using perf top for MozillaThunderbird I noticed quite some slow
dissably call with source code involved. E.g.
time ./objdump --start-address=0x0000000004e0dcd0 --stop-address=0x0000000004e0df8b -l -d --no-show-raw-insn -S -C /usr/lib64/thunderbird/libxul.so
took 2.071s and I noticed quite some time is spent in
find_abstract_instance:
33.46% objdump objdump [.] find_abstract_instance
18.22% objdump objdump [.] arange_add
13.77% objdump objdump [.] read_attribute_value
4.82% objdump objdump [.] comp_unit_maybe_decode_line_info
3.10% objdump libc.so.6 [.] __memset_avx2_unaligned_erms
where linked list of CU is iterated when searing for where info_ptr
belongs to:
: 3452 for (u = unit->prev_unit; u != NULL; u = u->prev_unit)
0.00 : 4c61f7: mov 0x10(%rbx),%rax
0.00 : 4c61fb: test %rax,%rax
0.00 : 4c61fe: je 4c6215 <find_abstract_instance+0x365>
: 3453 if (info_ptr >= u->info_ptr_unit && info_ptr < u->end_ptr)
0.00 : 4c6200: cmp 0x60(%rax),%rdx
83.20 : 4c6204: jb 4c620c <find_abstract_instance+0x35c>
0.00 : 4c6206: cmp 0x78(%rax),%rdx
6.89 : 4c620a: jb 4c6270 <find_abstract_instance+0x3c0>
: 3452 for (u = unit->prev_unit; u != NULL; u = u->prev_unit)
0.00 : 4c620c: mov 0x10(%rax),%rax
7.90 : 4c6210: test %rax,%rax
0.00 : 4c6213: jne 4c6200 <find_abstract_instance+0x350>
The following scan can be replaced with search in a splay tree and with
that I can get to 1.5s and there are other symbols where the difference
is even bigger.
bfd/ChangeLog:
* dwarf2.c (struct addr_range): New.
(addr_range_intersects): Likewise.
(splay_tree_compare_addr_range): Likewise.
(splay_tree_free_addr_range): Likewise.
(struct dwarf2_debug_file): Add comp_unit_tree.
(find_abstract_instance): Use the splay tree when searching
for a info_ptr.
(stash_comp_unit): Insert to the splay tree.
(_bfd_dwarf2_cleanup_debug_info): Clean up the splay tree.
---
bfd/dwarf2.c | 77 +++++++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 67 insertions(+), 10 deletions(-)
diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c
index 47618788513..0449877966a 100644
--- a/bfd/dwarf2.c
+++ b/bfd/dwarf2.c
@@ -36,6 +36,7 @@
#include "elf-bfd.h"
#include "dwarf2.h"
#include "hashtab.h"
+#include "splay-tree.h"
/* The data in the .debug_line statement prologue looks like this. */
@@ -152,6 +153,45 @@ static struct trie_node *alloc_trie_leaf (bfd *abfd)
return &leaf->head;
}
+struct addr_range
+{
+ bfd_byte *start;
+ bfd_byte *end;
+};
+
+/* Return true if address range do intersect. */
+
+static bool
+addr_range_intersects (struct addr_range *r1, struct addr_range *r2)
+{
+ return (r1->start <= r2->start && r2->start < r1->end)
+ || (r1->start <= (r2->end - 1) && (r2->end - 1) < r1->end);
+}
+
+/* Compare function for splay tree of addr_ranges. */
+
+static int
+splay_tree_compare_addr_range (splay_tree_key xa, splay_tree_key xb)
+{
+ struct addr_range *r1 = (struct addr_range *) xa;
+ struct addr_range *r2 = (struct addr_range *) xb;
+
+ if (addr_range_intersects (r1, r2) || addr_range_intersects (r2, r1))
+ return 0;
+ else if (r1->end <= r2->start)
+ return -1;
+ else
+ return 1;
+}
+
+/* Splay tree release function for keys (addr_range). */
+
+static void
+splay_tree_free_addr_range (splay_tree_key key)
+{
+ free ((struct addr_range *)key);
+}
+
struct dwarf2_debug_file
{
/* The actual bfd from which debug info was loaded. Might be
@@ -235,6 +275,9 @@ struct dwarf2_debug_file
/* Root of a trie to map addresses to compilation units. */
struct trie_node *trie_root;
+
+ /* Splay tree to map info_ptr address to compilation units. */
+ splay_tree comp_unit_tree;
};
struct dwarf2_debug
@@ -3447,16 +3490,12 @@ find_abstract_instance (struct comp_unit *unit,
else
{
/* Check other CUs to see if they contain the abbrev. */
- struct comp_unit *u;
-
- for (u = unit->prev_unit; u != NULL; u = u->prev_unit)
- if (info_ptr >= u->info_ptr_unit && info_ptr < u->end_ptr)
- break;
-
- if (u == NULL)
- for (u = unit->next_unit; u != NULL; u = u->next_unit)
- if (info_ptr >= u->info_ptr_unit && info_ptr < u->end_ptr)
- break;
+ struct comp_unit *u = NULL;
+ struct addr_range range = { info_ptr, info_ptr };
+ splay_tree_node v = splay_tree_lookup (unit->file->comp_unit_tree,
+ (splay_tree_key)&range);
+ if (v != NULL)
+ u = (struct comp_unit *)v->value;
if (attr_ptr->form == DW_FORM_ref_addr)
while (u == NULL)
@@ -5517,6 +5556,22 @@ stash_comp_unit (struct dwarf2_debug *stash, struct dwarf2_debug_file *file)
info_ptr_unit, offset_size);
if (each)
{
+ if (file->comp_unit_tree == NULL)
+ file->comp_unit_tree
+ = splay_tree_new (splay_tree_compare_addr_range,
+ splay_tree_free_addr_range, NULL);
+
+ struct addr_range *r
+ = (struct addr_range *)bfd_malloc (sizeof (struct addr_range));
+ r->start = each->info_ptr_unit;
+ r->end = each->end_ptr;
+ splay_tree_node v = splay_tree_lookup (file->comp_unit_tree,
+ (splay_tree_key)r);
+ if (v != NULL || r->end <= r->start)
+ abort ();
+ splay_tree_insert (file->comp_unit_tree, (splay_tree_key)r,
+ (splay_tree_value)each);
+
if (file->all_comp_units)
file->all_comp_units->prev_unit = each;
else
@@ -5990,6 +6045,8 @@ _bfd_dwarf2_cleanup_debug_info (bfd *abfd, void **pinfo)
free (file->line_table->dirs);
}
htab_delete (file->abbrev_offsets);
+ if (file->comp_unit_tree != NULL)
+ splay_tree_delete (file->comp_unit_tree);
free (file->dwarf_line_str_buffer);
free (file->dwarf_str_buffer);
--
2.37.1
next reply other threads:[~2022-08-07 18:05 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-07 18:05 Martin Liška [this message]
2022-08-08 11:06 ` Nick Clifton
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5101c1e0-e121-b897-03a2-0be6c1387d41@suse.cz \
--to=mliska@suse.cz \
--cc=binutils@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).