Skip to main content

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;