tracing/stat: replace linked list by an rbtree for sorting
authorFrederic Weisbecker <fweisbec@gmail.com>
Sat, 16 May 2009 04:24:36 +0000 (06:24 +0200)
committerFrederic Weisbecker <fweisbec@gmail.com>
Mon, 1 Jun 2009 23:17:35 +0000 (01:17 +0200)
commit8f184f27300f66f6dcc8296c2dae7a1fbe8429c9
treea21aa4d88a11217bdd9eaaf31b2189d8b6b45b5b
parent0d64f8342de26d02451900b1aad94716fe92c4ab
tracing/stat: replace linked list by an rbtree for sorting

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: Frederic Weisbecker <fweisbec@gmail.com>
kernel/trace/trace_stat.c