Untitled

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()))