Repository: mlange-42/arche
Pull request #9 (2023-02-06 17:06:20)

Implement Queries


Patch:
diff --git a/.gitignore b/.gitignore
index 46620af..e6ac766 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,1 +1,2 @@
 /coverage.out
+/*.pprof
\ No newline at end of file
diff --git a/ecs/query.go b/ecs/query.go
new file mode 100644
index 0000000..b1f80f4
--- /dev/null
+++ b/ecs/query.go
@@ -0,0 +1,87 @@
+package ecs
+
+import (
+	"unsafe"
+)
+
+// Query is an iterator to iterate entities
+type Query struct {
+	archetypes []archetypeIter
+	index      int
+	done       bool
+}
+
+// NewQuery creates a new QueryIter
+func NewQuery(arches []archetypeIter) Query {
+	return Query{
+		archetypes: arches,
+		index:      0,
+		done:       false,
+	}
+}
+
+// Next proceeds to the next entity
+func (q *Query) Next() bool {
+	if q.done {
+		return false
+	}
+	for {
+		if q.archetypes[q.index].Next() {
+			return true
+		}
+		q.index++
+		if q.index >= len(q.archetypes) {
+			q.done = true
+			return false
+		}
+	}
+}
+
+// Has returns whether the current entity has the given component
+func (q *Query) Has(comp ID) bool {
+	return q.archetypes[q.index].Has(comp)
+}
+
+// Get returns the pointer to the given component at the iterator's position
+func (q *Query) Get(comp ID) unsafe.Pointer {
+	return q.archetypes[q.index].Get(comp)
+}
+
+// Entity returns the entity at the iterator's position
+func (q *Query) Entity() Entity {
+	return q.archetypes[q.index].Entity()
+}
+
+type archetypeIter struct {
+	Archetype *Archetype
+	Length    int
+	Index     int
+}
+
+func newArchetypeIter(arch *Archetype) archetypeIter {
+	return archetypeIter{
+		Archetype: arch,
+		Length:    int(arch.Len()),
+		Index:     -1,
+	}
+}
+
+func (it *archetypeIter) Next() bool {
+	it.Index++
+	return it.Index < it.Length
+}
+
+// Has returns whether the current entity has the given component
+func (it *archetypeIter) Has(comp ID) bool {
+	return it.Archetype.HasComponent(comp)
+}
+
+// Get returns the pointer to the given component at the iterator's position
+func (it *archetypeIter) Get(comp ID) unsafe.Pointer {
+	return it.Archetype.Get(it.Index, comp)
+}
+
+// Entity returns the entity at the iterator's position
+func (it *archetypeIter) Entity() Entity {
+	return it.Archetype.GetEntity(it.Index)
+}
diff --git a/ecs/world.go b/ecs/world.go
index ec12f96..7eea529 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -6,42 +6,31 @@ import (
 	"unsafe"
 )
 
-// World is the interface for the ECS world
-type World interface {
-	NewEntity() Entity
-	RemEntity(entity Entity) bool
-	Get(entity Entity, comps ID) unsafe.Pointer
-	Has(entity Entity, comps ID) bool
-	Add(entity Entity, comps ...ID)
-	Remove(entity Entity, comps ...ID)
-	Alive(entity Entity) bool
-	Registry() *ComponentRegistry
-}
-
 // NewWorld creates a new World
 func NewWorld() World {
-	return newWorld()
-}
-
-func newWorld() *world {
-	return &world{
-		entities:   []entityIndex{},
-		entityPool: NewEntityPool(),
-		registry:   NewComponentRegistry(),
-		archetypes: []Archetype{NewArchetype()},
+	return World{
+		entities:         []entityIndex{},
+		entityPool:       NewEntityPool(),
+		registry:         NewComponentRegistry(),
+		archetypes:       []Archetype{NewArchetype()},
+		archetypeLengths: []int{0},
 	}
 }
 
-type world struct {
-	entities   []entityIndex
-	archetypes []Archetype
-	entityPool EntityPool
-	registry   ComponentRegistry
+// World holds all ECS data
+type World struct {
+	entities         []entityIndex
+	archetypes       []Archetype
+	archetypeLengths []int
+	entityPool       EntityPool
+	registry         ComponentRegistry
 }
 
-func (w *world) NewEntity() Entity {
+// NewEntity creates a new or recycled entity
+func (w *World) NewEntity() Entity {
 	entity := w.entityPool.Get()
 	idx := w.archetypes[0].Add(entity)
+	w.archetypeLengths[0]++
 	if int(entity.id) == len(w.entities) {
 		w.entities = append(w.entities, entityIndex{0, idx})
 	} else {
@@ -50,7 +39,8 @@ func (w *world) NewEntity() Entity {
 	return entity
 }
 
-func (w *world) RemEntity(entity Entity) bool {
+// RemEntity recycles an entity
+func (w *World) RemEntity(entity Entity) bool {
 	if !w.entityPool.Alive(entity) {
 		return false
 	}
@@ -58,6 +48,8 @@ func (w *world) RemEntity(entity Entity) bool {
 	index := w.entities[entity.id]
 	oldArch := &w.archetypes[index.arch]
 	swapped := oldArch.Remove(int(index.index))
+	w.archetypeLengths[index.arch]--
+
 	w.entityPool.Recycle(entity)
 
 	if swapped {
@@ -69,7 +61,8 @@ func (w *world) RemEntity(entity Entity) bool {
 	return true
 }
 
-func (w *world) Get(entity Entity, comp ID) unsafe.Pointer {
+// Get returns a component for an entity
+func (w *World) Get(entity Entity, comp ID) unsafe.Pointer {
 	index := w.entities[entity.id]
 	arch := w.archetypes[index.arch]
 
@@ -80,13 +73,15 @@ func (w *world) Get(entity Entity, comp ID) unsafe.Pointer {
 	return arch.Get(int(index.index), comp)
 }
 
-func (w *world) Has(entity Entity, comp ID) bool {
+// Has returns whether an entity has a component
+func (w *World) Has(entity Entity, comp ID) bool {
 	index := w.entities[entity.id]
 	arch := w.archetypes[index.arch]
 	return arch.HasComponent(comp)
 }
 
-func (w *world) Add(entity Entity, comps ...ID) {
+// Add adds components to an entity
+func (w *World) Add(entity Entity, comps ...ID) {
 	if len(comps) == 0 {
 		return
 	}
@@ -117,8 +112,10 @@ func (w *world) Add(entity Entity, comps ...ID) {
 	}
 
 	newIndex := arch.AddPointer(entity, allComps...)
+	w.archetypeLengths[archIdx]++
 
 	swapped := oldArch.Remove(int(index.index))
+	w.archetypeLengths[index.arch]--
 
 	if swapped {
 		swapEntity := oldArch.GetEntity(int(index.index))
@@ -127,7 +124,8 @@ func (w *world) Add(entity Entity, comps ...ID) {
 	w.entities[entity.id] = entityIndex{archIdx, newIndex}
 }
 
-func (w *world) Remove(entity Entity, comps ...ID) {
+// Remove removes components from an entity
+func (w *World) Remove(entity Entity, comps ...ID) {
 	if len(comps) == 0 {
 		return
 	}
@@ -160,8 +158,11 @@ func (w *world) Remove(entity Entity, comps ...ID) {
 	}
 
 	newIndex := arch.AddPointer(entity, allComps...)
+	w.archetypeLengths[archIdx]++
 
 	swapped := oldArch.Remove(int(index.index))
+	w.archetypeLengths[index.arch]--
+
 	if swapped {
 		swapEntity := oldArch.GetEntity(int(index.index))
 		w.entities[swapEntity.id].index = index.index
@@ -169,7 +170,7 @@ func (w *world) Remove(entity Entity, comps ...ID) {
 	w.entities[entity.id] = entityIndex{archIdx, newIndex}
 }
 
-func (w *world) findArchetype(mask Mask) (int, bool) {
+func (w *World) findArchetype(mask Mask) (int, bool) {
 	for i, a := range w.archetypes {
 		if a.mask == mask {
 			return i, true
@@ -178,7 +179,7 @@ func (w *world) findArchetype(mask Mask) (int, bool) {
 	return 0, false
 }
 
-func (w *world) createArchetype(comps ...ID) int {
+func (w *World) createArchetype(comps ...ID) int {
 	sort.Slice(comps, func(i, j int) bool { return comps[i] < comps[j] })
 	types := make([]ComponentType, len(comps))
 	for i, id := range comps {
@@ -186,25 +187,40 @@ func (w *world) createArchetype(comps ...ID) int {
 	}
 	a := NewArchetype(types...)
 	w.archetypes = append(w.archetypes, a)
+	w.archetypeLengths = append(w.archetypeLengths, 0)
 	return len(w.archetypes) - 1
 }
 
-func (w *world) Alive(entity Entity) bool {
+// Alive reports whether an entity is still alive
+func (w *World) Alive(entity Entity) bool {
 	return w.entityPool.Alive(entity)
 }
 
-func (w *world) Registry() *ComponentRegistry {
+// Registry returns the world's ComponentRegistry
+func (w *World) Registry() *ComponentRegistry {
 	return &w.registry
 }
 
+// Query creates a query iterator for the given components
+func (w *World) Query(comps ...ID) Query {
+	mask := NewMask(comps...)
+	arches := []archetypeIter{}
+	for _, arch := range w.archetypes {
+		if arch.mask.Contains(mask) {
+			arches = append(arches, newArchetypeIter(&arch))
+		}
+	}
+	return NewQuery(arches)
+}
+
 // RegisterComponent provides a way to register components via generics
-func RegisterComponent[T any](w World) ID {
+func RegisterComponent[T any](w *World) ID {
 	tp := reflect.TypeOf((*T)(nil)).Elem()
 	return w.Registry().RegisterComponent(tp)
 }
 
 // ComponentID provides a way to get a component's ID via generics
-func ComponentID[T any](w World) ID {
+func ComponentID[T any](w *World) ID {
 	tp := reflect.TypeOf((*T)(nil)).Elem()
 	return w.Registry().ComponentID(tp)
 }
diff --git a/go.mod b/go.mod
index daa4898..9667948 100644
--- a/go.mod
+++ b/go.mod
@@ -4,11 +4,14 @@ go 1.20
 
 require (
 	github.com/marioolofo/go-gameengine-ecs v0.0.0-20230205000850-cead1cc4bf6a
+	github.com/pkg/profile v1.7.0
 	github.com/stretchr/testify v1.8.1
 )
 
 require (
 	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/felixge/fgprof v0.9.3 // indirect
+	github.com/google/pprof v0.0.0-20211214055906-6f57359322fd // indirect
 	github.com/pmezard/go-difflib v1.0.0 // indirect
 	gopkg.in/yaml.v3 v3.0.1 // indirect
 )
diff --git a/go.sum b/go.sum
index e617318..c2d6769 100644
--- a/go.sum
+++ b/go.sum
@@ -1,8 +1,18 @@
+github.com/chzyer/logex v1.1.10/go.mod h1:+Ywpsq7O8HXn0nuIou7OrIPyXbp3wmkHB+jjWRnGsAI=
+github.com/chzyer/readline v0.0.0-20180603132655-2972be24d48e/go.mod h1:nSuG5e5PlCu98SY8svDHJxuZscDgtXS6KTTbou5AhLI=
+github.com/chzyer/test v0.0.0-20180213035817-a1ea475d72b1/go.mod h1:Q3SI9o4m/ZMnBNeIyt5eFwwo7qiLfzFZmjNmxjkiQlU=
 github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
 github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/felixge/fgprof v0.9.3 h1:VvyZxILNuCiUCSXtPtYmmtGvb65nqXh2QFWc0Wpf2/g=
+github.com/felixge/fgprof v0.9.3/go.mod h1:RdbpDgzqYVh/T9fPELJyV7EYJuHB55UTEULNun8eiPw=
+github.com/google/pprof v0.0.0-20211214055906-6f57359322fd h1:1FjCyPC+syAzJ5/2S8fqdZK1R22vvA0J7JZKcuOIQ7Y=
+github.com/google/pprof v0.0.0-20211214055906-6f57359322fd/go.mod h1:KgnwoLYCZ8IQu3XUZ8Nc/bM9CCZFOyjUNOSygVozoDg=
+github.com/ianlancetaylor/demangle v0.0.0-20210905161508-09a460cdf81d/go.mod h1:aYm2/VgdVmcIU8iMfdMvDMsRAQjcfZSKFby6HOFvi/w=
 github.com/marioolofo/go-gameengine-ecs v0.0.0-20230205000850-cead1cc4bf6a h1:jekwEG0D06sirA4kYHVfEbikefM7pvcnqCxtj/cnwmU=
 github.com/marioolofo/go-gameengine-ecs v0.0.0-20230205000850-cead1cc4bf6a/go.mod h1:YptmFsn359Z4KR6GK4xoFb74auGWY4uvnlpjGNOTtEg=
+github.com/pkg/profile v1.7.0 h1:hnbDkaNWPCLMO9wGLdBFTIZvzDrDfBM2072E1S9gJkA=
+github.com/pkg/profile v1.7.0/go.mod h1:8Uer0jas47ZQMJ7VD+OHknK4YDY07LPUC6dEvqDjvNo=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
 github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
 github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
@@ -12,6 +22,7 @@ github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/
 github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
 github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk=
 github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
+golang.org/x/sys v0.0.0-20211007075335-d3039528d8ac/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/profile/main/profile.go b/profile/main/profile.go
new file mode 100644
index 0000000..32f8cc1
--- /dev/null
+++ b/profile/main/profile.go
@@ -0,0 +1,49 @@
+package main
+
+// Profiling:
+// go build ./profile/main/profile.go
+// profile
+// go tool pprof -http=":8000" profile cpu.pprof
+// go tool pprof -http=":8000" profile mem.pprof
+
+import (
+	"github.com/mlange-42/arche/ecs"
+	"github.com/pkg/profile"
+)
+
+type position struct {
+	X int
+	Y int
+}
+
+type rotation struct {
+	Angle int
+}
+
+func main() {
+	defer profile.Start(profile.CPUProfile, profile.ProfilePath(".")).Stop()
+
+	count := 1000
+	iters := 1000
+	rounds := 100
+
+	for i := 0; i < rounds; i++ {
+		world := ecs.NewWorld()
+
+		posID := ecs.RegisterComponent[position](&world)
+		rotID := ecs.RegisterComponent[rotation](&world)
+
+		for j := 0; j < count; j++ {
+			entity := world.NewEntity()
+			world.Add(entity, posID, rotID)
+		}
+
+		for j := 0; j < iters; j++ {
+			query := world.Query(posID, rotID)
+			for query.Next() {
+				pos := (*position)(query.Get(posID))
+				_ = pos
+			}
+		}
+	}
+}


Test patch:
diff --git a/benchmark/arche_test.go b/benchmark/arche_test.go
index 9d187d1..8b67e13 100644
--- a/benchmark/arche_test.go
+++ b/benchmark/arche_test.go
@@ -7,7 +7,7 @@ import (
 	"github.com/mlange-42/arche/ecs"
 )
 
-func runArche(b *testing.B, count int) {
+func runArcheArchetype(b *testing.B, count int) {
 	world := ecs.NewWorld()
 
 	comps := []ecs.ComponentType{
@@ -33,14 +33,58 @@ func runArche(b *testing.B, count int) {
 	}
 }
 
-func BenchmarkArche100(b *testing.B) {
-	runArche(b, 100)
+func BenchmarkArcheArchetype100(b *testing.B) {
+	runArcheArchetype(b, 100)
 }
 
-func BenchmarkArche1000(b *testing.B) {
-	runArche(b, 1000)
+func BenchmarkArcheArchetype1000(b *testing.B) {
+	runArcheArchetype(b, 1000)
 }
 
-func BenchmarkArche10000(b *testing.B) {
-	runArche(b, 10000)
+func BenchmarkArcheArchetype10000(b *testing.B) {
+	runArcheArchetype(b, 10000)
+}
+
+func runArcheWorld(b *testing.B, count int) {
+	world := ecs.NewWorld()
+
+	posID := ecs.RegisterComponent[position](&world)
+	rotID := ecs.RegisterComponent[rotation](&world)
+
+	for i := 0; i < count; i++ {
+		entity := world.NewEntity()
+		world.Add(entity, posID, rotID)
+	}
+
+	for i := 0; i < b.N; i++ {
+		/*
+			b.StopTimer()
+			mask := ecs.NewMask(posID, rotID)
+			b.StartTimer()
+			world.IterQuery(mask, func(entity ecs.Entity) {
+				pos := (*position)(world.Get(entity, posID))
+				_ = pos
+			})
+		*/
+
+		b.StopTimer()
+		query := world.Query(posID, rotID)
+		b.StartTimer()
+		for query.Next() {
+			pos := (*position)(query.Get(posID))
+			_ = pos
+		}
+	}
+}
+
+/*func BenchmarkArcheWorld100(b *testing.B) {
+	runArcheWorld(b, 100)
+}*/
+
+func BenchmarkArcheWorld1000(b *testing.B) {
+	runArcheWorld(b, 1000)
+}
+
+func BenchmarkArcheWorld10000(b *testing.B) {
+	runArcheWorld(b, 10000)
 }
diff --git a/ecs/query_test.go b/ecs/query_test.go
new file mode 100644
index 0000000..d4a6416
--- /dev/null
+++ b/ecs/query_test.go
@@ -0,0 +1,65 @@
+package ecs
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestQuery(t *testing.T) {
+	w := NewWorld()
+
+	posID := RegisterComponent[position](&w)
+	rotID := RegisterComponent[rotation](&w)
+
+	e0 := w.NewEntity()
+	e1 := w.NewEntity()
+	e2 := w.NewEntity()
+	e3 := w.NewEntity()
+	e4 := w.NewEntity()
+
+	w.Add(e0, posID)
+	w.Add(e1, posID, rotID)
+	w.Add(e2, posID, rotID)
+	w.Add(e3, rotID)
+	w.Add(e4, rotID)
+
+	q := w.Query(posID, rotID)
+	cnt := 0
+	for q.Next() {
+		ent := q.Entity()
+		pos := (*position)(q.Get(posID))
+		rot := (*rotation)(q.Get(rotID))
+		_ = ent
+		_ = pos
+		_ = rot
+		cnt++
+	}
+	assert.Equal(t, 2, cnt)
+
+	q = w.Query(posID)
+	cnt = 0
+	for q.Next() {
+		ent := q.Entity()
+		pos := (*position)(q.Get(posID))
+		_ = ent
+		_ = pos
+		cnt++
+	}
+	assert.Equal(t, 3, cnt)
+
+	q = w.Query(rotID)
+	cnt = 0
+	for q.Next() {
+		ent := q.Entity()
+		rot := (*rotation)(q.Get(rotID))
+		_ = ent
+		_ = rot
+		hasPos := q.Has(posID)
+		_ = hasPos
+		cnt++
+	}
+	assert.Equal(t, 4, cnt)
+
+	assert.False(t, q.Next())
+}
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 53e7b32..9ac5893 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -7,7 +7,7 @@ import (
 )
 
 func TestWorldEntites(t *testing.T) {
-	w := newWorld()
+	w := NewWorld()
 
 	assert.Equal(t, Entity{0, 0}, w.NewEntity())
 	assert.Equal(t, Entity{1, 0}, w.NewEntity())
@@ -37,10 +37,10 @@ func TestWorldEntites(t *testing.T) {
 }
 
 func TestWorldComponents(t *testing.T) {
-	w := newWorld()
+	w := NewWorld()
 
-	posID := RegisterComponent[position](w)
-	rotID := RegisterComponent[rotation](w)
+	posID := RegisterComponent[position](&w)
+	rotID := RegisterComponent[rotation](&w)
 
 	e0 := w.NewEntity()
 	e1 := w.NewEntity()
@@ -94,10 +94,10 @@ func TestWorldComponents(t *testing.T) {
 }
 
 func TestWorldGetComponents(t *testing.T) {
-	w := newWorld()
+	w := NewWorld()
 
-	posID := RegisterComponent[position](w)
-	rotID := RegisterComponent[rotation](w)
+	posID := RegisterComponent[position](&w)
+	rotID := RegisterComponent[rotation](&w)
 
 	e0 := w.NewEntity()
 	e1 := w.NewEntity()
@@ -130,11 +130,29 @@ func TestWorldGetComponents(t *testing.T) {
 	assert.True(t, pos2 == nil)
 }
 
+func TestWorldIter(t *testing.T) {
+	world := NewWorld()
+
+	posID := RegisterComponent[position](&world)
+	rotID := RegisterComponent[rotation](&world)
+
+	for i := 0; i < 1000; i++ {
+		entity := world.NewEntity()
+		world.Add(entity, posID, rotID)
+	}
+
+	query := world.Query(posID, rotID)
+	for query.Next() {
+		pos := (*position)(query.Get(posID))
+		_ = pos
+	}
+}
+
 func TestRegisterComponents(t *testing.T) {
 	world := NewWorld()
 
-	RegisterComponent[position](world)
+	RegisterComponent[position](&world)
 
-	assert.Equal(t, ID(0), ComponentID[position](world))
-	assert.Equal(t, ID(1), ComponentID[rotation](world))
+	assert.Equal(t, ID(0), ComponentID[position](&world))
+	assert.Equal(t, ID(1), ComponentID[rotation](&world))
 }