Deep nesting results in poor performance

[AlexCharlton]

I'm using stretch to lay out a tree-like structure. With 63 nodes and a maximum depth of 16, compute_layout takes about 5 seconds to complete. Profiling illustrates that compute time increases exponentially with depth, and that compute_internal is called over 50k times for my structure of 63 nodes.

Is this sort of performance expected? Is nesting this deeply just an entirely unexpected thing to be doing with stretch? Are there constraints I could be putting in place to elide some of this recursion?

[emilsjolander]

This is not expected. It should scale much much better than this. Probably something to do with a specific calculation which means it's very tied to the specific tree you are passing in. Could you write a benchmark and submit it as a pull request (extending the current benchmark suite) so that we could have a look?

[mockersf]

I have met the same issue.

The following code can show it:

use std::time::SystemTime;
use stretch::geometry::Size;
use stretch::style::*;

fn main() -> Result<(), stretch::Error> {
    let mut stretch = stretch::node::Stretch::new();

    let node = stretch.new_node(
        Style { size: Size { width: Dimension::Points(50.), height: Dimension::Points(50.) }, ..Default::default() },
        vec![],
    )?;
    let mut child = stretch.new_node(Style::default(), vec![])?;
    stretch.set_children(node, vec![child]).unwrap();

    for i in 0..20 {
        let new_child = stretch.new_node(Style::default(), vec![])?;
        stretch.set_children(child, vec![new_child]).unwrap();
        child = new_child;

        let now = SystemTime::now();
        stretch.compute_layout(node, Size::undefined())?;
        println!("elapsed: {} nodes -> {:?}", i + 3, now.elapsed());
    }

    Ok(())
}

in debug mode:

elapsed: 3 nodes -> Ok(120µs)
elapsed: 4 nodes -> Ok(161µs)
elapsed: 5 nodes -> Ok(334µs)
elapsed: 6 nodes -> Ok(704µs)
elapsed: 7 nodes -> Ok(1.437ms)
elapsed: 8 nodes -> Ok(2.597ms)
elapsed: 9 nodes -> Ok(8.257ms)
elapsed: 10 nodes -> Ok(14.653ms)
elapsed: 11 nodes -> Ok(19.779ms)
elapsed: 12 nodes -> Ok(36.805ms)
elapsed: 13 nodes -> Ok(67.413ms)
elapsed: 14 nodes -> Ok(130.294ms)
elapsed: 15 nodes -> Ok(268.727ms)
elapsed: 16 nodes -> Ok(519.621ms)
elapsed: 17 nodes -> Ok(1.024435s)
elapsed: 18 nodes -> Ok(2.03991s)
elapsed: 19 nodes -> Ok(4.078674s)
elapsed: 20 nodes -> Ok(8.230985s)
elapsed: 21 nodes -> Ok(17.050925s)
elapsed: 22 nodes -> Ok(34.905185s)

and in release:

elapsed: 3 nodes -> Ok(31µs)
elapsed: 4 nodes -> Ok(15µs)
elapsed: 5 nodes -> Ok(29µs)
elapsed: 6 nodes -> Ok(64µs)
elapsed: 7 nodes -> Ok(177µs)
elapsed: 8 nodes -> Ok(260µs)
elapsed: 9 nodes -> Ok(497µs)
elapsed: 10 nodes -> Ok(836µs)
elapsed: 11 nodes -> Ok(1.696ms)
elapsed: 12 nodes -> Ok(3.272ms)
elapsed: 13 nodes -> Ok(6.373ms)
elapsed: 14 nodes -> Ok(10.881ms)
elapsed: 15 nodes -> Ok(21.904ms)
elapsed: 16 nodes -> Ok(45.07ms)
elapsed: 17 nodes -> Ok(76.651ms)
elapsed: 18 nodes -> Ok(145.677ms)
elapsed: 19 nodes -> Ok(296.503ms)
elapsed: 20 nodes -> Ok(590.395ms)
elapsed: 21 nodes -> Ok(1.150736s)
elapsed: 22 nodes -> Ok(2.323467s)

adding one node as a leaf doubles the compute_layout time