• Frederic Weisbecker's avatar
    tracing/stat: replace linked list by an rbtree for sorting · 8f184f27
    Frederic Weisbecker authored
    When the stat tracing framework prepares the entries from a tracer
    to output them to the user, it starts by computing a linear sort
    through a linked list to give the entries ordered by relevance
    to the user.
    
    This is quite ugly and causes a small latency when we begin to
    read the file.
    
    This patch changes that by turning the linked list into a red-black
    tree. Athough the whole iteration using the start and next tracer
    callbacks while opening the file remain the same, it is now much
    more fast and scalable.
    
    The rbtree guarantees O(log(n)) insertions whereas a linked
    list with linear sorting brought us a O(n) despair. Now the
    (visible) latency has disapeared.
    
    [ Impact: kill the latency while starting to read a stat tracer file ]
    Signed-off-by: default avatarFrederic Weisbecker <fweisbec@gmail.com>
    8f184f27
trace_stat.c 8.15 KB