tensor4all_core/dense_budget.rs
1//! Shared element-count budget for dense materialization in production paths.
2//!
3//! Production algorithms that must build a dense local object (an eigenproblem
4//! matrix, an embedded operator site, ...) check its size here before
5//! allocating. The unit is elements, not bytes: bytes = elements ×
6//! `size_of::<T>()`.
7
8use thiserror::Error;
9
10/// Default dense-element budget: `1 << 24` elements, i.e. 256 MiB per dense
11/// `Complex64` object.
12///
13/// The measured TreeTN GSE peak at `q_dim = 4096` (`q_dim² = 1 << 24`) is
14/// 1.9 GiB and 44 s on one machine, so this default admits that case and
15/// rejects `q_dim = 4097`. Callers with a tighter memory bound pass their own
16/// [`DenseElementBudget`] instead.
17pub const DEFAULT_MAX_DENSE_ELEMENTS: usize = 1 << 24;
18
19/// Element-count budget for one dense materialization.
20///
21/// A budget is checked against the element count of a dense object (or the
22/// total of several) before the allocation. Counts equal to the limit pass;
23/// only counts above it fail.
24///
25/// # Examples
26///
27/// ```
28/// use tensor4all_core::{DenseElementBudget, DEFAULT_MAX_DENSE_ELEMENTS};
29///
30/// assert_eq!(
31/// DenseElementBudget::default().max_elements(),
32/// DEFAULT_MAX_DENSE_ELEMENTS
33/// );
34/// assert_eq!(DenseElementBudget::unbounded().max_elements(), usize::MAX);
35/// ```
36#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
37pub struct DenseElementBudget {
38 max_elements: usize,
39}
40
41impl DenseElementBudget {
42 /// Create a budget that admits at most `max_elements` elements.
43 ///
44 /// `new(0)` admits only empty objects (an extent of `0` or no objects at
45 /// all).
46 pub const fn new(max_elements: usize) -> Self {
47 Self { max_elements }
48 }
49
50 /// Create a budget that admits every object whose element count fits in
51 /// `usize`.
52 pub const fn unbounded() -> Self {
53 Self::new(usize::MAX)
54 }
55
56 /// The maximum element count this budget admits.
57 pub const fn max_elements(self) -> usize {
58 self.max_elements
59 }
60
61 /// Element count of the dense object with `dims`, checked against the
62 /// budget.
63 ///
64 /// `dims` is the extent of each axis; an empty slice is a scalar (1
65 /// element) and any extent of `0` is an empty object (0 elements).
66 ///
67 /// # Errors
68 ///
69 /// Returns [`DenseBudgetError::Overflow`] when the element count does not
70 /// fit in `usize`, and [`DenseBudgetError::Exceeded`] when it is above
71 /// [`Self::max_elements`].
72 ///
73 /// # Examples
74 ///
75 /// ```
76 /// use tensor4all_core::{DenseBudgetError, DenseElementBudget};
77 ///
78 /// let budget = DenseElementBudget::new(4);
79 /// assert_eq!(budget.check_dims("density", &[2, 2]).unwrap(), 4);
80 /// assert_eq!(budget.check_dims("scalar", &[]).unwrap(), 1);
81 /// assert_eq!(budget.check_dims("empty", &[0, 9]).unwrap(), 0);
82 /// assert_eq!(
83 /// budget.check_dims("density", &[2, 3]),
84 /// Err(DenseBudgetError::Exceeded {
85 /// what: "density",
86 /// elements: 6,
87 /// max_elements: 4,
88 /// })
89 /// );
90 /// ```
91 pub fn check_dims(self, what: &'static str, dims: &[usize]) -> Result<usize, DenseBudgetError> {
92 self.check_total(what, std::iter::once(dims))
93 }
94
95 /// Total element count of several dense objects, checked against the
96 /// budget once.
97 ///
98 /// Use this when one operation allocates a list of dense objects whose sum,
99 /// not any single object, is the cost.
100 ///
101 /// # Errors
102 ///
103 /// Returns [`DenseBudgetError::Overflow`] when the total does not fit in
104 /// `usize`, and [`DenseBudgetError::Exceeded`] when it is above
105 /// [`Self::max_elements`].
106 ///
107 /// # Examples
108 ///
109 /// ```
110 /// use tensor4all_core::DenseElementBudget;
111 ///
112 /// let budget = DenseElementBudget::new(8);
113 /// let sites = [[1usize, 4, 1].as_slice(), [1, 4, 1].as_slice()];
114 /// assert_eq!(budget.check_total("mpo", sites).unwrap(), 8);
115 /// assert_eq!(
116 /// budget.check_total("mpo", std::iter::once(sites[0])).unwrap(),
117 /// 4
118 /// );
119 /// assert!(DenseElementBudget::new(7).check_total("mpo", sites).is_err());
120 /// ```
121 pub fn check_total<'a>(
122 self,
123 what: &'static str,
124 objects: impl IntoIterator<Item = &'a [usize]>,
125 ) -> Result<usize, DenseBudgetError> {
126 let mut elements = 0usize;
127 for dims in objects {
128 let count = element_count(what, dims)?;
129 elements = elements
130 .checked_add(count)
131 .ok_or(DenseBudgetError::Overflow { what })?;
132 }
133 if elements > self.max_elements {
134 return Err(DenseBudgetError::Exceeded {
135 what,
136 elements,
137 max_elements: self.max_elements,
138 });
139 }
140 Ok(elements)
141 }
142}
143
144impl Default for DenseElementBudget {
145 fn default() -> Self {
146 Self::new(DEFAULT_MAX_DENSE_ELEMENTS)
147 }
148}
149
150/// Element count of one dense object, checked against `usize`.
151///
152/// A zero extent wins over the product so that an empty object never reports
153/// an overflow.
154fn element_count(what: &'static str, dims: &[usize]) -> Result<usize, DenseBudgetError> {
155 if dims.contains(&0) {
156 return Ok(0);
157 }
158 dims.iter().try_fold(1usize, |acc, &dim| {
159 acc.checked_mul(dim)
160 .ok_or(DenseBudgetError::Overflow { what })
161 })
162}
163
164/// Error returned by a [`DenseElementBudget`] check.
165#[derive(Debug, Clone, PartialEq, Eq, Error)]
166#[non_exhaustive]
167pub enum DenseBudgetError {
168 /// The element count of `what` does not fit in `usize`.
169 #[error("{what}: dense element count overflows usize")]
170 Overflow {
171 /// The dense object or group that was checked.
172 what: &'static str,
173 },
174 /// The element count of `what` is above the configured budget.
175 #[error(
176 "{what}: dense materialization of {elements} elements exceeds the budget of {max_elements} elements"
177 )]
178 Exceeded {
179 /// The dense object or group that was checked.
180 what: &'static str,
181 /// The element count that was requested.
182 elements: usize,
183 /// The element count the budget admits.
184 max_elements: usize,
185 },
186}
187
188#[cfg(test)]
189mod tests;