fixedbitset
fixedbitset copied to clipboard
petgraph
Possible performance optimizations
- fixedbitset could be allocation free for small block counts (store blocks in a SmallVec)
- fixedbitset could have a const constructor
From Bevy's ECS rework notes. Figured I'd pass the thoughts on here in case there's appetite to improve this.
@alice-i-cecile could you elaborate on your first point. Fair warning I am still fairly new to rust so this might be a noob question. Are you suggesting that the struct FixedBitSet take a SmallVec of Blocks rather than a Vec?
That's correct :) It looks like swapping to a SmallVec https://github.com/petgraph/fixedbitset/blob/5ae6d8c6175acea4ee1f8c704bc9de0122b72d0a/src/lib.rs#L61 should be a seamless replacement.
I would probably gate this behind a feature flag to allow users who don't want the extra dependency to opt out.
@james7132 was the SmallVec in #74 problematic somehow? I'm interested in removing the Vec for small block counts and wondering if there's any particular direction we should explore next
@james7132 was the
SmallVecin #74 problematic somehow? I'm interested in removing theVecfor small block counts and wondering if there's any particular direction we should explore next
It had a strong regression for contains as it always needed to do the heap check every time. Definitely not ideal for use cases that heavily relied on contains checks.
FixedBitset::new is now const so one of the two parts of this issue have been resolved.
Maybe we can have a purely on stack version of fixedbitset with const generics?
Maybe we can have a purely on stack version of fixedbitset with const generics?
I created a proof-of-concept crate for my own usage fixedbitset-stack . This is essentially a massive copy-paste of generics. I think the main design choice to make is whether to support operations between two sets on stack with different capacity though. I am not even sure that all operations can be supported given the limited capacity of Rust const generics.