Use slotmap instead of bespoke arena, limiting to one parent only #196
Conversation
|
Definitely curious to see before / after benchmarks for these changes :) |
|
Here's the results:
It looks like overall a big win for building trees, but a negligible win for relayouts. Which, is what you'd expect since there was already an internal arena system. The connection between user code and internal code will be faster, at the very least. Old: New: |
|
@alice-i-cecile Should we use stable keys or unstable keys for the tree? The current implementation uses stable, I believe. This means that a key for a node that was removed because of a parent removal will throw a hard error when used later. Unstable keys mean you could be accidentally manipulating new nodes using old keys if you weren't careful. We could either adopt a generational arena, which I think slows down performance a tad, or just clearly document that Taffy uses a slab and that it is incorrect usage for outdated keys to be used once removed. Also We have methods that catch errors. However, a lot of the flexbox methods rely on panic-y indexing that don't trap errors. Should we continue to trap errors on indexing operations, or just panic like we would if flexbox was relayouting? |
|
I would prefer to use stable keys for now as the conservative choice. Once that's in place we can experiment with swapping to unstable keys, and see if the benchmarks justify it. WRT error handling, I would like to try and catch + propagate errors as aggressively as we can for now. This code base is a pain to debug and maintain, and moving away from panicking index operations will make fixing bugs much easier. Furthermore panics in the layout often means that an entire game or GUI is crashing, which is not an acceptable failure mode for a layouting library because of how inconsequential mistakes here are compared to things like app state. |
3890f55 to
7eb30f5
Compare
|
I got a bit overzealous but then toned back my changes. I've noticed a lot of methods that return results but don't actually create errors. Pretty much every public method except for two on our Some methods should not be fallible. Creating a new leaf, for example. We can figure out what to do about this later. Personally, I prefer the approach where taffy panics since it'll be faster, but it'll obviously be less robust. Perhaps we could have "try_" methods, though the primary method - compute_layout - will need a lot of work for it to actually produce real errors. |
| #[cfg(feature = "std")] | ||
| impl std::error::Error for InvalidNode {} | ||
| /// The error Taffy generates on invalid operations | ||
| pub type TaffyResult<T> = core::result::Result<T, TaffyError>; |
There was a problem hiding this comment.
I don't think this type alias makes things clearer.
| /// The error Taffy generates on invalid operations | ||
| pub type TaffyResult<T> = core::result::Result<T, TaffyError>; | ||
|
|
||
| /// An error that occurs while trying to access or modify a [`Node`]'s children by index. |
There was a problem hiding this comment.
These docs need updating.
There was a problem hiding this comment.
Awesome! General thoughts:
- Can you add
#[forbid(unsafe_code)]to the crate now that indexmap is gone? - I'd like to see some benchmarks, but won't block on it. I don't care if this regresses performance given the removal of unsafe + code quality improvements, but it's good marketing.
- I like the use of
Nodemuch more thanNodeId. - Getting rid of all that code in
Forestfeels great. - Only one parent is a nice correctness win.
Sure - I also need to fix some of the documentation surrounding "forests" as you've noted. Per 2 - I posted above #196 (comment). Roughly a 30-90% win from average to best case. Worst cases hover around 0-15%. I tried out slab but went to slotmap and saw no performance difference, and Slotmap keys are the same sizes as slab keys. They also benefit from nonzero optimizations, so the |
alice-i-cecile
left a comment
There was a problem hiding this comment.
This is good to go!
| /// Creates and adds a new unattached leaf node to the tree, and returns the [`NodeId`] of the new node | ||
| pub fn new_leaf(&mut self, layout: FlexboxLayout) -> TaffyResult<Node> { | ||
| let id = self.nodes.insert(NodeData::new(layout)); | ||
| let _ = self.children.insert(new_vec_with_capacity(0)); |
There was a problem hiding this comment.
What is the reason for the dropped binding here?
There was a problem hiding this comment.
The key for each slotmap ends up the same but .insert is labeled must_use so either we do a drop binding or we call drop manually.
I turned on clippy pedantic just to poke around and it suggested an explicit drop... in any case all of the keys are the same.
* feat: use slab instead of bespoke arena * fix: all but one test * chore: rip out forest and merge it into taffy * fix: final tests * polish: fix up some warnings * chore: clean up forest and data fails * chore: make clippy happier * fix: compilation for no-std targets * chore: clean up some more clippy stuff and renable more tests * chore: remove outdated indexmap * fix: update benches to not unwrap new elements * fix: revert back to errors everywhere * fix: revert complex bench too * chore: remove unused import * fix: removing parents * chore: clean up and remove references to forest * chore: remove final reference to forest * chore: update release log * Update error name in RELEASES * Add single parent fix to RELEASES * Remove extra whitespace * chore: add warning to mark dirty function Co-authored-by: Alice Cecile <alice.i.cecile@gmail.com>
Objective
This PR removes the ability for nodes to have multiple parents. Fixes #191
This simplifies some of the codebase, but mostly is intended to bring Taffy closer to spec for HTML.
It also removes some of the bespoke swap_remove code which seemed difficult to maintain.
The next logical step is to use hecs instead of slotmap, but I found that integrating hecs was becoming a lot of work given the code is designed mostly around a struct of arrays. Slotmap seemed to fit in better.