Skip to content

Laying out flex trees with height/width set to Auto is slow (100x slower than when set to Percent) #502

@matthewgapp

Description

@matthewgapp

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingperformanceLayout go brr

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions