• Matt Fleming's avatar
    sh: Optimise FDE/CIE lookup by using red-black trees · 858918b7
    Matt Fleming authored
    Now that the DWARF unwinder is being used to provide perf callstacks
    unwinding speed is an issue. It is no longer being used in exceptional
    circumstances where we don't care about runtime performance, e.g. when
    panicing, so it makes sense improve performance is possible.
    
    With this patch I saw a 42% improvement in unwind time when calling
    return_address(1). Greater improvements will be seen as the number of
    levels unwound increases as each unwind is now cheaper.
    
    Note that insertion time has doubled but that's just the price we pay
    for keeping the trees balanced. However, this is a one-time cost for
    kernel boot/module load and so the improvements in lookup time dominate
    the extra time we spend keeping the trees balanced.
    Signed-off-by: default avatarMatt Fleming <matt@console-pimps.org>
    Signed-off-by: default avatarPaul Mundt <lethal@linux-sh.org>
    858918b7
module.h 1.1 KB