31:T916,function plot_dist() { let dists = arguments let layers = []; let t_dists = []; let max_y = 0; let marks = []; // const colors = ["#ffffcc", "#a1dab4", "#41b6c4", "#2c7fb8", "#253494"] // const colors = ["navy", "red", "green", "blue", "gray"] // const colors = ["#fbb4ae", "#b3cde3", "#ccebc5", "#decbe4", "#fed9a6"] // const colors = ["#e41a1c", "#377eb8", "#4daf4a", "#984ea3", "#ff7f00"] const colors = ["#1f78b4", "#fb9a99", "#a6cee3", "#b2df8a", "#33a02c" ] for (let color of colors) { marks.push({ type: "bar", "opacity": .8, "fillOpacity": .8, "binSpacing": 0 }) } let title = ""; for (const dist of dists) { let mean = expectation(dist) let p95 = quantile(dist, .95); let p99 = quantile(dist, .99); const name = dist.name || ""; let t_dist = trunc_dist(dist, 1e-4, 200) t_dists.push(t_dist) layers.push({ data: { values: t_dist.p.map((v, i) => ({ "duration": t_dist.steps[i], "duration2": t_dist.steps[i] + t_dist.binw, "p": v, "name": name })) }, encoding: { y: { field: "p", type: "quantitative" }, color: { field: "name", type: "nominal", title: null }, }, mark: marks[layers.length] }) max_y = Math.max(t_dist.steps[t_dist.steps.length - 1], max_y) if (title != "") title += "; " title += `${name} (mean=${d3.format(".1f")(mean)} p95=${p95} p99=${p99})` } let t_dist = t_dists[0]; return vegalite({ width: 500, data: { values: t_dist.p.map((v, i) => ({ "duration": t_dist.steps[i], "duration2": t_dist.steps[i] + t_dist.binw, "p": v })) }, encoding: { x: { field: "duration", type: "quantitative", axis: { title: title }, scale: { domain: [0, max_y] }, bin: { binned: true } }, x2: { field: "duration2" } }, layer: layers }) }32:[] 2f:{"title":"Parallel task latency calculator","cells":[{"id":0,"value":"md`# Parallel task latency calculator`","pinned":false,"hidden":false,"mode":"ojs"},{"id":737,"value":"md`[Read the post here](https://oavdeev.github.io/posts/parallel_latency/) for more detail.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"md`Say, we want to model request-response latency of a system, where to complete a request we have ${Math.pow(2, pow)} tasks to execute. We assume that individual task execution times are independent. We model the execution time of a single task as a ${dist_id_to_name(dist_type)} distribution. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":429,"value":"viewof pow = radio({\n options: [{label: \"1\", value: 0}, {label: \"2\", value: 1}, {label: \"4\", value: 2}, {label: \"8\", value: 3}, {label: \"16 tasks\", value: 4}],\n value: 3\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"viewof dist_type = radio({\n options: dist_options,\n value: 'rayleigh'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"viewof b1 = multislider([\n {id: \"min\", label: \"min\", val: 10, min: 0, max: 300, step: 1, width: \"auto\"},\n {id: \"p95\", label: \"p95\", val: 56, min: 10, max: 300, step: 1, width: \"auto\"},\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":753,"value":"dot`digraph { ${[...Generators.map(Generators.range(Math.pow(2, pow) ), x => (\"request -> \" + x + \"; \" + x + \" -> \" + \"response\"))].join(\";\")}; }`","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"md`If we execute the tasks perfectly in parallel, the total latency of ${Math.pow(2, pow)} tasks would look like this (mean is ${Math.round(expectation(d_parallel)/expectation(d)*100 - 100)}% higher compared to a single task, p95 is ${Math.round(quantile(d_parallel, .95)/quantile(d, .95) * 100 - 100)}% higher):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"{\n d.name = \"single task\"\n d_parallel.name = `${Math.pow(2, pow)} in parallel`\n return plot_dist(d, d_parallel)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":773,"value":"dot`digraph { request -> 0; ${[...Generators.map(Generators.range(Math.pow(2, pow)-1 ), x => (x + \" -> \" + (x+1)))].join(\";\")}; ${Math.pow(2, pow)-1} -> response; rankdir=\"LR\"; }`","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"md`And if these ${Math.pow(2, pow)} tasks were executed sequentially, the latency distribution would be:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"{\n d.name = \"single task\"\n d_seq.name = `${Math.pow(2, pow)} sequential`\n return plot_dist(d, d_seq)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":724,"value":"md`------------------`","pinned":false,"hidden":false,"mode":"ojs"},{"id":719,"value":"md`### Implementation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":90,"value":"d = { \n let step_size = 1; //stdlib.linspace( 0.0, 200, 201 )\n let pdf = dist_id_to_gen(dist_type)(b1.p95, b1.min);\n return to_discrete(pdf, step_size)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"/* Compute pdf of maximum of two independent random variables \n * with pdfs dist1 and dist2 \n */\nfunction max_dist(dist1, dist2) {\n return {\n p: dist1.steps.map((s, i) => {\n let res = dist1.p[i] * dist2.p[i];\n for (let j = 0; j < i; j++) {\n res += dist1.p[i] * dist2.p[j] + dist1.p[j] * dist2.p[i];\n }\n return res;\n }),\n steps: dist1.steps,\n binw: dist1.binw\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":227,"value":"d_parallel = power2_f(d, x=>max_dist(x, x), pow)","pinned":false,"hidden":false,"mode":"ojs"},{"id":546,"value":"d_seq = power2_f(d, conv_power, pow)","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"/* Compute f^n(d) where n=2^p (that is, f(f(f(..f(d)))) ) */\nfunction power2_f(d, f, p) {\n let t = d;\n for (let i = 0; i < p; i++) {\n t = trunc_dist(f(t), 1e-6, 200);\n }\n return t\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"function shifted_rayleigh(p95, min) {\n const sigma = (p95 - min) / Math.sqrt(-2 * Math.log(0.05))\n return (v) => stdlib.base.dists.rayleigh.pdf( v - min, sigma)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"function betaprime(p95, min, alpha, beta) {\n let x = stdlib.base.dists.betaprime.quantile(0.95, alpha, beta)\n let scale = (p95 - min) / x\n return (v) => v < min ? 0 : stdlib.base.dists.betaprime.pdf((v-min) / scale, alpha, beta)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":320,"value":"function chi2(p95, min, k) {\n let x = stdlib.base.dists.chisquare.quantile(0.95, k)\n let scale = (p95 - min) / x\n return (v) => v < min ? 0 : stdlib.base.dists.chisquare.pdf((v-min) / scale, k)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":400,"value":"/*\n * A sum of betaprime and shifted+scaled normal, that gives a somewhat realistic bimodal distribution.\n */\nfunction bimodal_betap_norm(p95, min) {\n let pdf = (x) => (stdlib.base.dists.betaprime.pdf(x, 2, 3) + stdlib.base.dists.normal.pdf(x, 2, 0.5) / 2) / 1.5;\n let x = 2.87887989892477; // p95 for the pdf above, found using sympy\n let scale = (p95 - min) / x;\n return (v) => v < min ? 0 : pdf((v-min) / scale)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"/* Convert continous distribution to a discrete one */\nfunction to_discrete(f, step_size) {\n let new_steps = [];\n let unnorm = [];\n for (let i = 0; i < 4000; i++) {\n let x = i*step_size;\n let s = f(x);\n unnorm.push(s);\n new_steps.push(x);\n if (s < 1e-5 && i > 100) {\n break;\n }\n }\n \n let norm = unnorm.reduce((x,y) => x+y, 0)\n return { p: unnorm.map((x) => x / norm), steps: new_steps, binw: step_size }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"function expectation(dist) {\n return dist.p.reduce((acc, x, i) => acc + (x * dist.steps[i]), 0)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":170,"value":"/* Compute quantile of a discrete distribution */\nfunction quantile(dist, p) {\n let cs = 0\n for (let i = 0 ; i < dist.p.length ; i++) {\n cs += dist.p[i]\n if (cs >= p) {\n return dist.steps[i]\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"/* Compute convolution of a PDF with itself */\nfunction conv_power(dist) {\n let w = dist.p.length\n let res = [];\n let new_steps = [];\n for (let i = 0; i < w * 2 - 1; i++) {\n res[i] = dist.p.reduce((acc, cur, j) => acc + cur * ((i-j >= w || i-j<0) ? 0 : dist.p[i-j]), 0);\n new_steps[i] = (i < w) ? dist.steps[i] : (i*dist.binw);\n }\n return { p: res, steps: new_steps, binw: dist.binw }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":363,"value":"function trunc_point(dist, threshold, min_pts) {\n for (let i = dist.steps.length-1 ; i >= min_pts; i--) {\n if (dist.p[i] > threshold) \n return i;\n }\n return Math.min(dist.steps.length, min_pts)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":345,"value":"/* \n Remove near-zero bins in the tail of the discrete distribution.\n (but leave at least min_bins)\n*/\nfunction trunc_dist(dist, threshold, min_bins) {\n let tp = trunc_point(dist, threshold, min_bins);\n return {\n binw: dist.binw,\n steps: dist.steps.slice(0, tp+1),\n p: dist.p.slice(0, tp+1)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":300,"value":"dist_options = [\n { label: 'Rayleigh', value: 'rayleigh', gen: shifted_rayleigh },\n { label: 'χ2 (k=3)', value: 'chi2', gen: (p95, min) => chi2(p95, min, 3)},\n { label: 'Beta Prime (2,3)', value: 'betaprime', gen: (p95, min) => betaprime(p95, min, 2, 3) },\n { label: \"Bimodal\", value: \"bimodal\", gen: bimodal_betap_norm}\n]\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":302,"value":"function dist_id_to_name(n) {\n return dist_options.filter(x => x.value == n)[0].label\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":327,"value":"function dist_id_to_gen(id) {\n return dist_options.filter(x => x.value == id)[0].gen\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":34,"value":"vegalite = require(\"@observablehq/vega-lite@0.2\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":117,"value":"d3 = require(\"d3-format@1\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"//stdlib = require( \"https://unpkg.com/@stdlib/stdlib@0.0.60/dist/stdlib-flat.min.js\" )\nstdlib = require(\"https://oavdeev.github.io/static/stdlib-flat.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":261,"value":"import {radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"function multislider(items) {\n const divs = items.map(item => {\n return `

${item.label}\n

`\n })\n const div = html`${divs.concat(\"\")}`;\n\n const sync = (name, default_val) => {\n const range = div.querySelector('#' + name + \" > [type=range]\");\n const number = div.querySelector('#' + name + \" > [type=number]\");\n div.value[name] = range.value = number.value = default_val;\n range.oninput = () => number.value = div.value[name] = range.valueAsNumber;\n number.oninput = () => range.value = div.value[name] = number.valueAsNumber;\n }\n div.value = {}\n \n items.forEach(item => sync(item.id, item.val))\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"function slider(label, val, min, max, step, width) {\n const div = html`\n ${label}\n \n `;\n const range = div.querySelector(\"[type=range]\");\n const number = div.querySelector(\"[type=number]\");\n div.value = range.value = number.value = val;\n range.oninput = () => number.value = div.value = range.valueAsNumber;\n number.oninput = () => range.value = div.value = number.valueAsNumber;\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}