----- On Apr 19, 2016, at 4:50 PM, rostedt rostedt@xxxxxxxxxxx wrote: > On Tue, 19 Apr 2016 20:17:29 +0000 (UTC) > Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx> wrote: > > >> Ah indeed, since there is a hard limit to 4194304, that makes the >> worse case bitmap 512k. > > Yep. > >> >> We could argue that given a sparse dataset in the PID table (typical >> in our use-cases), a small hash table would have better cache locality >> than the bitmap. But I agree that the hash table does add a bit of >> complexity, so it becomes a complexity vs cache locality tradeoff. >> So I understand why you would want to go for the simpler bitmap >> solution, unless the hash table would prove to bring a measurable >> performance improvement. > > We discussed this too (cache locality), and came to the same conclusion > that a bitmask would still be better. If you think about it, if you > have a lot of CPUs and lots of PIDs, tasks don't migrate as much, and > if they do, cache locality of this bitmap will be the least of the > performance issues. Then you have a limited amount of PIDs per CPU, and > thus those PIDs will probably be in the CPU cache for the bitmap. It makes sense. Anyway, looking back at my own implementation, I have an array of 64 hlist_head entries (64 * 8 = 512 bytes), typically populated by NULL pointers. It's only a factor 8 smaller than the bitmap, so it's not a huge gain. One alternative approach would be to keep a few entries (e.g. 16 PIDs) in a fast-path lookup array that fits in a single-cache line. When the number of PIDs to track go beyond that, fall-back to the bitmap instead. > > Note, that the check of the bitmap to trace a task or not is not done > at every tracepoint. It's only done at sched_switch, and then an > internal flag is set. That flag will determine if the event should be > traced, and that is a single bit checked all the time (very good for > cache). Could this be used by multiple tracers, and used in a multi-session scheme ? In lttng, one user may want to track a set of PIDs, whereas another user may be concurrently interested by another set. Currently, in the lttng kernel tracer, we do the hash table query for each tracepoint hit, which is clearly not as efficient as checking a task struct flag. One option I see would be to set the task struct flag whenever there is at least one tracer/tracing session that is interested in this event (this would end up being a reference count on the flag). Then, for every flag check that passes, lttng could do HT/bitmap lookups to see if the event needs to go to each specific session. Is this task struct "trace" flag currently exposed to tracers through a reference-counting enable/disable API ? If not, do you think it would make sense ? Thanks, Mathieu > > -- Steve > > > -- > To unsubscribe from this list: send the line "unsubscribe linux-trace-users" in > the body of a message to majordomo@xxxxxxxxxxxxxxx > More majordomo info at http://vger.kernel.org/majordomo-info.html -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com -- To unsubscribe from this list: send the line "unsubscribe linux-trace-users" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
|