iovisor / iovisor/bcc

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

Open
#5,161 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
22.7k
Forks
4.1k
Avg merge
10d 4h
Merged PRs (30d)
3

Description

Hello 🙂 The function [`Context::add_probe`](https://github.com/iovisor/bcc/blob/master/src/cc/usdt/usdt.cc#L278-L283) 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](https://github.com/user-attachments/files/17938640/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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.