Project P135
Percentiles
Three shops' response times: exact percentiles, why their p95s cannot be averaged while their histograms can be added, which aggregates survive being computed by shop, and how strict backends must be when a request waits for N of them.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-17
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Response times from three shops, their exact percentiles, and what can and cannot be put together from per-shop numbers.
main.eml- the menu, the shops, the percentiles, putting the p95 together, aggregates by shop, and a request that fans outpct.eml- the response times, nearest-rank percentiles, histograms on fixed buckets, and the fan-out numbers
How each part works:
- Each shop has mostly quick requests and a share of slow ones: 3% of A's 600, 5% of B's 300, 10% of C's 100. A percentile is the smallest time with at least that share at or below it.
- The p95 of all 1000 is 185 ms. The shops' own p95s give 252.7 as a mean, 120.1 as a mean by requests, and 610 as the largest: none of them is the p95 of the whole. Histograms on fixed buckets add exactly, and the bucket the p95 falls in gives 200, an upper bound, never below.
- As in the corpus case
aggregates-that-do-not-decompose, a sum, a count, a maximum and a minimum put together by shop; a distinct count adds the times two shops share twice, 181 against 171, and the median of the medians is 71 where the median is 44. - As in the corpus case
percentile-composition, a request that waits for N backends is as slow as the slowest. Every backend within its p99 happens 0.99^N of the time: 90.44% for 10. To hold the request at p99, each backend must be held at the quantile q with q^N = 0.99: 99.900% for 10, near the p99.9. Both are worked out in whole numbers.
What is checked: menu choices 1 to 6.
Sessions: sessions/basic.in gives every screen once, and sessions/bad-input.in gives menu choices 0, x, 7, an empty one and 12, then the shops.
Built on the verified corpus cases aggregates-that-do-not-decompose (what computing per shard and merging keeps and loses) and percentile-composition (the slowest of N backends sets the request's time).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Percentiles ==
Response times from three shops: their percentiles, and what can be put together from per-shop numbers.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 0
Pick a number from 1 to 6.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> x
Pick a number from 1 to 6.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 7
Pick a number from 1 to 6.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice>
Pick a number from 1 to 6.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 12
Pick a number from 1 to 6.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 1
shop A: 600 requests, the first five 23, 200, 37, 35 and 26 ms
shop B: 300 requests, the first five 44, 84, 50, 70 and 52 ms
shop C: 100 requests, the first five 154, 777, 111, 143 and 187 ms
Each shop has mostly quick requests and a share of slow ones: 3% at A, 5% at B, 10% at C.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 6
Bye.
What was typed (7 lines)
0
x
7
12
1
6
basic
interpreter: byte-equal== Percentiles ==
Response times from three shops: their percentiles, and what can be put together from per-shop numbers.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 1
shop A: 600 requests, the first five 23, 200, 37, 35 and 26 ms
shop B: 300 requests, the first five 44, 84, 50, 70 and 52 ms
shop C: 100 requests, the first five 154, 777, 111, 143 and 187 ms
Each shop has mostly quick requests and a share of slow ones: 3% at A, 5% at B, 10% at C.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 2
Exact percentiles, by nearest rank (ms):
shop requests p50 p95 p99
A 600 35 49 410
B 300 71 99 518
C 100 154 610 771
all 1000 44 185 523
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 3
The p95 of all 1000 requests is 185 ms. From the shops' own p95s:
their mean: 252.7
their mean, by requests: 120.1
the largest: 610
the shops' histograms added: at most 200 (bucket edges at 25, 50, 100, 200, 300, 500, 800 and 1000)
None of the first three is the p95 of the whole; the histograms add exactly, and their answer is the edge of the bucket the p95 falls in, never below it.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 4
Computed for each shop and put together, against computed on all requests at once:
aggregate by shop at once
sum, added 71132 71132
count, added 1000 1000
max of the maxes 777 777
min of the mins 20 20
distinct, added 181 171 differs
median of medians 71 44 differs
A sum, a count, a maximum and a minimum put together; a distinct count adds the times two shops share twice, and a median of medians is not the median.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 5
A request that waits for N backends is as slow as the slowest of them.
N within every backend's p99 backend quantile needed for the request's p99
1 99.00% 99.000%
2 98.01% 99.499%
5 95.10% 99.800%
10 90.44% 99.900%
20 81.79% 99.950%
Holding a request over ten backends to p99 needs each backend held near its p99.9, not its p99.
1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit
choice> 6
Bye.
What was typed (6 lines)
1
2
3
4
5
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P135 percentiles: three shops' response times, their exact percentiles,
# the wrong and the right ways to put them together, aggregates by shop,
# and a request that fans out to several backends.
import pct
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def lpad(s, n):
s => out
while len(out) < n:
" " + out => out
return out
def all_times(sh):
[] => out
for s in sh:
out + s[1] => out
return out
def show(sh):
for s in sh:
(" shop " + s[0] + ": " + str(len(s[1])) + " requests, the first five " + str(s[1][0]) + ", " + str(s[1][1]) + ", " + str(s[1][2]) + ", " + str(s[1][3]) + " and " + str(s[1][4]) + " ms") ^0
"Each shop has mostly quick requests and a share of slow ones: 3% at A, 5% at B, 10% at C." ^0
def percentiles(sh):
"Exact percentiles, by nearest rank (ms):" ^0
" shop requests p50 p95 p99" ^0
for s in sh:
(" " + pad(s[0], 5) + lpad(str(len(s[1])), 10) + lpad(str(pct.percentile(s[1], 50)), 7) + lpad(str(pct.percentile(s[1], 95)), 7) + lpad(str(pct.percentile(s[1], 99)), 7)) ^0
all_times(sh) => t
(" " + pad("all", 5) + lpad(str(len(t)), 10) + lpad(str(pct.percentile(t, 50)), 7) + lpad(str(pct.percentile(t, 95)), 7) + lpad(str(pct.percentile(t, 99)), 7)) ^0
def merging(sh):
all_times(sh) => t
pct.percentile(t, 95) => truth
0 => total
0 => weighted
0 => most
for s in sh:
pct.percentile(s[1], 95) => p
total + p => total
weighted + p * len(s[1]) => weighted
if p > most:
p => most
("The p95 of all " + str(len(t)) + " requests is " + str(truth) + " ms. From the shops' own p95s:") ^0
(" their mean: " + mean_text(total, len(sh))) ^0
(" their mean, by requests: " + mean_text(weighted, len(t))) ^0
(" the largest: " + str(most)) ^0
[] => h
for k in [0:len(pct.buckets()) - 1]:
h + [0] => h
for s in sh:
pct.histogram(s[1]) => hs
for k in [0:len(h) - 1]:
h[k] + hs[k] => h[k]
pct.from_histogram(h, 95) => hb
(" the shops' histograms added: at most " + str(hb) + " (bucket edges at 25, 50, 100, 200, 300, 500, 800 and 1000)") ^0
"None of the first three is the p95 of the whole; the histograms add exactly, and their answer is the edge of the bucket the p95 falls in, never below it." ^0
def mean_text(s, n):
# s / n to one decimal, rounded half up
int((20 * s + n) / (2 * n)) => t
while t * 2 * n > 20 * s + n:
t - 1 => t
while (t + 1) * 2 * n <= 20 * s + n:
t + 1 => t
return str(int(t / 10)) + "." + str(t % 10)
def aggregates(sh):
all_times(sh) => t
0 => s_sum
0 => s_count
0 => s_max
100000 => s_min
0 => s_distinct
[] => meds
for s in sh:
0 => x
for v in s[1]:
x + v => x
s_sum + x => s_sum
s_count + len(s[1]) => s_count
for v in s[1]:
if v > s_max:
v => s_max
if v < s_min:
v => s_min
s_distinct + pct.distinct(s[1]) => s_distinct
meds + [pct.median_low(s[1])] => meds
0 => w_sum
0 => w_max
100000 => w_min
for v in t:
w_sum + v => w_sum
if v > w_max:
v => w_max
if v < w_min:
v => w_min
"Computed for each shop and put together, against computed on all requests at once:" ^0
" aggregate by shop at once" ^0
row("sum, added", s_sum, w_sum)
row("count, added", s_count, len(t))
row("max of the maxes", s_max, w_max)
row("min of the mins", s_min, w_min)
row("distinct, added", s_distinct, pct.distinct(t))
row("median of medians", pct.median_low(meds), pct.median_low(t))
"A sum, a count, a maximum and a minimum put together; a distinct count adds the times two shops share twice, and a median of medians is not the median." ^0
def row(name, a, b):
"" => mark
if a != b:
" differs" => mark
(" " + pad(name, 18) + lpad(str(a), 9) + lpad(str(b), 10) + mark) ^0
def fan_out():
"A request that waits for N backends is as slow as the slowest of them." ^0
" N within every backend's p99 backend quantile needed for the request's p99" ^0
for n in [1, 2, 5, 10, 20]:
pct.within(n) => w
pct.needed(n) => q
(" " + pad(str(n), 5) + lpad(str(int(w / 100)) + "." + two(w % 100) + "%", 14) + lpad(str(int(q / 1000)) + "." + three(q % 1000) + "%", 38)) ^0
"Holding a request over ten backends to p99 needs each backend held near its p99.9, not its p99." ^0
def two(x):
if x < 10:
return "0" + str(x)
return str(x)
def three(x):
if x < 10:
return "00" + str(x)
if x < 100:
return "0" + str(x)
return str(x)
pct.shops() => sh
"== Percentiles ==" ^0
"Response times from three shops: their percentiles, and what can be put together from per-shop numbers." ^0
True => running
while running:
"" ^0
"1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show(sh)
elif choice == "2":
percentiles(sh)
elif choice == "3":
merging(sh)
elif choice == "4":
aggregates(sh)
elif choice == "5":
fan_out()
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import pct
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def lpad(s, n):
out = s
while len(out) < n:
out = " " + out
return out
def all_times(sh):
out = []
for s in sh:
out = out + s[1]
return out
def show(sh):
for s in sh:
print(" shop " + s[0] + ": " + str(len(s[1])) + " requests, the first five " + str(s[1][0]) + ", " + str(s[1][1]) + ", " + str(s[1][2]) + ", " + str(s[1][3]) + " and " + str(s[1][4]) + " ms")
print("Each shop has mostly quick requests and a share of slow ones: 3% at A, 5% at B, 10% at C.")
def percentiles(sh):
print("Exact percentiles, by nearest rank (ms):")
print(" shop requests p50 p95 p99")
for s in sh:
print(" " + pad(s[0], 5) + lpad(str(len(s[1])), 10) + lpad(str(pct.percentile(s[1], 50)), 7) + lpad(str(pct.percentile(s[1], 95)), 7) + lpad(str(pct.percentile(s[1], 99)), 7))
t = all_times(sh)
print(" " + pad("all", 5) + lpad(str(len(t)), 10) + lpad(str(pct.percentile(t, 50)), 7) + lpad(str(pct.percentile(t, 95)), 7) + lpad(str(pct.percentile(t, 99)), 7))
def merging(sh):
t = all_times(sh)
truth = pct.percentile(t, 95)
total = 0
weighted = 0
most = 0
for s in sh:
p = pct.percentile(s[1], 95)
total = total + p
weighted = weighted + p * len(s[1])
if p > most:
most = p
print("The p95 of all " + str(len(t)) + " requests is " + str(truth) + " ms. From the shops' own p95s:")
print(" their mean: " + mean_text(total, len(sh)))
print(" their mean, by requests: " + mean_text(weighted, len(t)))
print(" the largest: " + str(most))
h = []
for k in range(0, len(pct.buckets())):
h = h + [0]
for s in sh:
hs = pct.histogram(s[1])
for k in range(0, len(h)):
h[k] = h[k] + hs[k]
hb = pct.from_histogram(h, 95)
print(" the shops' histograms added: at most " + str(hb) + " (bucket edges at 25, 50, 100, 200, 300, 500, 800 and 1000)")
print("None of the first three is the p95 of the whole; the histograms add exactly, and their answer is the edge of the bucket the p95 falls in, never below it.")
def mean_text(s, n):
t = int((20 * s + n) / (2 * n))
while t * 2 * n > 20 * s + n:
t = t - 1
while (t + 1) * 2 * n <= 20 * s + n:
t = t + 1
return str(int(t / 10)) + "." + str(t % 10)
def aggregates(sh):
t = all_times(sh)
s_sum = 0
s_count = 0
s_max = 0
s_min = 100000
s_distinct = 0
meds = []
for s in sh:
x = 0
for v in s[1]:
x = x + v
s_sum = s_sum + x
s_count = s_count + len(s[1])
for v in s[1]:
if v > s_max:
s_max = v
if v < s_min:
s_min = v
s_distinct = s_distinct + pct.distinct(s[1])
meds = meds + [pct.median_low(s[1])]
w_sum = 0
w_max = 0
w_min = 100000
for v in t:
w_sum = w_sum + v
if v > w_max:
w_max = v
if v < w_min:
w_min = v
print("Computed for each shop and put together, against computed on all requests at once:")
print(" aggregate by shop at once")
row("sum, added", s_sum, w_sum)
row("count, added", s_count, len(t))
row("max of the maxes", s_max, w_max)
row("min of the mins", s_min, w_min)
row("distinct, added", s_distinct, pct.distinct(t))
row("median of medians", pct.median_low(meds), pct.median_low(t))
print("A sum, a count, a maximum and a minimum put together; a distinct count adds the times two shops share twice, and a median of medians is not the median.")
def row(name, a, b):
mark = ""
if a != b:
mark = " differs"
print(" " + pad(name, 18) + lpad(str(a), 9) + lpad(str(b), 10) + mark)
def fan_out():
print("A request that waits for N backends is as slow as the slowest of them.")
print(" N within every backend's p99 backend quantile needed for the request's p99")
for n in [1, 2, 5, 10, 20]:
w = pct.within(n)
q = pct.needed(n)
print(" " + pad(str(n), 5) + lpad(str(int(w / 100)) + "." + two(w % 100) + "%", 14) + lpad(str(int(q / 1000)) + "." + three(q % 1000) + "%", 38))
print("Holding a request over ten backends to p99 needs each backend held near its p99.9, not its p99.")
def two(x):
if x < 10:
return "0" + str(x)
return str(x)
def three(x):
if x < 10:
return "00" + str(x)
if x < 100:
return "0" + str(x)
return str(x)
sh = pct.shops()
print("== Percentiles ==")
print("Response times from three shops: their percentiles, and what can be put together from per-shop numbers.")
running = True
while running:
print("")
print("1) the shops 2) percentiles 3) putting p95 together 4) aggregates by shop 5) fan-out 6) quit")
choice = plain(input("choice> "))
if choice == "1":
show(sh)
elif choice == "2":
percentiles(sh)
elif choice == "3":
merging(sh)
elif choice == "4":
aggregates(sh)
elif choice == "5":
fan_out()
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
pct.eml
eml# P135 percentiles - response times from three shops, and what can and
# cannot be put together from per-shop numbers. As in the corpus case
# aggregates-that-do-not-decompose, a sum, a count, a maximum and a minimum
# merge; a median, a distinct count and a percentile do not, while a
# histogram on fixed buckets does, and gives an upper bound. As in
# percentile-composition, a request that waits for N backends is as slow as
# the slowest, so it meets the backends' p99 only when all N do.
def mix(i, salt):
i * 7919 + salt * 104729 + 12345 => x
for k in [1:3]:
(x * x + 7) % 1000000007 => x
return x % 1000000
def shops():
# [name, response times in ms]
[["A", 600, 20, 30, 3, 200], ["B", 300, 40, 60, 5, 300], ["C", 100, 100, 100, 10, 500]] => spec
[] => out
for s in spec:
[] => times
for i in [1:s[1]]:
if mix(i, ord_of(s[0])) % 100 < s[4]:
times + [s[5] + mix(i, ord_of(s[0]) + 7) % 300] => times
else:
times + [s[2] + mix(i, ord_of(s[0]) + 3) % s[3]] => times
out + [[s[0], times]] => out
return out
def ord_of(name):
if name == "A":
return 11
if name == "B":
return 12
return 13
def counts(times):
# {time: how many}
{} => c
for t in times:
if t in c:
c[t] + 1 => c[t]
else:
1 => c[t]
return c
def percentile(times, p):
# nearest rank: the smallest time with at least p percent at or below it
counts(times) => c
0 => most
for t in times:
if t > most:
t => most
0 => run
for v in [0:most]:
if v in c:
run + c[v] => run
if run * 100 >= p * len(times):
return v
return most
def buckets():
return [25, 50, 100, 200, 300, 500, 800, 1000]
def histogram(times):
# how many times fall at or below each bucket's edge and above the last
[] => h
for b in buckets():
h + [0] => h
for t in times:
False => placed
for k in [0:len(buckets()) - 1]:
if not placed and t <= buckets()[k]:
h[k] + 1 => h[k]
True => placed
return h
def from_histogram(h, p):
# the edge of the bucket where p percent is reached: an upper bound
0 => n
for x in h:
n + x => n
0 => run
for k in [0:len(h) - 1]:
run + h[k] => run
if run * 100 >= p * n:
return buckets()[k]
return buckets()[len(h) - 1]
def distinct(times):
return len(counts(times))
def median_low(times):
return percentile(times, 50)
def within(n):
# [whole percent, hundredths]: the share of requests over n backends
# that are all within each backend's p99, 0.99 ^ n, rounded half up
1 => num
1 => den
for k in [1:n]:
num * 99 => num
den * 100 => den
# in hundredths of a percent
int((2 * 10000 * num + den) / (2 * den)) => t
while t * 2 * den > 2 * 10000 * num + den:
t - 1 => t
while (t + 1) * 2 * den <= 2 * 10000 * num + den:
t + 1 => t
return t
def needed(n):
# the smallest backend quantile, in thousandths of a percent, that
# keeps the request within it 99 times in 100: k / 100000 with
# (k / 100000) ^ n >= 0.99, found by bisection on whole numbers
0 => lo
100000 => hi
while lo < hi:
int((lo + hi) / 2) => mid
1 => a
1 => b
for k in [1:n]:
a * mid => a
b * 100000 => b
if a * 100 >= 99 * b:
mid => hi
else:
mid + 1 => lo
return lo
Python projection (pct.py)
def mix(i, salt):
x = i * 7919 + salt * 104729 + 12345
for k in range(1, 4):
x = (x * x + 7) % 1000000007
return x % 1000000
def shops():
spec = [["A", 600, 20, 30, 3, 200], ["B", 300, 40, 60, 5, 300], ["C", 100, 100, 100, 10, 500]]
out = []
for s in spec:
times = []
for i in range(1, s[1]+1):
if mix(i, ord_of(s[0])) % 100 < s[4]:
times = times + [s[5] + mix(i, ord_of(s[0]) + 7) % 300]
else:
times = times + [s[2] + mix(i, ord_of(s[0]) + 3) % s[3]]
out = out + [[s[0], times]]
return out
def ord_of(name):
if name == "A":
return 11
if name == "B":
return 12
return 13
def counts(times):
c = {}
for t in times:
if t in c:
c[t] = c[t] + 1
else:
c[t] = 1
return c
def percentile(times, p):
c = counts(times)
most = 0
for t in times:
if t > most:
most = t
run = 0
for v in range(0, most+1):
if v in c:
run = run + c[v]
if run * 100 >= p * len(times):
return v
return most
def buckets():
return [25, 50, 100, 200, 300, 500, 800, 1000]
def histogram(times):
h = []
for b in buckets():
h = h + [0]
for t in times:
placed = False
for k in range(0, len(buckets())):
if not placed and t <= buckets()[k]:
h[k] = h[k] + 1
placed = True
return h
def from_histogram(h, p):
n = 0
for x in h:
n = n + x
run = 0
for k in range(0, len(h)):
run = run + h[k]
if run * 100 >= p * n:
return buckets()[k]
return buckets()[len(h) - 1]
def distinct(times):
return len(counts(times))
def median_low(times):
return percentile(times, 50)
def within(n):
num = 1
den = 1
for k in range(1, n+1):
num = num * 99
den = den * 100
t = int((2 * 10000 * num + den) / (2 * den))
while t * 2 * den > 2 * 10000 * num + den:
t = t - 1
while (t + 1) * 2 * den <= 2 * 10000 * num + den:
t = t + 1
return t
def needed(n):
lo = 0
hi = 100000
while lo < hi:
mid = int((lo + hi) / 2)
a = 1
b = 1
for k in range(1, n+1):
a = a * mid
b = b * 100000
if a * 100 >= 99 * b:
hi = mid
else:
lo = mid + 1
return lo