Reading USDT Probes is a O(n^2) operation

[ttreyer]

Hello 🙂 The function Context::add_probe iterates through the entire list of probes_ every times it is called. It is looking for an existing Probe with matching provider+name, so the new probe entry can be added as a location to the existing probe.
This makes reading a large amount of USDT probes particularly slow!

I'm using bpftrace on a binary with about 400,000 USDT entries and am experiencing hang-up of ~1min. I could track the issue back to Context::add_probe and could confirm the wait was due to the many String comparisons done during the probes_ traversal. The long wait time makes using bpftrace non-interactive and prevents quickly iterating through ideas.

A possible solution could be to add a std::unordered_map as an index to quickly lookup a probe using its name. I was able to confirm the performance improvement with the following draft: fast-usdt.patch.

Another idea could be to use a reverse iterator when searching through the list of probes_, so that contiguous USDT entries that share the same name would find a match on their first iteration. On my end, I can sort the USDT entries by name to take advantage of that property.