llvm dev - May 2021 - llvm-objcopy --keep-symbols performance

While investigating an issue with android build performance, I found that
llvm-objcopy performance is far from parity with GNU objcopy for the
"--keep-symbols" case, when the keep symbols list is very large.

I can see that llvm objcopy creates a list of NameOrPattern-s to represent the
keep symbol list, but it looks like it exhaustively compares each symbol in the
keep list against each symbol in the input file.  Not sure what GNU objcopy does
but merging the non-pattern symbol names into a sorted list would make searching
much faster.

Below is a script to reproduce the problem and its output.  The test case below
demonstrates a significant performance difference.  The android build failure
case reported had a shared obj with ~700k symbols and the keep list was ~300k
symbols and it took ~8 minutes to execute.

~~~
#!/bin/bash

set -euo pipefail

echo creating init file
echo <<EOF > input.S
.section .text
EOF
echo '' > keep_syms.txt
for i in $(seq 0 100000)
do
    echo -e "sym_${i}:\nnop\n" >> input.S
    if [[ ${i} -lt 30000 ]]; then
        echo "sym_${i}" >> keep_syms.txt
    fi
done
echo <<EOF >> input.S
.section .ballast
nop
EOF
echo creating obj file
llvm-mc -triple arm-linux-androideabi -filetype=obj input.S -o out.o
echo creating shared obj file
ld.lld  -shared out.o -o libtestcase.so

echo performing llvm objcopy
\time llvm-objcopy -S --remove-section .ballast  \
    --keep-symbols=keep_syms.txt \
    libtestcase.so libtestcase_smaller.so

echo performing GNU objcopy
\time arm-linux-androideabi-objcopy -S --remove-section .ballast  \
    --keep-symbols=keep_syms.txt \
    libtestcase.so libtestcase_smaller.so
~~~

Here's the output I get when I run it on ToT-within-last-week-or-so:

$ PATH=$PWD/bin:$PATH ../../tmp/qt66370/32/objcopy_perf.sh
creating init file
creating obj file
creating shared obj file
ld.lld: warning: lld uses blx instruction, no object with architecture
supporting feature detected
performing llvm objcopy
12.34user 0.00system 0:12.35elapsed 99%CPU (0avgtext+0avgdata 20228maxresident)k
0inputs+2288outputs (0major+3815minor)pagefaults 0swaps
performing GNU objcopy
0.03user 0.00system 0:00.04elapsed 97%CPU (0avgtext+0avgdata 20396maxresident)k
0inputs+2288outputs (0major+5895minor)pagefaults 0swaps


Alternate access to the script above:
https://gist.github.com/androm3da/83560d92f3fe637b58aa115ba6b68456

-Brian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210518/92876f36/attachment.html>

Unfortunately I do not have an answer or workaround, but I want to add that I am
also hitting this issue. The performance of --keep-symbols with a large list of
symbols is quite slow.

Have you filed a bug to track this?

(For other reasons in my specific case I cannot fall back to GNU objcopy, so
this performance penalty must be paid today.)

Thanks,

Justin
> On May 18, 2021, at 12:11 AM, Brian Cain via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> While investigating an issue with android build performance, I found that
llvm-objcopy performance is far from parity with GNU objcopy for the
“--keep-symbols” case, when the keep symbols list is very large.
>  
> I can see that llvm objcopy creates a list of NameOrPattern-s to represent
the keep symbol list, but it looks like it exhaustively compares each symbol in
the keep list against each symbol in the input file.  Not sure what GNU objcopy
does but merging the non-pattern symbol names into a sorted list would make
searching much faster.
>  
> Below is a script to reproduce the problem and its output.  The test case
below demonstrates a significant performance difference.  The android build
failure case reported had a shared obj with ~700k symbols and the keep list was
~300k symbols and it took ~8 minutes to execute.
>  
> ~~~
> #!/bin/bash
>  
> set -euo pipefail
>  
> echo creating init file
> echo <<EOF > input.S
> .section .text
> EOF
> echo '' > keep_syms.txt
> for i in $(seq 0 100000)
> do
>     echo -e "sym_${i}:\nnop\n" >> input.S
>     if [[ ${i} -lt 30000 ]]; then
>         echo "sym_${i}" >> keep_syms.txt
>     fi
> done
> echo <<EOF >> input.S
> .section .ballast
> nop
> EOF
> echo creating obj file
> llvm-mc -triple arm-linux-androideabi -filetype=obj input.S -o out.o
> echo creating shared obj file
> ld.lld  -shared out.o -o libtestcase.so
>  
> echo performing llvm objcopy
> \time llvm-objcopy -S --remove-section .ballast  \
>     --keep-symbols=keep_syms.txt \
>     libtestcase.so libtestcase_smaller.so
>  
> echo performing GNU objcopy
> \time arm-linux-androideabi-objcopy -S --remove-section .ballast  \
>     --keep-symbols=keep_syms.txt \
>     libtestcase.so libtestcase_smaller.so
> ~~~
>  
> Here’s the output I get when I run it on ToT-within-last-week-or-so:
>  
> $ PATH=$PWD/bin:$PATH ../../tmp/qt66370/32/objcopy_perf.sh
> creating init file
> creating obj file
> creating shared obj file
> ld.lld: warning: lld uses blx instruction, no object with architecture
supporting feature detected
> performing llvm objcopy
> 12.34user 0.00system 0:12.35elapsed 99%CPU (0avgtext+0avgdata
20228maxresident)k
> 0inputs+2288outputs (0major+3815minor)pagefaults 0swaps
> performing GNU objcopy
> 0.03user 0.00system 0:00.04elapsed 97%CPU (0avgtext+0avgdata
20396maxresident)k
> 0inputs+2288outputs (0major+5895minor)pagefaults 0swaps
>  
>  
> Alternate access to the script above:
> https://gist.github.com/androm3da/83560d92f3fe637b58aa115ba6b68456
<https://gist.github.com/androm3da/83560d92f3fe637b58aa115ba6b68456>
>  
> -Brian
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210521/ef72ff23/attachment.html>