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