using bit vector instead of Vec<bool> and enum compression

[fereidani]

Hi,
Congratualtion first, You have a great project here and I'm a big fan for a while now!
I like to contribute to this project but before sending you PR I wanted to see if you are interested in such changes or not.

I noticed that soa-derive is using Vec<bool> for bool, which can be replaced with a bit vector for better cpu cache performance with crates like https://crates.io/crates/bitvec or https://crates.io/crates/bit-vec.
It can reduce memory usage by 8x for bool and improve performance by improving cpu cache hits.

Other possible improvement is simple enums (without holding values) can be reduced to bit for example:

enum IsOk{
    Ok,
    NotOk,
}

this can be stored as bool which can use same bit vector treatment.
and this idea can scale to u8, u16(or maybe u2 u3 u4 u5 u6 u7 encodings).

Please let me know you think about these possible changes.

[Luthaf]

Hey! Thanks for the kind words. I'm not sure I want to always use a bit vector instead of Vec, since this might not work for everyone. In particular, I don't think you can take a &bool reference out of a bit vector, right? Then I don't think we can make it work with the generated reference type.

An alternative solution would be to allow using a different type with the same API as vec as the backend storage for a given field in a struct, i.e. something like

#[derive(StructOfArray)]
struct MyData {
    field: String,
    #[soa_derive::vec_type("MyCustomBitVec")] 
    other: bool,
}

[fereidani]

I agree that it might not be useful in all cases, but for &bool, I think it could be achieved using something like MutBorrowedBit from the bit-vec crate.

About enum compression, I've already started working on that idea. I'm encoding enums based on their largest variant discriminant to fit them into the smallest possible unsigned integer type (u1/bit, u2, u4, or u8), packing them across different bit positions within usize values. However, it requires extensive testing, and I need to ensure the enum Drop implementation works correctly. It involves a lot of unsafe code and must be tested thoroughly.

I skipped the idea of supporting sizes like u3, u5, or u7, as calculating the bucket index and local bit position for them would be too expensive.

[fereidani]

After looking at MutBorrowedBit implementation it would be a performance nightmare to use,
I have a vague idea to force LLVM to optimize it in different implementation, but I'm not sure yet how to approach it.
As this design problem is blocking point for both ideas, feel free to close this issue, or maybe keep it open so someone else might find the solution.
Thank you for response.

[fereidani]

This should work for mut refrences:

pub struct UpdateIfNeededOnDrop<'a, T, F>
where
    T: Copy + PartialEq,
    F: FnMut(T) + 'a,
{
    current: T,
    updated: T,
    update_fn: F,
    _marker: core::marker::PhantomData<&'a ()>,
}

impl<'a, T, F> UpdateIfNeededOnDrop<'a, T, F>
where
    T: Copy + PartialEq,
    F: FnMut(T) + 'a,
{
    #[inline(always)]
    pub fn new(current: &'a T, update_fn: F) -> Self {
        Self {
            current: *current,
            updated: *current,
            update_fn,
            _marker: core::marker::PhantomData,
        }
    }

    #[inline(always)]
    pub fn get(&self) -> T {
        self.current
    }

    #[inline(always)]
    pub fn set(&mut self, val: T) {
        self.updated = val;
    }

    #[inline(always)]
    pub fn get_mut_ref(&mut self) -> &mut T {
        &mut self.updated
    }
}

impl<'a, T, F> Drop for UpdateIfNeededOnDrop<'a, T, F>
where
    T: Copy + PartialEq,
    F: FnMut(T) + 'a,
{
    #[inline(always)]
    fn drop(&mut self) {
        if self.current != self.updated {
            (self.update_fn)(self.updated);
        }
    }
}

For immutable we can cache value by load to struct and then self reference, if user doesn't use the value, theoretically LLVM should be able to optimize load away.

[Luthaf]

This feels very complex for a relatively minimal memory gain. If you have a struct with many bool inside, you might be better off using something like bitflags, which should work out of the box.

[fereidani]

It might work, I'll design it and we will test it, It actually can improve performance too as 8x bool values fit inside the CPU cache memory.
Imagine a case when user wants to search 1 million game objects for deads or not or count 1 million network packets to see if they are inbound or outbound.