Run setup for every iteration of the benchmark
1//! This file includes benchmarks for very large, pseudo-randomly generated trees
2use criterion::{criterion_group, criterion_main, Criterion};
3use rand::prelude::*;
4use rand_chacha::ChaCha8Rng;
5use taffy::prelude::*;
6use taffy::randomizable::Randomizeable;
7use taffy::style::Style;
8
9/// Build a random leaf node
10fn build_random_leaf(taffy: &mut Taffy, rng: &mut ChaCha8Rng) -> Node {
11 taffy.new_node(Style::random(rng), &[]).unwrap()
12}
13
14/// A tree with many children that have shallow depth
15fn build_flat_hierarchy(taffy: &mut Taffy, total_node_count: u32) -> Node {
16 let mut rng = ChaCha8Rng::seed_from_u64(12345);
17 let mut children = Vec::new();
18 let mut node_count = 0;
19
20 while node_count < total_node_count {
21 let sub_children_count = rng.gen_range(1..=4);
22 let sub_children: Vec<Node> = (0..sub_children_count).map(|_| build_random_leaf(taffy, &mut rng)).collect();
23 let node = taffy.new_node(Style::random(&mut rng), &sub_children).unwrap();
24
25 children.push(node);
26 node_count += 1 + sub_children_count;
27 }
28
29 taffy.new_node(Style { ..Default::default() }, children.as_slice()).unwrap()
30}
31
32/// A helper function to recursively construct a deep tree
33fn build_deep_tree(
34 taffy: &mut Taffy,
35 max_nodes: u32,
36 branching_factor: u32,
37 create_leaf_node: &mut impl FnMut(&mut Taffy) -> Node,
38 create_flex_node: &mut impl FnMut(&mut Taffy, Vec<Node>) -> Node,
39) -> Vec<Node> {
40 if max_nodes <= branching_factor {
41 // Build leaf nodes
42 return (0..max_nodes).map(|_| create_leaf_node(taffy)).collect();
43 }
44
45 // Add another layer to the tree
46 // Each child gets an equal amount of the remaining nodes
47 (0..branching_factor)
48 .map(|_| {
49 let max_nodes = (max_nodes - branching_factor) / branching_factor;
50 let sub_children = build_deep_tree(taffy, max_nodes, branching_factor, create_leaf_node, create_flex_node);
51 create_flex_node(taffy, sub_children)
52 })
53 .collect()
54}
55
56/// A tree with a higher depth for a more realistic scenario
57fn build_deep_hierarchy(taffy: &mut Taffy, node_count: u32, branching_factor: u32) -> Node {
58 let mut rng = ChaCha8Rng::seed_from_u64(12345);
59 let mut build_leaf_node = |taffy: &mut Taffy| build_random_leaf(taffy, &mut rng);
60 let mut rng = ChaCha8Rng::seed_from_u64(12345);
61 let mut build_flex_node = |taffy: &mut Taffy, children: Vec<Node>| {
62 taffy.new_node(Style::random(&mut rng), &children).unwrap()
63 };
64
65 let tree = build_deep_tree(taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
66
67 taffy.new_node(Style { ..Default::default() }, &tree).unwrap()
68}
69
70/// A deep tree that matches the shape and styling that yoga use on their benchmarks
71fn build_yoga_deep_hierarchy(taffy: &mut Taffy, node_count: u32, branching_factor: u32) -> Node {
72 let style = Style {
73 size: Size { width: Dimension::Points(10.0), height: Dimension::Points(10.0) },
74 flex_grow: 1.0,
75 ..Default::default()
76 };
77 let mut build_leaf_node = |taffy: &mut Taffy| taffy.new_node(style.clone(), &[]).unwrap();
78 let mut build_flex_node =
79 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_node(style.clone(), &children).unwrap();
80
81 let tree = build_deep_tree(taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
82 let root = taffy.new_node(Style { ..Default::default() }, &tree).unwrap();
83
84 root
85}
86
87fn taffy_benchmarks(c: &mut Criterion) {
88 let mut group = c.benchmark_group("yoga benchmarks");
89 group.sample_size(10);
90
91 group.bench_function("10 nodes", |b| {
92 b.iter_batched(
93 || {
94 let mut taffy = Taffy::new();
95 let root = build_yoga_deep_hierarchy(&mut taffy, 10, 10);
96 (taffy, root)
97 },
98 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
99 criterion::BatchSize::SmallInput,
100 )
101 });
102
103 group.bench_function("100 nodes", |b| {
104 b.iter_batched(
105 || {
106 let mut taffy = Taffy::new();
107 let root = build_yoga_deep_hierarchy(&mut taffy, 100, 10);
108 (taffy, root)
109 },
110 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
111 criterion::BatchSize::SmallInput,
112 )
113 });
114
115 group.bench_function("1_000 nodes", |b| {
116 b.iter_batched(
117 || {
118 let mut taffy = Taffy::new();
119 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000, 10);
120 (taffy, root)
121 },
122 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
123 criterion::BatchSize::SmallInput,
124 )
125 });
126
127 group.bench_function("10_000 nodes", |b| {
128 b.iter_batched(
129 || {
130 let mut taffy = Taffy::new();
131 let root = build_yoga_deep_hierarchy(&mut taffy, 10_000, 10);
132 (taffy, root)
133 },
134 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
135 criterion::BatchSize::SmallInput,
136 )
137 });
138
139 group.bench_function("100_000 nodes", |b| {
140 b.iter_batched(
141 || {
142 let mut taffy = Taffy::new();
143 let root = build_yoga_deep_hierarchy(&mut taffy, 100_000, 10);
144 (taffy, root)
145 },
146 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
147 criterion::BatchSize::LargeInput,
148 )
149 });
150
151 // group.bench_function("1_000_000 nodes", |b| {
152 // b.iter_batched(
153 // || {
154 // let mut taffy = Taffy::new();
155 // let root = build_yoga_deep_hierarchy(&mut taffy, 1_000_000, 10);
156 // (taffy, root)
157 // },
158 // |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
159 // criterion::BatchSize::LargeInput,
160 // )
161 // });
162 drop(group);
163
164 // Decrease sample size, because the tasks take longer
165 let mut group = c.benchmark_group("big trees (wide)");
166 group.sample_size(10);
167
168 group.bench_function("10 nodes (2-level hierarchy)", |b| {
169 b.iter_batched(
170 || {
171 let mut taffy = Taffy::new();
172 let root = build_flat_hierarchy(&mut taffy, 10);
173 (taffy, root)
174 },
175 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
176 criterion::BatchSize::SmallInput,
177 )
178 });
179
180 group.bench_function("100 nodes (2-level hierarchy)", |b| {
181 b.iter_batched(
182 || {
183 let mut taffy = Taffy::new();
184 let root = build_flat_hierarchy(&mut taffy, 100);
185 (taffy, root)
186 },
187 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
188 criterion::BatchSize::SmallInput,
189 )
190 });
191
192 group.bench_function("1_000 nodes (2-level hierarchy)", |b| {
193 b.iter_batched(
194 || {
195 let mut taffy = Taffy::new();
196 let root = build_flat_hierarchy(&mut taffy, 1_000);
197 (taffy, root)
198 },
199 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
200 criterion::BatchSize::SmallInput,
201 )
202 });
203
204 group.bench_function("10_000 nodes (2-level hierarchy)", |b| {
205 b.iter_batched(
206 || {
207 let mut taffy = Taffy::new();
208 let root = build_flat_hierarchy(&mut taffy, 10_000);
209 (taffy, root)
210 },
211 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
212 criterion::BatchSize::LargeInput,
213 )
214 });
215
216 group.bench_function("100_000 nodes (2-level hierarchy)", |b| {
217 b.iter_batched(
218 || {
219 let mut taffy = Taffy::new();
220 let root = build_flat_hierarchy(&mut taffy, 100_000);
221 (taffy, root)
222 },
223 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
224 criterion::BatchSize::LargeInput,
225 )
226 });
227
228 group.bench_function("100_000 nodes (7-level hierarchy)", |b| {
229 b.iter_batched(
230 || {
231 let mut taffy = Taffy::new();
232 let root = build_deep_hierarchy(&mut taffy, 100_000, 7);
233 (taffy, root)
234 },
235 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
236 criterion::BatchSize::LargeInput,
237 )
238 });
239
240 drop(group);
241
242 // Decrease sample size, because the tasks take longer
243 let mut group = c.benchmark_group("big trees (deep)");
244 group.sample_size(10);
245
246 group.bench_function("4000 nodes (12-level hierarchy)", |b| {
247 b.iter_batched(
248 || {
249 let mut taffy = Taffy::new();
250 let root = build_deep_hierarchy(&mut taffy, 4000, 2);
251 (taffy, root)
252 },
253 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
254 criterion::BatchSize::SmallInput,
255 )
256 });
257
258 group.bench_function("10_000 nodes (14-level hierarchy)", |b| {
259 b.iter_batched(
260 || {
261 let mut taffy = Taffy::new();
262 let root = build_deep_hierarchy(&mut taffy, 10_000, 2);
263 (taffy, root)
264 },
265 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
266 criterion::BatchSize::SmallInput,
267 )
268 });
269
270 // group.bench_function("100_000 nodes (17-level hierarchy)", |b| {
271 // b.iter_batched(
272 // || {
273 // let mut taffy = Taffy::new();
274 // let root = build_deep_hierarchy(&mut taffy, 100_000, 2);
275 // (taffy, root)
276 // },
277 // |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
278 // criterion::BatchSize::LargeInput,
279 // )
280 // });
281
282 // group.bench_function("1_000_000 nodes (20-level hierarchy)", |b| {
283 // b.iter_batched(
284 // || {
285 // let mut taffy = Taffy::new();
286 // let root = build_deep_hierarchy(&mut taffy, 1_000_000, 2);
287 // (taffy, root)
288 // },
289 // |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
290 // criterion::BatchSize::LargeInput,
291 // )
292 // });
293
294 drop(group);
295
296 let mut group = c.benchmark_group("super deep trees");
297 group.sample_size(10);
298
299 group.bench_function("100 nodes (100-level hierarchy)", |b| {
300 b.iter_batched(
301 || {
302 let mut taffy = Taffy::new();
303 let root = build_deep_hierarchy(&mut taffy, 100, 1);
304 (taffy, root)
305 },
306 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
307 criterion::BatchSize::SmallInput,
308 )
309 });
310
311 group.bench_function("1_000 nodes (1000-level hierarchy)", |b| {
312 b.iter_batched(
313 || {
314 let mut taffy = Taffy::new();
315 let root = build_deep_hierarchy(&mut taffy, 1_000, 1);
316 (taffy, root)
317 },
318 |(mut taffy, root)| taffy.compute_layout(root, Size::undefined()).unwrap(),
319 criterion::BatchSize::SmallInput,
320 )
321 });
322}
323
324criterion_group!(benches, taffy_benchmarks);
325criterion_main!(benches);