packages feed

kenshou-measure-0.1.0.0: src/Kenshou/Measure/Histogram.hs

module Kenshou.Measure.Histogram
  ( HistogramConfig (..),
    defaultHistogramConfig,
    MutableHistogram,
    Histogram,
    newHistogram,
    recordValue,
    freeze,
    merge,
    valueAtQuantile,
    totalCount,
    minValue,
    maxValue,
    overflowCount,
    meanValue,
    equivalentRange,
    histogramConfig,
    histogramCounts,
    histogramSum,
    histogramArrayLength,
    histogramFromCounts,
  )
where

import Control.Monad (forM_)
import Control.Monad.ST (runST)
import Data.Bits
import Data.IORef
import Data.Primitive.PrimArray
import Data.Text (Text)
import Data.Text qualified as Text
import Data.Word (Word64)
import GHC.Exts (RealWorld)

data HistogramConfig = HistogramConfig
  { lowestDiscernible :: !Word64,
    highestTrackable :: !Word64,
    significantDigits :: !Int
  }
  deriving stock (Eq, Show)

defaultHistogramConfig :: HistogramConfig
defaultHistogramConfig = HistogramConfig 1 3_600_000_000_000 3

data Layout = Layout
  { unitMagnitude :: !Int,
    subBucketCountMagnitude :: !Int,
    subBucketCount :: !Int,
    subBucketHalfCount :: !Int,
    subBucketHalfCountMagnitude :: !Int,
    subBucketMask :: !Word64,
    arrayLength :: !Int
  }

data MutableHistogram = MutableHistogram
  { config :: !HistogramConfig,
    layout :: !Layout,
    counts :: !(MutablePrimArray RealWorld Word64),
    count :: !(IORef Word64),
    minimum :: !(IORef Word64),
    maximum :: !(IORef Word64),
    total :: !(IORef Word64),
    overflow :: !(IORef Word64)
  }

data Histogram = Histogram
  { config :: !HistogramConfig,
    layout :: !Layout,
    counts :: !(PrimArray Word64),
    count :: !Word64,
    minimum :: !Word64,
    maximum :: !Word64,
    total :: !Word64,
    overflow :: !Word64
  }

instance Eq Histogram where
  left == right =
    left.config == right.config
      && left.count == right.count
      && left.minimum == right.minimum
      && left.maximum == right.maximum
      && left.total == right.total
      && left.overflow == right.overflow
      && histogramCounts left == histogramCounts right

instance Show Histogram where
  show value =
    "Histogram {config="
      <> show value.config
      <> ", count="
      <> show value.count
      <> ", min="
      <> show value.minimum
      <> ", max="
      <> show value.maximum
      <> ", overflow="
      <> show value.overflow
      <> "}"

newHistogram :: HistogramConfig -> IO MutableHistogram
newHistogram config = case makeLayout config of
  Left message -> ioError (userError (Text.unpack message))
  Right layout -> do
    counts <- newPrimArray layout.arrayLength
    setPrimArray counts 0 layout.arrayLength 0
    MutableHistogram config layout counts
      <$> newIORef 0
      <*> newIORef maxBound
      <*> newIORef 0
      <*> newIORef 0
      <*> newIORef 0

recordValue :: MutableHistogram -> Word64 -> IO ()
recordValue histogram value = do
  modifyIORef' histogram.count (+ 1)
  modifyIORef' histogram.minimum (min value)
  modifyIORef' histogram.maximum (max value)
  modifyIORef' histogram.total (+ value)
  if value > histogram.config.highestTrackable
    then modifyIORef' histogram.overflow (+ 1)
    else do
      let index = countsIndex histogram.layout value
      previous <- readPrimArray histogram.counts index
      writePrimArray histogram.counts index (previous + 1)

freeze :: MutableHistogram -> IO Histogram
freeze mutable = do
  immutable <- freezePrimArray mutable.counts 0 mutable.layout.arrayLength
  count <- readIORef mutable.count
  observedMinimum <- readIORef mutable.minimum
  observedMaximum <- readIORef mutable.maximum
  total <- readIORef mutable.total
  overflow <- readIORef mutable.overflow
  pure $ Histogram mutable.config mutable.layout immutable count (if count == 0 then 0 else observedMinimum) observedMaximum total overflow

merge :: Histogram -> Histogram -> Either Text Histogram
merge left right
  | left.config /= right.config = Left "histogram configurations differ"
  | otherwise =
      Right
        Histogram
          { config = left.config,
            layout = left.layout,
            counts = runST do
              mutable <- newPrimArray left.layout.arrayLength
              forM_ [0 .. left.layout.arrayLength - 1] \index ->
                writePrimArray mutable index (indexPrimArray left.counts index + indexPrimArray right.counts index)
              unsafeFreezePrimArray mutable,
            count = left.count + right.count,
            minimum = case (left.count, right.count) of
              (0, _) -> right.minimum
              (_, 0) -> left.minimum
              _ -> min left.minimum right.minimum,
            maximum = max left.maximum right.maximum,
            total = left.total + right.total,
            overflow = left.overflow + right.overflow
          }

valueAtQuantile :: Histogram -> Double -> Word64
valueAtQuantile histogram quantile
  | histogram.count == 0 = 0
  | quantile >= 1 = histogram.maximum
  | target > histogram.count - histogram.overflow = histogram.maximum
  | otherwise = findIndex 0 0
  where
    bounded = max 0 (min 1 quantile)
    target = max 1 (ceiling (bounded * fromIntegral histogram.count))
    findIndex index cumulative
      | index >= histogram.layout.arrayLength = histogram.maximum
      | next >= target =
          let (_, highest) = equivalentRangeAtIndex histogram.layout index
           in max histogram.minimum (min histogram.maximum highest)
      | otherwise = findIndex (index + 1) next
      where
        next = cumulative + indexPrimArray histogram.counts index

totalCount :: Histogram -> Word64
totalCount = (.count)

minValue :: Histogram -> Word64
minValue = (.minimum)

maxValue :: Histogram -> Word64
maxValue = (.maximum)

overflowCount :: Histogram -> Word64
overflowCount = (.overflow)

meanValue :: Histogram -> Double
meanValue histogram
  | histogram.count == 0 = 0
  | otherwise = fromIntegral histogram.total / fromIntegral histogram.count

equivalentRange :: HistogramConfig -> Word64 -> Either Text (Word64, Word64)
equivalentRange config value = do
  layout <- makeLayout config
  pure (equivalentRangeAtIndex layout (countsIndex layout (min value config.highestTrackable)))

histogramConfig :: Histogram -> HistogramConfig
histogramConfig = (.config)

histogramCounts :: Histogram -> [Word64]
histogramCounts histogram = [indexPrimArray histogram.counts index | index <- [0 .. histogram.layout.arrayLength - 1]]

histogramSum :: Histogram -> Word64
histogramSum = (.total)

histogramArrayLength :: HistogramConfig -> Either Text Int
histogramArrayLength config = (.arrayLength) <$> makeLayout config

histogramFromCounts :: HistogramConfig -> [Word64] -> Word64 -> Word64 -> Word64 -> Word64 -> Word64 -> Either Text Histogram
histogramFromCounts config values count observedMinimum observedMaximum total overflow = do
  layout <- makeLayout config
  if length values /= layout.arrayLength
    then Left "histogram count array has the wrong length"
    else
      pure
        Histogram
          { config,
            layout,
            counts = primArrayFromList values,
            count,
            minimum = if count == 0 then 0 else observedMinimum,
            maximum = observedMaximum,
            total,
            overflow
          }

makeLayout :: HistogramConfig -> Either Text Layout
makeLayout config
  | config.lowestDiscernible == 0 = Left "lowestDiscernible must be positive"
  | config.highestTrackable < config.lowestDiscernible = Left "highestTrackable must not be below lowestDiscernible"
  | config.significantDigits < 1 || config.significantDigits > 5 = Left "significantDigits must be between 1 and 5"
  | otherwise = Right Layout {unitMagnitude, subBucketCountMagnitude, subBucketCount, subBucketHalfCount, subBucketHalfCountMagnitude, subBucketMask, arrayLength}
  where
    unitMagnitude = integerLog2 config.lowestDiscernible
    required = 2 * (10 ^ config.significantDigits)
    subBucketCountMagnitude = ceilingLog2 required
    subBucketCount = 1 `shiftL` subBucketCountMagnitude
    subBucketHalfCount = subBucketCount `div` 2
    subBucketHalfCountMagnitude = subBucketCountMagnitude - 1
    subBucketMask = fromIntegral (subBucketCount - 1) `shiftL` unitMagnitude
    initial = fromIntegral subBucketCount `shiftL` unitMagnitude :: Word64
    bucketCount = length (takeWhile (<= config.highestTrackable) (iterate (`shiftL` 1) initial)) + 1
    arrayLength = (bucketCount + 1) * subBucketHalfCount

countsIndex :: Layout -> Word64 -> Int
countsIndex layout value =
  ((bucketIndex + 1) `shiftL` layout.subBucketHalfCountMagnitude)
    + (subBucketIndex - layout.subBucketHalfCount)
  where
    bucketIndex = (64 - layout.unitMagnitude - layout.subBucketCountMagnitude) - countLeadingZeros (value .|. layout.subBucketMask)
    subBucketIndex = fromIntegral (value `shiftR` (bucketIndex + layout.unitMagnitude))

equivalentRangeAtIndex :: Layout -> Int -> (Word64, Word64)
equivalentRangeAtIndex layout index = (lowest, lowest + rangeSize - 1)
  where
    initialBucket = (index `shiftR` layout.subBucketHalfCountMagnitude) - 1
    initialSub = (index .&. (layout.subBucketHalfCount - 1)) + layout.subBucketHalfCount
    (bucket, subBucket) = if initialBucket < 0 then (0, initialSub - layout.subBucketHalfCount) else (initialBucket, initialSub)
    lowest = fromIntegral subBucket `shiftL` (bucket + layout.unitMagnitude)
    rangeSize = 1 `shiftL` (bucket + layout.unitMagnitude)

integerLog2 :: Word64 -> Int
integerLog2 value = finiteBitSize value - 1 - countLeadingZeros value

ceilingLog2 :: Int -> Int
ceilingLog2 value = go 0 1
  where
    go magnitude power | power >= value = magnitude | otherwise = go (magnitude + 1) (power * 2)