Table redundantly stores 3 lengths and capacities for each column

[james7132]

Tables store a length and capacity for a BlobVec and two tick Vecs for every column in it. All of them are updated in unison when spawning/moving/despawning entities.

In an ideal world, a table should only store one length and one capacity that applies to all allocations underneath it. This would make Table::allocate O(1) in the best case instead of O(columns).

Note that addressing this likely will require a lot more unsafe, as this will require lifting a lot of the unsafe parts of BlobVec into Table.

[Adamkob12]

As I see it, there are two options: (please correct me if I'm wrong, I'm writing this without much experience in the storage system)

Option 1

1) Split BlobVec into RawBlobVec and BlobVec (like Vec's implementation) 2) Use RawBlobVec and RawVec in Column 3) Use a single length value for all columns in Table This will reduce 3*columns - 1 usizes from each Table (8[4]*(3*columns-1) bytes), not too shabby.

Option 2

Similar to option 1, but instead of RawVecs, Column will just store (small abstractions over) raw pointers. Capacity and length will be stored at the Table level. This will reduce 6*columns - 2 usizes from each Table (8[4]*(6*columns-2) bytes), twice as much as option 1.

[james7132]

Option 2 would be strongly preferred, though some other paths might need to be retained to keep support ComponentSparseSet, intact.

Bikeshedding here, but a RawBlobVec is just a Blob.

One thing to note is that the capacity of BlobVec is set to usize::MAX for ZSTs, which may not play well with this setup.

bevy_ptr has the concept of a ThinSlicePtr<'a, T> which is a NonNull that becomes a slice in debug builds. We may want to use a ThinVec<T> of the same nature to handle the component ticks in Column.

[Adamkob12]

Now that I think about it, option 2 would save a lot branching - it's a must. This does make me wonder if the ZSTs should be stored separately, maybe one SparseSet for ZSTs, and one for normal ones (eg):

struct Table {
    columns: ImmutableSparseSet<ComponentId, Column<false>>,
    zst_columns: ImmutableSparseSet<ComponentId, Column<true>>,
    cap: usize,
    len: usize
    entities: Vec<Entity>,
}
// ..
struct Column<const IS_ZST: bool> { .. }