Repository: mlange-42/arche
Pull request #36 (2023-02-08 18:47:00)

Paged archetypes
Use pages memory to store archetypes, use pointers instead of indices in entity list.

Pages are a minimal ovrhead, but they make it possible to store refs to artifacts. Speeds up component access through the world/using an entity ID by up to 30%.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 283fef4..0e175e9 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@
 
 * Optimization of `Query` iteration, avoids allocations and makes it approx. 30% faster (#35)
 * Removed method `Query.Count()`, as it was a by-product of the allocations in the above point (#35)
+* Archetypes are stored in a paged collection to use more efficient access by pointers (#36)
 
 ## [[v0.1.4]](https://github.com/mlange-42/arche/compare/v0.1.3...v0.1.4)
 
diff --git a/README.md b/README.md
index e3c90d2..7f20fbe 100644
--- a/README.md
+++ b/README.md
@@ -91,7 +91,7 @@ func main() {
 		// Iterate it
 		for query.Next() {
 			// Component access through a Query.
-			// About twice as fast as access through the World.
+			// About 20-30% faster than access through the World.
 			// Can also fetch components not in the query.
 			pos := (*Position)(query.Get(positionID))
 			vel := (*Velocity)(query.Get(velocityID))
diff --git a/ecs/entity.go b/ecs/entity.go
index 72c8081..8b51491 100644
--- a/ecs/entity.go
+++ b/ecs/entity.go
@@ -19,6 +19,6 @@ func (e Entity) IsZero() bool {
 }
 
 type entityIndex struct {
-	arch  int
+	arch  *archetype
 	index uint32
 }
diff --git a/ecs/paged.go b/ecs/paged.go
new file mode 100644
index 0000000..5104e40
--- /dev/null
+++ b/ecs/paged.go
@@ -0,0 +1,28 @@
+package ecs
+
+const fixedPageSize = 32
+
+// PagedArr32 is a paged collection working with pages of length 32 arrays
+type PagedArr32[T any] struct {
+	pages   [][fixedPageSize]T
+	len     int
+	lenLast int
+}
+
+func (p *PagedArr32[T]) Add(value T) {
+	if len(p.pages) == 0 || p.lenLast == fixedPageSize {
+		p.pages = append(p.pages, [fixedPageSize]T{})
+		p.lenLast = 0
+	}
+	p.pages[len(p.pages)-1][p.lenLast] = value
+	p.len++
+	p.lenLast++
+}
+
+func (p *PagedArr32[T]) Get(index int) *T {
+	return &p.pages[index/fixedPageSize][index%fixedPageSize]
+}
+
+func (p *PagedArr32[T]) Len() int {
+	return p.len
+}
diff --git a/ecs/world.go b/ecs/world.go
index 65fc450..aa8740c 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -21,13 +21,15 @@ func NewWorld() World {
 func FromConfig(conf Config) World {
 	arch := archetype{}
 	arch.init(conf.CapacityIncrement)
+	arches := PagedArr32[archetype]{}
+	arches.Add(arch)
 	return World{
 		config:     conf,
-		entities:   []entityIndex{{-1, 0}},
+		entities:   []entityIndex{{nil, 0}},
 		entityPool: newEntityPool(conf.CapacityIncrement),
 		bitPool:    newBitPool(),
 		registry:   newComponentRegistry(),
-		archetypes: []archetype{arch},
+		archetypes: arches,
 		locks:      Mask(0),
 	}
 }
@@ -36,7 +38,7 @@ func FromConfig(conf Config) World {
 type World struct {
 	config     Config
 	entities   []entityIndex
-	archetypes []archetype
+	archetypes PagedArr32[archetype]
 	entityPool entityPool
 	bitPool    bitPool
 	registry   componentRegistry
@@ -52,7 +54,7 @@ func (w *World) NewEntity() Entity {
 	w.checkLocked()
 
 	entity := w.entityPool.Get()
-	idx := w.archetypes[0].Add(entity)
+	idx := w.archetypes.Get(0).Add(entity)
 	len := len(w.entities)
 	if int(entity.id) == len {
 		if len == cap(w.entities) {
@@ -60,9 +62,9 @@ func (w *World) NewEntity() Entity {
 			w.entities = make([]entityIndex, len, len+w.config.CapacityIncrement)
 			copy(w.entities, old)
 		}
-		w.entities = append(w.entities, entityIndex{0, idx})
+		w.entities = append(w.entities, entityIndex{w.archetypes.Get(0), idx})
 	} else {
-		w.entities[entity.id] = entityIndex{0, idx}
+		w.entities[entity.id] = entityIndex{w.archetypes.Get(0), idx}
 	}
 	return entity
 }
@@ -76,7 +78,7 @@ func (w *World) RemEntity(entity Entity) {
 	w.checkLocked()
 
 	index := w.entities[entity.id]
-	oldArch := &w.archetypes[index.arch]
+	oldArch := index.arch
 	swapped := oldArch.Remove(int(index.index))
 
 	w.entityPool.Recycle(entity)
@@ -86,7 +88,7 @@ func (w *World) RemEntity(entity Entity) {
 		w.entities[swapEntity.id].index = index.index
 	}
 
-	w.entities[entity.id].arch = -1
+	w.entities[entity.id].arch = nil
 }
 
 // Get returns a pointer th the given component of an [Entity].
@@ -95,7 +97,7 @@ func (w *World) RemEntity(entity Entity) {
 // Panics when called for an already removed entity.
 func (w *World) Get(entity Entity, comp ID) unsafe.Pointer {
 	index := w.entities[entity.id]
-	arch := &w.archetypes[index.arch]
+	arch := index.arch
 
 	if !arch.HasComponent(comp) {
 		return nil
@@ -109,8 +111,7 @@ func (w *World) Get(entity Entity, comp ID) unsafe.Pointer {
 // Panics when called for an already removed entity.
 func (w *World) Has(entity Entity, comp ID) bool {
 	index := w.entities[entity.id]
-	arch := &w.archetypes[index.arch]
-	return arch.HasComponent(comp)
+	return index.arch.HasComponent(comp)
 }
 
 // Add adds components to an [Entity].
@@ -125,7 +126,7 @@ func (w *World) Add(entity Entity, comps ...ID) {
 		return
 	}
 	index := w.entities[entity.id]
-	oldArch := &w.archetypes[index.arch]
+	oldArch := index.arch
 	mask := oldArch.mask
 	for _, comp := range comps {
 		mask.Set(comp, true)
@@ -133,13 +134,11 @@ func (w *World) Add(entity Entity, comps ...ID) {
 
 	oldIDs := oldArch.Components()
 
-	archIdx, ok := w.findArchetype(mask)
+	arch, ok := w.findArchetype(mask)
 	if !ok {
 		ids := append(oldIDs, comps...)
-		archIdx = w.createArchetype(ids...)
+		arch = w.createArchetype(ids...)
 	}
-	arch := &w.archetypes[archIdx]
-	oldArch = &w.archetypes[index.arch]
 
 	allComps := make([]componentPointer, 0, len(oldIDs)+len(comps))
 	for _, id := range oldIDs {
@@ -158,7 +157,7 @@ func (w *World) Add(entity Entity, comps ...ID) {
 		swapEntity := oldArch.GetEntity(int(index.index))
 		w.entities[swapEntity.id].index = index.index
 	}
-	w.entities[entity.id] = entityIndex{archIdx, newIndex}
+	w.entities[entity.id] = entityIndex{arch, newIndex}
 }
 
 // Remove removes components from an entity.
@@ -173,7 +172,7 @@ func (w *World) Remove(entity Entity, comps ...ID) {
 		return
 	}
 	index := w.entities[entity.id]
-	oldArch := &w.archetypes[index.arch]
+	oldArch := index.arch
 	mask := oldArch.mask
 	for _, comp := range comps {
 		mask.Set(comp, false)
@@ -187,12 +186,10 @@ func (w *World) Remove(entity Entity, comps ...ID) {
 		}
 	}
 
-	archIdx, ok := w.findArchetype(mask)
+	arch, ok := w.findArchetype(mask)
 	if !ok {
-		archIdx = w.createArchetype(newIDs...)
+		arch = w.createArchetype(newIDs...)
 	}
-	arch := &w.archetypes[archIdx]
-	oldArch = &w.archetypes[index.arch]
 
 	allComps := make([]componentPointer, 0, len(newIDs))
 	for _, id := range newIDs {
@@ -208,29 +205,30 @@ func (w *World) Remove(entity Entity, comps ...ID) {
 		swapEntity := oldArch.GetEntity(int(index.index))
 		w.entities[swapEntity.id].index = index.index
 	}
-	w.entities[entity.id] = entityIndex{archIdx, newIndex}
+	w.entities[entity.id] = entityIndex{arch, newIndex}
 }
 
-func (w *World) findArchetype(mask Mask) (int, bool) {
-	length := len(w.archetypes)
+func (w *World) findArchetype(mask Mask) (*archetype, bool) {
+	length := w.archetypes.Len()
 	for i := 0; i < length; i++ {
-		if w.archetypes[i].mask == mask {
-			return i, true
+		arch := w.archetypes.Get(i)
+		if arch.mask == mask {
+			return arch, true
 		}
 	}
-	return 0, false
+	return nil, false
 }
 
-func (w *World) createArchetype(comps ...ID) int {
+func (w *World) createArchetype(comps ...ID) *archetype {
 	sort.Slice(comps, func(i, j int) bool { return comps[i] < comps[j] })
 	types := make([]componentType, len(comps))
 	for i, id := range comps {
 		types[i] = componentType{id, w.registry.types[id]}
 	}
-	w.archetypes = append(w.archetypes, archetype{})
-	idx := len(w.archetypes) - 1
-	w.archetypes[idx].init(w.config.CapacityIncrement, types...)
-	return idx
+	w.archetypes.Add(archetype{})
+	arch := w.archetypes.Get(w.archetypes.Len() - 1)
+	arch.init(w.config.CapacityIncrement, types...)
+	return arch
 }
 
 // Alive reports whether an entity is still alive.
@@ -244,12 +242,12 @@ func (w *World) componentID(tp reflect.Type) ID {
 }
 
 func (w *World) nextArchetype(mask Mask, index int) (int, archetypeIter, bool) {
-	len := len(w.archetypes)
+	len := w.archetypes.Len()
 	if index >= len {
 		panic("exceeded end of query")
 	}
 	for i := index + 1; i < len; i++ {
-		a := &w.archetypes[i]
+		a := w.archetypes.Get(i)
 		if a.Len() > 0 && a.mask.Contains(mask) {
 			return i, newArchetypeIter(a), true
 		}


Test patch:
diff --git a/ecs/paged_test.go b/ecs/paged_test.go
new file mode 100644
index 0000000..1526554
--- /dev/null
+++ b/ecs/paged_test.go
@@ -0,0 +1,17 @@
+package ecs
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestPagedArr32(t *testing.T) {
+	a := PagedArr32[int]{}
+
+	for i := 0; i < 66; i++ {
+		a.Add(i)
+		assert.Equal(t, i, *a.Get(i))
+		assert.Equal(t, i+1, a.Len())
+	}
+}
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 4cd008e..213ce87 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -1,6 +1,8 @@
 package ecs
 
 import (
+	"fmt"
+	"reflect"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
@@ -48,14 +50,14 @@ func TestWorldComponents(t *testing.T) {
 	e1 := w.NewEntity()
 	e2 := w.NewEntity()
 
-	assert.Equal(t, 1, len(w.archetypes))
+	assert.Equal(t, 1, w.archetypes.Len())
 
 	w.Add(e0, posID)
-	assert.Equal(t, 2, len(w.archetypes))
+	assert.Equal(t, 2, w.archetypes.Len())
 	w.Add(e1, posID, rotID)
-	assert.Equal(t, 3, len(w.archetypes))
+	assert.Equal(t, 3, w.archetypes.Len())
 	w.Add(e2, posID, rotID)
-	assert.Equal(t, 3, len(w.archetypes))
+	assert.Equal(t, 3, w.archetypes.Len())
 
 	w.Remove(e2, posID)
 
@@ -73,21 +75,21 @@ func TestWorldComponents(t *testing.T) {
 	archPosRot, ok := w.findArchetype(maskPosRot)
 	assert.True(t, ok)
 
-	assert.Equal(t, 0, int(w.archetypes[archNone].Len()))
-	assert.Equal(t, 1, int(w.archetypes[archPos].Len()))
-	assert.Equal(t, 1, int(w.archetypes[archRot].Len()))
-	assert.Equal(t, 1, int(w.archetypes[archPosRot].Len()))
+	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()))
 
 	w.Remove(e1, posID)
 
-	assert.Equal(t, 0, int(w.archetypes[archNone].Len()))
-	assert.Equal(t, 1, int(w.archetypes[archPos].Len()))
-	assert.Equal(t, 2, int(w.archetypes[archRot].Len()))
-	assert.Equal(t, 0, int(w.archetypes[archPosRot].Len()))
+	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()))
 
 	w.Add(e0, rotID)
-	assert.Equal(t, 0, int(w.archetypes[archPos].Len()))
-	assert.Equal(t, 1, int(w.archetypes[archPosRot].Len()))
+	assert.Equal(t, 0, int(archPos.Len()))
+	assert.Equal(t, 1, int(archPosRot.Len()))
 
 	w.Remove(e2, rotID)
 	// No-op add/remove
@@ -204,3 +206,22 @@ func TestRegisterComponents(t *testing.T) {
 	assert.Equal(t, ID(0), ComponentID[position](&world))
 	assert.Equal(t, ID(1), ComponentID[rotation](&world))
 }
+
+func TestTypeSizes(t *testing.T) {
+	printTypeSize[World]()
+	printTypeSizeName[PagedArr32[archetype]]("PagedArr32")
+	printTypeSize[archetype]()
+	printTypeSize[storage]()
+	printTypeSize[Query]()
+	printTypeSize[archetypeIter]()
+}
+
+func printTypeSize[T any]() {
+	tp := reflect.TypeOf((*T)(nil)).Elem()
+	fmt.Printf("%16s: %5db\n", tp.Name(), tp.Size())
+}
+
+func printTypeSizeName[T any](name string) {
+	tp := reflect.TypeOf((*T)(nil)).Elem()
+	fmt.Printf("%16s: %5db\n", name, tp.Size())
+}