Repository: mlange-42/arche (go)

Issue:
Split archetypes and archetype graph
Currently, the archetype graph sits in the archetypes themself. This means that arechetypes are created for component combinations that don't appear in the model.

This should be split.

Pull request description:
Archetype graph
- Split archetype graph out of archetypes
- Reduce size of component registry by using slice instead of fixed-size array

Fixes #112

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a1f4da2..0ab0679 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,9 +1,16 @@
 # Changelog
 
-## [[unpublished]](https://github.com/mlange-42/arche/compare/v0.4.1...main)
+## [[unpublished]](https://github.com/mlange-42/arche/compare/v0.4.2...main)
 
 Nothing
 
+## [[v0.4.2]](https://github.com/mlange-42/arche/compare/v0.4.1...v0.4.2)
+
+## Other
+
+* Avoid creation of unused archetypes by splitting the archetype graph out of the actual archetypes (#113)
+* Use slice instead of fixed-size array for type lookup in component registry (#113)
+
 ## [[v0.4.1]](https://github.com/mlange-42/arche/compare/v0.4.0...v0.4.1)
 
 ## Bugfixes
diff --git a/benchmark/profile/iter/main.go b/benchmark/profile/iter/main.go
index bf7bd2d..4943754 100644
--- a/benchmark/profile/iter/main.go
+++ b/benchmark/profile/iter/main.go
@@ -12,12 +12,13 @@ import (
 )
 
 type position struct {
-	X int
-	Y int
+	X float64
+	Y float64
 }
 
-type rotation struct {
-	Angle int
+type velocity struct {
+	X float64
+	Y float64
 }
 
 func main() {
@@ -42,17 +43,21 @@ func run(rounds, iters, entities int) {
 		)
 
 		posID := ecs.ComponentID[position](&world)
-		rotID := ecs.ComponentID[rotation](&world)
+		velID := ecs.ComponentID[velocity](&world)
 
 		for j := 0; j < entities; j++ {
-			_ = world.NewEntity(posID, rotID)
+			_ = world.NewEntity(posID, velID)
 		}
 
+		filter := ecs.All(posID, velID)
+
 		for j := 0; j < iters; j++ {
-			query := world.Query(ecs.All(posID, rotID))
+			query := world.Query(filter)
 			for query.Next() {
 				pos := (*position)(query.Get(posID))
-				pos.X = 1
+				vel := (*velocity)(query.Get(velID))
+				pos.X += vel.X
+				pos.Y += vel.Y
 			}
 		}
 	}
diff --git a/ecs/archetype.go b/ecs/archetype.go
index 92f3f34..294909d 100644
--- a/ecs/archetype.go
+++ b/ecs/archetype.go
@@ -7,6 +7,45 @@ import (
 	"github.com/mlange-42/arche/ecs/stats"
 )
 
+// archetypeNode is a node in the archetype graph
+type archetypeNode struct {
+	mask      Mask
+	archetype *archetype
+	toAdd     []*archetypeNode
+	toRemove  []*archetypeNode
+}
+
+// Creates a new archetypeNode
+func newArchetypeNode(mask Mask) archetypeNode {
+	return archetypeNode{
+		mask:     mask,
+		toAdd:    make([]*archetypeNode, MaskTotalBits),
+		toRemove: make([]*archetypeNode, MaskTotalBits),
+	}
+}
+
+// GetTransitionAdd returns the archetypeNode resulting from adding a component
+func (a *archetypeNode) GetTransitionAdd(id ID) (*archetypeNode, bool) {
+	p := a.toAdd[id]
+	return p, p != nil
+}
+
+// GetTransitionRemove returns the archetypeNode resulting from removing a component
+func (a *archetypeNode) GetTransitionRemove(id ID) (*archetypeNode, bool) {
+	p := a.toRemove[id]
+	return p, p != nil
+}
+
+// SetTransitionAdd sets the archetypeNode resulting from adding a component
+func (a *archetypeNode) SetTransitionAdd(id ID, to *archetypeNode) {
+	a.toAdd[id] = to
+}
+
+// SetTransitionRemove sets the archetypeNode resulting from removing a component
+func (a *archetypeNode) SetTransitionRemove(id ID, to *archetypeNode) {
+	a.toRemove[id] = to
+}
+
 // archetype represents an ECS archetype
 type archetype struct {
 	Mask Mask
@@ -16,12 +55,11 @@ type archetype struct {
 	references []*storage
 	entities   genericStorage[Entity]
 	components []storage
-	toAdd      []*archetype
-	toRemove   []*archetype
+	graphNode  *archetypeNode
 }
 
 // Init initializes an archetype
-func (a *archetype) Init(capacityIncrement int, forStorage bool, components ...componentType) {
+func (a *archetype) Init(node *archetypeNode, capacityIncrement int, forStorage bool, components ...componentType) {
 	var mask Mask
 	if len(components) > 0 {
 		a.Ids = make([]ID, len(components))
@@ -43,10 +81,9 @@ func (a *archetype) Init(capacityIncrement int, forStorage bool, components ...c
 		a.references[c.ID] = &a.components[i]
 	}
 
+	a.graphNode = node
 	a.Mask = mask
 	a.entities = genericStorage[Entity]{}
-	a.toAdd = make([]*archetype, MaskTotalBits)
-	a.toRemove = make([]*archetype, MaskTotalBits)
 	a.entities.Init(capacityIncrement, forStorage)
 }
 
@@ -136,28 +173,6 @@ func (a *archetype) Zero(index uint32, id ID) {
 	a.references[id].Zero(index)
 }
 
-// GetTransitionAdd returns the archetype resulting from adding a component
-func (a *archetype) GetTransitionAdd(id ID) (*archetype, bool) {
-	p := a.toAdd[id]
-	return p, p != nil
-}
-
-// GetTransitionRemove returns the archetype resulting from removing a component
-func (a *archetype) GetTransitionRemove(id ID) (*archetype, bool) {
-	p := a.toRemove[id]
-	return p, p != nil
-}
-
-// SetTransitionAdd sets the archetype resulting from adding a component
-func (a *archetype) SetTransitionAdd(id ID, to *archetype) {
-	a.toAdd[id] = to
-}
-
-// SetTransitionRemove sets the archetype resulting from removing a component
-func (a *archetype) SetTransitionRemove(id ID, to *archetype) {
-	a.toRemove[id] = to
-}
-
 // Stats generates statistics for an archetype
 func (a *archetype) Stats(reg *componentRegistry) stats.ArchetypeStats {
 	ids := a.Components()
diff --git a/ecs/registry.go b/ecs/registry.go
index ddc8469..4c156b5 100644
--- a/ecs/registry.go
+++ b/ecs/registry.go
@@ -5,13 +5,14 @@ import "reflect"
 // componentRegistry keeps track of component IDs
 type componentRegistry struct {
 	Components map[reflect.Type]ID
-	Types      [MaskTotalBits]reflect.Type
+	Types      []reflect.Type
 }
 
 // newComponentRegistry creates a new ComponentRegistry
 func newComponentRegistry() componentRegistry {
 	return componentRegistry{
 		Components: map[reflect.Type]ID{},
+		Types:      make([]reflect.Type, MaskTotalBits),
 	}
 }
 
diff --git a/ecs/storage.go b/ecs/storage.go
index 90b8491..858842d 100644
--- a/ecs/storage.go
+++ b/ecs/storage.go
@@ -38,8 +38,7 @@ func (s *storage) Init(tp reflect.Type, increment int, forStorage bool) {
 
 // Get retrieves an unsafe pointer to an element
 func (s *storage) Get(index uint32) unsafe.Pointer {
-	ptr := unsafe.Add(s.bufferAddress, uintptr(index)*s.itemSize)
-	return ptr
+	return unsafe.Add(s.bufferAddress, uintptr(index)*s.itemSize)
 }
 
 // Add adds an element to the end of the storage
diff --git a/ecs/world.go b/ecs/world.go
index 61cf82f..397b38a 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -23,6 +23,7 @@ type World struct {
 	config     Config
 	entities   []entityIndex
 	archetypes pagedArr32[archetype]
+	graph      pagedArr32[archetypeNode]
 	entityPool entityPool
 	bitPool    bitPool
 	registry   componentRegistry
@@ -58,10 +59,12 @@ func fromConfig(conf Config) World {
 		bitPool:    newBitPool(),
 		registry:   newComponentRegistry(),
 		archetypes: pagedArr32[archetype]{},
+		graph:      pagedArr32[archetypeNode]{},
 		locks:      Mask{},
 		listener:   nil,
 	}
-	w.createArchetype(Mask{}, false)
+	node := w.createArchetypeNode(Mask{})
+	w.createArchetype(node, false)
 	return w
 }
 
@@ -405,6 +408,7 @@ func (w *World) Stats() *stats.WorldStats {
 	}
 }
 
+// Copies a component to an entity
 func (w *World) copyTo(entity Entity, id ID, comp interface{}) unsafe.Pointer {
 	if !w.Has(entity, id) {
 		panic("can't copy component into entity that has no such component type")
@@ -415,55 +419,73 @@ func (w *World) copyTo(entity Entity, id ID, comp interface{}) unsafe.Pointer {
 	return arch.Set(index.index, id, comp)
 }
 
+// Tries to find an archetype by traversing the archetype graph,
+// searching by mask and extending the graph if necessary.
+// A new archetype is created for the final graph node if not already present.
 func (w *World) findOrCreateArchetype(start *archetype, add []ID, rem []ID) *archetype {
-	curr := start
+	curr := start.graphNode
 	mask := start.Mask
-	maxRem := len(rem) - 1
-	maxAdd := len(add) - 1
-	for i, id := range rem {
+	for _, id := range rem {
 		mask.Set(id, false)
 		if next, ok := curr.GetTransitionRemove(id); ok {
 			curr = next
 		} else {
-			next, _ := w.findOrCreateArchetypeSlow(mask, i == maxRem && maxAdd == 0)
+			next, _ := w.findOrCreateArchetypeSlow(mask)
 			next.SetTransitionAdd(id, curr)
 			curr.SetTransitionRemove(id, next)
 			curr = next
 		}
 	}
-	for i, id := range add {
+	for _, id := range add {
 		mask.Set(id, true)
 		if next, ok := curr.GetTransitionAdd(id); ok {
 			curr = next
 		} else {
-			next, _ := w.findOrCreateArchetypeSlow(mask, i == maxAdd)
+			next, _ := w.findOrCreateArchetypeSlow(mask)
 			next.SetTransitionRemove(id, curr)
 			curr.SetTransitionAdd(id, next)
 			curr = next
 		}
 	}
-	return curr
+	if curr.archetype == nil {
+		w.createArchetype(curr, true)
+	}
+	return curr.archetype
 }
 
-func (w *World) findOrCreateArchetypeSlow(mask Mask, forStorage bool) (*archetype, bool) {
-	if arch, ok := w.findArchetype(mask); ok {
+// Tries to find an archetype for a mask, when it can't be reached through the archetype graph.
+// Creates an archetype graph node.
+func (w *World) findOrCreateArchetypeSlow(mask Mask) (*archetypeNode, bool) {
+	if arch, ok := w.findArchetypeSlow(mask); ok {
 		return arch, false
 	}
-	return w.createArchetype(mask, forStorage), true
+	return w.createArchetypeNode(mask), true
 }
 
-func (w *World) findArchetype(mask Mask) (*archetype, bool) {
-	length := w.archetypes.Len()
+// Searches for an archetype by a mask.
+func (w *World) findArchetypeSlow(mask Mask) (*archetypeNode, bool) {
+	length := w.graph.Len()
 	for i := 0; i < length; i++ {
-		arch := w.archetypes.Get(i)
-		if arch.Mask == mask {
+		arch := w.graph.Get(i)
+		if arch.mask == mask {
 			return arch, true
 		}
 	}
 	return nil, false
 }
 
-func (w *World) createArchetype(mask Mask, forStorage bool) *archetype {
+// Creates a node in the archetype graph.
+func (w *World) createArchetypeNode(mask Mask) *archetypeNode {
+	w.graph.Add(newArchetypeNode(mask))
+	node := w.graph.Get(w.graph.Len() - 1)
+	return node
+}
+
+// Creates an archetype for the given archetype graph node.
+// Initializes the archetype with a capacity according to CapacityIncrement if forStorage is true,
+// and with a capacity of 1 otherwise.
+func (w *World) createArchetype(node *archetypeNode, forStorage bool) *archetype {
+	mask := node.mask
 	count := int(mask.TotalBitsSet())
 	types := make([]componentType, count)
 
@@ -475,9 +497,11 @@ func (w *World) createArchetype(mask Mask, forStorage bool) *archetype {
 			idx++
 		}
 	}
+
 	w.archetypes.Add(archetype{})
 	arch := w.archetypes.Get(w.archetypes.Len() - 1)
-	arch.Init(w.config.CapacityIncrement, forStorage, types...)
+	arch.Init(node, w.config.CapacityIncrement, forStorage, types...)
+	node.archetype = arch
 	return arch
 }
 


Test patch:
diff --git a/ecs/archetype_test.go b/ecs/archetype_test.go
index 2b558ee..1568c93 100644
--- a/ecs/archetype_test.go
+++ b/ecs/archetype_test.go
@@ -14,7 +14,7 @@ func TestArchetype(t *testing.T) {
 	}
 
 	arch := archetype{}
-	arch.Init(32, false, comps...)
+	arch.Init(nil, 32, false, comps...)
 
 	arch.Add(
 		newEntity(0),
@@ -74,7 +74,7 @@ func TestNewArchetype(t *testing.T) {
 		{ID: 1, Type: reflect.TypeOf(rotation{})},
 	}
 	arch := archetype{}
-	arch.Init(32, true, comps...)
+	arch.Init(nil, 32, true, comps...)
 
 	comps = []componentType{
 		{ID: 1, Type: reflect.TypeOf(rotation{})},
@@ -82,7 +82,7 @@ func TestNewArchetype(t *testing.T) {
 	}
 	assert.Panics(t, func() {
 		arch := archetype{}
-		arch.Init(32, true, comps...)
+		arch.Init(nil, 32, true, comps...)
 	})
 }
 
@@ -93,7 +93,7 @@ func BenchmarkArchetypeAccess_1000(b *testing.B) {
 	}
 
 	arch := archetype{}
-	arch.Init(32, true, comps...)
+	arch.Init(nil, 32, true, comps...)
 
 	for i := 0; i < 1000; i++ {
 		arch.Alloc(newEntity(eid(i)), true)
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 6b5e7a5..ed4fc5c 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -133,30 +133,30 @@ func TestWorldComponents(t *testing.T) {
 	maskRot := All(rotID)
 	maskPosRot := All(posID, rotID)
 
-	archNone, ok := w.findArchetype(maskNone)
+	archNone, ok := w.findArchetypeSlow(maskNone)
 	assert.True(t, ok)
-	archPos, ok := w.findArchetype(maskPos)
+	archPos, ok := w.findArchetypeSlow(maskPos)
 	assert.True(t, ok)
-	archRot, ok := w.findArchetype(maskRot)
+	archRot, ok := w.findArchetypeSlow(maskRot)
 	assert.True(t, ok)
-	archPosRot, ok := w.findArchetype(maskPosRot)
+	archPosRot, ok := w.findArchetypeSlow(maskPosRot)
 	assert.True(t, ok)
 
-	assert.Equal(t, 0, int(archNone.Len()))
-	assert.Equal(t, 1, int(archPos.Len()))
-	assert.Equal(t, 1, int(archRot.Len()))
-	assert.Equal(t, 1, int(archPosRot.Len()))
+	assert.Equal(t, 0, int(archNone.archetype.Len()))
+	assert.Equal(t, 1, int(archPos.archetype.Len()))
+	assert.Equal(t, 1, int(archRot.archetype.Len()))
+	assert.Equal(t, 1, int(archPosRot.archetype.Len()))
 
 	w.Remove(e1, posID)
 
-	assert.Equal(t, 0, int(archNone.Len()))
-	assert.Equal(t, 1, int(archPos.Len()))
-	assert.Equal(t, 2, int(archRot.Len()))
-	assert.Equal(t, 0, int(archPosRot.Len()))
+	assert.Equal(t, 0, int(archNone.archetype.Len()))
+	assert.Equal(t, 1, int(archPos.archetype.Len()))
+	assert.Equal(t, 2, int(archRot.archetype.Len()))
+	assert.Equal(t, 0, int(archPosRot.archetype.Len()))
 
 	w.Add(e0, rotID)
-	assert.Equal(t, 0, int(archPos.Len()))
-	assert.Equal(t, 1, int(archPosRot.Len()))
+	assert.Equal(t, 0, int(archPos.archetype.Len()))
+	assert.Equal(t, 1, int(archPosRot.archetype.Len()))
 
 	w.Remove(e2, rotID)
 	// No-op add/remove
@@ -420,18 +420,24 @@ func TestArchetypeGraph(t *testing.T) {
 	rotID := ComponentID[rotation](&world)
 
 	archEmpty := world.archetypes.Get(0)
-	arch0 := world.findOrCreateArchetype(archEmpty, []ID{posID}, []ID{})
-	archEmpty2 := world.findOrCreateArchetype(arch0, []ID{}, []ID{posID})
-
+	arch0 := world.findOrCreateArchetype(archEmpty, []ID{posID, velID}, []ID{})
+	archEmpty2 := world.findOrCreateArchetype(arch0, []ID{}, []ID{velID, posID})
 	assert.Equal(t, archEmpty, archEmpty2)
+	assert.Equal(t, 2, world.archetypes.Len())
+	assert.Equal(t, 3, world.graph.Len())
+
+	archEmpty3 := world.findOrCreateArchetype(arch0, []ID{}, []ID{posID, velID})
+	assert.Equal(t, archEmpty, archEmpty3)
+	assert.Equal(t, 2, world.archetypes.Len())
+	assert.Equal(t, 4, world.graph.Len())
 
 	arch01 := world.findOrCreateArchetype(arch0, []ID{velID}, []ID{})
 	arch012 := world.findOrCreateArchetype(arch01, []ID{rotID}, []ID{})
 
 	assert.Equal(t, []ID{0, 1, 2}, arch012.Ids)
 
-	archEmpty3 := world.findOrCreateArchetype(arch012, []ID{}, []ID{posID, rotID, velID})
-	assert.Equal(t, archEmpty, archEmpty3)
+	archEmpty4 := world.findOrCreateArchetype(arch012, []ID{}, []ID{posID, rotID, velID})
+	assert.Equal(t, archEmpty, archEmpty4)
 }
 
 func TestWorldListener(t *testing.T) {
@@ -565,21 +571,26 @@ func Test1000Archetypes(t *testing.T) {
 
 func TestTypeSizes(t *testing.T) {
 	printTypeSize[Entity]()
+	printTypeSize[entityIndex]()
 	printTypeSize[Mask]()
 	printTypeSize[World]()
 	printTypeSizeName[pagedArr32[archetype]]("PagedArr32")
 	printTypeSize[archetype]()
+	printTypeSize[archetypeNode]()
 	printTypeSize[storage]()
+	printTypeSize[entityPool]()
+	printTypeSize[componentRegistry]()
+	printTypeSize[bitPool]()
 	printTypeSize[Query]()
 	printTypeSize[archetypeIter]()
 }
 
 func printTypeSize[T any]() {
 	tp := reflect.TypeOf((*T)(nil)).Elem()
-	fmt.Printf("%16s: %5d B\n", tp.Name(), tp.Size())
+	fmt.Printf("%18s: %5d B\n", tp.Name(), tp.Size())
 }
 
 func printTypeSizeName[T any](name string) {
 	tp := reflect.TypeOf((*T)(nil)).Elem()
-	fmt.Printf("%16s: %5d B\n", name, tp.Size())
+	fmt.Printf("%18s: %5d B\n", name, tp.Size())
 }