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).unwrap();
77 let mut build_flex_node =
78 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_with_children(style, &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 let mut taffy = Taffy::new();
91 let root = build_yoga_deep_hierarchy(&mut taffy, 10, 10);
92 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
93 });
94
95 group.bench_function("100 nodes", |b| {
96 let mut taffy = Taffy::new();
97 let root = build_yoga_deep_hierarchy(&mut taffy, 100, 10);
98 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
99 });
100
101 group.bench_function("1_000 nodes", |b| {
102 let mut taffy = Taffy::new();
103 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000, 10);
104 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
105 });
106
107 group.bench_function("10_000 nodes", |b| {
108 let mut taffy = Taffy::new();
109 let root = build_yoga_deep_hierarchy(&mut taffy, 10_000, 10);
110 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
111 });
112
113 group.bench_function("100_000 nodes", |b| {
114 let mut taffy = Taffy::new();
115 let root = build_yoga_deep_hierarchy(&mut taffy, 100_000, 10);
116 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
117 });
118
119 group.bench_function("1_000_000 nodes", |b| {
120 let mut taffy = Taffy::new();
121 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000_000, 10);
122 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
123 });
124 drop(group);
125
126 // Decrease sample size, because the tasks take longer
127 let mut group = c.benchmark_group("big trees (wide)");
128 group.sample_size(10);
129
130 group.bench_function("10 nodes (2-level hierarchy)", |b| {
131 let mut taffy = Taffy::new();
132 let root = build_flat_hierarchy(&mut taffy, 10);
133
134 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
135 });
136
137 group.bench_function("100 nodes (2-level hierarchy)", |b| {
138 let mut taffy = Taffy::new();
139 let root = build_flat_hierarchy(&mut taffy, 100);
140
141 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
142 });
143
144 group.bench_function("1_000 nodes (2-level hierarchy)", |b| {
145 let mut taffy = Taffy::new();
146 let root = build_flat_hierarchy(&mut taffy, 1_000);
147
148 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
149 });
150
151 group.bench_function("10_000 nodes (2-level hierarchy)", |b| {
152 let mut taffy = Taffy::new();
153 let root = build_flat_hierarchy(&mut taffy, 10_000);
154
155 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
156 });
157
158 group.bench_function("100_000 nodes (2-level hierarchy)", |b| {
159 let mut taffy = Taffy::new();
160 let root = build_flat_hierarchy(&mut taffy, 100_000);
161
162 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
163 });
164
165 group.bench_function("100_000 nodes (7-level hierarchy)", |b| {
166 let mut taffy = Taffy::new();
167 let root = build_deep_hierarchy(&mut taffy, 100_000, 7);
168
169 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
170 });
171
172 drop(group);
173
174 // Decrease sample size, because the tasks take longer
175 let mut group = c.benchmark_group("big trees (deep)");
176 group.sample_size(10);
177
178 group.bench_function("4000 nodes (12-level hierarchy)", |b| {
179 let mut taffy = Taffy::new();
180 let root = build_deep_hierarchy(&mut taffy, 4000, 2);
181
182 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
183 });
184
185 group.bench_function("10_000 nodes (14-level hierarchy)", |b| {
186 let mut taffy = Taffy::new();
187 let root = build_deep_hierarchy(&mut taffy, 10_000, 2);
188
189 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
190 });
191
192 group.bench_function("100_000 nodes (17-level hierarchy)", |b| {
193 let mut taffy = Taffy::new();
194 let root = build_deep_hierarchy(&mut taffy, 100_000, 2);
195
196 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
197 });
198
199 group.bench_function("1_000_000 nodes (20-level hierarchy)", |b| {
200 let mut taffy = Taffy::new();
201 let root = build_deep_hierarchy(&mut taffy, 1_000_000, 2);
202
203 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
204 });
205
206 drop(group);
207
208 let mut group = c.benchmark_group("super deep trees");
209 group.sample_size(10);
210
211 group.bench_function("100 nodes (100-level hierarchy)", |b| {
212 let mut taffy = Taffy::new();
213 let root = build_yoga_deep_hierarchy(&mut taffy, 100, 1);
214 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
215 });
216
217 group.bench_function("1_000 nodes (1000-level hierarchy)", |b| {
218 let mut taffy = Taffy::new();
219 let root = build_yoga_deep_hierarchy(&mut taffy, 1_000, 1);
220 b.iter(|| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap())
221 });
222}
223
224criterion_group!(benches, taffy_benchmarks);
225criterion_main!(benches);