https://sourceware.org/bugzilla/show_bug.cgi?id=17677
Bug ID: 17677
Summary: _bfd_elf_get_synthetic_symtab runs in O(n^2)
complexity after commit
5840bf271c87c3fc14739173fdc91c6a14057130
Product: binutils
Version: 2.24
Status: NEW
Severity: normal
Priority: P2
Component: binutils
Assignee: unassigned at sourceware dot org
Reporter: tohava at gmail dot com
This bug was also reported here:
https://bugs.launchpad.net/ubuntu/+source/gdb/+bug/1388999
This bug causes a major slowdown for shared objects with many symbols (loading
times gone from 1 minute to 15 minutes). One possible fix for this is to
allocate an array of size n (n is the plt size) and fill it with the correct
values via random access, doing only one pass on the binary.
I will illustrate this with pseudo code.
Here is the current algorithm, as implemented in
_bfd_elf_get_synthetic_symtab's second for-loop.
for i = 0 to count
addr = bed->plt_sym_val(i, plt, p); // this function has average linear
complexity
// here addr is processed
I would replace the second for-loop with something like this (inspired by
elf_x86_64_plt_sym_val):
quick_plt_table = malloc(sizeof(bfd_vma) * count);
for i = 0 to count
if type_doesnt_match_backend()
continue
bfd_get_section_contents(abfd,..., reloc_index_raw);
reloc_index = H_GET_32(abfd, reloc_index_raw);
quick_plt_table[reloc_index] = plt->vma + plt_offset;
plt_offset += bed->plt_entry_size;
rel += int_rels_per_ext_rel;
for i = 0 to count
addr = quick_plt[i];
// here addr is processed as done previously
Note that my version runs in linear complexity, and thus takes less time.
--
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
bug-binutils mailing list
bug-binutils@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-binutils
