11 ms·

Show HN: O(log n) makes continuous profiling possible

166 points by petethepig 6y ago

sdenton4 6y ago
This looks hella cool. Kudos!
- petethepig 6y ago
  Thanks!
  - ktpsns 6y ago
    Can you tell about how you made these sweet animations (GIFs)?
neolog 6y ago
Any plans for a VSCode extension? I want it to highlight slow parts of my code inline like a linting layer.
- petethepig 6y ago
  That’s a great idea. We were thinking we could integrate Pyroscope with CI tools, so that you would be able to see how much time is spent in different tests. This seems to be an area where a lot of people are looking for quick ways to cut time. But yeah, having lines highlighed in VS code would be even cooler.
  - raihansaputra 6y ago
    The Jest VSCode extension can run the tests and highlight the relevant uncovered lines and annotate failed/successful tests. Maybe helpful to look into their implementation.
  - neolog 6y ago
    There's some similar ideas in https://www.destroyallsoftware.com/talks/a-whole-new-world https://www.destroyallsoftware.com/talks/a-whole-new-world
  - neolog 6y ago
    VSCode could show highlighting from different sources. For example, click a button to show what was slow in CI, in production, in local tests.
zwliew 6y ago
Segment trees are data structures commonly used in competitive programming. It was really interesting seeing it used here! That said, I wonder if there are any real-world comparisons on production code?
- petethepig 6y ago
  Thanks! We loved geeking out on all of these data structures and algorithms. RE comparisons: Do you mean comparisons of some production profiling data with versus without this compression?
- ZephyrBlu 6y ago
  How are segment trees used in competitive programming? I can't immediately see how they would be useful in that situation.
  - knuthsat 6y ago
    Any dynamic programming algorithm where n-th item depends on contiguous k ones with some nice binary operation (like +) can benefit from storing the state in a segment tree, so when you go and calculate n-th item, you can get the value in log(n) instead of O(k) (although prefix sums work fine there too if + is involved). I know also of examples where lazy segment tree is used too. Segment trees can also be used to decode the kth lexicographic permutation of a sequence of elements in O(n log n) instead of O(n ^ 2). Here's one variant of the above application: https://www.spoj.com/problems/QUE2/ https://www.spoj.com/problems/QUE2/
    - ZephyrBlu 6y ago
      The first example makes sense, but could you elaborate on decoding permutations with that problem? The only way I can currently envision a segment tree being used for a problem like that is grouping elements every k to provide a faster lookup. Like, these k elements have a value < x, the next k elements have a value < y, etc.
      - 6y ago
trungdq88 6y ago
Looks awesome! Do you have the benchmark on how the profiler would affect the app in term of CPU/Mem usage?
- petethepig 6y ago
  We measured it at some point and the numbers were around 1-2% CPU usage increase per 1 profiled process at 100 Hz. Did not measure memory overhead, but it should be pretty minimal, less than 10 MBs per process.
still_grokking 6y ago
How does it compare to just using a JVM agent to profile a production app?
- petethepig 6y ago
  Not very familiar with JVM unfortunately. Maybe someone else can chime in and tell us about how it stores profiling data?
  - brabel 6y ago
    Java Flight Recorder is also meant for being enabled in production and according to Oracle, typically has a very small footprint (in the order of 1-2% overhead). It even integrates with IntelliJ[1] so you can have your fancy charts as you run your tests or debug your application. [1] https://www.jetbrains.com/help/idea/read-the-profiling-report.html https://www.jetbrains.com/help/idea/read-the-profiling-repor...
ramary 6y ago
Nice! Seems super easy to use and the indexing + search are powerful features. Is it possible to configure the period of the sampling profiler? e.g. 1ms or 50ms instead of 10ms?
- petethepig 6y ago
  Not right now but we'll add that feature soon.
psykotic 6y ago
For interval-oriented data that you want to query at different levels of detail with a query window, there's a trick I used in a commercial profiler which you can easily bolt on top of any ordered search tree or database system. You have a separate tree for each power-of-two scale. The tree corresponding to scale k contains intervals with length between 2^k and 2^(k+1). An interval [u, v] is put in the tree corresponding to scale lg(v - u) under the key u. If you have a query window [a, b] you turn it into a range query a - 2^k <= u <= b for each relevant scale k and filter matches by interval overlap between [u, v] and [a, b]. "Each relevant scale" is defined by the desired level of detail, e.g. you don't query scales which are too small relative to the current zoom level. Each scale actually has two trees. One type is what I just described. The other type is a summary tree which contains bounding intervals with recursive summaries of all intervals at finer scales. When you cut off queries at scale k you also include data from the summary tree at scale k so that all data in the query window is returned, either verbatim or as part of the bounding intervals with summaries. An efficient, convenient way of implementing this is to stream the time series data to disk to separate append-only files for each scale. You can start doing interval queries immediately with a reasonable slowdown by directly doing binary search on the raw scale-segregated files (if the records are variable length you can use a COBS-style encoding so you can sync to the nearest record from a random point in the file). That said, the write amplification for a high-fanout B+ tree index is tiny here and building it in a streaming fashion is basically free, so generating the index synchronously is my recommendation. You can also generate the summary files in a streaming fashion but since they involve significant write amplification it's worth decoupling that task to a process with lower IO priority. To implement the interval query for [a, b] at a given scale you use the B+ tree index to find the starting position in the append-only record file for that scale using the a - 2^k lower bound and just do a linear scan in the file until you exceed b. There's a bunch of variations and optimizations (e.g. coarser scales than powers of two) but that's the gist of it.
jms55 6y ago
Coming from a Rust game development background, something that's noticeable to me is that sampling based profiling seeks to solve a different problem than the types of questions games need to answer. With sampling you can say "I saw function() 100/150 samples (10ms interval between samples), spend your time looking at that!". That doesn't really work for games, where your work is on the scale of 0.1ms, and you might call the same function 100's of times in 16ms. Calling update_object() 1000 times an interval isn't actually a problem, when it's only taking 5% of your overall frame budget (on average). Games also have the constraint of not wanting your profiling to throw off the game speed itself, it needs to run very fast. With games, what you really want to know are: 1. Which frames are taking over 16ms? (On the current machine; what's fast enough on one computer isn't on weaker machines. Sometimes you want to look at every frame, and not just the slow ones.) 2. What functions are causing them to go over? 3. Are those functions _usually_ that slow? How fast do they usually run, was this just an uncommon edge case? Mean/median/90th percentile performance? With typical applications, instead you want to know * Of the many diverging branches and tasks my application can do, which areas occur the most often, and are therefore worth spending time optimizing? Sampling based profiling obviously works better for applications like this, while non-sampling profiling works better for games. Sadly, there doesn't seem to be very many GUIs/APIs for working with the latter, especially with linux compatibility. I'm hoping to remedy this, as soon as I get better at GTK. EDIT: An example of why sampling based profilers (in this case, perf) aren't great for games. Although sandbox::sandbox::Sandbox::temperature_update takes up a decent amount of overall time, it's hard to tell whether that matters per frame or not. https://profiler.firefox.com/public/c4y22fect9qg9mfm0wv0pjweacpvpqz204y2by8/calltree/?globalTrackOrder=0&localTrackOrderByPid=560138-0-1~&thread=0&timelineType=stack&v=5 https://profiler.firefox.com/public/c4y22fect9qg9mfm0wv0pjwe...
- chairmanwow1 6y ago
  Great comment. Thank you for sharing
- vlovich123 6y ago
  Have you tried a flameshot graph? It’ll give you a nicer visualization of the relative amount of cpu something took. Sampling profilers are but one thing in the toolbox. On Windows you can use WPA for extremely detailed tracing and can link CPU work to GPu work (the tooling can be awkward as the GPU one hasn’t seen love in a while). Google is tackling this problem for Android via Perfetto although the tooling isn’t as mature and the GPU stuff will probably stay Android unless Nvidia/AMD extend it for the desktop (seeing as how stadia is being deprioritized).
yashap 6y ago
Looks really interesting! How do you avoid data getting all jumbled together though? Like say I’m profiling a web service with 20 endpoints. If I’m profiling locally, I just call the one endpoint I’m interested in, so it’s a “clean”, focused profile. But if I’m profiling against the same service running in prod, with all 20 endpoints getting called all the time, do they all get mixed together? Would there be a good way to separate them out?
- petethepig 6y ago
  Right now they are all mixed together. Based on our experience and talking to early users, for some types of applications this is not too big of a deal. You can always zoom in on a particular endpoint and dive deeper if you want to. And in some cases this is actually a great way to get a high level overview of where your app spends most of the time. In other cases this does become a problem. For example we've seen it with some large rails apps with a lot of controllers — the flamegraph just becomes too big and hard to read. This is something we're planning to address soon. The storage layer already has support for tags, we plan to make it so that you would be able to split the profiling data by endpoint, e.g something like app{endpoint=foo} app{endpoint=bar} and then make queries either for the whole app or individual endpoints.
  - yashap 6y ago
    That makes sense, sounds like a good approach, and thanks for the thoughtful response!
KMag 6y ago
One interesting thing is that using reservoir sampling "Algorithm L"[0], you can actually get an unbiased sample with overhead proportional to the logarithm of CPU time. That would require more state and work in the server to aggregate, though. On the other hand, moving overhead from the process to the aggregation server is useful if you want to run profiling in production. [0] https://en.wikipedia.org/wiki/Reservoir_sampling#An_optimal_algorithm https://en.wikipedia.org/wiki/Reservoir_sampling#An_optimal_...
zurfer 6y ago
Maybe I am overlooking something, but how do I use this on Windows? Do I need to put everything in Docker?

166 points by petethepig 6y ago

sdenton4 6y ago

This looks hella cool. Kudos!

petethepig 6y ago
Thanks!
- ktpsns 6y ago
  Can you tell about how you made these sweet animations (GIFs)?

neolog 6y ago

Any plans for a VSCode extension? I want it to highlight slow parts of my code inline like a linting layer.

petethepig 6y ago
That’s a great idea. We were thinking we could integrate Pyroscope with CI tools, so that you would be able to see how much time is spent in different tests. This seems to be an area where a lot of people are looking for quick ways to cut time. But yeah, having lines highlighed in VS code would be even cooler.
- raihansaputra 6y ago
  The Jest VSCode extension can run the tests and highlight the relevant uncovered lines and annotate failed/successful tests. Maybe helpful to look into their implementation.
- neolog 6y ago
  There's some similar ideas in https://www.destroyallsoftware.com/talks/a-whole-new-world https://www.destroyallsoftware.com/talks/a-whole-new-world
- neolog 6y ago
  VSCode could show highlighting from different sources. For example, click a button to show what was slow in CI, in production, in local tests.

zwliew 6y ago

Segment trees are data structures commonly used in competitive programming. It was really interesting seeing it used here! That said, I wonder if there are any real-world comparisons on production code?

petethepig 6y ago
Thanks! We loved geeking out on all of these data structures and algorithms. RE comparisons: Do you mean comparisons of some production profiling data with versus without this compression?
ZephyrBlu 6y ago
How are segment trees used in competitive programming? I can't immediately see how they would be useful in that situation.
- knuthsat 6y ago
  Any dynamic programming algorithm where n-th item depends on contiguous k ones with some nice binary operation (like +) can benefit from storing the state in a segment tree, so when you go and calculate n-th item, you can get the value in log(n) instead of O(k) (although prefix sums work fine there too if + is involved). I know also of examples where lazy segment tree is used too. Segment trees can also be used to decode the kth lexicographic permutation of a sequence of elements in O(n log n) instead of O(n ^ 2). Here's one variant of the above application: https://www.spoj.com/problems/QUE2/ https://www.spoj.com/problems/QUE2/
  - ZephyrBlu 6y ago
    The first example makes sense, but could you elaborate on decoding permutations with that problem? The only way I can currently envision a segment tree being used for a problem like that is grouping elements every k to provide a faster lookup. Like, these k elements have a value < x, the next k elements have a value < y, etc.
    - 6y ago

trungdq88 6y ago

Looks awesome! Do you have the benchmark on how the profiler would affect the app in term of CPU/Mem usage?

petethepig 6y ago
We measured it at some point and the numbers were around 1-2% CPU usage increase per 1 profiled process at 100 Hz. Did not measure memory overhead, but it should be pretty minimal, less than 10 MBs per process.

still_grokking 6y ago

How does it compare to just using a JVM agent to profile a production app?

petethepig 6y ago
Not very familiar with JVM unfortunately. Maybe someone else can chime in and tell us about how it stores profiling data?
- brabel 6y ago
  Java Flight Recorder is also meant for being enabled in production and according to Oracle, typically has a very small footprint (in the order of 1-2% overhead). It even integrates with IntelliJ[1] so you can have your fancy charts as you run your tests or debug your application. [1] https://www.jetbrains.com/help/idea/read-the-profiling-report.html https://www.jetbrains.com/help/idea/read-the-profiling-repor...

ramary 6y ago

Nice! Seems super easy to use and the indexing + search are powerful features. Is it possible to configure the period of the sampling profiler? e.g. 1ms or 50ms instead of 10ms?

petethepig 6y ago
Not right now but we'll add that feature soon.

psykotic 6y ago

For interval-oriented data that you want to query at different levels of detail with a query window, there's a trick I used in a commercial profiler which you can easily bolt on top of any ordered search tree or database system. You have a separate tree for each power-of-two scale. The tree corresponding to scale k contains intervals with length between 2^k and 2^(k+1). An interval [u, v] is put in the tree corresponding to scale lg(v - u) under the key u. If you have a query window [a, b] you turn it into a range query a - 2^k <= u <= b for each relevant scale k and filter matches by interval overlap between [u, v] and [a, b]. "Each relevant scale" is defined by the desired level of detail, e.g. you don't query scales which are too small relative to the current zoom level. Each scale actually has two trees. One type is what I just described. The other type is a summary tree which contains bounding intervals with recursive summaries of all intervals at finer scales. When you cut off queries at scale k you also include data from the summary tree at scale k so that all data in the query window is returned, either verbatim or as part of the bounding intervals with summaries. An efficient, convenient way of implementing this is to stream the time series data to disk to separate append-only files for each scale. You can start doing interval queries immediately with a reasonable slowdown by directly doing binary search on the raw scale-segregated files (if the records are variable length you can use a COBS-style encoding so you can sync to the nearest record from a random point in the file). That said, the write amplification for a high-fanout B+ tree index is tiny here and building it in a streaming fashion is basically free, so generating the index synchronously is my recommendation. You can also generate the summary files in a streaming fashion but since they involve significant write amplification it's worth decoupling that task to a process with lower IO priority. To implement the interval query for [a, b] at a given scale you use the B+ tree index to find the starting position in the append-only record file for that scale using the a - 2^k lower bound and just do a linear scan in the file until you exceed b. There's a bunch of variations and optimizations (e.g. coarser scales than powers of two) but that's the gist of it.

jms55 6y ago

Coming from a Rust game development background, something that's noticeable to me is that sampling based profiling seeks to solve a different problem than the types of questions games need to answer. With sampling you can say "I saw function() 100/150 samples (10ms interval between samples), spend your time looking at that!". That doesn't really work for games, where your work is on the scale of 0.1ms, and you might call the same function 100's of times in 16ms. Calling update_object() 1000 times an interval isn't actually a problem, when it's only taking 5% of your overall frame budget (on average). Games also have the constraint of not wanting your profiling to throw off the game speed itself, it needs to run very fast. With games, what you really want to know are: 1. Which frames are taking over 16ms? (On the current machine; what's fast enough on one computer isn't on weaker machines. Sometimes you want to look at every frame, and not just the slow ones.) 2. What functions are causing them to go over? 3. Are those functions _usually_ that slow? How fast do they usually run, was this just an uncommon edge case? Mean/median/90th percentile performance? With typical applications, instead you want to know * Of the many diverging branches and tasks my application can do, which areas occur the most often, and are therefore worth spending time optimizing? Sampling based profiling obviously works better for applications like this, while non-sampling profiling works better for games. Sadly, there doesn't seem to be very many GUIs/APIs for working with the latter, especially with linux compatibility. I'm hoping to remedy this, as soon as I get better at GTK. EDIT: An example of why sampling based profilers (in this case, perf) aren't great for games. Although sandbox::sandbox::Sandbox::temperature_update takes up a decent amount of overall time, it's hard to tell whether that matters per frame or not. https://profiler.firefox.com/public/c4y22fect9qg9mfm0wv0pjweacpvpqz204y2by8/calltree/?globalTrackOrder=0&localTrackOrderByPid=560138-0-1~&thread=0&timelineType=stack&v=5 https://profiler.firefox.com/public/c4y22fect9qg9mfm0wv0pjwe...

chairmanwow1 6y ago
Great comment. Thank you for sharing
vlovich123 6y ago
Have you tried a flameshot graph? It’ll give you a nicer visualization of the relative amount of cpu something took. Sampling profilers are but one thing in the toolbox. On Windows you can use WPA for extremely detailed tracing and can link CPU work to GPu work (the tooling can be awkward as the GPU one hasn’t seen love in a while). Google is tackling this problem for Android via Perfetto although the tooling isn’t as mature and the GPU stuff will probably stay Android unless Nvidia/AMD extend it for the desktop (seeing as how stadia is being deprioritized).

yashap 6y ago

Looks really interesting! How do you avoid data getting all jumbled together though? Like say I’m profiling a web service with 20 endpoints. If I’m profiling locally, I just call the one endpoint I’m interested in, so it’s a “clean”, focused profile. But if I’m profiling against the same service running in prod, with all 20 endpoints getting called all the time, do they all get mixed together? Would there be a good way to separate them out?

petethepig 6y ago
Right now they are all mixed together. Based on our experience and talking to early users, for some types of applications this is not too big of a deal. You can always zoom in on a particular endpoint and dive deeper if you want to. And in some cases this is actually a great way to get a high level overview of where your app spends most of the time. In other cases this does become a problem. For example we've seen it with some large rails apps with a lot of controllers — the flamegraph just becomes too big and hard to read. This is something we're planning to address soon. The storage layer already has support for tags, we plan to make it so that you would be able to split the profiling data by endpoint, e.g something like app{endpoint=foo} app{endpoint=bar} and then make queries either for the whole app or individual endpoints.
- yashap 6y ago
  That makes sense, sounds like a good approach, and thanks for the thoughtful response!

KMag 6y ago

One interesting thing is that using reservoir sampling "Algorithm L"[0], you can actually get an unbiased sample with overhead proportional to the logarithm of CPU time. That would require more state and work in the server to aggregate, though. On the other hand, moving overhead from the process to the aggregation server is useful if you want to run profiling in production. [0] https://en.wikipedia.org/wiki/Reservoir_sampling#An_optimal_algorithm https://en.wikipedia.org/wiki/Reservoir_sampling#An_optimal_...

zurfer 6y ago

Maybe I am overlooking something, but how do I use this on Windows? Do I need to put everything in Docker?