Would percentiles make sense as an option here?

We could do percentiles in telemetry with post processing, but it'll be more difficult with UMA and UKM.

It's hard to track exact percentiles given a stream of values unless we store all the values and post process. We'd have to do some kind of approximation using a static bucketing scheme like UMA does or maybe a dynamic bucketing scheme:
https://stats.stackexchange.com/questions/10539/compute-approximate-quantiles-for-a-stream-of-integers-using-moments

Approximate quantiles are (from my perspective) a fair bit more intuitive than RMS & SMR, and I don't think the implementation is too painful.

Sounds like a t-digest is the right approach, there are C++ implementations in < 500 lines floating around.

Here's one in python in <300: https://github.com/CamDavidsonPilon/tdigest/blob/master/tdigest/tdigest.py

For estimated percentiles, I'll make a static scheme P0. t-digest uses static buckets like UMA, which should be easy to implement.

The accuracy of static schemes shouldn't be affected by sample order like dynamic schemes are. Which approach is more accurate, for a given amount of CPU budget, probably depends on how multi-modal the input data is. Since we don't need to report all buckets like UMA does, we could just add more buckets in the static scheme to improve the accuracy without affecting performance much.

q-digest is a dynamic scheme with square shaped buckets, where the decision to merge or split buckets seems to assume that all percentiles are of equal importance. I wonder if we could improve q-digest by making some percentiles more precise and maybe using triangular shaped buckets. Probably not going to get to this though.

Yeah, I wouldn't worry about q-digest for now, though it is neat!

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/6aab84c9b3cedf39c63a01d495df2341223241f3

commit 6aab84c9b3cedf39c63a01d495df2341223241f3
Author: Brian Anderson <brianderson@chromium.org>
Date: Wed Mar 14 00:43:31 2018

base: Use CountLeadingZeroBits for Log2.

Make Log2Floor and Log2Ceiling use CountLeadingZeroBits,
which maps to fast underlying CPU instructions.

This improves the performance of adding samples to
a histogram that relies on Log2Floor to convert
values to buckets by 1.5x to 2x.

Other code that uses Log2*, will likely see similar
benefits.

Bug: 807463
Change-Id: Ie21465523d70ce451d8ded6471a0b39107d73d87
Reviewed-on: https://chromium-review.googlesource.com/961490
Reviewed-by: danakj <danakj@chromium.org>
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542972}
[modify] https://crrev.com/6aab84c9b3cedf39c63a01d495df2341223241f3/base/bits.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/0465b7fed4b9d0f5d4a8636e885871b82e54f318

commit 0465b7fed4b9d0f5d4a8636e885871b82e54f318
Author: Brian Anderson <brianderson@chromium.org>
Date: Mon Mar 19 19:32:59 2018

ui: Add FrameMetrics histogram helpers.

Adds a Histogram interface with two implementations. One for
ratios with most of it's precision just above 1 and another
for latency with higher precision near vsync intervals.

The Histogram can be queried for approximate percentiles,
which will be useful for UKM based frame metrics.

Bug: 807463
Change-Id: Ic50ce19eeb1804063628c09cbd1e0c30afbfd930
Reviewed-on: https://chromium-review.googlesource.com/952534
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Reviewed-by: Sadrul Chowdhury <sadrul@chromium.org>
Cr-Commit-Position: refs/heads/master@{#544119}
[modify] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/BUILD.gn
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms.cc
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms.h
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms_perftest.cc
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms_test_common.cc
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms_test_common.h
[add] https://crrev.com/0465b7fed4b9d0f5d4a8636e885871b82e54f318/ui/latency/histograms_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/5bad341141c37fd7f74a1b0f555d7b18cc9383ca

commit 5bad341141c37fd7f74a1b0f555d7b18cc9383ca
Author: Karan Bhatia <karandeepb@chromium.org>
Date: Mon Mar 19 20:37:36 2018

Revert "ui: Add FrameMetrics histogram helpers."

This reverts commit 0465b7fed4b9d0f5d4a8636e885871b82e54f318.

Reason for revert: Breaks compile on IOS bots.

Original change's description:
> ui: Add FrameMetrics histogram helpers.
> 
> Adds a Histogram interface with two implementations. One for
> ratios with most of it's precision just above 1 and another
> for latency with higher precision near vsync intervals.
> 
> The Histogram can be queried for approximate percentiles,
> which will be useful for UKM based frame metrics.
> 
> Bug: 807463
> Change-Id: Ic50ce19eeb1804063628c09cbd1e0c30afbfd930
> Reviewed-on: https://chromium-review.googlesource.com/952534
> Commit-Queue: Brian Anderson <brianderson@chromium.org>
> Reviewed-by: Timothy Dresser <tdresser@chromium.org>
> Reviewed-by: Sadrul Chowdhury <sadrul@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#544119}

TBR=sadrul@chromium.org,brianderson@chromium.org,tdresser@chromium.org

Change-Id: I9a706e7b936abb90e6856d983d550a9272f74e24
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: 807463,  823437 
Reviewed-on: https://chromium-review.googlesource.com/969226
Reviewed-by: Karan Bhatia <karandeepb@chromium.org>
Commit-Queue: Karan Bhatia <karandeepb@chromium.org>
Cr-Commit-Position: refs/heads/master@{#544148}
[modify] https://crrev.com/5bad341141c37fd7f74a1b0f555d7b18cc9383ca/ui/latency/BUILD.gn
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms.cc
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms.h
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms_perftest.cc
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms_test_common.cc
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms_test_common.h
[delete] https://crrev.com/7fb9d8f2850e74ff10c9e70301ba8d8b0842b30e/ui/latency/histograms_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/2b021ec72c8717c2c65c0ac20029ec7fb38104ce

commit 2b021ec72c8717c2c65c0ac20029ec7fb38104ce
Author: Brian Anderson <brianderson@chromium.org>
Date: Wed Mar 21 17:29:06 2018

ui: Add FrameMetrics histogram helpers.

Adds a Histogram interface with two implementations. One for
ratios with most of it's precision just above 1 and another
for latency with higher precision near vsync intervals.

The Histogram can be queried for approximate percentiles,
which will be useful for UKM based frame metrics.

Bug: 807463
Change-Id: I83b251e2d50166cd4c376a10050ee344e312368f
Reviewed-on: https://chromium-review.googlesource.com/972194
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Cr-Commit-Position: refs/heads/master@{#544754}
[modify] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/BUILD.gn
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms.cc
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms.h
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms_perftest.cc
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms_test_common.cc
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms_test_common.h
[add] https://crrev.com/2b021ec72c8717c2c65c0ac20029ec7fb38104ce/ui/latency/histograms_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b

commit ccd62c3f5b30dc57a416f60566a0af3fc6ff945b
Author: Brian Anderson <brianderson@chromium.org>
Date: Wed Mar 21 22:12:20 2018

ui: Add FrameMetrics windowed analyzer helpers.

Adds a class, WindowedAnalyzer, that maintains the worst
mean, RMS, and SMR values of a metric within a certain
window of time.

The results are updated only by looking at the oldest and
newest samples in the current window, so fixed-point
accumulators are used to avoid accumulation of error.

A client interface is provided that allows the client
to transform the units of the result.

Bug: 807463
Change-Id: Ifdb5729bf59c5479f254c4409f8d2c3d1b6eb996
Reviewed-on: https://chromium-review.googlesource.com/963730
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Cr-Commit-Position: refs/heads/master@{#544865}
[modify] https://crrev.com/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b/ui/latency/BUILD.gn
[modify] https://crrev.com/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b/ui/latency/fixed_point.h
[add] https://crrev.com/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b/ui/latency/windowed_analyzer.cc
[add] https://crrev.com/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b/ui/latency/windowed_analyzer.h
[add] https://crrev.com/ccd62c3f5b30dc57a416f60566a0af3fc6ff945b/ui/latency/windowed_analyzer_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/722959dd0dc896f1363747d3b76d8210b2c3510e

commit 722959dd0dc896f1363747d3b76d8210b2c3510e
Author: Brian Anderson <brianderson@chromium.org>
Date: Tue Mar 27 18:14:28 2018

ui: Add FrameMetrics stream analyzer helpers.

This adds the StreamAnalyzer class, which is responsible
for calculating the mean, rms, smr, standard deviation,
variance of roots, and threshold percentiles of a
continuous stream of values.

It owns a Histogram and a WindowedAnalyzer, which it uses
to delegate percentile estimates and to track regions of
time where metrics are worst.

Bug: 807463
Change-Id: I718b06778582d0628b964747f61352ae291452f0
Reviewed-on: https://chromium-review.googlesource.com/972568
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Reviewed-by: Sadrul Chowdhury <sadrul@chromium.org>
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Cr-Commit-Position: refs/heads/master@{#546168}
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/BUILD.gn
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/fixed_point.h
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/fixed_point_unittest.cc
[rename] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/frame_metrics_test_common.cc
[add] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/frame_metrics_test_common.h
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/histograms_perftest.cc
[delete] https://crrev.com/026a45f3b5fe9853244967c391186e701ddebc64/ui/latency/histograms_test_common.h
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/histograms_unittest.cc
[add] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/stream_analyzer.cc
[add] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/stream_analyzer.h
[add] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/stream_analyzer_unittest.cc
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/windowed_analyzer.cc
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/windowed_analyzer.h
[modify] https://crrev.com/722959dd0dc896f1363747d3b76d8210b2c3510e/ui/latency/windowed_analyzer_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d322cf20dca89c41cfac15bc61cabe0cc29c0caa

commit d322cf20dca89c41cfac15bc61cabe0cc29c0caa
Author: Brian Anderson <brianderson@chromium.org>
Date: Thu Apr 05 18:52:01 2018

ui: Add constructors to SharedWindowedAnalyzerClient

This adds a few constructors to SharedWindowedAnalyzerClient
and switches over all call sites that use initializer lists
to use a constructor instead. The upcoming FrameMetrics class
will use the "max_window_size" constructor.

Bug: 807463
Change-Id: Ie1d21b90ce00dff84d41c30e9563a9fba4ba67f5
Reviewed-on: https://chromium-review.googlesource.com/981415
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Reviewed-by: Sadrul Chowdhury <sadrul@chromium.org>
Cr-Commit-Position: refs/heads/master@{#548508}
[modify] https://crrev.com/d322cf20dca89c41cfac15bc61cabe0cc29c0caa/ui/latency/windowed_analyzer.h
[modify] https://crrev.com/d322cf20dca89c41cfac15bc61cabe0cc29c0caa/ui/latency/windowed_analyzer_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1

commit e5c3faf38a95c6c751310b7d39e7feee3a7df8f1
Author: Brian Anderson <brianderson@chromium.org>
Date: Fri Apr 06 00:37:02 2018

ui: Use "Compute" consistently in FrameMetrics.

To improve naming consistency, this changes instances
of "Calculate" prefixes to "Compute". It also prefixes
more methods with "Compute".

Bug: 807463
Change-Id: I9ccebc5ffbdf42e24142e21d850ea4a8e8ac0364
Reviewed-on: https://chromium-review.googlesource.com/981518
Commit-Queue: Brian Anderson <brianderson@chromium.org>
Reviewed-by: Sadrul Chowdhury <sadrul@chromium.org>
Reviewed-by: Timothy Dresser <tdresser@chromium.org>
Cr-Commit-Position: refs/heads/master@{#548621}
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/frame_metrics_test_common.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/frame_metrics_test_common.h
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/histograms.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/histograms.h
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/histograms_perftest.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/histograms_unittest.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/stream_analyzer.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/stream_analyzer_unittest.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/windowed_analyzer.cc
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/windowed_analyzer.h
[modify] https://crrev.com/e5c3faf38a95c6c751310b7d39e7feee3a7df8f1/ui/latency/windowed_analyzer_unittest.cc

This bug is stale. Is someone interested in picking this up? If there is no longer interest in these metrics then this can be closed.