Skip to content

Instantly share code, notes, and snippets.

@vlsi

vlsi/cms.r

Last active Aug 29, 2015
Embed
What would you like to do?
R simulation for "N servers running 1 full gc of duration 's' once every 'l' seconds". Probability of "all servers in GC" is computed
require(data.table)
N=3 #servers
l=86400 # interval
s=90 # gc duration
m=1000000 # samples
# Here we calculate "intersection of N intervals in each m groups independently"
# This is much faster than trying to do 'm' iterations of "intersect N intervals".
num_of_all_in_gc_cases <- function(d) {
# Here we transform each event to the pair of (sample, start, +1), (sample, start+s, -1)
x <- d[, list(sample=c(sample, sample), s=c(start, start+s), cnt=c(rep(1, .N), rep(-1, .N)))]
# Then we compute rolling sum ordered by "start", thus the resulting cnt is the number of intervals that overlap simultaneously
x[order(s), cnt:=cumsum(cnt), by=sample]
nrow(x[cnt >= N])
}
pick_gc <- function() {
data.table(start=runif(N*m, 0, l-s), sample=seq(1, m)) # uniform gc start distribution
}
n=0
k=100 # split to series to avoid out of memory
for(i in 1:k) {
n <- n + num_of_all_in_gc_cases(pick_gc())
print(paste(i, n, n/(m*i)))
}
m <- m*k
print(paste("N=", N, "servers, s=", s, "sec GC, l=", l, "sec between gc, m=", m, "random samples taken"))
print(paste("Probability of all servers in gc is", n/m, " (", n, "out of", m, "cases)"))
print(paste("Predicted bounds are", (l-2*s)/l*(2*s/l)**(N-1), "..", (l+2*s)/l*(2*s/l)**(N-1)))
# This is to verify computations in http://www.slideshare.net/yandex/java-party-2014-2014-07240150
[1] "N= 2 servers, s= 90 sec GC, l= 86400 sec between gc, m= 1e+08 random samples taken"
[1] "Probability of all servers in gc is 0.00208345 ( 208345 out of 1e+08 cases)"
[1] "Predicted bounds are 0.00207899305555556 .. 0.00208767361111111"
It looks like the formula does work for N=2
[1] "1 2054 0.002054"
[1] "2 4092 0.002046"
[1] "3 6171 0.002057"
[1] "4 8239 0.00205975"
[1] "5 10366 0.0020732"
[1] "6 12493 0.00208216666666667"
[1] "7 14535 0.00207642857142857"
[1] "8 16607 0.002075875"
[1] "9 18593 0.00206588888888889"
[1] "10 20648 0.0020648"
[1] "11 22766 0.00206963636363636"
[1] "12 24913 0.00207608333333333"
[1] "13 27000 0.00207692307692308"
[1] "14 29204 0.002086"
[1] "15 31265 0.00208433333333333"
[1] "16 33315 0.0020821875"
[1] "17 35381 0.00208123529411765"
[1] "18 37470 0.00208166666666667"
[1] "19 39480 0.00207789473684211"
[1] "20 41558 0.0020779"
[1] "21 43597 0.00207604761904762"
[1] "22 45659 0.00207540909090909"
[1] "23 47732 0.00207530434782609"
[1] "24 49870 0.00207791666666667"
[1] "25 51941 0.00207764"
[1] "26 54024 0.00207784615384615"
[1] "27 56046 0.00207577777777778"
[1] "28 58146 0.00207664285714286"
[1] "29 60274 0.00207841379310345"
[1] "30 62418 0.0020806"
[1] "31 64514 0.00208109677419355"
[1] "32 66590 0.0020809375"
[1] "33 68682 0.00208127272727273"
[1] "34 70775 0.00208161764705882"
[1] "35 72824 0.00208068571428571"
[1] "36 74923 0.00208119444444444"
[1] "37 77025 0.00208175675675676"
[1] "38 79241 0.00208528947368421"
[1] "39 81294 0.00208446153846154"
[1] "40 83357 0.002083925"
[1] "41 85451 0.00208417073170732"
[1] "42 87518 0.0020837619047619"
[1] "43 89597 0.0020836511627907"
[1] "44 91753 0.00208529545454545"
[1] "45 93884 0.00208631111111111"
[1] "46 96009 0.00208715217391304"
[1] "47 98112 0.00208748936170213"
[1] "48 100153 0.00208652083333333"
[1] "49 102249 0.00208671428571429"
[1] "50 104293 0.00208586"
[1] "51 106360 0.00208549019607843"
[1] "52 108507 0.00208667307692308"
[1] "53 110564 0.00208611320754717"
[1] "54 112652 0.00208614814814815"
[1] "55 114646 0.00208447272727273"
[1] "56 116689 0.00208373214285714"
[1] "57 118854 0.00208515789473684"
[1] "58 120903 0.00208453448275862"
[1] "59 123018 0.00208505084745763"
[1] "60 125195 0.00208658333333333"
[1] "61 127268 0.0020863606557377"
[1] "62 129333 0.00208601612903226"
[1] "63 131390 0.00208555555555556"
[1] "64 133464 0.002085375"
[1] "65 135451 0.00208386153846154"
[1] "66 137504 0.00208339393939394"
[1] "67 139531 0.00208255223880597"
[1] "68 141553 0.00208166176470588"
[1] "69 143670 0.00208217391304348"
[1] "70 145757 0.00208224285714286"
[1] "71 147827 0.00208207042253521"
[1] "72 149948 0.00208261111111111"
[1] "73 151973 0.00208182191780822"
[1] "74 154006 0.00208116216216216"
[1] "75 156062 0.00208082666666667"
[1] "76 158077 0.00207996052631579"
[1] "77 160217 0.00208074025974026"
[1] "78 162305 0.00208083333333333"
[1] "79 164352 0.00208040506329114"
[1] "80 166464 0.0020808"
[1] "81 168499 0.00208023456790123"
[1] "82 170591 0.00208037804878049"
[1] "83 172683 0.00208051807228916"
[1] "84 174826 0.0020812619047619"
[1] "85 176931 0.00208154117647059"
[1] "86 179032 0.00208176744186047"
[1] "87 181151 0.00208219540229885"
[1] "88 183254 0.00208243181818182"
[1] "89 185329 0.00208234831460674"
[1] "90 187438 0.00208264444444444"
[1] "91 189591 0.00208341758241758"
[1] "92 191659 0.00208325"
[1] "93 193639 0.00208213978494624"
[1] "94 195697 0.0020818829787234"
[1] "95 197822 0.00208233684210526"
[1] "96 199956 0.002082875"
[1] "97 202119 0.00208370103092784"
[1] "98 204204 0.00208371428571429"
[1] "99 206241 0.00208324242424242"
[1] "100 208345 0.00208345"
[1] "N= 3 servers, s= 90 sec GC, l= 86400 sec between gc, m= 1e+08 random samples taken"
[1] "Probability of all servers in gc is 3.11e-06 ( 311 out of 1e+08 cases)"
[1] "Predicted bounds are 4.33123553240741e-06 .. 4.34932002314815e-06"
I believe this tells us the formula is invalid (note that the probability is consistently below predicted 4.3e-6)
The detailed output is (millions_of_tested_intervals, all_servers_in_gc_cases_observed_so_far, probability_of_all_in_gc)
[1] "1 4 4e-06"
[1] "2 5 2.5e-06"
[1] "3 7 2.33333333333333e-06"
[1] "4 11 2.75e-06"
[1] "5 12 2.4e-06"
[1] "6 14 2.33333333333333e-06"
[1] "7 17 2.42857142857143e-06"
[1] "8 20 2.5e-06"
[1] "9 24 2.66666666666667e-06"
[1] "10 31 3.1e-06"
[1] "11 36 3.27272727272727e-06"
[1] "12 40 3.33333333333333e-06"
[1] "13 41 3.15384615384615e-06"
[1] "14 49 3.5e-06"
[1] "15 55 3.66666666666667e-06"
[1] "16 56 3.5e-06"
[1] "17 61 3.58823529411765e-06"
[1] "18 62 3.44444444444444e-06"
[1] "19 67 3.52631578947368e-06"
[1] "20 70 3.5e-06"
[1] "21 70 3.33333333333333e-06"
[1] "22 74 3.36363636363636e-06"
[1] "23 74 3.21739130434783e-06"
[1] "24 80 3.33333333333333e-06"
[1] "25 82 3.28e-06"
[1] "26 86 3.30769230769231e-06"
[1] "27 89 3.2962962962963e-06"
[1] "28 92 3.28571428571429e-06"
[1] "29 94 3.24137931034483e-06"
[1] "30 98 3.26666666666667e-06"
[1] "31 101 3.25806451612903e-06"
[1] "32 102 3.1875e-06"
[1] "33 104 3.15151515151515e-06"
[1] "34 107 3.14705882352941e-06"
[1] "35 111 3.17142857142857e-06"
[1] "36 113 3.13888888888889e-06"
[1] "37 116 3.13513513513514e-06"
[1] "38 120 3.15789473684211e-06"
[1] "39 124 3.17948717948718e-06"
[1] "40 128 3.2e-06"
[1] "41 133 3.24390243902439e-06"
[1] "42 135 3.21428571428571e-06"
[1] "43 137 3.18604651162791e-06"
[1] "44 139 3.15909090909091e-06"
[1] "45 141 3.13333333333333e-06"
[1] "46 144 3.1304347826087e-06"
[1] "47 146 3.1063829787234e-06"
[1] "48 148 3.08333333333333e-06"
[1] "49 149 3.04081632653061e-06"
[1] "50 151 3.02e-06"
[1] "51 155 3.03921568627451e-06"
[1] "52 157 3.01923076923077e-06"
[1] "53 160 3.0188679245283e-06"
[1] "54 165 3.05555555555556e-06"
[1] "55 171 3.10909090909091e-06"
[1] "56 174 3.10714285714286e-06"
[1] "57 179 3.14035087719298e-06"
[1] "58 184 3.17241379310345e-06"
[1] "59 186 3.15254237288136e-06"
[1] "60 188 3.13333333333333e-06"
[1] "61 190 3.11475409836066e-06"
[1] "62 195 3.14516129032258e-06"
[1] "63 197 3.12698412698413e-06"
[1] "64 197 3.078125e-06"
[1] "65 202 3.10769230769231e-06"
[1] "66 205 3.10606060606061e-06"
[1] "67 208 3.1044776119403e-06"
[1] "68 212 3.11764705882353e-06"
[1] "69 218 3.15942028985507e-06"
[1] "70 219 3.12857142857143e-06"
[1] "71 222 3.12676056338028e-06"
[1] "72 224 3.11111111111111e-06"
[1] "73 224 3.06849315068493e-06"
[1] "74 228 3.08108108108108e-06"
[1] "75 229 3.05333333333333e-06"
[1] "76 232 3.05263157894737e-06"
[1] "77 235 3.05194805194805e-06"
[1] "78 237 3.03846153846154e-06"
[1] "79 243 3.07594936708861e-06"
[1] "80 246 3.075e-06"
[1] "81 248 3.06172839506173e-06"
[1] "82 250 3.04878048780488e-06"
[1] "83 258 3.10843373493976e-06"
[1] "84 259 3.08333333333333e-06"
[1] "85 270 3.17647058823529e-06"
[1] "86 275 3.19767441860465e-06"
[1] "87 277 3.18390804597701e-06"
[1] "88 279 3.17045454545455e-06"
[1] "89 283 3.17977528089888e-06"
[1] "90 286 3.17777777777778e-06"
[1] "91 287 3.15384615384615e-06"
[1] "92 290 3.15217391304348e-06"
[1] "93 297 3.19354838709677e-06"
[1] "94 301 3.20212765957447e-06"
[1] "95 304 3.2e-06"
[1] "96 305 3.17708333333333e-06"
[1] "97 306 3.15463917525773e-06"
[1] "98 309 3.1530612244898e-06"
[1] "99 310 3.13131313131313e-06"
[1] "100 311 3.11e-06"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.