-
Notifications
You must be signed in to change notification settings - Fork 181
Laying out flex trees with height/width set to Auto is slow (100x slower than when set to Percent) #502
Description
taffy version
0.3.12
Platform
Rust
What you did
Reproduced via the script below.
use std::time::Instant;
use taffy::{
prelude::{Rect, Size},
style::{LengthPercentageAuto, Style},
};
fn build_style() -> Style {
let margin = Rect {
left: LengthPercentageAuto::Points(20.),
top: LengthPercentageAuto::Points(20.),
right: LengthPercentageAuto::Points(0.),
bottom: LengthPercentageAuto::Points(0.),
};
let size = Size {
width: taffy::style::Dimension::Auto,
height: taffy::style::Dimension::Auto,
// changing width and height to 100% decreases layout time by ~ 100x
// width: taffy::style::Dimension::Percent(1.),
// height: taffy::style::Dimension::Percent(1.),
};
let mut style = Style::DEFAULT;
// adding flex column increases time by 10x
style.flex_direction = taffy::style::FlexDirection::Column;
// adding margin increases layout time by 200 - 500ms
style.margin = margin;
style.size = size;
style
}
fn main() {
let mut app = taffy::Taffy::new();
let root = app.new_leaf(build_style()).unwrap();
let mut parent = root;
// adding depth increases time ~ exponentially
for _ in 0..200 {
let child = app.new_leaf(build_style()).unwrap();
app.add_child(parent, child).unwrap();
// adding more siblings increases time ~ linearly from what I can tell
let child = app.new_leaf(build_style()).unwrap();
app.add_child(parent, child).unwrap();
let child = app.new_leaf(build_style()).unwrap();
app.add_child(parent, child).unwrap();
parent = child;
}
let time_now = Instant::now();
app.compute_layout(
root,
Size {
width: taffy::style::AvailableSpace::Definite(800.),
height: taffy::style::AvailableSpace::Definite(600.),
},
)
.unwrap();
// this takes about 1,500ms on my M1 Macbook Pro in dev build
println!("Time elapsed: {:?}", time_now.elapsed());
}What went wrong
Laying out flex trees with height and width set to Auto is slow (and unusable). It's 100x - 200x slower than when height and width are set to 100%. I would expect height/width of Auto to perform about the same (maybe a littler slower) as height/width 100% Percent. But not 100 - 200x slower
Computing a flex layout of a tree of nodes scales extremely poorly with increasing tree depth, to the point where Taffy is not practical for trees that exceed a depth of about 20.
So think it boils down to a combination of flex column and width, height being set to Auto (see code comments in repro snippet).
I looked at the call stack and it appears that when the dimensions are set to Auto, it will recurse through the nodes ~N^2 times. The bottom-most nodes end up getting laid out almost 10,000x.
Caching of layout results is disabled on the layout pass. There should probably be some memoization at some point in that recursion so that nodes are not laid out redundantly over and over during a layout pass.
I'm not sure why flex direction of column makes things so much worse.
Additional information
Workaround is to use width and height set to 100% instead of Auto.