Possible performance optimizations

[alice-i-cecile]

1. fixedbitset could be allocation free for small block counts (store blocks in a SmallVec)
2. 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.

[AlvinKuruvilla]

@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?

[alice-i-cecile]

That's correct :) It looks like swapping to a SmallVec

fixedbitset/src/lib.rs

Line 61 in 5ae6d8c

data: Vec<Block>,

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.

[AlvinKuruvilla]

Awesome I will get do my best to work on it

[grovesNL]

@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]

@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

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.

[james7132]

FixedBitset::new is now const so one of the two parts of this issue have been resolved.

[Dan-wanna-M]

Maybe we can have a purely on stack version of fixedbitset with const generics?

[Dan-wanna-M]

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.