[Question] Is the `index` field in the Archetype struct redundant?

[carloskiki]

Hi, I'm very new to the ECS pattern, and I was reading the library's code to see how a simple ECS is efficiently implemented. I feel like I somewhat understand archetypes and how they work, but when I took a closer look at the Archetype struct, I felt like it was inefficient. Here is the struct:

pub struct Archetype {
    types: Vec<TypeInfo>,
    type_ids: Box<[TypeId]>,
    index: OrderedTypeIdMap<usize>,
    len: u32,
    entities: Box<[u32]>,
    /// One allocation per type, in the same order as `types`
    data: Box<[Data]>,
}

The OrderedTypeIdMap<T> type uses binary search under the hood as I understand it. Since the type_ids field is also sorted, wouldn't it be possible to replicate the behavior of the index? We would just need to keep track of the index during the binary search if we needed.

What am I missing?

[adamreichold]

type_ids is ordered in the same way as types, i.e. using impl Ord for TypeInfo which compares alignment, whereas index is ordered by TypeId to perform look-ups by TypeId.

IIRC, the type_ids field itself is only necessary to enable passing &[TypeId] (in contrast to &[TypeInfo]) in component order (meaning as stored in the archetype, meaning as sorted by TypeInfo).

[adamreichold]

(Also note that generally the cost of creating an Archetype should not be too critical as well, since if you have a workload that continuously creates new archetypes, an archetype-based ECS like hecs is probably not a good fit in the first place.)

[carloskiki]

Okay thank you very much!

If I may follow with an additional question: I have not looked at the code in depth, but it is not obvious to me why the data field stores every Data struct with an alignment of max_align (meaning the biggest alignment of all of the components present in the archetype). I probably do not understand correctly the Data struct, but it seems to me like since every component is stored in a separate array, then we could reduce space usage by using the alignment of every respective component.

[Ralith]

It doesn't. All component arrays are densely packed.

[carloskiki]

Thank you for your time!