Repository: Ralith/hecs
Pull request #224 (2021-12-24 17:48:40)

Add World::exchange as a optimised combination of World::remove followed by World::insert

adamreichold: I see at least two open issues here:
* [ ] How much of the copy-and-pasted code from `World::remove` and `World::insert` should be factored out into reusable helper functions?
* [ ] Should there be `exchange_edges` instead of querying `remove_edges` and `insert_edges`?
adamreichold: The included benchmark improves from
```
test exchange                       ... bench:      29,769 ns/iter (+/- 731)
```
using the "fake" implementation to
```
test exchange                       ... bench:      18,183 ns/iter (+/- 281)
```
Ralith: Nice speedup!

> How much of the copy-and-pasted code from World::remove and World::insert should be factored out into reusable helper functions?

Given that it's somewhat fraught unsafe stuff, I'd definitely like to minimize duplication here as much as is feasible. It hasn't needed to be touched in a good while, but when it was fresh it was a source of several serious bugs.

> Should there be exchange_edges instead of querying remove_edges and insert_edges?

If there's a meaningful benchmark benefit, I don't see why not.
adamreichold: > > Should there be exchange_edges instead of querying remove_edges and insert_edges?

> If there's a meaningful benchmark benefit, I don't see why not.

I pushed a commit implementing this for you to have a look at.

I think it is a tough sell: While the benchmark improves from
```
test exchange                       ... bench:      21,497 ns/iter (+/- 487)
```
to
```
test exchange                       ... bench:      19,907 ns/iter (+/- 611)
```
(different baseline to above as I remembered to disable frequency boost now), this requires another specialised hasher `TypeIdPairHasher` (as I cannot just use `TypeId::of::<(S,T)>` due to dynamic bundles), reduces the amount of code that can be shared with `World::{insert,remove}`, increases memory usage due to the extra hash tables and does not implicitly "discover" the intermediate edges for use with `World::{insert,remove}`.

Do you think the 7.5% improvement is worth the additional complexity?

(The additional hasher could probably be avoided by adding something like `Bundle::key_with<T>(&self) -> Option<TypeId>` which basically returns `TypeId::of::<(Self, T)>()`, but that would push the complexity further out into the user-facing API.)
adamreichold: As a bit of a tangent, I do use separate `{insert,remove,exchange}_map` in rs-ecs but the situation is slightly different because I do not have dynamic bundles and I have only one hash table per operation instead of per-operation-and-archetype by hashing `(index-of-source-archetype, type-id-of-bundle-or-pair-of-bundles)` with a specialised hasher.

If I did not miss anything which precludes this working at all, then I think these per-operation hash tables would also make sense for hecs. If you are interested in that, I can look into porting that as well. But I also think that should be a separate pull request instead of being folded into this one.
Ralith: > Do you think the 7.5% improvement is worth the additional complexity?

Hmm, that's not nothing, but unless it's solving a real problem for someone I'm amenable to holding off for now. I also suspect that it'll be easier to factor out shared logic between insert/remove and exchange without a new edge type.

> If I did not miss anything which precludes this working at all, then I think these per-operation hash tables would also make sense for hecs. If you are interested in that, I can look into porting that as well.

Thanks for the interest in all this backporting work! I'm open to this, but it's not immediately obvious to me what the advantage is over per-archetype tables. Maybe open an issue to discuss?
adamreichold: > I also suspect that it'll be easier to factor out shared logic between insert/remove and exchange without a new edge type.

Yes, that would be my main motivator for this PR as well.

> Thanks for the interest in all this backporting work!

Well, we started from hecs' design and it has helped our simulation work significantly to have a fast yet simple ECS that can be tailored to our needs. So it seems only fair to invest some effort back into hecs.

> I'm open to this, but it's not immediately obvious to me what the advantage is over per-archetype tables. Maybe open an issue to discuss?

I think for now, it is best to get this PR shipshape without an additional edge type.

(The idea behind the per-operation tables is to have fewer separate dynamic allocations and thereby better spatial locality and less memory usage overhead at the cost of slightly more difficult hash table look-ups (which are fast thanks to Hashbrown/SIMD). Producing a serviceable hash out of the type ID which already is a good hash and the small integer archetype indexes seems reasonably simple and efficient by just XOR'ing them.)
Ralith: > The idea behind the per-operation tables is [...]

Ah, that makes sense. I'd be happy to have that and I imagine it'd be fairly straightforward.
adamreichold: > Given that it's somewhat fraught unsafe stuff, I'd definitely like to minimize duplication here as much as is feasible. It hasn't needed to be touched in a good while, but when it was fresh it was a source of several serious bugs.

I pushed an updated version that drops the dedicated edges and factors out most of the shared code between `World::{insert,remove,exchange}`. The cuts are a bit weird, but I was unable to factor out something more natural like `World::insert_target` due to how the `InsertTarget` is sometimes owned and borrowed from `World::archetypes`.

(I tried returning something like `Cow<'_, InsertTarget>` or taking `target_storage: &mut Option<InsertTarget>` as an argument, but this both failed due to returning essentially `&'a InsertTarget` which means any borrow from which is derived must last for the whole body of the function which conflicts with borrowing `World::archetypes` several times if the first look-up fails.)
adamreichold: > Thanks! Just needs a rebase.

Pushed a rebase which including updates so that the intermediate commits still work.

Patch:
diff --git a/benches/bench.rs b/benches/bench.rs
index fed445d..9226210 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -100,6 +100,19 @@ fn insert_remove(b: &mut Bencher) {
     });
 }
 
+fn exchange(b: &mut Bencher) {
+    let mut world = World::new();
+    let entities = world
+        .spawn_batch((0..1_000).map(|_| (Position(0.0), Velocity(0.0))))
+        .collect::<Vec<_>>();
+    let mut entities = entities.iter().cycle();
+    b.iter(|| {
+        let e = *entities.next().unwrap();
+        world.exchange_one::<Velocity, _>(e, true).unwrap();
+        world.exchange_one::<bool, _>(e, Velocity(0.0)).unwrap();
+    });
+}
+
 fn iterate_100k(b: &mut Bencher) {
     let mut world = World::new();
     for i in 0..100_000 {
@@ -266,6 +279,7 @@ benchmark_group!(
     remove,
     insert,
     insert_remove,
+    exchange,
     iterate_100k,
     iterate_mut_100k,
     iterate_uncached_100_by_50,
diff --git a/src/world.rs b/src/world.rs
index 49f8184..b4110f0 100644
--- a/src/world.rs
+++ b/src/world.rs
@@ -13,7 +13,7 @@ use core::hash::{BuildHasherDefault, Hasher};
 use core::marker::PhantomData;
 use spin::Mutex;
 
-use core::{fmt, mem, ptr};
+use core::{fmt, ptr};
 
 #[cfg(feature = "std")]
 use std::error::Error;
@@ -553,23 +553,34 @@ impl World {
         components: impl DynamicBundle,
     ) -> Result<(), NoSuchEntity> {
         self.flush();
-        let loc = self.entities.get_mut(entity)?;
 
+        let loc = self.entities.get(entity)?;
+        self.insert_inner(entity, components, loc.archetype, loc)
+    }
+
+    /// The implementation backing [`insert`](Self::insert) exposed so that it can also be used by [`exchange`](Self::exchange).
+    ///
+    /// Note that `graph_origin` is always equal to `loc.archetype` during insertion. Only for exchange, `graph_origin` identifies
+    /// the intermediate archetype which would be reached after removal and before insertion even though
+    /// the actual component data still resides in `loc.archetype`.
+    fn insert_inner(
+        &mut self,
+        entity: Entity,
+        components: impl DynamicBundle,
+        graph_origin: u32,
+        loc: Location,
+    ) -> Result<(), NoSuchEntity> {
         let target_storage;
         let target = match components.key() {
             None => {
-                target_storage = self
-                    .archetypes
-                    .get_insert_target(loc.archetype, &components);
+                target_storage = self.archetypes.get_insert_target(graph_origin, &components);
                 &target_storage
             }
-            Some(key) => match self.insert_edges.get(&(loc.archetype, key)) {
+            Some(key) => match self.insert_edges.get(&(graph_origin, key)) {
                 Some(x) => x,
                 None => {
-                    let t = self
-                        .archetypes
-                        .get_insert_target(loc.archetype, &components);
-                    self.insert_edges.entry((loc.archetype, key)).or_insert(t)
+                    let t = self.archetypes.get_insert_target(graph_origin, &components);
+                    self.insert_edges.entry((graph_origin, key)).or_insert(t)
                 }
             },
         };
@@ -601,8 +612,9 @@ impl World {
 
             // Allocate storage in the archetype and update the entity's location to address it
             let target_index = target_arch.allocate(entity.id);
-            loc.archetype = target.index;
-            let old_index = mem::replace(&mut loc.index, target_index);
+            let meta = &mut self.entities.meta[entity.id as usize];
+            meta.location.archetype = target.index;
+            meta.location.index = target_index;
 
             // Move the new components
             components.put(|ptr, ty| {
@@ -612,14 +624,14 @@ impl World {
             // Move the components we're keeping
             for &ty in &target.retained {
                 let src = source_arch
-                    .get_dynamic(ty.id(), ty.layout().size(), old_index)
+                    .get_dynamic(ty.id(), ty.layout().size(), loc.index)
                     .unwrap();
                 target_arch.put_dynamic(src.as_ptr(), ty.id(), ty.layout().size(), target_index)
             }
 
             // Free storage in the old archetype
-            if let Some(moved) = source_arch.remove(old_index, false) {
-                self.entities.meta[moved as usize].location.index = old_index;
+            if let Some(moved) = source_arch.remove(loc.index, false) {
+                self.entities.meta[moved as usize].location.index = loc.index;
             }
         }
         Ok(())
@@ -660,7 +672,6 @@ impl World {
 
         // Gather current metadata
         let loc = self.entities.get_mut(entity)?;
-        let old_archetype = loc.archetype;
         let old_index = loc.index;
         let source_arch = &self.archetypes.archetypes[loc.archetype as usize];
 
@@ -670,23 +681,8 @@ impl World {
         };
 
         // Find the target archetype ID
-        let target = match self.remove_edges.get(&(old_archetype, TypeId::of::<T>())) {
-            Some(&x) => x,
-            None => {
-                let removed = T::with_static_ids(|ids| ids.iter().copied().collect::<HashSet<_>>());
-                let info = source_arch
-                    .types()
-                    .iter()
-                    .cloned()
-                    .filter(|x| !removed.contains(&x.id()))
-                    .collect::<Vec<_>>();
-                let elements = info.iter().map(|x| x.id()).collect::<Box<_>>();
-                let index = self.archetypes.get(&*elements, move || info);
-                self.remove_edges
-                    .insert((old_archetype, TypeId::of::<T>()), index);
-                index
-            }
-        };
+        let target =
+            Self::remove_target::<T>(&mut self.archetypes, &mut self.remove_edges, loc.archetype);
 
         // Store components to the target archetype and update metadata
         if loc.archetype != target {
@@ -714,6 +710,31 @@ impl World {
         Ok(bundle)
     }
 
+    fn remove_target<T: Bundle + 'static>(
+        archetypes: &mut ArchetypeSet,
+        remove_edges: &mut IndexTypeIdMap<u32>,
+        old_archetype: u32,
+    ) -> u32 {
+        match remove_edges.get(&(old_archetype, TypeId::of::<T>())) {
+            Some(&x) => x,
+            None => {
+                let removed = T::with_static_ids(|ids| ids.iter().copied().collect::<HashSet<_>>());
+                let info = archetypes.archetypes[old_archetype as usize]
+                    .types()
+                    .iter()
+                    .cloned()
+                    .filter(|x| !removed.contains(&x.id()))
+                    .collect::<Vec<_>>();
+                let elements = info.iter().map(|x| x.id()).collect::<Box<_>>();
+                let index = archetypes.get(&*elements, move || info);
+
+                remove_edges.insert((old_archetype, TypeId::of::<T>()), index);
+
+                index
+            }
+        }
+    }
+
     /// Remove the `T` component from `entity`
     ///
     /// See [`remove`](Self::remove).
@@ -721,6 +742,48 @@ impl World {
         self.remove::<(T,)>(entity).map(|(x,)| x)
     }
 
+    /// Remove `S` components from `entity` and then `components`
+    ///
+    /// This has the same effect as calling [`remove::<S>`](Self::remove) and then [`insert::<T>`](Self::insert),
+    /// but is more efficient as the intermediate archetype after removal but before insertion is skipped.
+    pub fn exchange<S: Bundle + 'static, T: DynamicBundle>(
+        &mut self,
+        entity: Entity,
+        components: T,
+    ) -> Result<S, ComponentError> {
+        self.flush();
+
+        // Gather current metadata
+        let loc = self.entities.get(entity)?;
+
+        // Move out of the source archetype, or bail out if a component is missing
+        let source_arch = &self.archetypes.archetypes[loc.archetype as usize];
+
+        let bundle = unsafe {
+            S::get(|ty| source_arch.get_dynamic(ty.id(), ty.layout().size(), loc.index))?
+        };
+
+        // Find the intermediate archetype ID
+        let intermediate =
+            Self::remove_target::<S>(&mut self.archetypes, &mut self.remove_edges, loc.archetype);
+
+        self.insert_inner(entity, components, intermediate, loc)?;
+
+        Ok(bundle)
+    }
+
+    /// Remove the `S` component from `entity` and then add `component`
+    ///
+    /// See [`exchange`](Self::exchange).
+    pub fn exchange_one<S: Component, T: Component>(
+        &mut self,
+        entity: Entity,
+        component: T,
+    ) -> Result<S, ComponentError> {
+        self.exchange::<(S,), (T,)>(entity, (component,))
+            .map(|(x,)| x)
+    }
+
     /// Borrow the `T` component of `entity` without safety checks
     ///
     /// Should only be used as a building block for safe abstractions.


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index e9ba980..7fa7232 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -567,6 +567,21 @@ fn remove_missing() {
     assert!(world.remove_one::<bool>(e).is_err());
 }
 
+#[test]
+fn exchange_components() {
+    let mut world = World::new();
+
+    let entity = world.spawn(("abc".to_owned(), 123));
+    assert!(world.get::<String>(entity).is_ok());
+    assert!(world.get::<i32>(entity).is_ok());
+    assert!(world.get::<bool>(entity).is_err());
+
+    world.exchange_one::<String, _>(entity, true).unwrap();
+    assert!(world.get::<String>(entity).is_err());
+    assert!(world.get::<i32>(entity).is_ok());
+    assert!(world.get::<bool>(entity).is_ok());
+}
+
 #[test]
 fn reserve() {
     let mut world = World::new();