<commit_before>(**
 * Copyright (c) 2015, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the "hack" directory of this source tree.
 *
 *)

(**
 * The Measure module is primarily useful for debugging. It's particularly
 * useful for gathering stats about something that happens a lot. Let's say you
 * have some code like this
 *
 *   let number_bunnies = count_bunnies () in
 *
 * If you want to debug how many bunnies are being counted, you could do
 * something like
 *
 *   let number_bunnies = count_bunnies () in
 *   Utils.prerr_endlinef "Num bunnies: %d" number_bunnies;
 *
 * but what if this code is called 1000 times? Then you end up with log spew.
 * Using the Measure module helps with this. You can now do
 *
 *   let number_bunnies = count_bunnies () in
 *   Measure.sample "num_bunnies" number_bunnies;
 *
 * and then later you do
 *
 *   Measure.print_stats ();
 *
 * which will print the number of samples, the total, the average, the
 * variance, the max and the min.
 *
 * Measure can keep track of the distribution of measurements if you give it a
 * bucket size. Before we collect our measurements, call
 *
 *   Measure.track_distribution "num_bunnies" ~bucket_size:10 =
 *   ...do logging
 *   Measure.print_distribution ();
 *
 * And this will print how many samples fall in the 0-9 bucket, how many fall
 * into the 10-19 bucket, etc
 *
 * A common use case is timing, and there's an easy helper method. Let's say we
 * wanted to see how long our code takes
 *
 *   let number_bunnies = Measure.time "count_bunnies_time" (fun () ->
 *     count_bunnies ()
 *   ) in
 *
 * now when we call print_stats we'll see how fast count_bunnies is and how
 * much total time we spend counting bunnies.
 *
 * Measurements are stored in a stateful way in a record. You can either use a
 * global record or a local record.
 *
 * Using a global record:
 *   Measure.sample "num_bunnies" number_bunnies;
 *   Measure.print_stats ();
 *
 * You can push and pop the global record. This is useful if you want to reset
 * some counters without throwing away that data
 *
 *   Measure.push_global ();
 *   ...measure stuff
 *   let record = Measure.pop_global () in
 *   Measure.print_stats ~record ();
 *
 * Using a local record:
 *   let record = Measure.create () in
 *   Measure.sample ~record "num_bunnies" number_bunnies;
 *   Measure.print_stats ~record ();
 *
 * A record does not store the individual measurements, just the aggregate
 * stats, which are updated online. Records can be serialized in order to be
 * sent across pipes.
 *)

module List = Hh_core.List
module FloatMap = MyMap.Make(struct type t = float let compare = compare end)

type distribution = {
  bucket_size: float;
  buckets: float FloatMap.t;
}

type record_entry = {
  count: float;
  mean: float;
  variance_sum: float;
  max: float;
  min: float;
  distribution: distribution option;
}
type record_data = record_entry SMap.t
type record = record_data ref

(* Creates a new empty record *)
let create () = ref SMap.empty

let global: (record list) ref = ref [create ()]
let push_global () =
  global := (create ()) :: (!global)
let pop_global () =
  match !global with
  | ret::globals ->
      global := globals;
      ret
  | _ -> failwith "Measure.pop_global called with empty stack"


let serialize record = !record
let deserialize data = ref data

let new_entry = {
  count = 0.0;
  mean = 0.0;
  variance_sum = 0.0;
  max = min_float;
  min = max_float;
  distribution = None;
}

let new_distribution ~bucket_size = Some {
  bucket_size;
  buckets = FloatMap.empty;
}

let get_record = function
  | Some record -> record
  | None -> (match List.hd (!global) with
      | Some record -> record
      | None ->
          failwith ("No global record available! " ^
            "Did you forget to call Measure.push_global?"))


(* Measure can track how the values are distributed by creating buckets and
 * keeping track of how many samples fall into each buckets. It will not track
 * distribution by default, so call this function to turn it on *)
let track_distribution ?record name ~bucket_size =
  let record = get_record record in
  let entry = match SMap.get name (!record) with
  | None -> new_entry
  | Some entry -> entry in
  let entry = { entry with distribution = new_distribution ~bucket_size; } in
  record := SMap.add name entry (!record)

let round_down ~bucket_size value =
  bucket_size *. (floor (value /. bucket_size))

let update_distribution ~weight value = function
  | None -> None
  | Some { bucket_size; buckets } ->
      let bucket = round_down ~bucket_size value in
      let bucket_count = match FloatMap.get bucket buckets with
      | None -> weight
      | Some count -> count +. weight in
      let buckets = FloatMap.add bucket bucket_count buckets in
      Some { bucket_size; buckets; }

let sample ?record ?(weight=1.0) name value =
  let record = get_record record in
  let {
    count = old_count;
    mean = old_mean;
    variance_sum;
    max;
    min;
    distribution;
  } = match SMap.get name (!record) with
    | None -> new_entry
    | Some entry -> entry in

  (* Add 1 * weight to the count *)
  let count = old_count +. weight in
  let mean = old_mean +. weight *. (value -. old_mean) /. count in
  (* Knuth's online variance approximation algorithm, updated for weights.
   * Weighted version from http://people.ds.cam.ac.uk/fanf2/hermes/doc/antiforgery/stats.pdf *)
  let variance_sum = variance_sum +. weight *. (value -. old_mean) *. (value -. mean) in

  let max = Pervasives.max max value in
  let min = Pervasives.min min value in

  let distribution = update_distribution ~weight value distribution in

  let entry = { count; mean; variance_sum; max; min; distribution; } in
  record := SMap.add name entry (!record)

let merge_entries name from into = match (from, into) with
  | None, into -> into
  | from, None -> from
  | Some from, Some into ->
      let count = from.count +. into.count in

      (* Using this algorithm to combine the variance sums
       * https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Parallel_algorithm
       *)
      (* d = meanB - meanA *)
      let delta = from.mean -. into.mean in
      (* mean = meanA + delta * (countB/count) *)
      let mean = into.mean +. (delta *. from.count /. count) in
      (* VarSum = VarSumA + VarSumB + delta * delta * countA * countB / count *)
      let variance_sum = from.variance_sum +. into.variance_sum +.
        delta *. delta *. into.count *. from.count /. count in

      let max = Pervasives.max from.max into.max in
      let min = Pervasives.min from.min into.min in

      let distribution = match (from.distribution, into.distribution) with
      | None, into -> into
      | from, None -> from
      | Some { bucket_size = from; _; }, Some { bucket_size = into; _; }
      when from <> into -> Printf.kprintf failwith
          "Merging buckets for %s failed: bucket sizes %f, %f"
          name from into
      | Some { bucket_size; buckets = from; }, Some { buckets = into; _; } ->
          let buckets = FloatMap.merge (fun _bucket from_count into_count ->
            match (from_count, into_count) with
            | None, into -> into
            | from, None -> from
            | Some from_count, Some into_count -> Some (from_count +. into_count))<commit_msg>Fix merging two empty distributions in measure.ml<commit_after>(**
 * Copyright (c) 2015, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the "hack" directory of this source tree.
 *
 *)

(**
 * The Measure module is primarily useful for debugging. It's particularly
 * useful for gathering stats about something that happens a lot. Let's say you
 * have some code like this
 *
 *   let number_bunnies = count_bunnies () in
 *
 * If you want to debug how many bunnies are being counted, you could do
 * something like
 *
 *   let number_bunnies = count_bunnies () in
 *   Utils.prerr_endlinef "Num bunnies: %d" number_bunnies;
 *
 * but what if this code is called 1000 times? Then you end up with log spew.
 * Using the Measure module helps with this. You can now do
 *
 *   let number_bunnies = count_bunnies () in
 *   Measure.sample "num_bunnies" number_bunnies;
 *
 * and then later you do
 *
 *   Measure.print_stats ();
 *
 * which will print the number of samples, the total, the average, the
 * variance, the max and the min.
 *
 * Measure can keep track of the distribution of measurements if you give it a
 * bucket size. Before we collect our measurements, call
 *
 *   Measure.track_distribution "num_bunnies" ~bucket_size:10 =
 *   ...do logging
 *   Measure.print_distribution ();
 *
 * And this will print how many samples fall in the 0-9 bucket, how many fall
 * into the 10-19 bucket, etc
 *
 * A common use case is timing, and there's an easy helper method. Let's say we
 * wanted to see how long our code takes
 *
 *   let number_bunnies = Measure.time "count_bunnies_time" (fun () ->
 *     count_bunnies ()
 *   ) in
 *
 * now when we call print_stats we'll see how fast count_bunnies is and how
 * much total time we spend counting bunnies.
 *
 * Measurements are stored in a stateful way in a record. You can either use a
 * global record or a local record.
 *
 * Using a global record:
 *   Measure.sample "num_bunnies" number_bunnies;
 *   Measure.print_stats ();
 *
 * You can push and pop the global record. This is useful if you want to reset
 * some counters without throwing away that data
 *
 *   Measure.push_global ();
 *   ...measure stuff
 *   let record = Measure.pop_global () in
 *   Measure.print_stats ~record ();
 *
 * Using a local record:
 *   let record = Measure.create () in
 *   Measure.sample ~record "num_bunnies" number_bunnies;
 *   Measure.print_stats ~record ();
 *
 * A record does not store the individual measurements, just the aggregate
 * stats, which are updated online. Records can be serialized in order to be
 * sent across pipes.
 *)

module List = Hh_core.List
module FloatMap = MyMap.Make(struct type t = float let compare = compare end)

type distribution = {
  bucket_size: float;
  buckets: float FloatMap.t;
}

type record_entry = {
  count: float;
  mean: float;
  variance_sum: float;
  max: float;
  min: float;
  distribution: distribution option;
}
type record_data = record_entry SMap.t
type record = record_data ref

(* Creates a new empty record *)
let create () = ref SMap.empty

let global: (record list) ref = ref [create ()]
let push_global () =
  global := (create ()) :: (!global)
let pop_global () =
  match !global with
  | ret::globals ->
      global := globals;
      ret
  | _ -> failwith "Measure.pop_global called with empty stack"


let serialize record = !record
let deserialize data = ref data

let new_entry = {
  count = 0.0;
  mean = 0.0;
  variance_sum = 0.0;
  max = min_float;
  min = max_float;
  distribution = None;
}

let new_distribution ~bucket_size = Some {
  bucket_size;
  buckets = FloatMap.empty;
}

let get_record = function
  | Some record -> record
  | None -> (match List.hd (!global) with
      | Some record -> record
      | None ->
          failwith ("No global record available! " ^
            "Did you forget to call Measure.push_global?"))


(* Measure can track how the values are distributed by creating buckets and
 * keeping track of how many samples fall into each buckets. It will not track
 * distribution by default, so call this function to turn it on *)
let track_distribution ?record name ~bucket_size =
  let record = get_record record in
  let entry = match SMap.get name (!record) with
  | None -> new_entry
  | Some entry -> entry in
  let entry = { entry with distribution = new_distribution ~bucket_size; } in
  record := SMap.add name entry (!record)

let round_down ~bucket_size value =
  bucket_size *. (floor (value /. bucket_size))

let update_distribution ~weight value = function
  | None -> None
  | Some { bucket_size; buckets } ->
      let bucket = round_down ~bucket_size value in
      let bucket_count = match FloatMap.get bucket buckets with
      | None -> weight
      | Some count -> count +. weight in
      let buckets = FloatMap.add bucket bucket_count buckets in
      Some { bucket_size; buckets; }

let sample ?record ?(weight=1.0) name value =
  let record = get_record record in
  let {
    count = old_count;
    mean = old_mean;
    variance_sum;
    max;
    min;
    distribution;
  } = match SMap.get name (!record) with
    | None -> new_entry
    | Some entry -> entry in

  (* Add 1 * weight to the count *)
  let count = old_count +. weight in
  let mean = old_mean +. weight *. (value -. old_mean) /. count in
  (* Knuth's online variance approximation algorithm, updated for weights.
   * Weighted version from http://people.ds.cam.ac.uk/fanf2/hermes/doc/antiforgery/stats.pdf *)
  let variance_sum = variance_sum +. weight *. (value -. old_mean) *. (value -. mean) in

  let max = Pervasives.max max value in
  let min = Pervasives.min min value in

  let distribution = update_distribution ~weight value distribution in

  let entry = { count; mean; variance_sum; max; min; distribution; } in
  record := SMap.add name entry (!record)

let merge_entries name from into = match (from, into) with
  | None, into -> into
  | from, None -> from
  | Some from, into when from.count = 0. -> into
  | from, Some into when into.count = 0. -> from
  | Some from, Some into ->
      let count = from.count +. into.count in

      (* Using this algorithm to combine the variance sums
       * https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Parallel_algorithm
       *)
      (* d = meanB - meanA *)
      let delta = from.mean -. into.mean in
      (* mean = meanA + delta * (countB/count) *)
      let mean = into.mean +. (delta *. from.count /. count) in
      (* VarSum = VarSumA + VarSumB + delta * delta * countA * countB / count *)
      let variance_sum = from.variance_sum +. into.variance_sum +.
        delta *. delta *. into.count *. from.count /. count in

      let max = Pervasives.max from.max into.max in
      let min = Pervasives.min from.min into.min in

      let distribution = match (from.distribution, into.distribution) with
      | None, into -> into
      | from, None -> from
      | Some { bucket_size = from; _; }, Some { bucket_size = into; _; }
      when from <> into -> Printf.kprintf failwith
          "Merging buckets for %s failed: bucket sizes %f, %f"
          name from into
      | Some { bucket_size; buckets = from; }, Some { buckets = into; _; } ->
          let buckets = FloatMap.merge (fun _bucket from_count into_count ->
            match (from_count, into_count) with
            | None, into -> into
            | from, None -> from
            | Some from_count, Some into_count -> Some (from_count +. into_count))
{'fraction_non_alphanumeric': 0.09661221210498125, 'fraction_numerical': 0.003615425816818425, 'mean_word_length': 2.9432418162618794, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 59, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6243648', 'n_tokens_mistral': 4586, 'n_tokens_neox': 4408, 'n_words': 1727}