Repository: mlange-42/arche
Pull request #289 (2023-05-10 23:01:13)

Cached filters use a map for faster removal of archetypes

coveralls: ## Pull Request Test Coverage Report for [Build 4942058393](https://coveralls.io/builds/59839615)

* **22** of **22**   **(100.0%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **100.0%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/59839615/badge)](https://coveralls.io/builds/59839615) |
| :-- | --: |
| Change from base [Build 4942034631](https://coveralls.io/builds/59839510): |  0.0% |
| Covered Lines: | 3776 |
| Relevant Lines: | 3776 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index c3b307e..cdf6f2e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -38,6 +38,7 @@
 * Speed up archetype and node iteration to be as fast as before the new nested structure (#270, #288)
 * ~~Filter cache stores archetype graph nodes instead of archetypes (#276)~~ (#288)
 * Use `uint32` instead of `uintptr` for indices and query iteration counter (#283)
+* Cached filters use a map for faster removal of archetypes (#289)
 
 ### Documentation
 
diff --git a/ecs/archetypes.go b/ecs/archetypes.go
index 76e0f75..0ac192f 100644
--- a/ecs/archetypes.go
+++ b/ecs/archetypes.go
@@ -63,17 +63,19 @@ func (a *pointers[T]) Add(elem *T) {
 	a.pointers = append(a.pointers, elem)
 }
 
-// Remove an element.
-func (a *pointers[T]) Remove(elem *T) {
+// RemoveAt swap-removes an element at a given index.
+//
+// Returns whether it was a swap.
+func (a *pointers[T]) RemoveAt(index int) bool {
 	ln := len(a.pointers)
-	for i := 0; i < ln; i++ {
-		arch2 := a.pointers[i]
-		if elem == arch2 {
-			a.pointers[i], a.pointers[ln-1] = a.pointers[ln-1], nil
-			a.pointers = a.pointers[:ln-1]
-			return
-		}
+	if index == ln-1 {
+		a.pointers[index] = nil
+		a.pointers = a.pointers[:index]
+		return false
 	}
+	a.pointers[index], a.pointers[ln-1] = a.pointers[ln-1], nil
+	a.pointers = a.pointers[:ln-1]
+	return true
 }
 
 // Len returns the current number of items in the paged array.
diff --git a/ecs/cache.go b/ecs/cache.go
index 6223690..d5eae70 100644
--- a/ecs/cache.go
+++ b/ecs/cache.go
@@ -5,6 +5,7 @@ type cacheEntry struct {
 	ID         uint32              // Filter ID.
 	Filter     Filter              // The underlying filter.
 	Archetypes pointers[archetype] // Nodes matching the filter.
+	Indices    map[*archetype]int  // Map of archetype indices for removal.
 }
 
 // Cache provides [Filter] caching to speed up queries.
@@ -54,6 +55,7 @@ func (c *Cache) Register(f Filter) CachedFilter {
 			ID:         id,
 			Filter:     f,
 			Archetypes: pointers[archetype]{c.getArchetypes(f)},
+			Indices:    nil,
 		})
 	c.indices[id] = len(c.filters) - 1
 	return CachedFilter{f, id}
@@ -114,29 +116,46 @@ func (c *Cache) addArchetype(arch *archetype) {
 		if rf, ok := e.Filter.(*RelationFilter); ok {
 			if rf.Target == arch.RelationTarget {
 				e.Archetypes.Add(arch)
+				// Not required: can't add after removing,
+				// as the target entity is dead.
+				// if e.Indices != nil { e.Indices[arch] = int(e.Archetypes.Len() - 1) }
 			}
 			continue
 		}
 		e.Archetypes.Add(arch)
+		if e.Indices != nil {
+			e.Indices[arch] = int(e.Archetypes.Len() - 1)
+		}
 	}
 }
 
 // Removes an archetype.
 //
-// Iterates over all filters and removes the archetype from the resp. entry where the filter matches.
+// Can only be used for archetypes that have a relation target.
+// Archetypes without a relation are never removed.
 func (c *Cache) removeArchetype(arch *archetype) {
 	for i := range c.filters {
 		e := &c.filters[i]
-		if !e.Filter.Matches(arch.Mask) {
-			continue
+
+		if e.Indices == nil && e.Filter.Matches(arch.Mask) {
+			c.mapArchetypes(e)
 		}
 
-		if rf, ok := e.Filter.(*RelationFilter); ok {
-			if rf.Target == arch.RelationTarget {
-				e.Archetypes.Remove(arch)
+		if idx, ok := e.Indices[arch]; ok {
+			swap := e.Archetypes.RemoveAt(idx)
+			if swap {
+				e.Indices[e.Archetypes.Get(int32(idx))] = idx
 			}
-			continue
+			delete(e.Indices, arch)
+		}
+	}
+}
+
+func (c *Cache) mapArchetypes(e *cacheEntry) {
+	e.Indices = map[*archetype]int{}
+	for i, arch := range e.Archetypes.pointers {
+		if arch.HasRelation() {
+			e.Indices[arch] = i
 		}
-		e.Archetypes.Remove(arch)
 	}
 }
diff --git a/ecs/util.go b/ecs/util.go
index 05cc66c..75f65be 100644
--- a/ecs/util.go
+++ b/ecs/util.go
@@ -95,11 +95,6 @@ type pagedSlice[T any] struct {
 	lenLast int32
 }
 
-// newPagedSlice creates a new pagedSlice with the given page size/capacity increment.
-func newPagedSlice[T any]() pagedSlice[T] {
-	return pagedSlice[T]{}
-}
-
 // Add adds a value to the paged slice.
 func (p *pagedSlice[T]) Add(value T) {
 	if p.len == 0 || p.lenLast == pageSize {
diff --git a/ecs/world.go b/ecs/world.go
index 45f5088..16928bb 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -112,8 +112,8 @@ func fromConfig(conf Config) World {
 		targetEntities: targetEntities,
 		entityPool:     newEntityPool(uint32(conf.CapacityIncrement)),
 		registry:       newComponentRegistry(),
-		archetypes:     newPagedSlice[archetype](),
-		nodes:          newPagedSlice[archNode](),
+		archetypes:     pagedSlice[archetype]{},
+		nodes:          pagedSlice[archNode]{},
 		relationNodes:  []*archNode{},
 		locks:          lockMask{},
 		listener:       nil,
@@ -375,8 +375,11 @@ func (w *World) removeEntities(filter Filter) int {
 	var i int32
 	for i = 0; i < numArches; i++ {
 		arch := arches[i]
-
 		len := arch.Len()
+		if len == 0 {
+			continue
+		}
+
 		count += len
 
 		var j uint32


Test patch:
diff --git a/ecs/archetypes_test.go b/ecs/archetypes_test.go
index 052d3c8..e7f53cc 100644
--- a/ecs/archetypes_test.go
+++ b/ecs/archetypes_test.go
@@ -32,7 +32,7 @@ func TestArchetypePointers(t *testing.T) {
 
 	assert.Equal(t, int32(18), pt.Len())
 
-	pt.Remove(&a2)
+	pt.RemoveAt(1)
 	assert.Equal(t, int32(17), pt.Len())
 	assert.Equal(t, unsafe.Pointer(&last), unsafe.Pointer(pt.Get(1)))
 	assert.Equal(t, unsafe.Pointer(&a3), unsafe.Pointer(pt.Get(2)))
diff --git a/ecs/cache_test.go b/ecs/cache_test.go
index a43e96b..770bfbb 100644
--- a/ecs/cache_test.go
+++ b/ecs/cache_test.go
@@ -56,6 +56,7 @@ func TestFilterCacheRelation(t *testing.T) {
 	target1 := world.NewEntity()
 	target2 := world.NewEntity()
 	target3 := world.NewEntity()
+	target4 := world.NewEntity()
 
 	cache := world.Cache()
 
@@ -78,15 +79,27 @@ func TestFilterCacheRelation(t *testing.T) {
 	assert.Equal(t, int32(0), c2.Archetypes.Len())
 	assert.Equal(t, int32(0), c3.Archetypes.Len())
 
-	NewBuilder(&world, rel1ID).WithRelation(rel1ID).NewBatch(10, target1)
+	e1 := NewBuilder(&world, rel1ID).WithRelation(rel1ID).New(target1)
 	assert.Equal(t, int32(1), c1.Archetypes.Len())
 	assert.Equal(t, int32(1), c2.Archetypes.Len())
 
-	NewBuilder(&world, rel1ID).WithRelation(rel1ID).NewBatch(10, target3)
+	_ = NewBuilder(&world, rel1ID).WithRelation(rel1ID).New(target3)
 	assert.Equal(t, int32(2), c1.Archetypes.Len())
 	assert.Equal(t, int32(1), c2.Archetypes.Len())
 
-	NewBuilder(&world, rel2ID).WithRelation(rel2ID).NewBatch(10, target2)
+	_ = NewBuilder(&world, rel2ID).WithRelation(rel2ID).New(target2)
+
+	world.RemoveEntity(e1)
+	world.RemoveEntity(target1)
+	assert.Equal(t, int32(1), c1.Archetypes.Len())
+	assert.Equal(t, int32(0), c2.Archetypes.Len())
+
+	_ = NewBuilder(&world, rel1ID).WithRelation(rel1ID).New(target2)
+	_ = NewBuilder(&world, rel1ID, posID).WithRelation(rel1ID).New(target2)
+	_ = NewBuilder(&world, rel1ID, posID).WithRelation(rel1ID).New(target3)
+	_ = NewBuilder(&world, rel1ID, posID).WithRelation(rel1ID).New(target4)
+	assert.Equal(t, int32(5), c1.Archetypes.Len())
+	assert.Equal(t, int32(2), c3.Archetypes.Len())
 
 	world.Batch().RemoveEntities(All())
 	assert.Equal(t, int32(0), c1.Archetypes.Len())
diff --git a/ecs/util_test.go b/ecs/util_test.go
index fec9725..3e5b007 100644
--- a/ecs/util_test.go
+++ b/ecs/util_test.go
@@ -44,7 +44,7 @@ func TestLockMask(t *testing.T) {
 }
 
 func TestPagedSlice(t *testing.T) {
-	a := newPagedSlice[int32]()
+	a := pagedSlice[int32]{}
 
 	var i int32
 	for i = 0; i < 66; i++ {
@@ -58,7 +58,7 @@ func TestPagedSlice(t *testing.T) {
 }
 
 func TestPagedSlicePointerPersistence(t *testing.T) {
-	a := newPagedSlice[int32]()
+	a := pagedSlice[int32]{}
 
 	a.Add(0)
 	p1 := a.Get(0)
@@ -80,7 +80,7 @@ func BenchmarkPagedSlice_Get(b *testing.B) {
 	b.StopTimer()
 
 	count := 128
-	s := newPagedSlice[int]()
+	s := pagedSlice[int]{}
 
 	for i := 0; i < count; i++ {
 		s.Add(1)