From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id E55EC3858C50 for ; Sun, 7 Aug 2022 18:05:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E55EC3858C50 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 2F6271F938 for ; Sun, 7 Aug 2022 18:05:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1659895514; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=FvCLRTS+AKdXszquvLHKQdKnrJHdrWVElZxDxQaxJAI=; b=2gnxSNo2erCmsg2wNm7eEkvGL2JRa6wh5zSsuYfwktei+Iyds/IoHgM5Y4Ndru9Dg/MS7n RZPVmkFExSGNOouW8qBDFMmR9moGfoi2b3xrK1iB2xifFB9TQ964EHfaYZwX0PmgbFjvHD zgvsrJ5FsorqYCQFvDlt00c/XUgrd0U= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1659895514; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=FvCLRTS+AKdXszquvLHKQdKnrJHdrWVElZxDxQaxJAI=; b=5q17EsIl8i++bwADR3SlAjcjrgpdM7TES5Ka++8ZPMWArBweSgIr3CFk2WuWZpcUJYmzYy oN5zLRN7yrEzu/AQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 201D81333E for ; Sun, 7 Aug 2022 18:05:14 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id hca+Btr+72KiWgAAMHmgww (envelope-from ) for ; Sun, 07 Aug 2022 18:05:14 +0000 Message-ID: <5101c1e0-e121-b897-03a2-0be6c1387d41@suse.cz> Date: Sun, 7 Aug 2022 20:05:13 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.1.0 From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Subject: [PATCH] add splay tree for info_ptr -> CU mapping To: binutils@sourceware.org Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_SOFTFAIL, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Aug 2022 18:05:16 -0000 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 : 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 0.00 : 4c6206: cmp 0x78(%rax),%rdx 6.89 : 4c620a: jb 4c6270 : 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 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