Implement head-to-head benchmarks against Yoga (#337)
1//! This file includes benchmarks for very large, pseudo-randomly generated trees
2use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
3use rand::prelude::*;
4use rand_chacha::ChaCha8Rng;
5use taffy::prelude::*;
6use taffy::randomizable::Randomizeable;
7use taffy::style::Style;
8
9#[cfg(feature = "yoga_benchmark")]
10mod yoga_helpers;
11#[cfg(feature = "yoga_benchmark")]
12use slotmap::SlotMap;
13#[cfg(feature = "yoga_benchmark")]
14use yoga_helpers::yg;
15
16/// Build a random leaf node
17fn build_random_leaf(taffy: &mut Taffy, rng: &mut ChaCha8Rng) -> Node {
18 taffy.new_with_children(Style::random(rng), &[]).unwrap()
19}
20
21/// A tree with many children that have shallow depth
22fn build_taffy_flat_hierarchy(total_node_count: u32) -> (Taffy, Node) {
23 let mut taffy = Taffy::new();
24 let mut rng = ChaCha8Rng::seed_from_u64(12345);
25 let mut children = Vec::new();
26 let mut node_count = 0;
27
28 while node_count < total_node_count {
29 let sub_children_count = rng.gen_range(1..=4);
30 let sub_children: Vec<Node> =
31 (0..sub_children_count).map(|_| build_random_leaf(&mut taffy, &mut rng)).collect();
32 let node = taffy.new_with_children(Style::random(&mut rng), &sub_children).unwrap();
33
34 children.push(node);
35 node_count += 1 + sub_children_count;
36 }
37
38 let root = taffy.new_with_children(Style::DEFAULT, children.as_slice()).unwrap();
39 (taffy, root)
40}
41
42#[cfg(feature = "yoga_benchmark")]
43/// A tree with many children that have shallow depth
44fn build_yoga_flat_hierarchy(total_node_count: u32) -> (yg::YogaTree, Node) {
45 let mut tree = SlotMap::new();
46 let mut rng = ChaCha8Rng::seed_from_u64(12345);
47 let mut children = Vec::new();
48 let mut node_count = 0;
49
50 while node_count < total_node_count {
51 let sub_children_count = rng.gen_range(1..=4);
52 let sub_children: Vec<Node> = (0..sub_children_count)
53 .map(|_| yoga_helpers::new_with_children(&mut tree, &Style::random(&mut rng), vec![]))
54 .collect();
55 let node = yoga_helpers::new_with_children(&mut tree, &Style::random(&mut rng), sub_children);
56
57 children.push(node);
58 node_count += 1 + sub_children_count;
59 }
60
61 let root = yoga_helpers::new_with_children(&mut tree, &Style::DEFAULT, children);
62 (tree, root)
63}
64
65/// A helper function to recursively construct a deep tree
66fn build_deep_tree<T, N>(
67 tree: &mut T,
68 max_nodes: u32,
69 branching_factor: u32,
70 create_leaf_node: &mut impl FnMut(&mut T) -> N,
71 create_flex_node: &mut impl FnMut(&mut T, Vec<N>) -> N,
72) -> Vec<N> {
73 if max_nodes <= branching_factor {
74 // Build leaf nodes
75 return (0..max_nodes).map(|_| create_leaf_node(tree)).collect();
76 }
77
78 // Add another layer to the tree
79 // Each child gets an equal amount of the remaining nodes
80 (0..branching_factor)
81 .map(|_| {
82 let max_nodes = (max_nodes - branching_factor) / branching_factor;
83 let sub_children = build_deep_tree(tree, max_nodes, branching_factor, create_leaf_node, create_flex_node);
84 create_flex_node(tree, sub_children)
85 })
86 .collect()
87}
88
89/// A tree with a higher depth for a more realistic scenario
90fn build_taffy_deep_hierarchy(node_count: u32, branching_factor: u32) -> (Taffy, Node) {
91 let mut rng = ChaCha8Rng::seed_from_u64(12345);
92 let mut build_leaf_node = |taffy: &mut Taffy| build_random_leaf(taffy, &mut rng);
93 let mut rng = ChaCha8Rng::seed_from_u64(12345);
94 let mut build_flex_node =
95 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_with_children(Style::random(&mut rng), &children).unwrap();
96
97 let mut taffy = Taffy::new();
98 let tree = build_deep_tree(&mut taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
99 let root = taffy.new_with_children(Style::DEFAULT, &tree).unwrap();
100 (taffy, root)
101}
102
103#[cfg(feature = "yoga_benchmark")]
104/// A tree with a higher depth for a more realistic scenario
105fn build_yoga_deep_hierarchy(node_count: u32, branching_factor: u32) -> (yg::YogaTree, Node) {
106 let mut rng = ChaCha8Rng::seed_from_u64(12345);
107 let mut build_leaf_node =
108 |tree: &mut yg::YogaTree| yoga_helpers::new_with_children(tree, &Style::random(&mut rng), vec![]);
109 let mut rng = ChaCha8Rng::seed_from_u64(12345);
110 let mut build_flex_node = |tree: &mut yg::YogaTree, children: Vec<Node>| {
111 yoga_helpers::new_with_children(tree, &Style::random(&mut rng), children)
112 };
113
114 let mut tree = SlotMap::new();
115 let children = build_deep_tree(&mut tree, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
116 let root = yoga_helpers::new_with_children(&mut tree, &Style::DEFAULT, children);
117
118 (tree, root)
119}
120
121/// A deep tree that matches the shape and styling that yoga use on their benchmarks
122fn build_taffy_huge_nested_hierarchy(node_count: u32, branching_factor: u32) -> (Taffy, Node) {
123 let style = Style {
124 size: Size { width: Dimension::Points(10.0), height: Dimension::Points(10.0) },
125 flex_grow: 1.0,
126 ..Default::default()
127 };
128 let mut build_leaf_node = |taffy: &mut Taffy| taffy.new_leaf(style.clone()).unwrap();
129 let mut build_flex_node =
130 |taffy: &mut Taffy, children: Vec<Node>| taffy.new_with_children(style.clone(), &children).unwrap();
131
132 let mut taffy = Taffy::new();
133 let tree = build_deep_tree(&mut taffy, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
134 let root = taffy.new_with_children(Style::DEFAULT, &tree).unwrap();
135 (taffy, root)
136}
137
138#[cfg(feature = "yoga_benchmark")]
139/// A deep tree that matches the shape and styling that yoga use on their benchmarks
140fn build_yoga_huge_nested_hierarchy(node_count: u32, branching_factor: u32) -> (yg::YogaTree, Node) {
141 let style = Style {
142 size: Size { width: Dimension::Points(10.0), height: Dimension::Points(10.0) },
143 flex_grow: 1.0,
144 ..Default::default()
145 };
146 let mut build_leaf_node = |tree: &mut yg::YogaTree| -> Node {
147 let mut node = yg::Node::new();
148 yoga_helpers::apply_taffy_style(&mut node, &style.clone());
149 tree.insert(node)
150 };
151 let mut build_flex_node = |tree: &mut yg::YogaTree, children: Vec<Node>| -> Node {
152 let mut node = yg::Node::new();
153 yoga_helpers::apply_taffy_style(&mut node, &style.clone());
154 for (i, child) in children.into_iter().enumerate() {
155 node.insert_child(&mut tree[child], i as u32);
156 }
157 tree.insert(node)
158 };
159
160 let mut tree = SlotMap::new();
161 let children = build_deep_tree(&mut tree, node_count, branching_factor, &mut build_leaf_node, &mut build_flex_node);
162 let mut root = yg::Node::new();
163 for (i, child) in children.into_iter().enumerate() {
164 root.insert_child(&mut tree[child], i as u32);
165 }
166 let root = tree.insert(root);
167 (tree, root)
168}
169
170fn taffy_benchmarks(c: &mut Criterion) {
171 let mut group = c.benchmark_group("yoga 'huge nested'");
172 for node_count in [1_000u32, 10_000, 100_000].iter() {
173 #[cfg(feature = "yoga_benchmark")]
174 group.bench_with_input(BenchmarkId::new("Yoga", node_count), node_count, |b, &node_count| {
175 b.iter_batched(
176 || build_yoga_huge_nested_hierarchy(node_count, 10),
177 |(mut tree, root)| {
178 tree[root].calculate_layout(f32::INFINITY, f32::INFINITY, yg::Direction::LTR);
179 },
180 criterion::BatchSize::SmallInput,
181 )
182 });
183 group.bench_with_input(BenchmarkId::new("Taffy", node_count), node_count, |b, &node_count| {
184 b.iter_batched(
185 || build_taffy_huge_nested_hierarchy(node_count, 10),
186 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
187 criterion::BatchSize::SmallInput,
188 )
189 });
190 }
191 group.finish();
192
193 // Decrease sample size, because the tasks take longer
194 let mut group = c.benchmark_group("big trees (wide)");
195 group.sample_size(10);
196 for node_count in [1_000u32, 10_000, 100_000].iter() {
197 #[cfg(feature = "yoga_benchmark")]
198 let benchmark_id = BenchmarkId::new(format!("Yoga (2-level hierarchy)"), node_count);
199 #[cfg(feature = "yoga_benchmark")]
200 group.bench_with_input(benchmark_id, node_count, |b, &node_count| {
201 b.iter_batched(
202 || build_yoga_flat_hierarchy(node_count),
203 |(mut tree, root)| {
204 tree[root].calculate_layout(f32::INFINITY, f32::INFINITY, yg::Direction::LTR);
205 },
206 criterion::BatchSize::SmallInput,
207 )
208 });
209 let benchmark_id = BenchmarkId::new(format!("Taffy (2-level hierarchy)"), node_count);
210 group.bench_with_input(benchmark_id, node_count, |b, &node_count| {
211 b.iter_batched(
212 || build_taffy_flat_hierarchy(node_count),
213 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
214 criterion::BatchSize::SmallInput,
215 )
216 });
217 }
218 group.finish();
219
220 // Decrease sample size, because the tasks take longer
221 let mut group = c.benchmark_group("big trees (deep)");
222 group.sample_size(10);
223 let benches = [(4000, "(12-level hierarchy)"), (10_000, "(14-level hierarchy)"), (100_000, "(17-level hierarchy)")];
224 for (node_count, label) in benches.iter() {
225 #[cfg(feature = "yoga_benchmark")]
226 group.bench_with_input(BenchmarkId::new(format!("Yoga {label}"), node_count), node_count, |b, &node_count| {
227 b.iter_batched(
228 || build_yoga_deep_hierarchy(node_count, 2),
229 |(mut tree, root)| {
230 tree[root].calculate_layout(f32::INFINITY, f32::INFINITY, yg::Direction::LTR);
231 },
232 criterion::BatchSize::SmallInput,
233 )
234 });
235 group.bench_with_input(BenchmarkId::new(format!("Taffy {label}"), node_count), node_count, |b, &node_count| {
236 b.iter_batched(
237 || build_taffy_deep_hierarchy(node_count, 2),
238 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
239 criterion::BatchSize::SmallInput,
240 )
241 });
242 }
243 group.finish();
244
245 let mut group = c.benchmark_group("super deep (1000-level hierarchy)");
246 group.sample_size(10);
247 for node_count in [1000u32].iter() {
248 #[cfg(feature = "yoga_benchmark")]
249 group.bench_with_input(BenchmarkId::new("Yoga", node_count), node_count, |b, &node_count| {
250 b.iter_batched(
251 || build_yoga_deep_hierarchy(node_count, 2),
252 |(mut tree, root)| {
253 tree[root].calculate_layout(f32::INFINITY, f32::INFINITY, yg::Direction::LTR);
254 },
255 criterion::BatchSize::SmallInput,
256 )
257 });
258 group.bench_with_input(BenchmarkId::new("Taffy", node_count), node_count, |b, &node_count| {
259 b.iter_batched(
260 || build_taffy_deep_hierarchy(node_count, 2),
261 |(mut taffy, root)| taffy.compute_layout(root, Size::MAX_CONTENT).unwrap(),
262 criterion::BatchSize::SmallInput,
263 )
264 });
265 }
266 group.finish();
267}
268
269criterion_group!(benches, taffy_benchmarks);
270criterion_main!(benches);