kernel-shark-qt: Add generic instruments for searching inside the trace data
This patch introduces the instrumentation for data extraction used by the
visualization model of the Qt-based KernelShark. The effectiveness of these
instruments for searching has a dominant effect over the performance of the
model, so let's spend some time and explain this in detail.
The first type of instruments provide binary search inside a sorted in time
arrays of kshark_entries or trace_records. The search returns the first
element of the array, having timestamp bigger than a reference time value.
The time complexity of these searches is log(n).
The second type of instruments provide searching for the first (in time)
entry, satisfying an abstract Matching condition. Since the array is sorted
in time, but we search for an abstract property, for this search the array
is considered unsorted, thus we have to iterate and check all elements of the
array one by one. If we search for a type of entries, which are well presented
in the array, the time complexity of the search is constant, because no matter
how big is the array the search only goes through small number of entries at
the beginning of the array (or at the end, if we search backwards), before it
finds the first match. However if we search for sparse, or even nonexistent
entries, the time complexity becomes linear.
These explanations will start making more sense with the following patches.
Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
2 files changed
