Repository: mlange-42/arche (go)

Issue:
More efficient filtering for simple relation filters
Currently, all archetypes of relation nodes are iterated if the node matches.

For plain `RelationFilter`, this could be improved by just accessing the single matching archetype throught the node's archetype map.

Pull request description:
Optimize `RelationFilter`: Query archetype directly instead of iterating node
Fixes #250

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2ca8a97..cac2758 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -24,6 +24,7 @@
 * Queries iterate archetype graph nodes in an outer loop, potentially skipping nested relation archetypes (#248)
 * Relation archetypes are recycled in archetype graph nodes (#248)
 * Already empty archetypes are not zeroed on reset (#248)
+* Optimize `RelationFilter`: get archetype directly instead of iterating complete node (#251)
 
 ### Other
 
diff --git a/ecs/query.go b/ecs/query.go
index 050eaa6..ca1b4fe 100644
--- a/ecs/query.go
+++ b/ecs/query.go
@@ -203,15 +203,32 @@ func (q *Query) nextNode() bool {
 		q.nodeIndex++
 		n := q.nodes.Get(q.nodeIndex)
 		arches := n.Archetypes()
-		if arches != nil && n.Matches(q.filter) && arches.Len() > 0 {
-			q.archetypes = arches
-			q.archIndex = -1
-			q.entityIndex = 0
-			q.entityIndexMax = 0
-			if q.nextArchetypeSimple() {
-				return true
+
+		if arches == nil || !n.Matches(q.filter) || arches.Len() == 0 {
+			continue
+		}
+
+		if arches.Len() > 1 {
+			if rf, ok := q.filter.(*RelationFilter); ok {
+				target := rf.Target
+				if arch, ok := n.archetypeMap[target]; ok && arch.Len() > 0 {
+					q.archetypes = nil
+					q.archIndex = arch.index
+					q.access = &arch.archetypeAccess
+					q.entityIndex = 0
+					q.entityIndexMax = uintptr(arch.Len()) - 1
+					return true
+				}
+				continue
 			}
 		}
+		q.archetypes = arches
+		q.archIndex = -1
+		q.entityIndex = 0
+		q.entityIndexMax = 0
+		if q.nextArchetypeSimple() {
+			return true
+		}
 	}
 	q.archetypes = nil
 	q.world.closeQuery(q)
@@ -233,9 +250,7 @@ func (q *Query) countEntities() int {
 		var i int32
 		for i = 0; i < len; i++ {
 			a := q.archetypes.Get(i)
-			if a.IsActive() && (q.isFiltered || a.Matches(q.filter)) {
-				count += a.Len()
-			}
+			count += a.Len()
 		}
 		return int(count)
 	}
@@ -254,6 +269,16 @@ func (q *Query) countEntities() int {
 		}
 		nArch := arches.Len()
 
+		if nArch > 1 {
+			if rf, ok := q.filter.(*RelationFilter); ok {
+				target := rf.Target
+				if arch, ok := nd.archetypeMap[target]; ok {
+					count += arch.Len()
+				}
+				continue
+			}
+		}
+
 		var j int32
 		for j = 0; j < nArch; j++ {
 			a := arches.Get(j)
diff --git a/ecs/world.go b/ecs/world.go
index 65b41de..981fec7 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -1096,9 +1096,19 @@ func (w *World) getArchetypes(filter Filter) archetypePointers {
 		}
 
 		ln2 := int32(nodeArches.Len())
+		if ln2 > 1 {
+			if rf, ok := filter.(*RelationFilter); ok {
+				target := rf.Target
+				if arch, ok := nd.archetypeMap[target]; ok {
+					arches = append(arches, arch)
+				}
+				continue
+			}
+		}
+
 		var j int32
 		for j = 0; j < ln2; j++ {
-			a := nodeArches.Get(i)
+			a := nodeArches.Get(j)
 			if a.IsActive() && a.Matches(filter) {
 				arches = append(arches, a)
 			}


Test patch:
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 7e657fc..42a8181 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -745,7 +745,70 @@ func TestWorldRelationQuery(t *testing.T) {
 	filter2 = RelationFilter{Filter: All(relID), Target: targ3}
 	query = world.Query(&filter2)
 	assert.Equal(t, 0, query.Count())
+	cnt = 0
+	for query.Next() {
+		cnt++
+	}
+	assert.Equal(t, 0, cnt)
+}
+
+func TestWorldRelationQueryCached(t *testing.T) {
+	world := NewWorld()
+
+	rotID := ComponentID[rotation](&world)
+	relID := ComponentID[testRelationA](&world)
+
+	targ0 := world.NewEntityWith(Component{ID: rotID, Comp: &rotation{Angle: 0}})
+
+	targ1 := world.NewEntityWith(Component{ID: rotID, Comp: &rotation{Angle: 1}})
+	targ2 := world.NewEntityWith(Component{ID: rotID, Comp: &rotation{Angle: 2}})
+	targ3 := world.NewEntityWith(Component{ID: rotID, Comp: &rotation{Angle: 3}})
+
+	e1 := world.NewEntity(relID)
+	world.SetRelation(e1, relID, targ0)
+
+	for i := 0; i < 4; i++ {
+		e1 := world.NewEntity(relID)
+		world.SetRelation(e1, relID, targ1)
+
+		e2 := world.NewEntity(relID)
+		world.SetRelation(e2, relID, targ2)
+	}
+
+	world.RemoveEntity(e1)
+	world.RemoveEntity(targ0)
+
+	filter := All(relID)
+	regFilter := world.Cache().Register(filter)
+	query := world.Query(&regFilter)
+	assert.Equal(t, 8, query.Count())
+	cnt := 0
+	for query.Next() {
+		cnt++
+	}
+	assert.Equal(t, 8, cnt)
+	world.Cache().Unregister(&regFilter)
+
+	filter2 := RelationFilter{Filter: All(relID), Target: targ1}
+	regFilter2 := world.Cache().Register(&filter2)
+	query = world.Query(&regFilter2)
+	assert.Equal(t, 4, query.Count())
+	query.Close()
+	world.Cache().Unregister(&regFilter2)
+
+	filter2 = RelationFilter{Filter: All(relID), Target: targ2}
+	regFilter2 = world.Cache().Register(&filter2)
+	query = world.Query(&regFilter2)
+	assert.Equal(t, 4, query.Count())
+	query.Close()
+	world.Cache().Unregister(&regFilter2)
+
+	filter2 = RelationFilter{Filter: All(relID), Target: targ3}
+	regFilter2 = world.Cache().Register(&filter2)
+	query = world.Query(&regFilter2)
+	assert.Equal(t, 0, query.Count())
 	query.Close()
+	world.Cache().Unregister(&regFilter2)
 }
 
 func TestWorldRelation(t *testing.T) {