1// Copyright 2016, Circonus, Inc. All rights reserved. 2// See the LICENSE file. 3 4// Package circllhist provides an implementation of Circonus' fixed log-linear 5// histogram data structure. This allows tracking of histograms in a 6// composable way such that accurate error can be reasoned about. 7package circonusllhist 8 9import ( 10 "bytes" 11 "encoding/base64" 12 "encoding/binary" 13 "encoding/json" 14 "errors" 15 "fmt" 16 "io" 17 "math" 18 "strconv" 19 "strings" 20 "sync" 21 "time" 22) 23 24const ( 25 defaultHistSize = uint16(100) 26) 27 28var powerOfTen = [...]float64{ 29 1, 10, 100, 1000, 10000, 100000, 1e+06, 1e+07, 1e+08, 1e+09, 1e+10, 30 1e+11, 1e+12, 1e+13, 1e+14, 1e+15, 1e+16, 1e+17, 1e+18, 1e+19, 1e+20, 31 1e+21, 1e+22, 1e+23, 1e+24, 1e+25, 1e+26, 1e+27, 1e+28, 1e+29, 1e+30, 32 1e+31, 1e+32, 1e+33, 1e+34, 1e+35, 1e+36, 1e+37, 1e+38, 1e+39, 1e+40, 33 1e+41, 1e+42, 1e+43, 1e+44, 1e+45, 1e+46, 1e+47, 1e+48, 1e+49, 1e+50, 34 1e+51, 1e+52, 1e+53, 1e+54, 1e+55, 1e+56, 1e+57, 1e+58, 1e+59, 1e+60, 35 1e+61, 1e+62, 1e+63, 1e+64, 1e+65, 1e+66, 1e+67, 1e+68, 1e+69, 1e+70, 36 1e+71, 1e+72, 1e+73, 1e+74, 1e+75, 1e+76, 1e+77, 1e+78, 1e+79, 1e+80, 37 1e+81, 1e+82, 1e+83, 1e+84, 1e+85, 1e+86, 1e+87, 1e+88, 1e+89, 1e+90, 38 1e+91, 1e+92, 1e+93, 1e+94, 1e+95, 1e+96, 1e+97, 1e+98, 1e+99, 1e+100, 39 1e+101, 1e+102, 1e+103, 1e+104, 1e+105, 1e+106, 1e+107, 1e+108, 1e+109, 40 1e+110, 1e+111, 1e+112, 1e+113, 1e+114, 1e+115, 1e+116, 1e+117, 1e+118, 41 1e+119, 1e+120, 1e+121, 1e+122, 1e+123, 1e+124, 1e+125, 1e+126, 1e+127, 42 1e-128, 1e-127, 1e-126, 1e-125, 1e-124, 1e-123, 1e-122, 1e-121, 1e-120, 43 1e-119, 1e-118, 1e-117, 1e-116, 1e-115, 1e-114, 1e-113, 1e-112, 1e-111, 44 1e-110, 1e-109, 1e-108, 1e-107, 1e-106, 1e-105, 1e-104, 1e-103, 1e-102, 45 1e-101, 1e-100, 1e-99, 1e-98, 1e-97, 1e-96, 46 1e-95, 1e-94, 1e-93, 1e-92, 1e-91, 1e-90, 1e-89, 1e-88, 1e-87, 1e-86, 47 1e-85, 1e-84, 1e-83, 1e-82, 1e-81, 1e-80, 1e-79, 1e-78, 1e-77, 1e-76, 48 1e-75, 1e-74, 1e-73, 1e-72, 1e-71, 1e-70, 1e-69, 1e-68, 1e-67, 1e-66, 49 1e-65, 1e-64, 1e-63, 1e-62, 1e-61, 1e-60, 1e-59, 1e-58, 1e-57, 1e-56, 50 1e-55, 1e-54, 1e-53, 1e-52, 1e-51, 1e-50, 1e-49, 1e-48, 1e-47, 1e-46, 51 1e-45, 1e-44, 1e-43, 1e-42, 1e-41, 1e-40, 1e-39, 1e-38, 1e-37, 1e-36, 52 1e-35, 1e-34, 1e-33, 1e-32, 1e-31, 1e-30, 1e-29, 1e-28, 1e-27, 1e-26, 53 1e-25, 1e-24, 1e-23, 1e-22, 1e-21, 1e-20, 1e-19, 1e-18, 1e-17, 1e-16, 54 1e-15, 1e-14, 1e-13, 1e-12, 1e-11, 1e-10, 1e-09, 1e-08, 1e-07, 1e-06, 55 1e-05, 0.0001, 0.001, 0.01, 0.1, 56} 57 58// A Bracket is a part of a cumulative distribution. 59type bin struct { 60 count uint64 61 val int8 62 exp int8 63} 64 65func newBinRaw(val int8, exp int8, count uint64) *bin { 66 return &bin{ 67 count: count, 68 val: val, 69 exp: exp, 70 } 71} 72 73func newBin() *bin { 74 return newBinRaw(0, 0, 0) 75} 76 77func newBinFromFloat64(d float64) *bin { 78 hb := newBinRaw(0, 0, 0) 79 hb.setFromFloat64(d) 80 return hb 81} 82 83type fastL2 struct { 84 l1, l2 int 85} 86 87func (hb *bin) newFastL2() fastL2 { 88 return fastL2{l1: int(uint8(hb.exp)), l2: int(uint8(hb.val))} 89} 90 91func (hb *bin) setFromFloat64(d float64) *bin { 92 hb.val = -1 93 if math.IsInf(d, 0) || math.IsNaN(d) { 94 return hb 95 } 96 if d == 0.0 { 97 hb.val = 0 98 return hb 99 } 100 sign := 1 101 if math.Signbit(d) { 102 sign = -1 103 } 104 d = math.Abs(d) 105 big_exp := int(math.Floor(math.Log10(d))) 106 hb.exp = int8(big_exp) 107 if int(hb.exp) != big_exp { //rolled 108 hb.exp = 0 109 if big_exp < 0 { 110 hb.val = 0 111 } 112 return hb 113 } 114 d = d / hb.powerOfTen() 115 d = d * 10 116 hb.val = int8(sign * int(math.Floor(d+1e-13))) 117 if hb.val == 100 || hb.val == -100 { 118 if hb.exp < 127 { 119 hb.val = hb.val / 10 120 hb.exp++ 121 } else { 122 hb.val = 0 123 hb.exp = 0 124 } 125 } 126 if hb.val == 0 { 127 hb.exp = 0 128 return hb 129 } 130 if !((hb.val >= 10 && hb.val < 100) || 131 (hb.val <= -10 && hb.val > -100)) { 132 hb.val = -1 133 hb.exp = 0 134 } 135 return hb 136} 137 138func (hb *bin) powerOfTen() float64 { 139 idx := int(uint8(hb.exp)) 140 return powerOfTen[idx] 141} 142 143func (hb *bin) isNaN() bool { 144 // aval := abs(hb.val) 145 aval := hb.val 146 if aval < 0 { 147 aval = -aval 148 } 149 if 99 < aval { // in [100... ]: nan 150 return true 151 } 152 if 9 < aval { // in [10 - 99]: valid range 153 return false 154 } 155 if 0 < aval { // in [1 - 9 ]: nan 156 return true 157 } 158 if 0 == aval { // in [0] : zero bucket 159 return false 160 } 161 return false 162} 163 164func (hb *bin) value() float64 { 165 if hb.isNaN() { 166 return math.NaN() 167 } 168 if hb.val < 10 && hb.val > -10 { 169 return 0.0 170 } 171 return (float64(hb.val) / 10.0) * hb.powerOfTen() 172} 173 174func (hb *bin) binWidth() float64 { 175 if hb.isNaN() { 176 return math.NaN() 177 } 178 if hb.val < 10 && hb.val > -10 { 179 return 0.0 180 } 181 return hb.powerOfTen() / 10.0 182} 183 184func (hb *bin) midpoint() float64 { 185 if hb.isNaN() { 186 return math.NaN() 187 } 188 out := hb.value() 189 if out == 0 { 190 return 0 191 } 192 interval := hb.binWidth() 193 if out < 0 { 194 interval = interval * -1 195 } 196 return out + interval/2.0 197} 198 199func (hb *bin) left() float64 { 200 if hb.isNaN() { 201 return math.NaN() 202 } 203 out := hb.value() 204 if out >= 0 { 205 return out 206 } 207 return out - hb.binWidth() 208} 209 210func (h1 *bin) compare(h2 *bin) int { 211 var v1, v2 int 212 213 // 1) slide exp positive 214 // 2) shift by size of val multiple by (val != 0) 215 // 3) then add or subtract val accordingly 216 217 if h1.val >= 0 { 218 v1 = ((int(h1.exp)+256)<<8)*int(((int(h1.val)|(^int(h1.val)+1))>>8)&1) + int(h1.val) 219 } else { 220 v1 = ((int(h1.exp)+256)<<8)*int(((int(h1.val)|(^int(h1.val)+1))>>8)&1) - int(h1.val) 221 } 222 223 if h2.val >= 0 { 224 v2 = ((int(h2.exp)+256)<<8)*int(((int(h2.val)|(^int(h2.val)+1))>>8)&1) + int(h2.val) 225 } else { 226 v2 = ((int(h2.exp)+256)<<8)*int(((int(h2.val)|(^int(h2.val)+1))>>8)&1) - int(h2.val) 227 } 228 229 // return the difference 230 return v2 - v1 231} 232 233// This histogram structure tracks values are two decimal digits of precision 234// with a bounded error that remains bounded upon composition 235type Histogram struct { 236 bvs []bin 237 used uint16 238 allocd uint16 239 240 lookup [256][]uint16 241 242 mutex sync.RWMutex 243 useLocks bool 244} 245 246const ( 247 BVL1, BVL1MASK uint64 = iota, 0xff << (8 * iota) 248 BVL2, BVL2MASK 249 BVL3, BVL3MASK 250 BVL4, BVL4MASK 251 BVL5, BVL5MASK 252 BVL6, BVL6MASK 253 BVL7, BVL7MASK 254 BVL8, BVL8MASK 255) 256 257func getBytesRequired(val uint64) (len int8) { 258 if 0 != (BVL8MASK|BVL7MASK|BVL6MASK|BVL5MASK)&val { 259 if 0 != BVL8MASK&val { 260 return int8(BVL8) 261 } 262 if 0 != BVL7MASK&val { 263 return int8(BVL7) 264 } 265 if 0 != BVL6MASK&val { 266 return int8(BVL6) 267 } 268 if 0 != BVL5MASK&val { 269 return int8(BVL5) 270 } 271 } else { 272 if 0 != BVL4MASK&val { 273 return int8(BVL4) 274 } 275 if 0 != BVL3MASK&val { 276 return int8(BVL3) 277 } 278 if 0 != BVL2MASK&val { 279 return int8(BVL2) 280 } 281 } 282 return int8(BVL1) 283} 284 285func writeBin(out io.Writer, in bin, idx int) (err error) { 286 287 err = binary.Write(out, binary.BigEndian, in.val) 288 if err != nil { 289 return 290 } 291 292 err = binary.Write(out, binary.BigEndian, in.exp) 293 if err != nil { 294 return 295 } 296 297 var tgtType int8 = getBytesRequired(in.count) 298 299 err = binary.Write(out, binary.BigEndian, tgtType) 300 if err != nil { 301 return 302 } 303 304 var bcount = make([]uint8, 8) 305 b := bcount[0 : tgtType+1] 306 for i := tgtType; i >= 0; i-- { 307 b[i] = uint8(uint64(in.count>>(uint8(i)*8)) & 0xff) 308 } 309 310 err = binary.Write(out, binary.BigEndian, b) 311 if err != nil { 312 return 313 } 314 return 315} 316 317func readBin(in io.Reader) (out bin, err error) { 318 err = binary.Read(in, binary.BigEndian, &out.val) 319 if err != nil { 320 return 321 } 322 323 err = binary.Read(in, binary.BigEndian, &out.exp) 324 if err != nil { 325 return 326 } 327 var bvl uint8 328 err = binary.Read(in, binary.BigEndian, &bvl) 329 if err != nil { 330 return 331 } 332 if bvl > uint8(BVL8) { 333 return out, errors.New("encoding error: bvl value is greater than max allowable") 334 } 335 336 bcount := make([]byte, 8) 337 b := bcount[0 : bvl+1] 338 err = binary.Read(in, binary.BigEndian, b) 339 if err != nil { 340 return 341 } 342 343 var count uint64 = 0 344 for i := int(bvl + 1); i >= 0; i-- { 345 count |= (uint64(bcount[i]) << (uint8(i) * 8)) 346 } 347 348 out.count = count 349 return 350} 351 352func Deserialize(in io.Reader) (h *Histogram, err error) { 353 h = New() 354 if h.bvs == nil { 355 h.bvs = make([]bin, 0, defaultHistSize) 356 } 357 358 var nbin int16 359 err = binary.Read(in, binary.BigEndian, &nbin) 360 if err != nil { 361 return 362 } 363 364 for ii := int16(0); ii < nbin; ii++ { 365 bb, err := readBin(in) 366 if err != nil { 367 return h, err 368 } 369 h.insertBin(&bb, int64(bb.count)) 370 } 371 return h, nil 372} 373 374func (h *Histogram) Serialize(w io.Writer) error { 375 376 var nbin int16 = int16(len(h.bvs)) 377 if err := binary.Write(w, binary.BigEndian, nbin); err != nil { 378 return err 379 } 380 381 for i := 0; i < len(h.bvs); i++ { 382 if err := writeBin(w, h.bvs[i], i); err != nil { 383 return err 384 } 385 } 386 return nil 387} 388 389func (h *Histogram) SerializeB64(w io.Writer) error { 390 buf := bytes.NewBuffer([]byte{}) 391 h.Serialize(buf) 392 393 encoder := base64.NewEncoder(base64.StdEncoding, w) 394 if _, err := encoder.Write(buf.Bytes()); err != nil { 395 return err 396 } 397 encoder.Close() 398 return nil 399} 400 401// New returns a new Histogram 402func New() *Histogram { 403 return &Histogram{ 404 allocd: defaultHistSize, 405 used: 0, 406 bvs: make([]bin, defaultHistSize), 407 useLocks: true, 408 } 409} 410 411// New returns a Histogram without locking 412func NewNoLocks() *Histogram { 413 return &Histogram{ 414 allocd: defaultHistSize, 415 used: 0, 416 bvs: make([]bin, defaultHistSize), 417 useLocks: false, 418 } 419} 420 421// NewFromStrings returns a Histogram created from DecStrings strings 422func NewFromStrings(strs []string, locks bool) (*Histogram, error) { 423 424 bin, err := stringsToBin(strs) 425 if err != nil { 426 return nil, err 427 } 428 429 return newFromBins(bin, locks), nil 430} 431 432// NewFromBins returns a Histogram created from a bins struct slice 433func newFromBins(bins []bin, locks bool) *Histogram { 434 return &Histogram{ 435 allocd: uint16(len(bins) + 10), // pad it with 10 436 used: uint16(len(bins)), 437 bvs: bins, 438 useLocks: locks, 439 } 440} 441 442// Max returns the approximate maximum recorded value. 443func (h *Histogram) Max() float64 { 444 return h.ValueAtQuantile(1.0) 445} 446 447// Min returns the approximate minimum recorded value. 448func (h *Histogram) Min() float64 { 449 return h.ValueAtQuantile(0.0) 450} 451 452// Mean returns the approximate arithmetic mean of the recorded values. 453func (h *Histogram) Mean() float64 { 454 return h.ApproxMean() 455} 456 457// Reset forgets all bins in the histogram (they remain allocated) 458func (h *Histogram) Reset() { 459 if h.useLocks { 460 h.mutex.Lock() 461 defer h.mutex.Unlock() 462 } 463 for i := 0; i < 256; i++ { 464 if h.lookup[i] != nil { 465 for j := range h.lookup[i] { 466 h.lookup[i][j] = 0 467 } 468 } 469 } 470 h.used = 0 471} 472 473// RecordIntScale records an integer scaler value, returning an error if the 474// value is out of range. 475func (h *Histogram) RecordIntScale(val int64, scale int) error { 476 return h.RecordIntScales(val, scale, 1) 477} 478 479// RecordValue records the given value, returning an error if the value is out 480// of range. 481func (h *Histogram) RecordValue(v float64) error { 482 return h.RecordValues(v, 1) 483} 484 485// RecordDuration records the given time.Duration in seconds, returning an error 486// if the value is out of range. 487func (h *Histogram) RecordDuration(v time.Duration) error { 488 return h.RecordIntScale(int64(v), -9) 489} 490 491// RecordCorrectedValue records the given value, correcting for stalls in the 492// recording process. This only works for processes which are recording values 493// at an expected interval (e.g., doing jitter analysis). Processes which are 494// recording ad-hoc values (e.g., latency for incoming requests) can't take 495// advantage of this. 496// CH Compat 497func (h *Histogram) RecordCorrectedValue(v, expectedInterval int64) error { 498 if err := h.RecordValue(float64(v)); err != nil { 499 return err 500 } 501 502 if expectedInterval <= 0 || v <= expectedInterval { 503 return nil 504 } 505 506 missingValue := v - expectedInterval 507 for missingValue >= expectedInterval { 508 if err := h.RecordValue(float64(missingValue)); err != nil { 509 return err 510 } 511 missingValue -= expectedInterval 512 } 513 514 return nil 515} 516 517// find where a new bin should go 518func (h *Histogram) internalFind(hb *bin) (bool, uint16) { 519 if h.used == 0 { 520 return false, 0 521 } 522 f2 := hb.newFastL2() 523 if h.lookup[f2.l1] != nil { 524 if idx := h.lookup[f2.l1][f2.l2]; idx != 0 { 525 return true, idx - 1 526 } 527 } 528 rv := -1 529 idx := uint16(0) 530 l := int(0) 531 r := int(h.used - 1) 532 for l < r { 533 check := (r + l) / 2 534 rv = h.bvs[check].compare(hb) 535 if rv == 0 { 536 l = check 537 r = check 538 } else if rv > 0 { 539 l = check + 1 540 } else { 541 r = check - 1 542 } 543 } 544 if rv != 0 { 545 rv = h.bvs[l].compare(hb) 546 } 547 idx = uint16(l) 548 if rv == 0 { 549 return true, idx 550 } 551 if rv < 0 { 552 return false, idx 553 } 554 idx++ 555 return false, idx 556} 557 558func (h *Histogram) insertBin(hb *bin, count int64) uint64 { 559 if h.useLocks { 560 h.mutex.Lock() 561 defer h.mutex.Unlock() 562 } 563 found, idx := h.internalFind(hb) 564 if !found { 565 if h.used == h.allocd { 566 new_bvs := make([]bin, h.allocd+defaultHistSize) 567 if idx > 0 { 568 copy(new_bvs[0:], h.bvs[0:idx]) 569 } 570 if idx < h.used { 571 copy(new_bvs[idx+1:], h.bvs[idx:]) 572 } 573 h.allocd = h.allocd + defaultHistSize 574 h.bvs = new_bvs 575 } else { 576 copy(h.bvs[idx+1:], h.bvs[idx:h.used]) 577 } 578 h.bvs[idx].val = hb.val 579 h.bvs[idx].exp = hb.exp 580 h.bvs[idx].count = uint64(count) 581 h.used++ 582 for i := idx; i < h.used; i++ { 583 f2 := h.bvs[i].newFastL2() 584 if h.lookup[f2.l1] == nil { 585 h.lookup[f2.l1] = make([]uint16, 256) 586 } 587 h.lookup[f2.l1][f2.l2] = uint16(i) + 1 588 } 589 return h.bvs[idx].count 590 } 591 var newval uint64 592 if count >= 0 { 593 newval = h.bvs[idx].count + uint64(count) 594 } else { 595 newval = h.bvs[idx].count - uint64(-count) 596 } 597 if newval < h.bvs[idx].count { //rolled 598 newval = ^uint64(0) 599 } 600 h.bvs[idx].count = newval 601 return newval - h.bvs[idx].count 602} 603 604// RecordIntScales records n occurrences of the given value, returning an error if 605// the value is out of range. 606func (h *Histogram) RecordIntScales(val int64, scale int, n int64) error { 607 sign := int64(1) 608 if val == 0 { 609 scale = 0 610 } else { 611 scale++ 612 if val < 0 { 613 val = 0 - val 614 sign = -1 615 } 616 if val < 10 { 617 val *= 10 618 scale -= 1 619 } 620 for val >= 100 { 621 val /= 10 622 scale++ 623 } 624 } 625 if scale < -128 { 626 val = 0 627 scale = 0 628 } else if scale > 127 { 629 val = 0xff 630 scale = 0 631 } 632 val *= sign 633 hb := bin{val: int8(val), exp: int8(scale), count: 0} 634 h.insertBin(&hb, n) 635 return nil 636} 637 638// RecordValues records n occurrences of the given value, returning an error if 639// the value is out of range. 640func (h *Histogram) RecordValues(v float64, n int64) error { 641 var hb bin 642 hb.setFromFloat64(v) 643 h.insertBin(&hb, n) 644 return nil 645} 646 647// Approximate mean 648func (h *Histogram) ApproxMean() float64 { 649 if h.useLocks { 650 h.mutex.RLock() 651 defer h.mutex.RUnlock() 652 } 653 divisor := 0.0 654 sum := 0.0 655 for i := uint16(0); i < h.used; i++ { 656 midpoint := h.bvs[i].midpoint() 657 cardinality := float64(h.bvs[i].count) 658 divisor += cardinality 659 sum += midpoint * cardinality 660 } 661 if divisor == 0.0 { 662 return math.NaN() 663 } 664 return sum / divisor 665} 666 667// Approximate sum 668func (h *Histogram) ApproxSum() float64 { 669 if h.useLocks { 670 h.mutex.RLock() 671 defer h.mutex.RUnlock() 672 } 673 sum := 0.0 674 for i := uint16(0); i < h.used; i++ { 675 midpoint := h.bvs[i].midpoint() 676 cardinality := float64(h.bvs[i].count) 677 sum += midpoint * cardinality 678 } 679 return sum 680} 681 682func (h *Histogram) ApproxQuantile(q_in []float64) ([]float64, error) { 683 if h.useLocks { 684 h.mutex.RLock() 685 defer h.mutex.RUnlock() 686 } 687 q_out := make([]float64, len(q_in)) 688 i_q, i_b := 0, uint16(0) 689 total_cnt, bin_width, bin_left, lower_cnt, upper_cnt := 0.0, 0.0, 0.0, 0.0, 0.0 690 if len(q_in) == 0 { 691 return q_out, nil 692 } 693 // Make sure the requested quantiles are in order 694 for i_q = 1; i_q < len(q_in); i_q++ { 695 if q_in[i_q-1] > q_in[i_q] { 696 return nil, errors.New("out of order") 697 } 698 } 699 // Add up the bins 700 for i_b = 0; i_b < h.used; i_b++ { 701 if !h.bvs[i_b].isNaN() { 702 total_cnt += float64(h.bvs[i_b].count) 703 } 704 } 705 if total_cnt == 0.0 { 706 return nil, errors.New("empty_histogram") 707 } 708 709 for i_q = 0; i_q < len(q_in); i_q++ { 710 if q_in[i_q] < 0.0 || q_in[i_q] > 1.0 { 711 return nil, errors.New("out of bound quantile") 712 } 713 q_out[i_q] = total_cnt * q_in[i_q] 714 } 715 716 for i_b = 0; i_b < h.used; i_b++ { 717 if h.bvs[i_b].isNaN() { 718 continue 719 } 720 bin_width = h.bvs[i_b].binWidth() 721 bin_left = h.bvs[i_b].left() 722 lower_cnt = upper_cnt 723 upper_cnt = lower_cnt + float64(h.bvs[i_b].count) 724 break 725 } 726 for i_q = 0; i_q < len(q_in); i_q++ { 727 for i_b < (h.used-1) && upper_cnt < q_out[i_q] { 728 i_b++ 729 bin_width = h.bvs[i_b].binWidth() 730 bin_left = h.bvs[i_b].left() 731 lower_cnt = upper_cnt 732 upper_cnt = lower_cnt + float64(h.bvs[i_b].count) 733 } 734 if lower_cnt == q_out[i_q] { 735 q_out[i_q] = bin_left 736 } else if upper_cnt == q_out[i_q] { 737 q_out[i_q] = bin_left + bin_width 738 } else { 739 if bin_width == 0 { 740 q_out[i_q] = bin_left 741 } else { 742 q_out[i_q] = bin_left + (q_out[i_q]-lower_cnt)/(upper_cnt-lower_cnt)*bin_width 743 } 744 } 745 } 746 return q_out, nil 747} 748 749// ValueAtQuantile returns the recorded value at the given quantile (0..1). 750func (h *Histogram) ValueAtQuantile(q float64) float64 { 751 if h.useLocks { 752 h.mutex.RLock() 753 defer h.mutex.RUnlock() 754 } 755 q_in := make([]float64, 1) 756 q_in[0] = q 757 q_out, err := h.ApproxQuantile(q_in) 758 if err == nil && len(q_out) == 1 { 759 return q_out[0] 760 } 761 return math.NaN() 762} 763 764// SignificantFigures returns the significant figures used to create the 765// histogram 766// CH Compat 767func (h *Histogram) SignificantFigures() int64 { 768 return 2 769} 770 771// Equals returns true if the two Histograms are equivalent, false if not. 772func (h *Histogram) Equals(other *Histogram) bool { 773 if h.useLocks { 774 h.mutex.RLock() 775 defer h.mutex.RUnlock() 776 } 777 if other.useLocks { 778 other.mutex.RLock() 779 defer other.mutex.RUnlock() 780 } 781 switch { 782 case 783 h.used != other.used: 784 return false 785 default: 786 for i := uint16(0); i < h.used; i++ { 787 if h.bvs[i].compare(&other.bvs[i]) != 0 { 788 return false 789 } 790 if h.bvs[i].count != other.bvs[i].count { 791 return false 792 } 793 } 794 } 795 return true 796} 797 798// Copy creates and returns an exact copy of a histogram. 799func (h *Histogram) Copy() *Histogram { 800 if h.useLocks { 801 h.mutex.Lock() 802 defer h.mutex.Unlock() 803 } 804 805 newhist := New() 806 newhist.allocd = h.allocd 807 newhist.used = h.used 808 newhist.useLocks = h.useLocks 809 810 newhist.bvs = []bin{} 811 for _, v := range h.bvs { 812 newhist.bvs = append(newhist.bvs, v) 813 } 814 815 for i, u := range h.lookup { 816 for _, v := range u { 817 newhist.lookup[i] = append(newhist.lookup[i], v) 818 } 819 } 820 821 return newhist 822} 823 824// FullReset resets a histogram to default empty values. 825func (h *Histogram) FullReset() { 826 if h.useLocks { 827 h.mutex.Lock() 828 defer h.mutex.Unlock() 829 } 830 831 h.allocd = defaultHistSize 832 h.bvs = make([]bin, defaultHistSize) 833 h.used = 0 834 h.lookup = [256][]uint16{} 835} 836 837// CopyAndReset creates and returns an exact copy of a histogram, 838// and resets it to default empty values. 839func (h *Histogram) CopyAndReset() *Histogram { 840 newhist := h.Copy() 841 h.FullReset() 842 return newhist 843} 844 845func (h *Histogram) DecStrings() []string { 846 if h.useLocks { 847 h.mutex.Lock() 848 defer h.mutex.Unlock() 849 } 850 out := make([]string, h.used) 851 for i, bin := range h.bvs[0:h.used] { 852 var buffer bytes.Buffer 853 buffer.WriteString("H[") 854 buffer.WriteString(fmt.Sprintf("%3.1e", bin.value())) 855 buffer.WriteString("]=") 856 buffer.WriteString(fmt.Sprintf("%v", bin.count)) 857 out[i] = buffer.String() 858 } 859 return out 860} 861 862// takes the output of DecStrings and deserializes it into a Bin struct slice 863func stringsToBin(strs []string) ([]bin, error) { 864 865 bins := make([]bin, len(strs)) 866 for i, str := range strs { 867 868 // H[0.0e+00]=1 869 870 // H[0.0e+00]= <1> 871 countString := strings.Split(str, "=")[1] 872 countInt, err := strconv.ParseInt(countString, 10, 64) 873 if err != nil { 874 return nil, err 875 } 876 877 // H[ <0.0> e+00]=1 878 valString := strings.Split(strings.Split(strings.Split(str, "=")[0], "e")[0], "[")[1] 879 valInt, err := strconv.ParseFloat(valString, 64) 880 if err != nil { 881 return nil, err 882 } 883 884 // H[0.0e <+00> ]=1 885 expString := strings.Split(strings.Split(strings.Split(str, "=")[0], "e")[1], "]")[0] 886 expInt, err := strconv.ParseInt(expString, 10, 8) 887 if err != nil { 888 return nil, err 889 } 890 bins[i] = *newBinRaw(int8(valInt*10), int8(expInt), uint64(countInt)) 891 } 892 893 return bins, nil 894} 895 896// UnmarshalJSON - histogram will come in a base64 encoded serialized form 897func (h *Histogram) UnmarshalJSON(b []byte) error { 898 var s string 899 if err := json.Unmarshal(b, &s); err != nil { 900 return err 901 } 902 data, err := base64.StdEncoding.DecodeString(s) 903 if err != nil { 904 return err 905 } 906 h, err = Deserialize(bytes.NewBuffer(data)) 907 return err 908} 909 910func (h *Histogram) MarshalJSON() ([]byte, error) { 911 buf := bytes.NewBuffer([]byte{}) 912 err := h.SerializeB64(buf) 913 if err != nil { 914 return buf.Bytes(), err 915 } 916 return json.Marshal(buf.String()) 917} 918