[PATCH] unwind-libdw: add caching

[Masatake YAMATO]

On Sun, 22 Mar 2020 20:40:22 +0100, Jann Horn <jannh at google.com> wrote:
> libdw's address-to-symbol logic is quite slow. Since when stracing a
> process, it is normal to see the same call sites over and over again, let's
> address that by adding a straightforward N-way associative cache in front
> of libdw.
> 
> The cache parameters could probably use some fine-tuning, but ought to be
> good enough for now.
> 
> The resulting performance improvement:
> 
> $ time ./strace-orig -o /dev/null -k bash -c 'for i in {0..10000}; do echo; done' >/dev/null
> 
> real	0m12,014s
> user	0m11,512s
> sys	0m0,575s
> $ time ./strace-cache -o /dev/null -k bash -c 'for i in {0..10000}; do echo; done' >/dev/null
> 
> real	0m0,765s
> user	0m0,451s

I've tried the patch.

    [yamato at slave]~/var/strace$ time strace -k ctags *.c > /dev/null 2>&1 
    strace -k ctags *.c > /dev/null 2>&1  5.59s user 0.40s system 98% cpu 6.076 total
    [yamato at slave]~/var/strace$ time ./strace -k ctags *.c > /dev/null 2>&1 
    ./strace -k ctags *.c > /dev/null 2>&1  0.43s user 0.25s system 101% cpu 0.669 total
    [yamato at slave]~/var/strace$ time strace -k ctags *.c > /dev/null 2>&1   
    strace -k ctags *.c > /dev/null 2>&1  5.56s user 0.37s system 98% cpu 6.003 total
    [yamato at slave]~/var/strace$ time ./strace -k ctags *.c > /dev/null 2>&1 
    ./strace -k ctags *.c > /dev/null 2>&1  0.45s user 0.24s system 101% cpu 0.680 total

    [yamato at slave]~/var/strace% time ./strace -o with-patch ctags *.c > /dev/null 2>&1  
    ./strace -o with-patch ctags *.c > /dev/null 2>&1  0.09s user 0.18s system 106% cpu 0.253 total
    [yamato at slave]~/var/strace% time strace -o with-patch ctags *.c > /dev/null 2>&1  
    strace -o with-patch ctags *.c > /dev/null 2>&1  0.10s user 0.21s system 104% cpu 0.304 total

Much faster as you wrote!

Without your patch, strace -k was about 20 times slower than strace.
With your patch, ./strace -k was about 2.5 times slower than ./strace.

In my experience in contributing to strace development, I have two comments.

* The commit log is written in ChangeLog-style.
  Quoted from ~/var/strace/README-hacking:

    Commit requirements
    ===================
    Each commit message should always start with a one-line summary, the second
    line should be blank, and the remaining lines are usually ChangeLog-style
    entries for all affected files, except the leading TABs which should
    be omitted.

* mention this improvement in NEWS.
  Quoted from ~/var/strace/README-hacking:

    Documentation
    =============
    All noteworthy changes should be mentioned in NEWS.  All changes in strace
    command interface should be reflected in the man page.  New options should
    be documented both in -h output and in the man page.

  I strong believe this change is a noteworthy change.

I also read your code. However, I cannot find anything I want to comment.

Thank you for the great patch.
I would like to use it daily.

Masatake YAMATO