Repository: mlange-42/arche
Pull request #192 (2023-03-30 12:21:56)

Efficient data structure for mapping from component IDs
`idMap ` is a data structure meant for fast lookup by component ID keys, while being memory-efficient.
Access time is around 2ns, compared to 0.5ns for array access and 20ns for `map[int]T`.

The memory footprint is reduced by using chunks, and only allocating chunks if they contain a key.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index b04f401..4e3697c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -34,6 +34,7 @@
 * Avoid slice allocations in generic mapper methods (#170)
 * 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)
 
 ### Bugfixes
 
diff --git a/ecs/archetype.go b/ecs/archetype.go
index cd7bb97..ead6338 100644
--- a/ecs/archetype.go
+++ b/ecs/archetype.go
@@ -13,41 +13,39 @@ var layoutSize = unsafe.Sizeof(layout{})
 
 // archetypeNode is a node in the archetype graph.
 type archetypeNode struct {
-	mask      Mask             // Mask of the archetype
-	archetype *archetype       // The archetype
-	toAdd     []*archetypeNode // Mapping from component ID to add to the resulting archetype
-	toRemove  []*archetypeNode // Mapping from component ID to remove to the resulting archetype
+	mask      Mask                  // Mask of the archetype
+	archetype *archetype            // The archetype
+	toAdd     idMap[*archetypeNode] // Mapping from component ID to add to the resulting archetype
+	toRemove  idMap[*archetypeNode] // Mapping from component ID to remove to the resulting archetype
 }
 
 // Creates a new archetypeNode
 func newArchetypeNode(mask Mask) archetypeNode {
 	return archetypeNode{
 		mask:     mask,
-		toAdd:    make([]*archetypeNode, MaskTotalBits),
-		toRemove: make([]*archetypeNode, MaskTotalBits),
+		toAdd:    newIDMap[*archetypeNode](),
+		toRemove: newIDMap[*archetypeNode](),
 	}
 }
 
 // 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
+	return a.toAdd.Get(id)
 }
 
 // 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
+	return a.toRemove.Get(id)
 }
 
 // SetTransitionAdd sets the archetypeNode resulting from adding a component
 func (a *archetypeNode) SetTransitionAdd(id ID, to *archetypeNode) {
-	a.toAdd[id] = to
+	a.toAdd.Set(id, to)
 }
 
 // SetTransitionRemove sets the archetypeNode resulting from removing a component
 func (a *archetypeNode) SetTransitionRemove(id ID, to *archetypeNode) {
-	a.toRemove[id] = to
+	a.toRemove.Set(id, to)
 }
 
 // Helper for accessing data from an archetype
@@ -97,7 +95,7 @@ type archetype struct {
 	graphNode         *archetypeNode  // Node in the archetype graph.
 	Ids               []ID            // List of component IDs.
 	layouts           []layout        // Column layouts by ID.
-	indices           []uint32        // Mapping from IDs to buffer indices.
+	indices           idMap[uint32]   // Mapping from IDs to buffer indices.
 	buffers           []reflect.Value // Reflection arrays containing component data.
 	entityBuffer      reflect.Value   // Reflection array containing entity data.
 	len               uint32          // Current number of entities
@@ -116,7 +114,7 @@ func (a *archetype) Init(node *archetypeNode, capacityIncrement int, forStorage
 
 	a.buffers = make([]reflect.Value, len(components))
 	a.layouts = make([]layout, MaskTotalBits)
-	a.indices = make([]uint32, MaskTotalBits)
+	a.indices = newIDMap[uint32]()
 
 	cap := 1
 	if forStorage {
@@ -144,7 +142,7 @@ func (a *archetype) Init(node *archetypeNode, capacityIncrement int, forStorage
 			a.buffers[i].Addr().UnsafePointer(),
 			size,
 		}
-		a.indices[c.ID] = uint32(i)
+		a.indices.Set(c.ID, uint32(i))
 	}
 	a.entityBuffer = reflect.New(reflect.ArrayOf(cap, entityType)).Elem()
 
@@ -355,7 +353,7 @@ func (a *archetype) extend(by uint32) {
 		if lay.itemSize == 0 {
 			continue
 		}
-		index := a.indices[id]
+		index, _ := a.indices.Get(id)
 		old := a.buffers[index]
 		a.buffers[index] = reflect.New(reflect.ArrayOf(int(a.cap), old.Type().Elem())).Elem()
 		lay.pointer = a.buffers[index].Addr().UnsafePointer()
diff --git a/ecs/cache.go b/ecs/cache.go
index 46a8fe2..767bca3 100644
--- a/ecs/cache.go
+++ b/ecs/cache.go
@@ -20,7 +20,7 @@ type cacheEntry struct {
 //
 // The overhead of tracking cached filters is very low, as updates are required only when new archetypes are created.
 type Cache struct {
-	indices       []int                            // Mapping from filter IDs to indices in filters
+	indices       idMap[int]                       // Mapping from filter IDs to indices in filters
 	filters       []cacheEntry                     // The cached filters, indexed by indices
 	getArchetypes func(f Filter) archetypePointers // Callback for getting archetypes for a new filter from the world
 	bitPool       bitPool                          // Pool for filter IDs
@@ -28,13 +28,9 @@ type Cache struct {
 
 // newCache creates a new [Cache].
 func newCache() Cache {
-	indices := make([]int, MaskTotalBits)
-	for i := 0; i < MaskTotalBits; i++ {
-		indices[i] = MaskTotalBits
-	}
 	return Cache{
 		bitPool: bitPool{},
-		indices: indices,
+		indices: newIDMap[int](),
 		filters: []cacheEntry{},
 	}
 }
@@ -54,7 +50,7 @@ func (c *Cache) Register(f Filter) CachedFilter {
 			Filter:     f,
 			Archetypes: c.getArchetypes(f),
 		})
-	c.indices[id] = len(c.filters) - 1
+	c.indices.Set(id, len(c.filters)-1)
 	return CachedFilter{f, id}
 }
 
@@ -62,17 +58,17 @@ func (c *Cache) Register(f Filter) CachedFilter {
 //
 // Returns the original filter.
 func (c *Cache) Unregister(f *CachedFilter) Filter {
-	idx := c.indices[f.id]
-	if idx >= MaskTotalBits {
+	idx, ok := c.indices.Get(f.id)
+	if !ok {
 		panic("no filter for id found to unregister")
 	}
 	filter := c.filters[idx].Filter
-	c.indices[f.id] = MaskTotalBits
+	c.indices.Remove(f.id)
 
 	last := len(c.filters) - 1
 	if idx != last {
 		c.filters[idx], c.filters[last] = c.filters[last], c.filters[idx]
-		c.indices[c.filters[idx].ID] = idx
+		c.indices.Set(c.filters[idx].ID, idx)
 	}
 	c.filters[last] = cacheEntry{}
 	c.filters = c.filters[:last]
@@ -84,8 +80,7 @@ func (c *Cache) Unregister(f *CachedFilter) Filter {
 //
 // Panics if there is no entry for the filter's ID.
 func (c *Cache) get(f *CachedFilter) *cacheEntry {
-	idx := c.indices[f.id]
-	if idx < MaskTotalBits {
+	if idx, ok := c.indices.Get(f.id); ok {
 		return &c.filters[idx]
 	}
 	panic("no filter for id found")
diff --git a/ecs/id_map.go b/ecs/id_map.go
new file mode 100644
index 0000000..c750a65
--- /dev/null
+++ b/ecs/id_map.go
@@ -0,0 +1,73 @@
+package ecs
+
+const (
+	numChunks = 8
+	chunkSize = 16
+)
+
+// idMap maps component IDs to values.
+//
+// Is is a data structure meant for fast lookup while being memory-efficient.
+// Access time is around 2ns, compared to 0.5ns for array access and 20ns for map[int]T.
+//
+// The memory footprint is reduced by using chunks, and only allocating chunks if they contain a key.
+//
+// The range of keys is limited from 0 to [MaskTotalBits]-1.
+type idMap[T any] struct {
+	chunks    [][]T
+	used      Mask
+	chunkUsed []uint8
+	zeroValue T
+}
+
+// newIDMap creates a new idMap
+func newIDMap[T any]() idMap[T] {
+	return idMap[T]{
+		chunks:    make([][]T, numChunks),
+		used:      Mask{},
+		chunkUsed: make([]uint8, numChunks),
+	}
+}
+
+// Get returns the value at the given key and whether the key is present.
+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
+}
+
+// Get returns a pointer to the value at the given key and whether the key is present.
+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
+}
+
+// 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.used.Set(index, true)
+	m.chunkUsed[chunk]++
+}
+
+// Remove removes the value at the given key.
+// It de-allocates empty chunks.
+func (m *idMap[T]) Remove(index uint8) {
+	chunk := index / chunkSize
+	m.used.Set(index, false)
+	m.chunkUsed[chunk]--
+	if m.chunkUsed[chunk] == 0 {
+		m.chunks[chunk] = nil
+	}
+}


Test patch:
diff --git a/benchmark/arche/build/arche_test.go b/benchmark/arche/build/arche_test.go
new file mode 100644
index 0000000..dc443ec
--- /dev/null
+++ b/benchmark/arche/build/arche_test.go
@@ -0,0 +1,31 @@
+package iterate
+
+import (
+	"testing"
+
+	c "github.com/mlange-42/arche/benchmark/arche/common"
+	"github.com/mlange-42/arche/ecs"
+)
+
+func BenchmarkBuild1kArch(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		world := ecs.NewWorld()
+		c.RegisterAll(&world)
+		b.StartTimer()
+
+		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/id_map_test.go b/ecs/id_map_test.go
new file mode 100644
index 0000000..b1203f4
--- /dev/null
+++ b/ecs/id_map_test.go
@@ -0,0 +1,141 @@
+package ecs
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestIDMap(t *testing.T) {
+	m := newIDMap[*Entity]()
+
+	e0 := Entity{0, 0}
+	e1 := Entity{1, 0}
+	e121 := Entity{121, 0}
+
+	m.Set(0, &e0)
+	m.Set(1, &e1)
+	m.Set(121, &e121)
+
+	e, ok := m.Get(0)
+	assert.True(t, ok)
+	assert.Equal(t, e0, *e)
+
+	e, ok = m.Get(1)
+	assert.True(t, ok)
+	assert.Equal(t, e1, *e)
+
+	e, ok = m.Get(121)
+	assert.True(t, ok)
+	assert.Equal(t, e121, *e)
+
+	e, ok = m.Get(15)
+	assert.False(t, ok)
+	assert.Nil(t, e)
+
+	m.Remove(0)
+	m.Remove(1)
+
+	e, ok = m.Get(0)
+	assert.False(t, ok)
+	assert.Nil(t, e)
+
+	assert.Nil(t, m.chunks[0])
+}
+
+func TestIDMapPointers(t *testing.T) {
+	m := newIDMap[Entity]()
+
+	e0 := Entity{0, 0}
+	e1 := Entity{1, 0}
+	e121 := Entity{121, 0}
+
+	m.Set(0, e0)
+	m.Set(1, e1)
+	m.Set(121, e121)
+
+	e, ok := m.GetPointer(0)
+	assert.True(t, ok)
+	assert.Equal(t, e0, *e)
+
+	e, ok = m.GetPointer(1)
+	assert.True(t, ok)
+	assert.Equal(t, e1, *e)
+
+	e, ok = m.GetPointer(121)
+	assert.True(t, ok)
+	assert.Equal(t, e121, *e)
+
+	e, ok = m.GetPointer(15)
+	assert.False(t, ok)
+	assert.Nil(t, e)
+
+	m.Remove(0)
+	m.Remove(1)
+
+	e, ok = m.GetPointer(0)
+	assert.False(t, ok)
+	assert.Nil(t, e)
+
+	assert.Nil(t, m.chunks[0])
+}
+
+func BenchmarkIdMapping_IDMap(b *testing.B) {
+	b.StopTimer()
+
+	entities := [MaskTotalBits]Entity{}
+	m := newIDMap[*Entity]()
+
+	for i := 0; i < MaskTotalBits; i++ {
+		entities[i] = Entity{eid(i), 0}
+		m.Set(ID(i), &entities[i])
+	}
+
+	b.StartTimer()
+
+	var ptr *Entity = nil
+	for i := 0; i < b.N; i++ {
+		ptr, _ = m.Get(ID(i % MaskTotalBits))
+	}
+	_ = ptr
+}
+
+func BenchmarkIdMapping_Array(b *testing.B) {
+	b.StopTimer()
+
+	entities := [MaskTotalBits]Entity{}
+	m := [MaskTotalBits]*Entity{}
+
+	for i := 0; i < MaskTotalBits; i++ {
+		entities[i] = Entity{eid(i), 0}
+		m[i] = &entities[i]
+	}
+
+	b.StartTimer()
+
+	var ptr *Entity = nil
+	for i := 0; i < b.N; i++ {
+		ptr = m[i%MaskTotalBits]
+	}
+	_ = ptr
+}
+
+func BenchmarkIdMapping_HashMap(b *testing.B) {
+	b.StopTimer()
+
+	entities := [MaskTotalBits]Entity{}
+	m := make(map[uint8]*Entity, MaskTotalBits)
+
+	for i := 0; i < MaskTotalBits; i++ {
+		entities[i] = Entity{eid(i), 0}
+		m[ID(i)] = &entities[i]
+	}
+
+	b.StartTimer()
+
+	var ptr *Entity = nil
+	for i := 0; i < b.N; i++ {
+		ptr = m[ID(i%MaskTotalBits)]
+	}
+	_ = ptr
+}
diff --git a/ecs/world_test.go b/ecs/world_test.go
index ffc3563..dc69ad2 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -921,6 +921,7 @@ func TestTypeSizes(t *testing.T) {
 	printTypeSizeName[reflect.Value]("reflect.Value")
 	printTypeSize[EntityEvent]()
 	printTypeSize[Cache]()
+	printTypeSizeName[idMap[archetype]]("idMap")
 }
 
 func printTypeSize[T any]() {