import math,logging,strutils,os type Bracket =object quantile: float64 count ,valueAt :int64 Snapshot =object lowestTrackableValue,highestTrackableValue,significantFigures:int64 counts :seq[int64] Histogram =ref object of RootObj lowestTrackableValue:int64 highestTrackableValue:int64 unitMagnitude:int64 significantFigures:int64 subBucketHalfCountMagnitude: int32 subBucketHalfCount:int32 subBucketMask:int64 subBucketCount:int32 bucketCount:int32 countsLen:int32 totalCount:int64 counts:seq[int64] type Iterator =ref object of Histogram bucketIdx, subBucketIdx:int32 countAtIdx, countToIdx, valueFromIdx:int64 highestEquivalentValue:int64 type rIterator=ref object of Iterator countAddedThisStep:int64 type pIterator=ref object of Iterator seenLastValue:bool ticksPerHalfDistance:int32 percentileToIteratorTo,percentile:float64 proc new(minValue,maxValue:int64,sigfigs:int):Iterator= if sigfigs<1 or sigfigs>5:echo "sigfigs must be [1,5] was",$sigfigs var largestValueWithSingleUnitResolution =2*math.pow(float64(10),float64(sigfigs)) var subBucketCountMagnitude = math.ceil(math.log2(largestValueWithSingleUnitResolution)) var subBucketHalfCountMagnitude = int(subBucketCountMagnitude) if subBucketHalfCountMagnitude < 1 : subBucketHalfCountMagnitude = 1 subBucketHalfCountMagnitude.dec() var unitMagnitude = math.floor(math.log2(float64(minValue))) if unitMagnitude < 0 : unitMagnitude = 0 var subBucketCount = math.pow(2, float64(subBucketHalfCountMagnitude)+1) var subBucketHalfCount = subBucketCount / 2 var subBucketMask = int(subBucketCount-1) shl unitMagnitude.int var smallestUntrackableValue = subBucketCount.int shl unitMagnitude.int var bucketsNeeded = 1 while smallestUntrackableValue < maxValue : smallestUntrackableValue=smallestUntrackableValue shl 1 bucketsNeeded.inc() var bucketCount = bucketsNeeded var countsLen = (bucketCount + 1) * (subBucketCount / 2).int result = Iterator( lowestTrackableValue:minValue, highestTrackableValue:maxValue, unitMagnitude:unitMagnitude.int64, significantFigures:sigfigs.int64, subBucketHalfCountMagnitude: subBucketHalfCountMagnitude.int32, subBucketHalfCount:subBucketHalfCount.int32, subBucketMask:subBucketMask.int32, subBucketCount:subBucketCount.int32, bucketCount:bucketCount.int32, countsLen:countsLen.int32, totalCount:0, counts: newSeq[int64](maxValue)) proc byteSize(h: Histogram): int =6*8 + 5*4 + len(h.counts)*8 proc totalCount(h: Histogram): int64 =h.totalCount proc countsIndex(h :Iterator, bucketIdx, subBucketIdx:int32):int32 = (bucketIdx + 1) shl h.subBucketHalfCountMagnitude + subBucketIdx - h.subBucketHalfCount proc bitLen(x: int64):int64 = result=0 var tmp=x while tmp >= 0x8000 : tmp =tmp shr 16 result += 16 if tmp >= 0x80 : tmp=tmp shr 8 result += 8 if tmp >= 0x8 : tmp =tmp shr 4 result += 4 if tmp >= 0x2 : tmp =tmp shr 2 result += 2 if tmp >= 0x1 : result.inc() proc getBucketIndex(h :Iterator,v: int64): int32 = int32(bitLen(v or h.subBucketMask) - h.unitMagnitude - h.subBucketHalfCountMagnitude+1) proc getSubBucketIdx(h :Iterator,v: int64, idx :int32):int32 = int32(v.uint shr uint(idx+h.unitMagnitude)) proc countsIndexFor(h :Iterator,v: int64):int32 = var bucketIdx = h.getBucketIndex(v) h.countsIndex(bucketIdx, h.getSubBucketIdx(v, bucketIdx)) proc recordValue(h : Iterator,v,n :int64):string = result=nil var idx=h.countsIndexFor(v) if idx<0 or h.countsLen <= idx: result= "value"& $v & "is too large to be recorded" h.counts[idx] += n h.totalCount += n proc newIterator(h :ptr Histogram) :Iterator = Iterator(subBucketIdx: -1) proc getCountAtIndex(h :Iterator,bucketIdx, subBucketIdx :int32):int64 = h.counts[h.countsIndex(bucketIdx, subBucketIdx)] proc valueFromIndex(h :Iterator,bucketIdx, subBucketIdx:int32):int64 =subBucketIdx shl (bucketIdx+h.unitMagnitude) proc lowestEquivalentValue(h :Iterator,v :int64) :int64= var bucketIdx = h.getBucketIndex(v) var subBucketIdx = h.getSubBucketIdx(v, bucketIdx) result= h.valueFromIndex(bucketIdx, subBucketIdx) proc sizeOfEquivalentValueRange(h :Iterator,v :int64): int64= var bucketIdx = h.getBucketIndex(v) var subBucketIdx = h.getSubBucketIdx(v, bucketIdx) var adjustedBucket = bucketIdx if subBucketIdx >= h.subBucketCount :adjustedBucket.inc() result = 1 shl (h.unitMagnitude+adjustedBucket) proc nextNonEquivalentValue(h:Iterator,v:int64): int64 =h.lowestEquivalentValue(v) + h.sizeOfEquivalentValueRange(v) proc highestEquivalentValue(h:Iterator,v:int64): int64 =h.nextNonEquivalentValue(v) - 1 proc next(i :var Iterator):bool = result= true if i.countToIdx >= i.totalCount : result=false i.subBucketIdx.inc() if i.subBucketIdx >= i.subBucketCount : i.subBucketIdx = i.subBucketHalfCount i.bucketIdx.inc() if i.bucketIdx >= i.bucketCount :result= false i.countAtIdx = i.getCountAtIndex(i.bucketIdx, i.subBucketIdx) i.countToIdx += i.countAtIdx i.valueFromIdx = i.valueFromIndex(i.bucketIdx, i.subBucketIdx) i.highestEquivalentValue = i.valueFromIdx proc valueAtQuantile(h:var Iterator,q: float64):int64= var qq= if q>100'f64 : 100'f64 else :q var total :int64 var countAtPercentile = qq/100*h.totalCount.float+0.5 while h.next(): total += h.countAtIdx if countAtPercentile<= total.float64 : result=h.valueFromIdx proc newrIterator(h :ptr Histogram): rIterator = rIterator(subBucketIdx: -1) proc newpIterator(h: ptr Histogram,ticksPerHalfDistance :int32): pIterator = new(pIterator) proc next(r :rIterator):bool = while r.next() : if r.countAtIdx != 0 : r.countAddedThisStep = r.countAtIdx result=true proc next(p :pIterator):bool = result= false if p.countToIdx >= p.totalCount: if p.seenLastValue : result= false p.seenLastValue = true p.percentile = 100 result= true if p.subBucketIdx == -1 and not p.next() : result= false var done = false while not done : var currentPercentile = (100.0 * float64(p.countToIdx)) / float64(p.totalCount) if p.countAtIdx != 0 and p.percentileToIteratorTo <= currentPercentile : p.percentile = p.percentileToIteratorTo var halfDistance = math.trunc(math.pow(2, math.trunc(math.log2(100.0/(100.0-p.percentileToIteratorTo)))+1)) var percentileReportingTicks = float64(p.ticksPerHalfDistance) * halfDistance p.percentileToIteratorTo += 100.0 / percentileReportingTicks result= true done = not p.next() result= true try: var latency :seq[int64]=newSeq[int64](0) for i in 0..120000: latency.add(i) var h = new(0, 12000, 5) for sample in latency : discard h.recordValue(sample,1) var quantile = h.valueAtQuantile(50) logging.debug("quantile:$1" % $quantile) except: logging.error("Could not send response: $1" % osErrorMsg(osLastError()))