traitgraph_algo/dijkstra/
performance_counters.rs

1use std::ops::{Add, AddAssign};
2
3/// Performance data collected by Dijkstra's algorithm.
4/// This trait allows to collect the performance data optionally,
5/// by providing a type that either collects it, or ignores it.
6pub trait DijkstraPerformanceData {
7    /// Increment the number of iterations of the main loop of Dijkstra's algorithm.
8    fn add_iteration(&mut self);
9
10    /// Increment the number of heap elements that already have a lower weight than what was stored in the heap.
11    /// These are wasted cycles because our heap does not support the `decrease_key` operation.
12    fn add_unnecessary_heap_element(&mut self);
13
14    /// Record the current heap size of Dijkstra's algorithm.
15    fn record_heap_size(&mut self, heap_size: usize);
16
17    /// Record the current distance array size of Dijkstra's algorithm.
18    fn record_distance_array_size(&mut self, distance_array_size: usize);
19
20    /// Finish an invocation of Dijkstra's algorithm.
21    /// Performs finalisation of recorded metrics that are local to single Dijkstra invocations.
22    fn finish_dijkstra(&mut self);
23
24    /// Get the number of iterations of the main loop of Dijkstra's algorithm.
25    fn iterations(&self) -> Option<u64>;
26
27    /// Get the number of unnecessary heap elements that were inserted during Dijkstra's algorithm.
28    fn unnecessary_heap_elements(&self) -> Option<u64>;
29
30    /// Get the maximum heap size encountered at any point during execution.
31    fn max_max_heap_size(&self) -> Option<usize>;
32
33    /// Get the maximum distance array size encountered at any point during execution.
34    fn max_max_distance_array_size(&self) -> Option<usize>;
35
36    /// Get the maximum heap size as average over all invocations of Dijkstra's algorithm.
37    fn average_max_heap_size(&self) -> Option<f64>;
38
39    /// Get the maximum distance array size as average over all invocations of Dijkstra's algorithm.
40    fn average_max_distance_array_size(&self) -> Option<f64>;
41}
42
43/// A simple performance counter for Dijkstra's algorithm, keeping all supported counts.
44#[derive(Default, Debug, Clone, Eq, PartialEq)]
45pub struct DijkstraPerformanceCounter {
46    /// The number of iterations of the main loop of Dijkstra's algorithm.
47    pub iterations: u64,
48    /// The number of unnecessary heap elements.
49    pub unnecessary_heap_elements: u64,
50    max_heap_size: usize,
51    max_distance_array_size: usize,
52    max_max_heap_size: usize,
53    max_max_distance_array_size: usize,
54    sum_max_heap_size: u128,
55    sum_max_distance_array_size: u128,
56    total_invocations: u64,
57}
58
59/// A performance counter for Dijkstra's algorithm that ignores all counts.
60#[derive(Default, Debug, Clone, Copy, Eq, PartialEq)]
61pub struct NoopDijkstraPerformanceCounter;
62
63impl DijkstraPerformanceData for DijkstraPerformanceCounter {
64    fn add_iteration(&mut self) {
65        self.iterations += 1;
66    }
67
68    fn add_unnecessary_heap_element(&mut self) {
69        self.unnecessary_heap_elements += 1;
70    }
71
72    fn record_heap_size(&mut self, heap_size: usize) {
73        self.max_heap_size = self.max_heap_size.max(heap_size);
74    }
75
76    fn record_distance_array_size(&mut self, distance_array_size: usize) {
77        self.max_distance_array_size = self.max_distance_array_size.max(distance_array_size);
78    }
79
80    fn finish_dijkstra(&mut self) {
81        self.max_max_heap_size = self.max_max_heap_size.max(self.max_heap_size);
82        self.max_max_distance_array_size = self
83            .max_max_distance_array_size
84            .max(self.max_distance_array_size);
85        self.sum_max_heap_size += self.max_heap_size as u128;
86        self.sum_max_distance_array_size += self.max_distance_array_size as u128;
87
88        self.max_heap_size = 0;
89        self.max_distance_array_size = 0;
90        self.total_invocations += 1;
91    }
92
93    fn iterations(&self) -> Option<u64> {
94        Some(self.iterations)
95    }
96
97    fn unnecessary_heap_elements(&self) -> Option<u64> {
98        Some(self.unnecessary_heap_elements)
99    }
100
101    fn max_max_heap_size(&self) -> Option<usize> {
102        Some(self.max_max_heap_size)
103    }
104
105    fn max_max_distance_array_size(&self) -> Option<usize> {
106        Some(self.max_max_distance_array_size)
107    }
108
109    fn average_max_heap_size(&self) -> Option<f64> {
110        Some(self.sum_max_heap_size as f64 / self.total_invocations as f64)
111    }
112
113    fn average_max_distance_array_size(&self) -> Option<f64> {
114        Some(self.sum_max_distance_array_size as f64 / self.total_invocations as f64)
115    }
116}
117
118impl DijkstraPerformanceData for NoopDijkstraPerformanceCounter {
119    fn add_iteration(&mut self) {}
120
121    fn add_unnecessary_heap_element(&mut self) {}
122
123    fn record_heap_size(&mut self, _heap_size: usize) {}
124
125    fn record_distance_array_size(&mut self, _distance_array_size: usize) {}
126
127    fn finish_dijkstra(&mut self) {}
128
129    fn iterations(&self) -> Option<u64> {
130        None
131    }
132
133    fn unnecessary_heap_elements(&self) -> Option<u64> {
134        None
135    }
136
137    fn max_max_heap_size(&self) -> Option<usize> {
138        None
139    }
140
141    fn max_max_distance_array_size(&self) -> Option<usize> {
142        None
143    }
144
145    fn average_max_heap_size(&self) -> Option<f64> {
146        None
147    }
148
149    fn average_max_distance_array_size(&self) -> Option<f64> {
150        None
151    }
152}
153
154impl Add for DijkstraPerformanceCounter {
155    type Output = Self;
156
157    fn add(self, rhs: Self) -> Self::Output {
158        Self {
159            iterations: self.iterations + rhs.iterations,
160            unnecessary_heap_elements: self.unnecessary_heap_elements
161                + rhs.unnecessary_heap_elements,
162            max_heap_size: self.max_heap_size.max(rhs.max_heap_size),
163            max_distance_array_size: self
164                .max_distance_array_size
165                .max(rhs.max_distance_array_size),
166            max_max_heap_size: self.max_max_heap_size.max(rhs.max_max_heap_size),
167            max_max_distance_array_size: self
168                .max_max_distance_array_size
169                .max(rhs.max_max_distance_array_size),
170            sum_max_heap_size: self.sum_max_heap_size + rhs.sum_max_heap_size,
171            sum_max_distance_array_size: self.sum_max_distance_array_size
172                + rhs.sum_max_distance_array_size,
173            total_invocations: self.total_invocations + rhs.total_invocations,
174        }
175    }
176}
177
178impl Add for NoopDijkstraPerformanceCounter {
179    type Output = Self;
180
181    fn add(self, _rhs: Self) -> Self::Output {
182        Self
183    }
184}
185
186impl AddAssign for DijkstraPerformanceCounter {
187    fn add_assign(&mut self, rhs: Self) {
188        // I trust that the compiler optimises this correctly
189        *self = self.clone() + rhs;
190    }
191}
192
193impl AddAssign for NoopDijkstraPerformanceCounter {
194    fn add_assign(&mut self, _rhs: Self) {
195        // do nothing
196    }
197}
traitgraph_algo/dijkstra/performance_counters.rs

traitgraph_algo/dijkstra/
performance_counters.rs
