Repository: mlange-42/arche
Pull request #197 (2023-03-30 21:16:26)

Optimize archetype creation
- Speedup of `pagedSlice.Get(index)` by factor 4, by using a `const` for archetype storage page sizes
- Results in speedup of archetype creation by 40%
- Adds profiling code for archetype creation
- Optimize entity and bit pool code for inlining, cleanup idMap


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7d72fd9..562f640 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -35,6 +35,7 @@
 * Avoid type checks in query when iterating archetypes (#179)
 * Speed up counting entities in queries with a cached filter (#182)
 * Implements a fast and memory-efficient lookup data structure for components ID keys, to reduce the memory footprint of archetypes and the archetype graph (#192)
+* Speedup of archetype creation by 40% by using a `const` for archetype storage page sizes (#197)
 
 ### Bugfixes
 
diff --git a/benchmark/profile/many_arch_build/main.go b/benchmark/profile/many_arch_build/main.go
new file mode 100644
index 0000000..879936d
--- /dev/null
+++ b/benchmark/profile/many_arch_build/main.go
@@ -0,0 +1,47 @@
+package main
+
+// Profiling:
+// go build ./benchmark/profile/many_arch_build
+// many_arch_build
+// go tool pprof -http=":8000" -nodefraction=0.001 many_arch_build cpu.pprof
+// go tool pprof -http=":8000" -nodefraction=0.001 many_arch_build mem.pprof
+
+import (
+	c "github.com/mlange-42/arche/benchmark/arche/common"
+	"github.com/mlange-42/arche/ecs"
+	"github.com/pkg/profile"
+)
+
+func main() {
+
+	count := 1000
+
+	stop := profile.Start(profile.CPUProfile, profile.ProfilePath("."))
+	run(count)
+	stop.Stop()
+
+	stop = profile.Start(profile.MemProfileAllocs, profile.ProfilePath("."))
+	run(count)
+	stop.Stop()
+}
+
+func run(rounds int) {
+	for i := 0; i < rounds; i++ {
+		world := ecs.NewWorld()
+		c.RegisterAll(&world)
+
+		for i := 0; i < 1024; i++ {
+			mask := i
+			add := make([]ecs.ID, 0, 10)
+			for j := 0; j < 10; j++ {
+				id := ecs.ID(j)
+				m := 1 << j
+				if mask&m == m {
+					add = append(add, id)
+				}
+			}
+			entity := world.NewEntity()
+			world.Add(entity, add...)
+		}
+	}
+}
diff --git a/ecs/archetype.go b/ecs/archetype.go
index 328a9b8..0f93813 100644
--- a/ecs/archetype.go
+++ b/ecs/archetype.go
@@ -170,12 +170,13 @@ func (a *archetype) Add(entity Entity, components ...Component) uintptr {
 	a.addEntity(idx, &entity)
 	for _, c := range components {
 		lay := a.getLayout(c.ID)
-		if lay.itemSize == 0 {
+		size := lay.itemSize
+		if size == 0 {
 			continue
 		}
 		src := reflect.ValueOf(c.Comp).UnsafePointer()
 		dst := a.Get(uintptr(idx), c.ID)
-		a.copy(src, dst, lay.itemSize)
+		a.copy(src, dst, size)
 	}
 	a.len++
 	return idx
@@ -193,12 +194,13 @@ func (a *archetype) Remove(index uintptr) bool {
 	if index != old {
 		for _, id := range a.Ids {
 			lay := a.getLayout(id)
-			if lay.itemSize == 0 {
+			size := lay.itemSize
+			if size == 0 {
 				continue
 			}
-			src := unsafe.Add(lay.pointer, old*lay.itemSize)
-			dst := unsafe.Add(lay.pointer, index*lay.itemSize)
-			a.copy(src, dst, lay.itemSize)
+			src := unsafe.Add(lay.pointer, old*size)
+			dst := unsafe.Add(lay.pointer, index*size)
+			a.copy(src, dst, size)
 		}
 	}
 	a.ZeroAll(old)
@@ -217,11 +219,12 @@ func (a *archetype) ZeroAll(index uintptr) {
 // ZeroAll resets a block of storage in one buffer.
 func (a *archetype) Zero(index uintptr, id ID) {
 	lay := a.getLayout(id)
-	if lay.itemSize == 0 {
+	size := lay.itemSize
+	if size == 0 {
 		return
 	}
-	dst := unsafe.Add(lay.pointer, index*lay.itemSize)
-	a.copy(a.zeroPointer, dst, lay.itemSize)
+	dst := unsafe.Add(lay.pointer, index*size)
+	a.copy(a.zeroPointer, dst, size)
 }
 
 // SetEntity overwrites an entity
@@ -233,13 +236,14 @@ func (a *archetype) SetEntity(index uintptr, entity Entity) {
 func (a *archetype) Set(index uintptr, id ID, comp interface{}) unsafe.Pointer {
 	lay := a.getLayout(id)
 	dst := a.Get(index, id)
-	if lay.itemSize == 0 {
+	size := lay.itemSize
+	if size == 0 {
 		return dst
 	}
 	rValue := reflect.ValueOf(comp)
 
 	src := rValue.UnsafePointer()
-	a.copy(src, dst, lay.itemSize)
+	a.copy(src, dst, size)
 	return dst
 }
 
@@ -247,11 +251,12 @@ func (a *archetype) Set(index uintptr, id ID, comp interface{}) unsafe.Pointer {
 func (a *archetype) SetPointer(index uintptr, id ID, comp unsafe.Pointer) unsafe.Pointer {
 	lay := a.getLayout(id)
 	dst := a.Get(index, id)
-	if lay.itemSize == 0 {
+	size := lay.itemSize
+	if size == 0 {
 		return dst
 	}
 
-	a.copy(comp, dst, lay.itemSize)
+	a.copy(comp, dst, size)
 	return dst
 }
 
diff --git a/ecs/id_map.go b/ecs/id_map.go
index c750a65..035bf5d 100644
--- a/ecs/id_map.go
+++ b/ecs/id_map.go
@@ -34,9 +34,7 @@ func (m *idMap[T]) Get(index uint8) (T, bool) {
 	if !m.used.Get(index) {
 		return m.zeroValue, false
 	}
-	chunk := index / chunkSize
-	subIndex := index % chunkSize
-	return m.chunks[chunk][subIndex], true
+	return m.chunks[index/chunkSize][index%chunkSize], true
 }
 
 // Get returns a pointer to the value at the given key and whether the key is present.
@@ -44,19 +42,16 @@ func (m *idMap[T]) GetPointer(index uint8) (*T, bool) {
 	if !m.used.Get(index) {
 		return nil, false
 	}
-	chunk := index / chunkSize
-	subIndex := index % chunkSize
-	return &m.chunks[chunk][subIndex], true
+	return &m.chunks[index/chunkSize][index%chunkSize], true
 }
 
 // Set sets the value at the given key.
 func (m *idMap[T]) Set(index uint8, value T) {
 	chunk := index / chunkSize
-	subIndex := index % chunkSize
 	if m.chunks[chunk] == nil {
 		m.chunks[chunk] = make([]T, chunkSize)
 	}
-	m.chunks[chunk][subIndex] = value
+	m.chunks[chunk][index%chunkSize] = value
 	m.used.Set(index, true)
 	m.chunkUsed[chunk]++
 }
diff --git a/ecs/pool.go b/ecs/pool.go
index 943c2f8..f67b7f6 100644
--- a/ecs/pool.go
+++ b/ecs/pool.go
@@ -28,14 +28,7 @@ func newEntityPool(capacityIncrement int) entityPool {
 // Get returns a fresh or recycled entity.
 func (p *entityPool) Get() Entity {
 	if p.available == 0 {
-		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)+p.capacityIncrement)
-			copy(p.entities, old)
-		}
-		p.entities = append(p.entities, e)
-		return e
+		return p.getNew()
 	}
 	curr := p.next
 	p.next, p.entities[p.next].id = p.entities[p.next].id, p.next
@@ -43,6 +36,18 @@ func (p *entityPool) Get() Entity {
 	return p.entities[curr]
 }
 
+// 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)+p.capacityIncrement)
+		copy(p.entities, old)
+	}
+	p.entities = append(p.entities, e)
+	return e
+}
+
 // Recycle hands an entity back for recycling.
 func (p *entityPool) Recycle(e Entity) {
 	if e.id == 0 {
@@ -96,13 +101,7 @@ type bitPool struct {
 // Get returns a fresh or recycled bit.
 func (p *bitPool) Get() uint8 {
 	if p.available == 0 {
-		if p.length >= MaskTotalBits {
-			panic("run out of the maximum of 128 bits")
-		}
-		b := p.length
-		p.bits[p.length] = b
-		p.length++
-		return b
+		return p.getNew()
 	}
 	curr := p.next
 	p.next, p.bits[p.next] = p.bits[p.next], p.next
@@ -110,6 +109,17 @@ func (p *bitPool) Get() uint8 {
 	return p.bits[curr]
 }
 
+// Allocates and returns a new bit. For internal use.
+func (p *bitPool) getNew() uint8 {
+	if p.length >= MaskTotalBits {
+		panic("run out of the maximum of 128 bits")
+	}
+	b := p.length
+	p.bits[p.length] = b
+	p.length++
+	return b
+}
+
 // Recycle hands a bit back for recycling.
 func (p *bitPool) Recycle(b uint8) {
 	p.next, p.bits[b] = b, p.next
diff --git a/ecs/util.go b/ecs/util.go
index bb39059..1fb8ad7 100644
--- a/ecs/util.go
+++ b/ecs/util.go
@@ -1,5 +1,8 @@
 package ecs
 
+// Page size of pagedSlice type
+const pageSize = 32
+
 // Calculates the capacity required for size, given an increment.
 func capacity(size, increment int) int {
 	cap := increment * (size / increment)
@@ -58,23 +61,20 @@ func (m *lockMask) Reset() {
 //
 // Implements [archetypes].
 type pagedSlice[T any] struct {
-	pages    [][]T
-	len      int
-	lenLast  int
-	pageSize int
+	pages   [][]T
+	len     int
+	lenLast int
 }
 
 // newPagedSlice creates a new pagedSlice with the given page size/capacity increment.
-func newPagedSlice[T any](pageSize int) pagedSlice[T] {
-	return pagedSlice[T]{
-		pageSize: pageSize,
-	}
+func newPagedSlice[T any]() pagedSlice[T] {
+	return pagedSlice[T]{}
 }
 
 // Add adds a value to the paged slice.
 func (p *pagedSlice[T]) Add(value T) {
-	if p.len == 0 || p.lenLast == p.pageSize {
-		p.pages = append(p.pages, make([]T, p.pageSize))
+	if p.len == 0 || p.lenLast == pageSize {
+		p.pages = append(p.pages, make([]T, pageSize))
 		p.lenLast = 0
 	}
 	p.pages[len(p.pages)-1][p.lenLast] = value
@@ -84,7 +84,7 @@ func (p *pagedSlice[T]) Add(value T) {
 
 // Get returns the value at the given index.
 func (p *pagedSlice[T]) Get(index int) *T {
-	return &p.pages[index/p.pageSize][index%p.pageSize]
+	return &p.pages[index/pageSize][index%pageSize]
 }
 
 // Len returns the current number of items in the paged slice.
diff --git a/ecs/world.go b/ecs/world.go
index 60113db..7da27e8 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -99,8 +99,8 @@ func fromConfig(conf Config) World {
 		entities:    entities,
 		entityPool:  newEntityPool(conf.CapacityIncrement),
 		registry:    newComponentRegistry(),
-		archetypes:  newPagedSlice[archetype](32),
-		graph:       newPagedSlice[archetypeNode](32),
+		archetypes:  newPagedSlice[archetype](),
+		graph:       newPagedSlice[archetypeNode](),
 		locks:       lockMask{},
 		listener:    nil,
 		resources:   newResources(),


Test patch:
diff --git a/ecs/util_test.go b/ecs/util_test.go
index 6e3d4f8..397ce0c 100644
--- a/ecs/util_test.go
+++ b/ecs/util_test.go
@@ -44,7 +44,7 @@ func TestLockMask(t *testing.T) {
 }
 
 func TestPagedSlice(t *testing.T) {
-	a := newPagedSlice[int](32)
+	a := newPagedSlice[int]()
 
 	for i := 0; i < 66; i++ {
 		a.Add(i)
@@ -54,7 +54,7 @@ func TestPagedSlice(t *testing.T) {
 }
 
 func TestPagedSlicePointerPersistence(t *testing.T) {
-	a := newPagedSlice[int](32)
+	a := newPagedSlice[int]()
 
 	a.Add(0)
 	p1 := a.Get(0)
@@ -70,3 +70,21 @@ func TestPagedSlicePointerPersistence(t *testing.T) {
 	*p1 = 100
 	assert.Equal(t, 100, *p2)
 }
+
+func BenchmarkPagedSlice_Get(b *testing.B) {
+	b.StopTimer()
+
+	count := 128
+	s := newPagedSlice[int]()
+
+	for i := 0; i < count; i++ {
+		s.Add(1)
+	}
+
+	b.StartTimer()
+
+	sum := 0
+	for i := 0; i < b.N; i++ {
+		sum += *s.Get(i % count)
+	}
+}
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 2c48111..7ecf3e4 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -913,6 +913,7 @@ func TestTypeSizes(t *testing.T) {
 	printTypeSize[archetype]()
 	printTypeSize[archetypeAccess]()
 	printTypeSize[archetypeNode]()
+	printTypeSize[layout]()
 	printTypeSize[entityPool]()
 	printTypeSizeName[componentRegistry[ID]]("componentRegistry")
 	printTypeSize[bitPool]()