oxidd_rules_bdd/
recursor.rs

1use oxidd_core::util::{AllocResult, Borrowed, EdgeDropGuard};
2use oxidd_core::Manager;
3
4type UnaryOp<M, R> = fn(&M, R, Borrowed<<M as Manager>::Edge>) -> AllocResult<<M as Manager>::Edge>;
5
6type BinaryOp<M, R> = fn(
7    &M,
8    R,
9    Borrowed<<M as Manager>::Edge>,
10    Borrowed<<M as Manager>::Edge>,
11) -> AllocResult<<M as Manager>::Edge>;
12
13type TernaryOp<M, R> = fn(
14    &M,
15    R,
16    Borrowed<<M as Manager>::Edge>,
17    Borrowed<<M as Manager>::Edge>,
18    Borrowed<<M as Manager>::Edge>,
19) -> AllocResult<<M as Manager>::Edge>;
20
21type SubstOp<M, R> = fn(
22    &M,
23    R,
24    Borrowed<<M as Manager>::Edge>,
25    &[<M as Manager>::Edge],
26    u32,
27) -> AllocResult<<M as Manager>::Edge>;
28
29pub trait Recursor<M: Manager>: Copy {
30    fn unary<'a>(
31        self,
32        op: UnaryOp<M, Self>,
33        manager: &'a M,
34        a: Borrowed<M::Edge>,
35        b: Borrowed<M::Edge>,
36    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)>;
37
38    fn binary<'a>(
39        self,
40        op: BinaryOp<M, Self>,
41        manager: &'a M,
42        a: (Borrowed<M::Edge>, Borrowed<M::Edge>),
43        b: (Borrowed<M::Edge>, Borrowed<M::Edge>),
44    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)>;
45
46    #[allow(clippy::type_complexity)]
47    fn ternary<'a>(
48        self,
49        op: TernaryOp<M, Self>,
50        manager: &'a M,
51        a: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
52        b: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
53    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)>;
54
55    fn subst<'a>(
56        self,
57        op: SubstOp<M, Self>,
58        manager: &'a M,
59        a: (Borrowed<M::Edge>, &[M::Edge], u32),
60        b: (Borrowed<M::Edge>, &[M::Edge], u32),
61    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)>;
62
63    /// Returns true if the algorithm should switch to a sequential recursor
64    ///
65    /// With the current [`join()`][oxidd_core::WorkerPool::join]
66    /// implementations, we observe a significant performance overhead
67    /// compared to sequentially calling the functions. Therefore, it may
68    /// make sense to switch to the sequential version after, e.g., a
69    /// certain recursion depth.
70    fn should_switch_to_sequential(self) -> bool;
71}
72
73#[derive(Clone, Copy)]
74pub struct SequentialRecursor;
75
76impl<M: Manager> Recursor<M> for SequentialRecursor {
77    #[inline(always)]
78    fn unary<'a>(
79        self,
80        op: UnaryOp<M, Self>,
81        manager: &'a M,
82        a: Borrowed<M::Edge>,
83        b: Borrowed<M::Edge>,
84    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
85        let ra = EdgeDropGuard::new(manager, op(manager, self, a)?);
86        let rb = EdgeDropGuard::new(manager, op(manager, self, b)?);
87        Ok((ra, rb))
88    }
89
90    #[inline(always)]
91    fn binary<'a>(
92        self,
93        op: BinaryOp<M, Self>,
94        manager: &'a M,
95        a: (Borrowed<M::Edge>, Borrowed<M::Edge>),
96        b: (Borrowed<M::Edge>, Borrowed<M::Edge>),
97    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
98        let ra = EdgeDropGuard::new(manager, op(manager, self, a.0, a.1)?);
99        let rb = EdgeDropGuard::new(manager, op(manager, self, b.0, b.1)?);
100        Ok((ra, rb))
101    }
102
103    #[inline(always)]
104    fn ternary<'a>(
105        self,
106        op: TernaryOp<M, Self>,
107        manager: &'a M,
108        a: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
109        b: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
110    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
111        let ra = EdgeDropGuard::new(manager, op(manager, self, a.0, a.1, a.2)?);
112        let rb = EdgeDropGuard::new(manager, op(manager, self, b.0, b.1, b.2)?);
113        Ok((ra, rb))
114    }
115
116    #[inline(always)]
117    fn subst<'a>(
118        self,
119        op: SubstOp<M, Self>,
120        manager: &'a M,
121        a: (Borrowed<M::Edge>, &[M::Edge], u32),
122        b: (Borrowed<M::Edge>, &[M::Edge], u32),
123    ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
124        let ra = EdgeDropGuard::new(manager, op(manager, self, a.0, a.1, a.2)?);
125        let rb = EdgeDropGuard::new(manager, op(manager, self, b.0, b.1, a.2)?);
126        Ok((ra, rb))
127    }
128
129    #[inline(always)]
130    fn should_switch_to_sequential(self) -> bool {
131        false // returning true would make the algorithms diverge
132    }
133}
134
135#[cfg(feature = "multi-threading")]
136pub mod mt {
137    use super::*;
138    use oxidd_core::WorkerPool;
139
140    #[derive(Clone, Copy)]
141    pub struct ParallelRecursor {
142        remaining_depth: u32,
143    }
144
145    impl ParallelRecursor {
146        pub fn new<M: oxidd_core::HasWorkers>(manager: &M) -> Self {
147            Self {
148                remaining_depth: manager.workers().split_depth(),
149            }
150        }
151    }
152
153    impl<M> Recursor<M> for ParallelRecursor
154    where
155        M: Manager + oxidd_core::HasWorkers,
156        M::Edge: Send + Sync,
157    {
158        fn unary<'a>(
159            mut self,
160            op: UnaryOp<M, Self>,
161            manager: &'a M,
162            a: Borrowed<M::Edge>,
163            b: Borrowed<M::Edge>,
164        ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
165            self.remaining_depth -= 1;
166            let (ra, rb) = manager.workers().join(
167                move || {
168                    let edge = op(manager, self, a)?;
169                    Ok(EdgeDropGuard::new(manager, edge))
170                },
171                move || {
172                    let edge = op(manager, self, b)?;
173                    Ok(EdgeDropGuard::new(manager, edge))
174                },
175            );
176            Ok((ra?, rb?))
177        }
178
179        fn binary<'a>(
180            mut self,
181            op: BinaryOp<M, Self>,
182            manager: &'a M,
183            a: (Borrowed<M::Edge>, Borrowed<M::Edge>),
184            b: (Borrowed<M::Edge>, Borrowed<M::Edge>),
185        ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
186            self.remaining_depth -= 1;
187            let (ra, rb) = manager.workers().join(
188                move || {
189                    let edge = op(manager, self, a.0, a.1)?;
190                    Ok(EdgeDropGuard::new(manager, edge))
191                },
192                move || {
193                    let edge = op(manager, self, b.0, b.1)?;
194                    Ok(EdgeDropGuard::new(manager, edge))
195                },
196            );
197            Ok((ra?, rb?))
198        }
199
200        fn ternary<'a>(
201            mut self,
202            op: TernaryOp<M, Self>,
203            manager: &'a M,
204            a: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
205            b: (Borrowed<M::Edge>, Borrowed<M::Edge>, Borrowed<M::Edge>),
206        ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
207            self.remaining_depth -= 1;
208            let (ra, rb) = manager.workers().join(
209                move || {
210                    let edge = op(manager, self, a.0, a.1, a.2)?;
211                    Ok(EdgeDropGuard::new(manager, edge))
212                },
213                move || {
214                    let edge = op(manager, self, b.0, b.1, b.2)?;
215                    Ok(EdgeDropGuard::new(manager, edge))
216                },
217            );
218            Ok((ra?, rb?))
219        }
220
221        fn subst<'a>(
222            mut self,
223            op: SubstOp<M, Self>,
224            manager: &'a M,
225            a: (Borrowed<M::Edge>, &[M::Edge], u32),
226            b: (Borrowed<M::Edge>, &[M::Edge], u32),
227        ) -> AllocResult<(EdgeDropGuard<'a, M>, EdgeDropGuard<'a, M>)> {
228            self.remaining_depth -= 1;
229            let (ra, rb) = manager.workers().join(
230                move || {
231                    let edge = op(manager, self, a.0, a.1, a.2)?;
232                    Ok(EdgeDropGuard::new(manager, edge))
233                },
234                move || {
235                    let edge = op(manager, self, b.0, b.1, b.2)?;
236                    Ok(EdgeDropGuard::new(manager, edge))
237                },
238            );
239            Ok((ra?, rb?))
240        }
241
242        #[inline(always)]
243        fn should_switch_to_sequential(self) -> bool {
244            self.remaining_depth == 0
245        }
246    }
247}
oxidd_rules_bdd/recursor.rs

oxidd_rules_bdd/
recursor.rs
