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_with_children(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_with_children(Style::random(&mut rng), &sub_children).unwrap();
24
25 children.push(node);
26 node_count += 1 + sub_children_count;
27 }
28
29 taffy.new_with_children(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 =
62 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_with_children(Style::random(&mut rng), &children).unwrap();
63
64 let tree = build_deep_tree(taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
65
66 taffy.new_with_children(Style { ..Default::default() }, &tree).unwrap()
67}
68
69/// A deep tree that matches the shape and styling that yoga use on their benchmarks
70fn build_yoga_deep_hierarchy(taffy: &mut Taffy, node_count: u32, branching_factor: u32) -> Node {
71 let style = Style {
72 size: Size { width: Dimension::Points(10.0), height: Dimension::Points(10.0) },
73 flex_grow: 1.0,
74 ..Default::default()
75 };
76 let mut build_leaf_node = |taffy: &mut Taffy| taffy.new_leaf(style.clone()).unwrap();
77 let mut build_flex_node =
78 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_with_children(style.clone(), &children).unwrap();
79
80 let tree = build_deep_tree(taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
81
82 taffy.new_with_children(Style::DEFAULT, &tree).unwrap()
83}
84
85fn taffy_benchmarks(c: &mut Criterion) {
86 let mut group = c.benchmark_group("yoga benchmarks");
87 group.sample_size(10);
88
89 group.bench_function("10 nodes", |b| {
90 b.iter_batched(
91 || {
92 let mut taffy = Taffy::new();
93 let root = build_yoga_deep_hierarchy(&mut taffy, 10, 10);
94 (taffy, root)
95 },
96 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
97 criterion::BatchSize::SmallInput,
98 )
99 });
100
101 group.bench_function("100 nodes", |b| {
102 b.iter_batched(
103 || {
104 let mut taffy = Taffy::new();
105 let root = build_yoga_deep_hierarchy(&mut taffy, 100, 10);
106 (taffy, root)
107 },
108 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
109 criterion::BatchSize::SmallInput,
110 )
111 });
112
113 group.bench_function("1_000 nodes", |b| {
114 b.iter_batched(
115 || {
116 let mut taffy = Taffy::new();
117 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000, 10);
118 (taffy, root)
119 },
120 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
121 criterion::BatchSize::SmallInput,
122 )
123 });
124
125 group.bench_function("10_000 nodes", |b| {
126 b.iter_batched(
127 || {
128 let mut taffy = Taffy::new();
129 let root = build_yoga_deep_hierarchy(&mut taffy, 10_000, 10);
130 (taffy, root)
131 },
132 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
133 criterion::BatchSize::SmallInput,
134 )
135 });
136
137 group.bench_function("100_000 nodes", |b| {
138 b.iter_batched(
139 || {
140 let mut taffy = Taffy::new();
141 let root = build_yoga_deep_hierarchy(&mut taffy, 100_000, 10);
142 (taffy, root)
143 },
144 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
145 criterion::BatchSize::LargeInput,
146 )
147 });
148
149 group.bench_function("1_000_000 nodes", |b| {
150 b.iter_batched(
151 || {
152 let mut taffy = Taffy::new();
153 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000_000, 10);
154 (taffy, root)
155 },
156 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
157 criterion::BatchSize::LargeInput,
158 )
159 });
160 drop(group);
161
162 // Decrease sample size, because the tasks take longer
163 let mut group = c.benchmark_group("big trees (wide)");
164 group.sample_size(10);
165
166 group.bench_function("10 nodes (2-level hierarchy)", |b| {
167 b.iter_batched(
168 || {
169 let mut taffy = Taffy::new();
170 let root = build_flat_hierarchy(&mut taffy, 10);
171 (taffy, root)
172 },
173 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
174 criterion::BatchSize::SmallInput,
175 )
176 });
177
178 group.bench_function("100 nodes (2-level hierarchy)", |b| {
179 b.iter_batched(
180 || {
181 let mut taffy = Taffy::new();
182 let root = build_flat_hierarchy(&mut taffy, 100);
183 (taffy, root)
184 },
185 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
186 criterion::BatchSize::SmallInput,
187 )
188 });
189
190 group.bench_function("1_000 nodes (2-level hierarchy)", |b| {
191 b.iter_batched(
192 || {
193 let mut taffy = Taffy::new();
194 let root = build_flat_hierarchy(&mut taffy, 1_000);
195 (taffy, root)
196 },
197 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
198 criterion::BatchSize::SmallInput,
199 )
200 });
201
202 group.bench_function("10_000 nodes (2-level hierarchy)", |b| {
203 b.iter_batched(
204 || {
205 let mut taffy = Taffy::new();
206 let root = build_flat_hierarchy(&mut taffy, 10_000);
207 (taffy, root)
208 },
209 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
210 criterion::BatchSize::LargeInput,
211 )
212 });
213
214 group.bench_function("100_000 nodes (2-level hierarchy)", |b| {
215 b.iter_batched(
216 || {
217 let mut taffy = Taffy::new();
218 let root = build_flat_hierarchy(&mut taffy, 100_000);
219 (taffy, root)
220 },
221 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
222 criterion::BatchSize::LargeInput,
223 )
224 });
225
226 group.bench_function("100_000 nodes (7-level hierarchy)", |b| {
227 b.iter_batched(
228 || {
229 let mut taffy = Taffy::new();
230 let root = build_deep_hierarchy(&mut taffy, 100_000, 7);
231 (taffy, root)
232 },
233 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
234 criterion::BatchSize::LargeInput,
235 )
236 });
237
238 drop(group);
239
240 // Decrease sample size, because the tasks take longer
241 let mut group = c.benchmark_group("big trees (deep)");
242 group.sample_size(10);
243
244 group.bench_function("4000 nodes (12-level hierarchy)", |b| {
245 b.iter_batched(
246 || {
247 let mut taffy = Taffy::new();
248 let root = build_deep_hierarchy(&mut taffy, 4000, 2);
249 (taffy, root)
250 },
251 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
252 criterion::BatchSize::SmallInput,
253 )
254 });
255
256 group.bench_function("10_000 nodes (14-level hierarchy)", |b| {
257 b.iter_batched(
258 || {
259 let mut taffy = Taffy::new();
260 let root = build_deep_hierarchy(&mut taffy, 10_000, 2);
261 (taffy, root)
262 },
263 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
264 criterion::BatchSize::SmallInput,
265 )
266 });
267
268 group.bench_function("100_000 nodes (17-level hierarchy)", |b| {
269 b.iter_batched(
270 || {
271 let mut taffy = Taffy::new();
272 let root = build_deep_hierarchy(&mut taffy, 100_000, 2);
273 (taffy, root)
274 },
275 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
276 criterion::BatchSize::LargeInput,
277 )
278 });
279
280 group.bench_function("1_000_000 nodes (20-level hierarchy)", |b| {
281 b.iter_batched(
282 || {
283 let mut taffy = Taffy::new();
284 let root = build_deep_hierarchy(&mut taffy, 1_000_000, 2);
285 (taffy, root)
286 },
287 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
288 criterion::BatchSize::LargeInput,
289 )
290 });
291
292 drop(group);
293
294 let mut group = c.benchmark_group("super deep trees");
295 group.sample_size(10);
296
297 group.bench_function("100 nodes (100-level hierarchy)", |b| {
298 b.iter_batched(
299 || {
300 let mut taffy = Taffy::new();
301 let root = build_deep_hierarchy(&mut taffy, 100, 1);
302 (taffy, root)
303 },
304 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
305 criterion::BatchSize::SmallInput,
306 )
307 });
308
309 group.bench_function("1_000 nodes (1000-level hierarchy)", |b| {
310 b.iter_batched(
311 || {
312 let mut taffy = Taffy::new();
313 let root = build_deep_hierarchy(&mut taffy, 1_000, 1);
314 (taffy, root)
315 },
316 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
317 criterion::BatchSize::SmallInput,
318 )
319 });
320}
321
322criterion_group!(benches, taffy_benchmarks);
323criterion_main!(benches);