Add more robust benchmarks#165
Conversation
alice-i-cecile
left a comment
There was a problem hiding this comment.
Is a pseudo-random generation approach like this useful for bench-marking?
Yes, I think this is quite nice. It allows us to explore how robust are benchmarks are down the line, and the seed makes generation repeatable.
Is the approach to generate the leaf styles good to generate versatile trees?
I like this, but I don't see why we're only randomizing the leaf styles. Why not randomize the style of every node?
The match statement in get_random_dimension uses float ranges, however this will be disallowed in the future. What is a better approach to select the dimension here?
Use one of the more appropriate tools from the rand crate; there should be one available to select randomly from an iterator (and possibly from an enum). Let me know if you need help finding this.
benches/big_tree.rs
Outdated
| } | ||
|
|
||
| /// Get a randomly generated style for a node | ||
| fn get_random_style(rng: &mut ChaCha8Rng) -> FlexboxLayout { |
There was a problem hiding this comment.
IMO this should be a method on FlexboxLayout. I would actually put this into the main crate and hide it behind a off-by-default feature flag. This functionality would be excellent for downstream crates like bevy and dioxus as well.
I think the best architecture here is actually a Random trait that we can implement for each of the fields on the FlexboxLayout, as well as on the FlexboxLayout itself.
There was a problem hiding this comment.
How would a random layout style be useful for bevy and dioxus? Or do you mean for their benchmarks?
This would require us to add the rng dependencies to the main crate, but I guess if it's behind a feature flag that's okay.
There was a problem hiding this comment.
One problem of this approach might be that you might want to fine-tune the probabilities of each style.
Another problem might be that for deep layouts, it's easy to create nonsensical styles, e.g. a parent node will often be smaller than the child nodes. I'm not sure what the best way would be to fix this.
There was a problem hiding this comment.
How would a random layout style be useful for bevy and dioxus? Or do you mean for their benchmarks?
For their benchmarks, yes :)
There was a problem hiding this comment.
@alice-i-cecile One problem with this approach would be that I can not find a way to enable specific features by default only in a given profile.
We don't want to have the rand feature enabled by default, but we do want it in the bench profile.
I guess one way to resolve this would be to explicitly enable the feature with the CLI flag and to only define the benchmarks if the feature is enabled. However, then you would need to always remember to enable the feature.
Do you know of a better way to do this?
There was a problem hiding this comment.
Hmm. I think if taffy defines these methods in a feature flag, downstream dependencies will be able to use that feature flag in their dev dependencies?
I think that having to remember to add a flag to the dev dependencies a single time per library is fine.
There was a problem hiding this comment.
And how can we handle that for our own benchmarks? I haven't found a way to enable a feature for a specific profile only.
There was a problem hiding this comment.
We should be able to import taffy as a dev-dependency within this crate, and can enable additional features there.
Sorry, this is a mistake on my part. We'll probably randomize all node styles, if we can avoid the issues mentioned in my other comment. |
I'm alright with these nonsense layouts as a startout. I don't expect them to be terribly unrepresentative, and if we find that they are we can tune the randomization in a followup. |
38f5abc to
4362ff9
Compare
|
This should now be ready for review. The two benchmarks (both use 100_000 nodes):
The deep hierarchy benchmark needs almost 3 seconds while the flat benchmark finishes in < 5 ms on my system. This difference seems insane to me, is there an error in the tree generation? Otherwise we might have some performance problems, 100k is not that many nodes. |
alice-i-cecile
left a comment
There was a problem hiding this comment.
This looks correct to me, and the code is in a solid place to start.
Unfortunately yes, the performance differences in nested hierarchies are really stark. We should probably add and then graph a single branch tree by depth as a follow-up, but there was at least one remaining exponential performance issues according to @mockersf :(
I think Taffy is currently at least O(n^2) complexity in respect to depth. Possibly even O(n!). I think some of this is unavoidable, but I also think there's something not quite right with the caching layer. I was logging out calls to |
Objective
Closes #128.
This PR aims to add more robust benchmarks that deal with much larger trees to get a better comparison point for performance improvements.
Solution
This PR generates large trees of 100,000 nodes via pseudo-random generation.
One benchmark uses a very flat hierarchy, the other one has a branching factor of 7 so it goes deeper (about 6).
I also increased the sample size of the other benchmarks from 100 to 200 to reduce noise.
Context
The current benchmarks worked with rather small trees and are very noisy. We can also think about increasing the sample size to improve the stability of these benchmarks.
Feedback wanted