Repository: Ralith/hecs
Pull request #206 (2021-11-19 15:58:50)

Optimization for random component access
This is an optimal solution for issue #177  in my benchmarks I got 30% better performance compared to the native method of getting single component from an entity many times. 

qthree: Since `Column` is already `!Send` you can use `Cell` and fill `archetype_column_offsets` lazily upon first get access to concrete `Archetype`.
```rust
archetype_column_offsets: Vec<Cell<Poll<Option<usize>>>>,
```
This way you'll also know which archetypes you've already borrowed with `archetype.borrow::<T>(state);`.
ouz-a: <img width="606" alt="Screen Shot 2021-11-23 at 00 00 07" src="https://user-images.githubusercontent.com/90461915/142935899-c38845c8-3370-4089-a581-30cd12451657.png">

I wrote a basic function to compare two access types and columnar access as expected is significantly faster

Patch:
diff --git a/benches/bench.rs b/benches/bench.rs
index b6539a2..aac9c70 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -207,6 +207,17 @@ fn build_cloneable(b: &mut Bencher) {
     });
 }
 
+fn access_column(b: &mut Bencher) {
+    let mut world = World::new();
+    let _enta = world.spawn((Position(0.0), Velocity(0.0)));
+    let _entb = world.spawn((true, 12));
+    let entc = world.spawn((Position(3.0),));
+    let _entd = world.spawn((13, true, 4.0));
+    let column = world.column::<Position>();
+    b.iter(|| {
+        let _comp = bencher::black_box(column.get(entc).unwrap());
+    });
+}
 fn spawn_buffered(b: &mut Bencher) {
     let mut world = World::new();
     let mut buffer = CommandBuffer::new();
@@ -232,6 +243,7 @@ benchmark_group!(
     iterate_mut_cached_100_by_50,
     build,
     build_cloneable,
+    access_column,
     spawn_buffered,
 );
 benchmark_main!(benches);
diff --git a/src/archetype.rs b/src/archetype.rs
index 4b993b1..656259c 100644
--- a/src/archetype.rs
+++ b/src/archetype.rs
@@ -494,7 +494,11 @@ impl<V> OrderedTypeIdMap<V> {
     }
 }
 
-/// Metadata required to store a component
+/// Metadata required to store a component.
+///
+/// All told, this means a [`TypeId`], to be able to dynamically name/check the component type; a
+/// [`Layout`], so that we know how to allocate memory for this component type; and a drop function
+/// which internally calls [`core::ptr::drop_in_place`] with the correct type parameter.
 #[derive(Debug, Copy, Clone)]
 pub struct TypeInfo {
     id: TypeId,
@@ -505,7 +509,7 @@ pub struct TypeInfo {
 }
 
 impl TypeInfo {
-    /// Metadata for `T`
+    /// Construct a `TypeInfo` directly from the static type.
     pub fn of<T: 'static>() -> Self {
         unsafe fn drop_ptr<T>(x: *mut u8) {
             x.cast::<T>().drop_in_place()
@@ -520,17 +524,45 @@ impl TypeInfo {
         }
     }
 
-    pub(crate) fn id(&self) -> TypeId {
+    /// Construct a `TypeInfo` from its components. This is useful in the rare case that you have
+    /// some kind of pointer to raw bytes/erased memory holding a component type, coming from a
+    /// source unrelated to hecs, and you want to treat it as an insertable component by
+    /// implementing the `DynamicBundle` API.
+    pub fn from_parts(id: TypeId, layout: Layout, drop: unsafe fn(*mut u8)) -> Self {
+        Self {
+            id,
+            layout,
+            drop,
+            #[cfg(debug_assertions)]
+            type_name: "<unknown> (TypeInfo constructed from parts)",
+        }
+    }
+
+    /// Access the `TypeId` for this component type.
+    pub fn id(&self) -> TypeId {
         self.id
     }
 
-    pub(crate) fn layout(&self) -> Layout {
+    /// Access the `Layout` of this component type.
+    pub fn layout(&self) -> Layout {
         self.layout
     }
 
-    pub(crate) unsafe fn drop(&self, data: *mut u8) {
+    /// Directly call the destructor on a pointer to data of this component type.
+    ///
+    /// # Safety
+    ///
+    /// All of the caveats of [`core::ptr::drop_in_place`] apply, with the additional requirement
+    /// that this method is being called on a pointer to an object of the correct component type.
+    pub unsafe fn drop(&self, data: *mut u8) {
         (self.drop)(data)
     }
+
+    /// Get the function pointer encoding the destructor for the component type this `TypeInfo`
+    /// represents.
+    pub fn drop_shim(&self) -> unsafe fn(*mut u8) {
+        self.drop
+    }
 }
 
 impl PartialOrd for TypeInfo {
diff --git a/src/column.rs b/src/column.rs
new file mode 100644
index 0000000..a68e4cf
--- /dev/null
+++ b/src/column.rs
@@ -0,0 +1,148 @@
+use core::marker::PhantomData;
+
+use alloc::vec::Vec;
+
+use crate::entities::{EntityMeta, NoSuchEntity};
+use crate::{Archetype, Component, ComponentError, Entity, MissingComponent};
+
+/// Column of a single component
+pub struct Column<'a, T: Component> {
+    entities: &'a [EntityMeta],
+    archetypes: &'a [Archetype],
+    archetype_column_indices: Vec<Option<usize>>,
+    _marker: PhantomData<T>,
+}
+
+impl<'a, T: Component> Column<'a, T> {
+    pub(crate) fn new(
+        entities: &'a [EntityMeta],
+        archetypes: &'a [Archetype],
+        _marker: PhantomData<T>,
+    ) -> Self {
+        let mut archetype_column_indices: Vec<Option<usize>> = Vec::new();
+        for i in archetypes.iter() {
+            archetype_column_indices.push(i.get_state::<T>());
+        }
+        for val in archetypes.iter() {
+            if val.has::<T>() {
+                let state = val.get_state::<T>().unwrap();
+                val.borrow::<T>(state);
+            }
+        }
+
+        Self {
+            entities,
+            archetypes,
+            archetype_column_indices,
+            _marker,
+        }
+    }
+
+    /// Get this column's component from entity if it exist
+    pub fn get(&self, entity: Entity) -> Result<&T, ComponentError> {
+        let meta = self
+            .entities
+            .get(entity.id as usize)
+            .filter(|meta| meta.generation == entity.generation)
+            .ok_or(NoSuchEntity)?;
+        let archetype = self
+            .archetypes
+            .get(meta.location.archetype as usize)
+            .unwrap();
+        let state = self.archetype_column_indices[meta.location.archetype as usize]
+            .ok_or_else(MissingComponent::new::<T>)?;
+        unsafe {
+            let target = archetype
+                .get_base::<T>(state)
+                .as_ptr()
+                .add(meta.location.index as usize);
+
+            Ok(&*target)
+        }
+    }
+}
+
+unsafe impl<'a, T: Component> Send for Column<'a, T> {}
+unsafe impl<'a, T: Component> Sync for Column<'a, T> {}
+
+impl<'a, T: Component> Drop for Column<'a, T> {
+    fn drop(&mut self) {
+        self.archetype_column_indices.clear();
+        for val in self.archetypes.iter() {
+            if val.has::<T>() {
+                let state = val.get_state::<T>().unwrap();
+                val.release::<T>(state);
+            }
+        }
+    }
+}
+
+/// Mutable column of a single component
+pub struct ColumnMut<'a, T: Component> {
+    entities: &'a [EntityMeta],
+    archetypes: &'a [Archetype],
+    archetype_column_indices: Vec<Option<usize>>,
+    _marker: PhantomData<T>,
+}
+
+impl<'a, T: Component> ColumnMut<'a, T> {
+    pub(crate) fn new(
+        entities: &'a [EntityMeta],
+        archetypes: &'a [Archetype],
+        _marker: PhantomData<T>,
+    ) -> Self {
+        let mut archetype_column_indices: Vec<Option<usize>> = Vec::new();
+        for i in archetypes.iter() {
+            archetype_column_indices.push(i.get_state::<T>());
+        }
+        for val in archetypes.iter() {
+            if val.has::<T>() {
+                let state = val.get_state::<T>().unwrap();
+                val.borrow_mut::<T>(state);
+            }
+        }
+        Self {
+            entities,
+            archetypes,
+            archetype_column_indices,
+            _marker,
+        }
+    }
+
+    /// Mutably get this column's component from entity if it exist
+    pub fn get(&self, entity: Entity) -> Result<&mut T, ComponentError> {
+        let meta = self
+            .entities
+            .get(entity.id as usize)
+            .filter(|meta| meta.generation == entity.generation)
+            .ok_or(NoSuchEntity)?;
+        let archetype = self
+            .archetypes
+            .get(meta.location.archetype as usize)
+            .unwrap();
+        let state = self.archetype_column_indices[meta.location.archetype as usize]
+            .ok_or_else(MissingComponent::new::<T>)?;
+        unsafe {
+            let target = archetype
+                .get_base::<T>(state)
+                .as_ptr()
+                .add(meta.location.index as usize);
+            Ok(&mut *target)
+        }
+    }
+}
+
+unsafe impl<'a, T: Component> Send for ColumnMut<'a, T> {}
+unsafe impl<'a, T: Component> Sync for ColumnMut<'a, T> {}
+
+impl<'a, T: Component> Drop for ColumnMut<'a, T> {
+    fn drop(&mut self) {
+        self.archetype_column_indices.clear();
+        for val in self.archetypes.iter() {
+            if val.has::<T>() {
+                let state = val.get_state::<T>().unwrap();
+                val.release_mut::<T>(state);
+            }
+        }
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index a89d8d8..38e9579 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -60,6 +60,7 @@ mod archetype;
 mod batch;
 mod borrow;
 mod bundle;
+mod column;
 mod command_buffer;
 mod entities;
 mod entity_builder;
@@ -73,6 +74,7 @@ mod world;
 pub use archetype::{Archetype, ColumnRef};
 pub use batch::{BatchIncomplete, BatchWriter, ColumnBatch, ColumnBatchBuilder, ColumnBatchType};
 pub use bundle::{Bundle, DynamicBundle, MissingComponent};
+pub use column::{Column, ColumnMut};
 pub use command_buffer::CommandBuffer;
 pub use entities::{Entity, NoSuchEntity};
 pub use entity_builder::{BuiltEntity, Cloneable, EntityBuilder, ReusableBuiltEntity};
diff --git a/src/world.rs b/src/world.rs
index b460d09..b74c641 100644
--- a/src/world.rs
+++ b/src/world.rs
@@ -9,6 +9,7 @@ use crate::alloc::{vec, vec::Vec};
 use core::any::TypeId;
 use core::borrow::Borrow;
 use core::convert::TryFrom;
+use core::marker::PhantomData;
 use spin::Mutex;
 
 use core::{fmt, mem, ptr};
@@ -22,8 +23,8 @@ use crate::alloc::boxed::Box;
 use crate::archetype::{Archetype, TypeIdMap, TypeInfo};
 use crate::entities::{Entities, EntityMeta, Location, ReserveEntitiesIterator};
 use crate::{
-    Bundle, ColumnBatch, DynamicBundle, Entity, EntityRef, Fetch, MissingComponent, NoSuchEntity,
-    Query, QueryBorrow, QueryItem, QueryMut, QueryOne, Ref, RefMut,
+    Bundle, Column, ColumnBatch, ColumnMut, DynamicBundle, Entity, EntityRef, Fetch,
+    MissingComponent, NoSuchEntity, Query, QueryBorrow, QueryItem, QueryMut, QueryOne, Ref, RefMut,
 };
 
 /// An unordered collection of entities, each having any number of distinctly typed components
@@ -774,6 +775,35 @@ impl World {
         self.archetypes_inner().iter()
     }
 
+    /// Efficient random access within a single component type
+    pub fn column<T: Component>(&self) -> Column<'_, T> {
+        let archetypes = self.archetypes.archetypes.as_slice();
+        let entities = self.entities.meta.as_slice();
+        Column::new(entities, archetypes, PhantomData)
+    }
+
+    /// Efficient random access within a single component type
+    ///
+    /// It's useful for applications that do large amount of random
+    /// access to same Component type
+    ///
+    /// Since Column borrows every component T in all archetypes
+    /// borrow checker will panic if you try to borrow T before column goes out of scope
+    ///
+    /// # Example
+    /// ```
+    /// use::hecs::*;
+    /// let mut world = World::new();
+    /// let ent = world.spawn((123, "abc"));
+    /// let column_mut = world.column_mut::<i32>();
+    /// assert_eq!(*column_mut.get(ent).unwrap(), 123);
+    /// ```
+    pub fn column_mut<T: Component>(&self) -> ColumnMut<'_, T> {
+        let archetypes = self.archetypes.archetypes.as_slice();
+        let entities = self.entities.meta.as_slice();
+        ColumnMut::new(entities, archetypes, PhantomData)
+    }
+
     /// Returns a distinct value after `archetypes` is changed
     ///
     /// Store the current value after deriving information from [`archetypes`](Self::archetypes),


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index b2a31c2..e09c7f3 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -607,3 +607,25 @@ fn query_or() {
     assert!(results.contains(&(f, "ghi", Or::Right(true))));
     assert!(results.contains(&(g, "jkl", Or::Both(456, false))));
 }
+
+#[test]
+fn column_get() {
+    let mut world = World::new();
+    let ent = world.spawn((123, "abc"));
+    let ent2 = world.spawn((true, "hecs"));
+    let column = world.column::<&str>();
+    assert_eq!(*column.get(ent).unwrap(), "abc");
+    assert_eq!(*column.get(ent2).unwrap(), "hecs");
+}
+
+#[test]
+fn column_get_mut() {
+    let mut world = World::new();
+    let ent = world.spawn((0, true));
+    {
+        let column = world.column_mut::<i32>();
+        *column.get(ent).unwrap() = 99;
+        assert_eq!(*column.get(ent).unwrap(), 99);
+    }
+    assert_eq!(*world.get::<i32>(ent).unwrap(), 99);
+}