Repository: mlange-42/arche
Pull request #464 (2025-01-07 18:03:11)

Optimize entity pool by removing manual growth policy

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


### Details

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

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/71622155/badge)](https://coveralls.io/builds/71622155) |
| :-- | --: |
| Change from base [Build 12656641063](https://coveralls.io/builds/71622045): |  0.0% |
| Covered Lines: | 6514 |
| Relevant Lines: | 6514 |

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


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 614315d..0f92002 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,5 +1,9 @@
 ## [[unpublished]](https://github.com/mlange-42/arche/compare/v0.14.5...main)
 
+### Performance
+
+* Optimizes entity creation by an altered growth policy for archetypes, entity list and entity pool (#464)
+
 ### Other
 
 *  Use mask pointers in all tests and benchmarks (#460)
diff --git a/benchmark/profile/create_many/main.go b/benchmark/profile/create_many/main.go
new file mode 100644
index 0000000..771b3b3
--- /dev/null
+++ b/benchmark/profile/create_many/main.go
@@ -0,0 +1,48 @@
+package main
+
+// Profiling:
+// go build ./benchmark/profile/create_many
+// ./create_many
+// go tool pprof -http=":8000" -nodefraction=0.001 ./create_many cpu.pprof
+// go tool pprof -http=":8000" -nodefraction=0.001 ./create_many 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() {
+
+	iters := 100
+	entities := 1_000_000
+
+	stop := profile.Start(profile.CPUProfile, profile.ProfilePath("."))
+	run(iters, entities)
+	stop.Stop()
+
+	stop = profile.Start(profile.MemProfileAllocs, profile.ProfilePath("."))
+	run(iters, entities)
+	stop.Stop()
+}
+
+func run(iters, entityCount int) {
+	for i := 0; i < iters; i++ {
+		world := ecs.NewWorld(
+			ecs.NewConfig().WithCapacityIncrement(1024),
+		)
+
+		posID := ecs.ComponentID[position](&world)
+		rotID := ecs.ComponentID[rotation](&world)
+
+		ecs.NewBuilder(&world, posID, rotID).NewBatch(entityCount)
+	}
+}
diff --git a/ecs/archetype.go b/ecs/archetype.go
index fe10d3c..15f5e80 100644
--- a/ecs/archetype.go
+++ b/ecs/archetype.go
@@ -93,7 +93,7 @@ func (a *archetype) Init(node *archNode, data *archetypeData, index int32, forSt
 
 	cap := 1
 	if forStorage {
-		cap = int(node.capacityIncrement)
+		cap = int(node.initialCapacity)
 	}
 
 	for i, id := range node.Ids {
@@ -330,7 +330,10 @@ func (a *archetype) extend(by uint32) {
 	if a.cap >= required {
 		return
 	}
-	a.cap = capacityU32(required, a.node.capacityIncrement)
+	for a.cap < required {
+		a.cap *= 2
+	}
+	a.cap = max(a.cap, a.node.initialCapacity)
 
 	old := a.entityBuffer
 	a.entityBuffer = reflect.New(reflect.ArrayOf(int(a.cap), entityType)).Elem()
diff --git a/ecs/archetype_node.go b/ecs/archetype_node.go
index 896db67..7b38d21 100644
--- a/ecs/archetype_node.go
+++ b/ecs/archetype_node.go
@@ -17,21 +17,21 @@ type archNode struct {
 }
 
 type nodeData struct {
-	archetype         *archetype            // The single archetype for nodes without entity relation
-	archetypeMap      map[Entity]*archetype // Mapping from relation targets to archetypes
-	zeroPointer       unsafe.Pointer        // Points to zeroValue for fast access
-	Types             []reflect.Type        // Component type per column
-	Ids               []ID                  // List of component IDs
-	freeIndices       []int32               // Indices of free/inactive archetypes
-	zeroValue         []byte                // Used as source for setting storage to zero
-	archetypes        pagedSlice[archetype] // Storage for archetypes in nodes with entity relation
-	archetypeData     pagedSlice[archetypeData]
-	neighbors         idMap[*archNode] // Mapping from component ID to add/remove, to the resulting archetype
-	capacityIncrement uint32           // Capacity increment
+	archetype       *archetype            // The single archetype for nodes without entity relation
+	archetypeMap    map[Entity]*archetype // Mapping from relation targets to archetypes
+	zeroPointer     unsafe.Pointer        // Points to zeroValue for fast access
+	Types           []reflect.Type        // Component type per column
+	Ids             []ID                  // List of component IDs
+	freeIndices     []int32               // Indices of free/inactive archetypes
+	zeroValue       []byte                // Used as source for setting storage to zero
+	archetypes      pagedSlice[archetype] // Storage for archetypes in nodes with entity relation
+	archetypeData   pagedSlice[archetypeData]
+	neighbors       idMap[*archNode] // Mapping from component ID to add/remove, to the resulting archetype
+	initialCapacity uint32           // Initial capacity of component columns
 }
 
 // Creates a new archNode
-func newArchNode(mask Mask, data *nodeData, relation ID, hasRelation bool, capacityIncrement int, components []componentType) archNode {
+func newArchNode(mask Mask, data *nodeData, relation ID, hasRelation bool, initialCapacity int, components []componentType) archNode {
 	var arch map[Entity]*archetype
 	if hasRelation {
 		arch = map[Entity]*archetype{}
@@ -66,7 +66,7 @@ func newArchNode(mask Mask, data *nodeData, relation ID, hasRelation bool, capac
 	data.Ids = ids
 	data.Types = types
 	data.archetypeMap = arch
-	data.capacityIncrement = uint32(capacityIncrement)
+	data.initialCapacity = uint32(initialCapacity)
 	data.zeroValue = zeroValue
 	data.zeroPointer = zeroPointer
 	data.neighbors = newIDMap[*archNode]()
diff --git a/ecs/pool.go b/ecs/pool.go
index c7ecd4c..b6e7d00 100644
--- a/ecs/pool.go
+++ b/ecs/pool.go
@@ -12,21 +12,19 @@ type number interface {
 // entityPool is an implementation using implicit linked lists.
 // Implements https://skypjack.github.io/2019-05-06-ecs-baf-part-3/
 type entityPool struct {
-	entities          []Entity
-	next              eid
-	available         uint32
-	capacityIncrement uint32
+	entities  []Entity
+	next      eid
+	available uint32
 }
 
 // newEntityPool creates a new, initialized Entity pool.
-func newEntityPool(capacityIncrement uint32) entityPool {
-	entities := make([]Entity, 1, capacityIncrement)
+func newEntityPool(initialCapacity uint32) entityPool {
+	entities := make([]Entity, 1, initialCapacity)
 	entities[0] = Entity{0, math.MaxUint32}
 	return entityPool{
-		entities:          entities,
-		next:              0,
-		available:         0,
-		capacityIncrement: capacityIncrement,
+		entities:  entities,
+		next:      0,
+		available: 0,
 	}
 }
 
@@ -44,11 +42,6 @@ func (p *entityPool) Get() Entity {
 // Allocates and returns a new entity. For internal use.
 func (p *entityPool) getNew() Entity {
 	e := newEntity(eid(len(p.entities)))
-	if len(p.entities) == cap(p.entities) {
-		old := p.entities
-		p.entities = make([]Entity, len(p.entities), len(p.entities)+int(p.capacityIncrement))
-		copy(p.entities, old)
-	}
 	p.entities = append(p.entities, e)
 	return e
 }
diff --git a/ecs/world_internal.go b/ecs/world_internal.go
index e94ad29..35046b6 100644
--- a/ecs/world_internal.go
+++ b/ecs/world_internal.go
@@ -277,12 +277,6 @@ func (w *World) createEntity(arch *archetype) Entity {
 	idx := arch.Alloc(entity)
 	len := len(w.entities)
 	if int(entity.id) == len {
-		if len == cap(w.entities) {
-			old := w.entities
-			w.entities = make([]entityIndex, len, len+w.config.CapacityIncrement)
-			copy(w.entities, old)
-
-		}
 		w.entities = append(w.entities, entityIndex{arch: arch, index: idx})
 		w.targetEntities.ExtendTo(len + w.config.CapacityIncrement)
 	} else {


Test patch:
diff --git a/ecs/archetype_test.go b/ecs/archetype_test.go
index a6caad1..0b875c2 100644
--- a/ecs/archetype_test.go
+++ b/ecs/archetype_test.go
@@ -105,7 +105,7 @@ func TestArchetypeExtend(t *testing.T) {
 	assert.Equal(t, 8, int(arch.Cap()))
 
 	arch.extend(17)
-	assert.Equal(t, 24, int(arch.Cap()))
+	assert.Equal(t, 32, int(arch.Cap()))
 }
 
 func TestArchetypeExtendLayouts(t *testing.T) {
diff --git a/ecs/world_benchmark_test.go b/ecs/world_benchmark_test.go
index 2e02184..df0a911 100644
--- a/ecs/world_benchmark_test.go
+++ b/ecs/world_benchmark_test.go
@@ -100,6 +100,30 @@ func BenchmarkNewEntitiesBatch_10_000_New(b *testing.B) {
 	}
 }
 
+func BenchmarkNewEntitiesBatch_1_000_000_New(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		world := NewWorld(NewConfig().WithCapacityIncrement(1024))
+
+		posID := ComponentID[Position](&world)
+		velID := ComponentID[Velocity](&world)
+
+		world.newEntities(1_000_000, ID{}, false, Entity{}, posID, velID)
+	}
+}
+
+func BenchmarkNewEntities_1_000_000_New(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		world := NewWorld(NewConfig().WithCapacityIncrement(1024))
+
+		posID := ComponentID[Position](&world)
+		velID := ComponentID[Velocity](&world)
+
+		for i := 0; i < 1_000_000; i++ {
+			world.NewEntity(posID, velID)
+		}
+	}
+}
+
 func BenchmarkNewEntities_10_000_Reset(b *testing.B) {
 	b.StopTimer()
 	world := NewWorld(NewConfig().WithCapacityIncrement(1024))
diff --git a/ecs/world_test.go b/ecs/world_test.go
index bd1a32e..ad48915 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -28,8 +28,8 @@ func TestWorldConfig(t *testing.T) {
 	world.NewEntity()
 	world.NewEntity(relID)
 
-	assert.Equal(t, uint32(32), world.nodes.Get(0).capacityIncrement)
-	assert.Equal(t, uint32(8), world.nodes.Get(1).capacityIncrement)
+	assert.Equal(t, uint32(32), world.nodes.Get(0).initialCapacity)
+	assert.Equal(t, uint32(8), world.nodes.Get(1).initialCapacity)
 }
 
 func TestWorldEntites(t *testing.T) {