histogram_test.go 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325
  1. // Copyright 2015 The Go Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style
  3. // license that can be found in the LICENSE file.
  4. package trace
  5. import (
  6. "math"
  7. "testing"
  8. )
  9. type sumTest struct {
  10. value int64
  11. sum int64
  12. sumOfSquares float64
  13. total int64
  14. }
  15. var sumTests = []sumTest{
  16. {100, 100, 10000, 1},
  17. {50, 150, 12500, 2},
  18. {50, 200, 15000, 3},
  19. {50, 250, 17500, 4},
  20. }
  21. type bucketingTest struct {
  22. in int64
  23. log int
  24. bucket int
  25. }
  26. var bucketingTests = []bucketingTest{
  27. {0, 0, 0},
  28. {1, 1, 0},
  29. {2, 2, 1},
  30. {3, 2, 1},
  31. {4, 3, 2},
  32. {1000, 10, 9},
  33. {1023, 10, 9},
  34. {1024, 11, 10},
  35. {1000000, 20, 19},
  36. }
  37. type multiplyTest struct {
  38. in int64
  39. ratio float64
  40. expectedSum int64
  41. expectedTotal int64
  42. expectedSumOfSquares float64
  43. }
  44. var multiplyTests = []multiplyTest{
  45. {15, 2.5, 37, 2, 562.5},
  46. {128, 4.6, 758, 13, 77953.9},
  47. }
  48. type percentileTest struct {
  49. fraction float64
  50. expected int64
  51. }
  52. var percentileTests = []percentileTest{
  53. {0.25, 48},
  54. {0.5, 96},
  55. {0.6, 109},
  56. {0.75, 128},
  57. {0.90, 205},
  58. {0.95, 230},
  59. {0.99, 256},
  60. }
  61. func TestSum(t *testing.T) {
  62. var h histogram
  63. for _, test := range sumTests {
  64. h.addMeasurement(test.value)
  65. sum := h.sum
  66. if sum != test.sum {
  67. t.Errorf("h.Sum = %v WANT: %v", sum, test.sum)
  68. }
  69. sumOfSquares := h.sumOfSquares
  70. if sumOfSquares != test.sumOfSquares {
  71. t.Errorf("h.SumOfSquares = %v WANT: %v", sumOfSquares, test.sumOfSquares)
  72. }
  73. total := h.total()
  74. if total != test.total {
  75. t.Errorf("h.Total = %v WANT: %v", total, test.total)
  76. }
  77. }
  78. }
  79. func TestMultiply(t *testing.T) {
  80. var h histogram
  81. for i, test := range multiplyTests {
  82. h.addMeasurement(test.in)
  83. h.Multiply(test.ratio)
  84. if h.sum != test.expectedSum {
  85. t.Errorf("#%v: h.sum = %v WANT: %v", i, h.sum, test.expectedSum)
  86. }
  87. if h.total() != test.expectedTotal {
  88. t.Errorf("#%v: h.total = %v WANT: %v", i, h.total(), test.expectedTotal)
  89. }
  90. if h.sumOfSquares != test.expectedSumOfSquares {
  91. t.Errorf("#%v: h.SumOfSquares = %v WANT: %v", i, test.expectedSumOfSquares, h.sumOfSquares)
  92. }
  93. }
  94. }
  95. func TestBucketingFunctions(t *testing.T) {
  96. for _, test := range bucketingTests {
  97. log := log2(test.in)
  98. if log != test.log {
  99. t.Errorf("log2 = %v WANT: %v", log, test.log)
  100. }
  101. bucket := getBucket(test.in)
  102. if bucket != test.bucket {
  103. t.Errorf("getBucket = %v WANT: %v", bucket, test.bucket)
  104. }
  105. }
  106. }
  107. func TestAverage(t *testing.T) {
  108. a := new(histogram)
  109. average := a.average()
  110. if average != 0 {
  111. t.Errorf("Average of empty histogram was %v WANT: 0", average)
  112. }
  113. a.addMeasurement(1)
  114. a.addMeasurement(1)
  115. a.addMeasurement(3)
  116. const expected = float64(5) / float64(3)
  117. average = a.average()
  118. if !isApproximate(average, expected) {
  119. t.Errorf("Average = %g WANT: %v", average, expected)
  120. }
  121. }
  122. func TestStandardDeviation(t *testing.T) {
  123. a := new(histogram)
  124. add(a, 10, 1<<4)
  125. add(a, 10, 1<<5)
  126. add(a, 10, 1<<6)
  127. stdDev := a.standardDeviation()
  128. const expected = 19.95
  129. if !isApproximate(stdDev, expected) {
  130. t.Errorf("StandardDeviation = %v WANT: %v", stdDev, expected)
  131. }
  132. // No values
  133. a = new(histogram)
  134. stdDev = a.standardDeviation()
  135. if !isApproximate(stdDev, 0) {
  136. t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
  137. }
  138. add(a, 1, 1<<4)
  139. if !isApproximate(stdDev, 0) {
  140. t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
  141. }
  142. add(a, 10, 1<<4)
  143. if !isApproximate(stdDev, 0) {
  144. t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
  145. }
  146. }
  147. func TestPercentileBoundary(t *testing.T) {
  148. a := new(histogram)
  149. add(a, 5, 1<<4)
  150. add(a, 10, 1<<6)
  151. add(a, 5, 1<<7)
  152. for _, test := range percentileTests {
  153. percentile := a.percentileBoundary(test.fraction)
  154. if percentile != test.expected {
  155. t.Errorf("h.PercentileBoundary (fraction=%v) = %v WANT: %v", test.fraction, percentile, test.expected)
  156. }
  157. }
  158. }
  159. func TestCopyFrom(t *testing.T) {
  160. a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
  161. 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
  162. b := histogram{6, 36, []int64{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
  163. 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39}, 5, -1}
  164. a.CopyFrom(&b)
  165. if a.String() != b.String() {
  166. t.Errorf("a.String = %s WANT: %s", a.String(), b.String())
  167. }
  168. }
  169. func TestClear(t *testing.T) {
  170. a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
  171. 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
  172. a.Clear()
  173. expected := "0, 0.000000, 0, 0, []"
  174. if a.String() != expected {
  175. t.Errorf("a.String = %s WANT %s", a.String(), expected)
  176. }
  177. }
  178. func TestNew(t *testing.T) {
  179. a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
  180. 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
  181. b := a.New()
  182. expected := "0, 0.000000, 0, 0, []"
  183. if b.(*histogram).String() != expected {
  184. t.Errorf("b.(*histogram).String = %s WANT: %s", b.(*histogram).String(), expected)
  185. }
  186. }
  187. func TestAdd(t *testing.T) {
  188. // The tests here depend on the associativity of addMeasurement and Add.
  189. // Add empty observation
  190. a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
  191. 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
  192. b := a.New()
  193. expected := a.String()
  194. a.Add(b)
  195. if a.String() != expected {
  196. t.Errorf("a.String = %s WANT: %s", a.String(), expected)
  197. }
  198. // Add same bucketed value, no new buckets
  199. c := new(histogram)
  200. d := new(histogram)
  201. e := new(histogram)
  202. c.addMeasurement(12)
  203. d.addMeasurement(11)
  204. e.addMeasurement(12)
  205. e.addMeasurement(11)
  206. c.Add(d)
  207. if c.String() != e.String() {
  208. t.Errorf("c.String = %s WANT: %s", c.String(), e.String())
  209. }
  210. // Add bucketed values
  211. f := new(histogram)
  212. g := new(histogram)
  213. h := new(histogram)
  214. f.addMeasurement(4)
  215. f.addMeasurement(12)
  216. f.addMeasurement(100)
  217. g.addMeasurement(18)
  218. g.addMeasurement(36)
  219. g.addMeasurement(255)
  220. h.addMeasurement(4)
  221. h.addMeasurement(12)
  222. h.addMeasurement(100)
  223. h.addMeasurement(18)
  224. h.addMeasurement(36)
  225. h.addMeasurement(255)
  226. f.Add(g)
  227. if f.String() != h.String() {
  228. t.Errorf("f.String = %q WANT: %q", f.String(), h.String())
  229. }
  230. // add buckets to no buckets
  231. i := new(histogram)
  232. j := new(histogram)
  233. k := new(histogram)
  234. j.addMeasurement(18)
  235. j.addMeasurement(36)
  236. j.addMeasurement(255)
  237. k.addMeasurement(18)
  238. k.addMeasurement(36)
  239. k.addMeasurement(255)
  240. i.Add(j)
  241. if i.String() != k.String() {
  242. t.Errorf("i.String = %q WANT: %q", i.String(), k.String())
  243. }
  244. // add buckets to single value (no overlap)
  245. l := new(histogram)
  246. m := new(histogram)
  247. n := new(histogram)
  248. l.addMeasurement(0)
  249. m.addMeasurement(18)
  250. m.addMeasurement(36)
  251. m.addMeasurement(255)
  252. n.addMeasurement(0)
  253. n.addMeasurement(18)
  254. n.addMeasurement(36)
  255. n.addMeasurement(255)
  256. l.Add(m)
  257. if l.String() != n.String() {
  258. t.Errorf("l.String = %q WANT: %q", l.String(), n.String())
  259. }
  260. // mixed order
  261. o := new(histogram)
  262. p := new(histogram)
  263. o.addMeasurement(0)
  264. o.addMeasurement(2)
  265. o.addMeasurement(0)
  266. p.addMeasurement(0)
  267. p.addMeasurement(0)
  268. p.addMeasurement(2)
  269. if o.String() != p.String() {
  270. t.Errorf("o.String = %q WANT: %q", o.String(), p.String())
  271. }
  272. }
  273. func add(h *histogram, times int, val int64) {
  274. for i := 0; i < times; i++ {
  275. h.addMeasurement(val)
  276. }
  277. }
  278. func isApproximate(x, y float64) bool {
  279. return math.Abs(x-y) < 1e-2
  280. }