prettyping icon indicating copy to clipboard operation
prettyping copied to clipboard

big speedup for "Last N" statistics

Open xwang1498 opened this issue 5 months ago • 2 comments

Use O(1) algorithms to compute the "Last N" min/max/mean/stddev statistics.

I often use --last with a high N, e.g. prettyping -i 0.1 --last 6000 ... to watch for microbursts of loss or latency during the last 10 minutes.

Currently, those "Last N" statistics (min/max/mean/mean-absolute-dev) are computed by passing through the whole Last N arrays each time, which becomes very slow and CPU intensive for high values of --last.

Luckily, there are relatively simple constant-time algorithms for these, which this PR switches too.

(It also needs to change from Mean Absolute Deviation to Standard Deviation, because I'm not aware of an online, constant-time algo for Mean Absolute Deviation. But Standard Deviation will be very close anyways, and that's how most other ping tools do it.)

Tested fairly extensively for correctness with nawk (macOS), gawk, mawk, and Busybox awk.

Benchmarking shows dramatic speedups as --last grows.

xwang1498 avatar May 30 '25 18:05 xwang1498