2837

Committed 30 Oct 2024 07:56AM UTC coverage: 38.267% (-22.8%) from 61.098%

Build # 2837

Build Type

push

buildkite

Committed by

web-flow

Commit Message

Merge pull request #16306 from MinaProtocol/dkijania/fix_promotion_to_gcr

Fix promotion job PUBLISH misuse

Run Details

7417 of 19382 relevant lines covered (38.27%)

298565.44 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

67.47

/src/lib/allocation_functor/table.ml

open Core_kernel

(** immutable, serializable statistics derived from allocation data *)
module Allocation_statistics = struct
  (* times represented in ms *)
  type quartiles = { q1 : float; q2 : float; q3 : float; q4 : float }
  [@@deriving yojson]

  let make_quartiles n = { q1 = n; q2 = n; q3 = n; q4 = n }

  let empty_quartiles = make_quartiles 0.0

  type t = { count : int; lifetimes : quartiles } [@@deriving yojson]

  let write_metrics { count; lifetimes } object_id =
    let open Mina_metrics in
    let open Mina_metrics.Object_lifetime_statistics in
    let { q1; q2; q3; q4 } = lifetimes in
    let q x = lifetime_quartile_ms ~name:object_id ~quartile:x in
    Gauge.set (live_count ~name:object_id) (Int.to_float count) ;
    Gauge.set (q `Q1) q1 ;
    Gauge.set (q `Q2) q2 ;
    Gauge.set (q `Q3) q3 ;
    Gauge.set (q `Q4) q4
end

(** mutable data for an object we track allocations of (one exists per object type) *)
module Allocation_data = struct
  (* stops being unique after 2^{30,62} values; perhaps we should use guids instead *)
  type allocation_id = int

  let initial_allocation_id = Int.min_value

  (* indexed queue data structure would be more effecient here, but keeping this simple for now *)
  type t =
    { allocation_times : (allocation_id * Time.t) Queue.t
    ; mutable next_allocation_id : allocation_id
    }

  let create () =
    { allocation_times = Queue.create ()
    ; next_allocation_id = initial_allocation_id
    }

  let register_allocation data =
    let id = data.next_allocation_id in
    Queue.enqueue data.allocation_times (id, Time.now ()) ;
    data.next_allocation_id <- data.next_allocation_id + 1 ;
    id

  (* currently O(n) wrt queue size *)
  let unregister_allocation data id =
    Queue.filter_inplace data.allocation_times ~f:(fun (id', _) -> id = id')

  let compute_statistics { allocation_times; _ } =
    let now = Time.now () in
    let count = Queue.length allocation_times in
    let lifetime_ms_of_time time = Time.Span.to_ms (Time.diff now time) in
    let get_lifetime_ms i =
      lifetime_ms_of_time (snd @@ Queue.get allocation_times i)
    in
    let mean_indices max_len =
      let m = max_len - 1 in
      if m mod 2 = 0 then [ m / 2 ] else [ m / 2; (m / 2) + 1 ]
    in
    let mean offset length =
      let indices =
        mean_indices length |> List.filter ~f:(fun x -> x < count)
      in
      let sum =
        List.fold_left indices ~init:0.0 ~f:(fun acc i ->
            acc +. get_lifetime_ms (count - 1 - (i + offset)) )
      in
      sum /. Int.to_float (List.length indices)
    in
    let lifetimes =
      match count with
      | 0 ->
          Allocation_statistics.empty_quartiles
      | 1 ->
          Allocation_statistics.make_quartiles (get_lifetime_ms 0)
      | _ ->
          let q1 = mean 0 (count / 2) in
          let q2 = mean 0 count in
          let q3_offset = if count mod 2 = 0 then 0 else 1 in
          let q3 = mean ((count / 2) + q3_offset) (count / 2) in
          let q4 = get_lifetime_ms 0 in
          Allocation_statistics.{ q1; q2; q3; q4 }
    in
    Allocation_statistics.{ count; lifetimes }

  let compute_statistics t =
    try compute_statistics t
    with _ ->
      Allocation_statistics.
        { count = 0; lifetimes = Allocation_statistics.make_quartiles 0. }

  let%test_module "Allocation_data unit tests" =
    ( module struct
      open Allocation_statistics

      module Float_compare = Float.Robust_compare.Make (struct
        let robust_comparison_tolerance = 0.04
      end)

      type robust_float = float [@@deriving sexp]

      let compare_robust_float = Float_compare.robustly_compare

      (* time_offsets passed in here should be ordered monotonically (to match real world behavior) *)
      let run_test time_offsets expected_quartiles =
        let now = Time.now () in
        (* ids do not need to be unique in this test *)
        let data =
          { allocation_times =
              Queue.of_list
              @@ List.map (List.rev time_offsets) ~f:(fun offset ->
                     (0, Time.sub now (Time.Span.of_ms offset)) )
          ; next_allocation_id = 0
          }
        in
        let stats = compute_statistics data in
        [%test_eq: int] stats.count (List.length time_offsets) ;
        [%test_eq: robust_float] stats.lifetimes.q1 expected_quartiles.q1 ;
        [%test_eq: robust_float] stats.lifetimes.q2 expected_quartiles.q2 ;
        [%test_eq: robust_float] stats.lifetimes.q3 expected_quartiles.q3 ;
        [%test_eq: robust_float] stats.lifetimes.q4 expected_quartiles.q4

      let%test_unit "quartiles of empty list" =
        run_test [] { q1 = 0.0; q2 = 0.0; q3 = 0.0; q4 = 0.0 }

      let%test_unit "quartiles of singleton list" =
        run_test [ 1.0 ] { q1 = 1.0; q2 = 1.0; q3 = 1.0; q4 = 1.0 }

      let%test_unit "quartiles of 2 element list" =
        run_test [ 1.0; 2.0 ] { q1 = 1.0; q2 = 1.5; q3 = 2.0; q4 = 2.0 }

      let%test_unit "quartiles of 3 element list" =
        run_test [ 1.0; 2.0; 3.0 ] { q1 = 1.0; q2 = 2.0; q3 = 3.0; q4 = 3.0 }

      let%test_unit "quartiles of even list (> 3)" =
        run_test
          [ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0 ]
          { q1 = 2.0; q2 = 3.5; q3 = 5.0; q4 = 6.0 }

      let%test_unit "quartiles of odd list with even split (> 3)" =
        run_test
          [ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0; 7.0 ]
          { q1 = 2.0; q2 = 4.0; q3 = 6.0; q4 = 7.0 }

      let%test_unit "quartiles of odd list with odd split (> 3)" =
        run_test
          [ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0; 7.0; 8.0; 9.0 ]
          { q1 = 2.5; q2 = 5.0; q3 = 7.5; q4 = 9.0 }
    end )
end

(** correlation of allocation data and derived statistics *)
module Allocation_info = struct
  type t = { statistics : Allocation_statistics.t; data : Allocation_data.t }
end

let table = String.Table.create ()

let capture object_id =
  let open Allocation_info in
  let info_opt = String.Table.find table object_id in
  let data_opt = Option.map info_opt ~f:(fun { data; _ } -> data) in
  let data =
    Lazy.(
      force
      @@ Option.value_map data_opt
           ~default:(lazy (Allocation_data.create ()))
           ~f:Lazy.return)
  in
  let allocation_id = Allocation_data.register_allocation data in
  let statistics = Allocation_data.compute_statistics data in
  String.Table.set table ~key:object_id ~data:{ data; statistics } ;
  Allocation_statistics.write_metrics statistics object_id ;
  Mina_metrics.(
    Counter.inc_one (Object_lifetime_statistics.allocated_count ~name:object_id)) ;
  allocation_id

(* release is currently O(n), where n = number of active allocations for this object type; this can be improved by implementing indexed queues (with decent random delete computational complexity) in ocaml *)
let release ~object_id ~allocation_id =
  let open Allocation_info in
  let info = String.Table.find_exn table object_id in
  Allocation_data.unregister_allocation info.data allocation_id ;
  let statistics = Allocation_data.compute_statistics info.data in
  String.Table.set table ~key:object_id ~data:{ info with statistics } ;
  Allocation_statistics.write_metrics statistics object_id ;
  Mina_metrics.(
    Counter.inc_one (Object_lifetime_statistics.collected_count ~name:object_id))

let attach_finalizer object_id obj =
  let allocation_id = capture object_id in
  Gc.Expert.add_finalizer_exn obj (fun _ -> release ~object_id ~allocation_id) ;
  obj

let dump () =
  let open Allocation_info in
  let entries =
    String.Table.to_alist table
    |> List.Assoc.map ~f:(fun { statistics; _ } ->
           Allocation_statistics.to_yojson statistics )
  in
  `Assoc entries

1	open Core_kernel	12✔
2
3	(** immutable, serializable statistics derived from allocation data *)
4	module Allocation_statistics = struct
5	(* times represented in ms *)
6	type quartiles = { q1 : float; q2 : float; q3 : float; q4 : float }	×
7	[@@deriving yojson]	×
8
9	let make_quartiles n = { q1 = n; q2 = n; q3 = n; q4 = n }	1,270✔
10
11	let empty_quartiles = make_quartiles 0.0	12✔
12
13	type t = { count : int; lifetimes : quartiles } [@@deriving yojson]	×
14
15	let write_metrics { count; lifetimes } object_id =
16	let open Mina_metrics in	5,190✔
17	let open Mina_metrics.Object_lifetime_statistics in
18	let { q1; q2; q3; q4 } = lifetimes in
19	let q x = lifetime_quartile_ms ~name:object_id ~quartile:x in	20,760✔
20	Gauge.set (live_count ~name:object_id) (Int.to_float count) ;	5,190✔
21	Gauge.set (q `Q1) q1 ;	5,190✔
22	Gauge.set (q `Q2) q2 ;	5,190✔
23	Gauge.set (q `Q3) q3 ;	5,190✔
24	Gauge.set (q `Q4) q4	5,190✔
25	end
26
27	(** mutable data for an object we track allocations of (one exists per object type) *)
28	module Allocation_data = struct
29	(* stops being unique after 2^{30,62} values; perhaps we should use guids instead *)
30	type allocation_id = int
31
32	let initial_allocation_id = Int.min_value
33
34	(* indexed queue data structure would be more effecient here, but keeping this simple for now *)
35	type t =
36	{ allocation_times : (allocation_id * Time.t) Queue.t
37	; mutable next_allocation_id : allocation_id
38	}
39
40	let create () =
41	{ allocation_times = Queue.create ()	10✔
42	; next_allocation_id = initial_allocation_id
43	}
44
45	let register_allocation data =
46	let id = data.next_allocation_id in	2,905✔
47	Queue.enqueue data.allocation_times (id, Time.now ()) ;	2,905✔
48	data.next_allocation_id <- data.next_allocation_id + 1 ;	2,905✔
49	id
50
51	(* currently O(n) wrt queue size *)
52	let unregister_allocation data id =
53	Queue.filter_inplace data.allocation_times ~f:(fun (id', _) -> id = id')	2,285✔
54
55	let compute_statistics { allocation_times; _ } =
56	let now = Time.now () in	5,190✔
57	let count = Queue.length allocation_times in	5,190✔
58	let lifetime_ms_of_time time = Time.Span.to_ms (Time.diff now time) in	5,190✔
59	let get_lifetime_ms i =
60	lifetime_ms_of_time (snd @@ Queue.get allocation_times i)	12,659✔
61	in
62	let mean_indices max_len =
63	let m = max_len - 1 in	6,741✔
64	if m mod 2 = 0 then [ m / 2 ] else [ m / 2; (m / 2) + 1 ]	2,413✔
65	in
66	let mean offset length =
67	let indices =	6,741✔
68	mean_indices length \|> List.filter ~f:(fun x -> x < count)	6,741✔
69	in
70	let sum =	6,741✔
71	List.fold_left indices ~init:0.0 ~f:(fun acc i ->
72	acc +. get_lifetime_ms (count - 1 - (i + offset)) )	9,154✔
73	in
74	sum /. Int.to_float (List.length indices)	6,741✔
75	in
76	let lifetimes =
77	match count with
78	\| 0 ->	1,685✔
79	Allocation_statistics.empty_quartiles
80	\| 1 ->	1,258✔
81	Allocation_statistics.make_quartiles (get_lifetime_ms 0)	1,258✔
82	\| _ ->	2,247✔
83	let q1 = mean 0 (count / 2) in
84	let q2 = mean 0 count in	2,247✔
85	let q3_offset = if count mod 2 = 0 then 0 else 1 in	1,026✔
86	let q3 = mean ((count / 2) + q3_offset) (count / 2) in
87	let q4 = get_lifetime_ms 0 in	2,247✔
88	Allocation_statistics.{ q1; q2; q3; q4 }	2,247✔
89	in
90	Allocation_statistics.{ count; lifetimes }
91
92	let compute_statistics t =
93	try compute_statistics t	5,190✔
94	with _ ->	×
95	Allocation_statistics.
96	{ count = 0; lifetimes = Allocation_statistics.make_quartiles 0. }	×
97
98	let%test_module "Allocation_data unit tests" =
99	( module struct
100	open Allocation_statistics
101
102	module Float_compare = Float.Robust_compare.Make (struct
103	let robust_comparison_tolerance = 0.04
104	end)
105
106	type robust_float = float [@@deriving sexp]	×
107
108	let compare_robust_float = Float_compare.robustly_compare
109
110	(* time_offsets passed in here should be ordered monotonically (to match real world behavior) *)
111	let run_test time_offsets expected_quartiles =
112	let now = Time.now () in	×
113	(* ids do not need to be unique in this test *)
114	let data =	×
115	{ allocation_times =
116	Queue.of_list	×
117	@@ List.map (List.rev time_offsets) ~f:(fun offset ->	×
118	(0, Time.sub now (Time.Span.of_ms offset)) )	×
119	; next_allocation_id = 0
120	}
121	in
122	let stats = compute_statistics data in
123	[%test_eq: int] stats.count (List.length time_offsets) ;	×
124	[%test_eq: robust_float] stats.lifetimes.q1 expected_quartiles.q1 ;	×
125	[%test_eq: robust_float] stats.lifetimes.q2 expected_quartiles.q2 ;	×
126	[%test_eq: robust_float] stats.lifetimes.q3 expected_quartiles.q3 ;	×
127	[%test_eq: robust_float] stats.lifetimes.q4 expected_quartiles.q4	×
128
129	let%test_unit "quartiles of empty list" =
130	run_test [] { q1 = 0.0; q2 = 0.0; q3 = 0.0; q4 = 0.0 }	×
131
132	let%test_unit "quartiles of singleton list" =
133	run_test [ 1.0 ] { q1 = 1.0; q2 = 1.0; q3 = 1.0; q4 = 1.0 }	×
134
135	let%test_unit "quartiles of 2 element list" =
136	run_test [ 1.0; 2.0 ] { q1 = 1.0; q2 = 1.5; q3 = 2.0; q4 = 2.0 }	×
137
138	let%test_unit "quartiles of 3 element list" =
139	run_test [ 1.0; 2.0; 3.0 ] { q1 = 1.0; q2 = 2.0; q3 = 3.0; q4 = 3.0 }	×
140
141	let%test_unit "quartiles of even list (> 3)" =
142	run_test	×
143	[ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0 ]
144	{ q1 = 2.0; q2 = 3.5; q3 = 5.0; q4 = 6.0 }
145
146	let%test_unit "quartiles of odd list with even split (> 3)" =
147	run_test	×
148	[ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0; 7.0 ]
149	{ q1 = 2.0; q2 = 4.0; q3 = 6.0; q4 = 7.0 }
150
151	let%test_unit "quartiles of odd list with odd split (> 3)" =
152	run_test	×
153	[ 1.0; 2.0; 3.0; 4.0; 5.0; 6.0; 7.0; 8.0; 9.0 ]
154	{ q1 = 2.5; q2 = 5.0; q3 = 7.5; q4 = 9.0 }
155	end )
156	end
157
158	(** correlation of allocation data and derived statistics *)
159	module Allocation_info = struct
160	type t = { statistics : Allocation_statistics.t; data : Allocation_data.t }
161	end
162
163	let table = String.Table.create ()	12✔
164
165	let capture object_id =
166	let open Allocation_info in	2,905✔
167	let info_opt = String.Table.find table object_id in
168	let data_opt = Option.map info_opt ~f:(fun { data; _ } -> data) in	2,895✔
169	let data =	2,905✔
170	Lazy.(
171	force	2,905✔
172	@@ Option.value_map data_opt	2,905✔
173	~default:(lazy (Allocation_data.create ()))	10✔
174	~f:Lazy.return)
175	in
176	let allocation_id = Allocation_data.register_allocation data in
177	let statistics = Allocation_data.compute_statistics data in	2,905✔
178	String.Table.set table ~key:object_id ~data:{ data; statistics } ;	2,905✔
179	Allocation_statistics.write_metrics statistics object_id ;	2,905✔
180	Mina_metrics.(	2,905✔
181	Counter.inc_one (Object_lifetime_statistics.allocated_count ~name:object_id)) ;	2,905✔
182	allocation_id
183
184	(* release is currently O(n), where n = number of active allocations for this object type; this can be improved by implementing indexed queues (with decent random delete computational complexity) in ocaml *)
185	let release ~object_id ~allocation_id =
186	let open Allocation_info in	2,285✔
187	let info = String.Table.find_exn table object_id in
188	Allocation_data.unregister_allocation info.data allocation_id ;	2,285✔
189	let statistics = Allocation_data.compute_statistics info.data in	2,285✔
190	String.Table.set table ~key:object_id ~data:{ info with statistics } ;	2,285✔
191	Allocation_statistics.write_metrics statistics object_id ;	2,285✔
192	Mina_metrics.(	2,285✔
193	Counter.inc_one (Object_lifetime_statistics.collected_count ~name:object_id))
194
195	let attach_finalizer object_id obj =
196	let allocation_id = capture object_id in	2,905✔
197	Gc.Expert.add_finalizer_exn obj (fun _ -> release ~object_id ~allocation_id) ;	2,285✔
198	obj	2,905✔
199
200	let dump () =
201	let open Allocation_info in	×
202	let entries =
203	String.Table.to_alist table	×
204	\|> List.Assoc.map ~f:(fun { statistics; _ } ->
205	Allocation_statistics.to_yojson statistics )	×
206	in
207	`Assoc entries	×

MinaProtocol / mina / 2837

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous