Repository: mlange-42/arche
Pull request #3 (2023-02-05 13:15:55)

Implement component storage


Patch:
diff --git a/ecs/entity.go b/ecs/entity.go
index c091474..6c6c94f 100644
--- a/ecs/entity.go
+++ b/ecs/entity.go
@@ -1,6 +1,7 @@
 package ecs
 
 // Entity identifier
+// TODO: Store ID and generation in a single uint64?
 type Entity struct {
 	id  uint32
 	gen uint16
diff --git a/ecs/entity_pool.go b/ecs/entity_pool.go
index 4c14d1d..0819372 100644
--- a/ecs/entity_pool.go
+++ b/ecs/entity_pool.go
@@ -1,6 +1,7 @@
 package ecs
 
 // EntityPool is the interface for entity recycling
+// TODO: Add a way to shrink/compact the pool?
 type EntityPool interface {
 	// Get returns a fresh or recycled entity
 	Get() Entity
@@ -56,7 +57,7 @@ func (p *implicitListEntityPool) Recycle(e Entity) {
 	p.available++
 }
 
-// Alive return whether an entity is currently alive
+// Alive return whether an entity is still alive, based on the entity's generations
 func (p *implicitListEntityPool) Alive(e Entity) bool {
 	return e.gen == p.entities[e.id].gen
 }
diff --git a/ecs/storage.go b/ecs/storage.go
new file mode 100644
index 0000000..85adfb9
--- /dev/null
+++ b/ecs/storage.go
@@ -0,0 +1,201 @@
+package ecs
+
+import (
+	"math"
+	"reflect"
+	"unsafe"
+)
+
+// Storage is the interface for component storage
+type Storage interface {
+	Get(index uint32) unsafe.Pointer
+	Add(value interface{}) (index uint32)
+	Remove(index uint32)
+	Len() uint32
+}
+
+// ByteStorage stores components in a byte slice
+// It does not work with components that contain references or pointers,
+// because the referenced memory will be garbage-collected.
+type ByteStorage struct {
+	data              []byte
+	itemSize          uintptr
+	len               uint32
+	capacityIncrement uint32
+}
+
+// NewByteStorage creates a new ByteStorage
+func NewByteStorage(obj interface{}, increment int) *ByteStorage {
+	tp := reflect.TypeOf(obj)
+	size := tp.Size()
+
+	return &ByteStorage{
+		data:              make([]byte, increment*int(size)),
+		itemSize:          size,
+		len:               0,
+		capacityIncrement: uint32(increment),
+	}
+}
+
+// Get retrieves an unsafe pointer to an element
+func (s *ByteStorage) Get(index uint32) unsafe.Pointer {
+	base := unsafe.Pointer(&s.data[0])
+
+	offset := uintptr(index) * s.itemSize
+	return unsafe.Add(base, offset)
+}
+
+// Add adds an element to the end of the storage
+func (s *ByteStorage) Add(value interface{}) (index uint32) {
+	// TODO this allocates a new slice and should be improved
+	if uint32(len(s.data)) < (s.len+1)*uint32(s.itemSize) {
+		old := s.data
+		s.data = make([]byte, (s.len+s.capacityIncrement)*uint32(s.itemSize))
+		copy(s.data, old)
+	}
+	s.len++
+	s.set(s.len-1, value)
+	return s.len - 1
+}
+
+// Remove swap-removes an element
+func (s *ByteStorage) Remove(index uint32) {
+	o := s.len - 1
+	n := index
+	s.copy(o, n)
+	s.len--
+	// TODO shrink the underlying data arrays
+}
+
+// Len returns the number of items in the storage
+func (s *ByteStorage) Len() uint32 {
+	return s.len
+}
+
+func (s *ByteStorage) set(index uint32, value interface{}) {
+	dst := s.Get(index)
+	src := unsafe.Pointer(reflect.ValueOf(value).Pointer())
+	for i := uintptr(0); i < s.itemSize; i++ {
+		*(*byte)(dst) = *(*byte)(src)
+		dst = unsafe.Add(dst, 1)
+		src = unsafe.Add(src, 1)
+	}
+}
+
+func (s *ByteStorage) copy(from, to uint32) {
+	if from == to {
+		return
+	}
+	f := uintptr(from) * s.itemSize
+	t := uintptr(to) * s.itemSize
+	copy(s.data[t:t+s.itemSize], s.data[f:f+s.itemSize])
+}
+
+// ReflectStorage is a storage implementation that works with reflection
+type ReflectStorage struct {
+	buffer            reflect.Value
+	bufferAddress     unsafe.Pointer
+	typeOf            reflect.Type
+	itemSize          uintptr
+	len               uint32
+	cap               uint32
+	capacityIncrement uint32
+}
+
+// NewReflectStorage creates a new ReflectStorage
+func NewReflectStorage(obj interface{}, increment int) *ReflectStorage {
+	tp := reflect.TypeOf(obj)
+	size := tp.Size()
+
+	buffer := reflect.New(reflect.ArrayOf(increment, tp)).Elem()
+	return &ReflectStorage{
+		buffer:            buffer,
+		bufferAddress:     buffer.Addr().UnsafePointer(),
+		typeOf:            tp,
+		itemSize:          size,
+		len:               0,
+		cap:               uint32(increment),
+		capacityIncrement: uint32(increment),
+	}
+}
+
+// Get retrieves an unsafe pointer to an element
+func (s *ReflectStorage) Get(index uint32) unsafe.Pointer {
+	ptr := unsafe.Add(s.bufferAddress, uintptr(index)*s.itemSize)
+	return unsafe.Pointer(ptr)
+}
+
+// Add adds an element to the end of the storage
+func (s *ReflectStorage) Add(value interface{}) (index uint32) {
+	if s.cap < s.len+1 {
+		newCap := s.cap + s.capacityIncrement
+
+		old := s.buffer
+		oldAddr := s.bufferAddress
+
+		buffer := reflect.New(reflect.ArrayOf(int(newCap), s.typeOf)).Elem()
+		newAddr := buffer.Addr().UnsafePointer()
+
+		if s.len > 0 {
+			dstSlice := (*[math.MaxInt32]byte)(newAddr)[: s.itemSize : s.itemSize*uintptr(s.len)]
+			srcSlice := (*[math.MaxInt32]byte)(oldAddr)[: s.itemSize : s.itemSize*uintptr(s.len)]
+
+			copy(dstSlice, srcSlice)
+		}
+
+		s.cap = newCap
+		s.buffer = buffer
+		s.bufferAddress = newAddr
+		reflect.Copy(s.buffer, old)
+	}
+	s.len++
+	s.set(s.len-1, value)
+	return s.len - 1
+}
+
+// Remove swap-removes an element
+func (s *ReflectStorage) Remove(index uint32) {
+	o := s.len - 1
+	n := index
+	size := s.itemSize
+
+	src := unsafe.Add(s.bufferAddress, uintptr(o)*s.itemSize)
+	dst := unsafe.Add(s.bufferAddress, uintptr(n)*s.itemSize)
+
+	dstSlice := (*[math.MaxInt32]byte)(dst)[:size:size]
+	srcSlice := (*[math.MaxInt32]byte)(src)[:size:size]
+
+	copy(dstSlice, srcSlice)
+
+	s.len--
+	// TODO shrink the underlying data arrays
+}
+
+func (s *ReflectStorage) set(index uint32, value interface{}) {
+	rValue := reflect.ValueOf(value)
+	dst := s.Get(index)
+	var src unsafe.Pointer
+	size := s.itemSize
+
+	src = rValue.UnsafePointer()
+
+	dstSlice := (*[math.MaxInt32]byte)(dst)[:size:size]
+	srcSlice := (*[math.MaxInt32]byte)(src)[:size:size]
+
+	copy(dstSlice, srcSlice)
+}
+
+// Len returns the number of items in the storage
+func (s *ReflectStorage) Len() uint32 {
+	return s.len
+}
+
+// ToSlice converts the content of a storage to a slice of structs
+func ToSlice[T any](s Storage) []T {
+	res := make([]T, s.Len())
+	for i := 0; i < int(s.Len()); i++ {
+		ptr := (*T)(s.Get(uint32(i)))
+		res[i] = *ptr
+	}
+	return res
+}


Test patch:
diff --git a/ecs/storage_test.go b/ecs/storage_test.go
new file mode 100644
index 0000000..bd8ef97
--- /dev/null
+++ b/ecs/storage_test.go
@@ -0,0 +1,374 @@
+package ecs
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+type testStruct struct {
+	Int32 int32
+	Int64 int64
+	Bool1 bool
+	Bool2 bool
+}
+
+type simpleStruct struct {
+	Index int
+}
+
+func TestByteStorageItemSize(t *testing.T) {
+	obj1 := struct{}{}
+	obj2 := struct{ bool }{true}
+	obj3 := struct{ int8 }{0}
+	obj4 := struct{ int16 }{0}
+	obj5 := struct{ int32 }{0}
+	obj6 := struct{ int64 }{0}
+	obj7 := struct {
+		int64
+		bool
+	}{0, true}
+
+	s1 := NewByteStorage(obj1, 32)
+	s2 := NewByteStorage(obj2, 32)
+	s3 := NewByteStorage(obj3, 32)
+	s4 := NewByteStorage(obj4, 32)
+	s5 := NewByteStorage(obj5, 32)
+	s6 := NewByteStorage(obj6, 32)
+	s7 := NewByteStorage(obj7, 32)
+
+	assert.Equal(
+		t,
+		[]uintptr{0, 1, 1, 2, 4, 8, 16},
+		[]uintptr{s1.itemSize, s2.itemSize, s3.itemSize, s4.itemSize, s5.itemSize, s6.itemSize, s7.itemSize},
+		"Unexpected struct size",
+	)
+}
+
+func TestByteStorageAddGet(t *testing.T) {
+	obj1 := testStruct{}
+	s := NewByteStorage(obj1, 32)
+	storageAddGet(t, s)
+}
+
+func TestReflectStorageAddGet(t *testing.T) {
+	obj1 := testStruct{}
+	s := NewReflectStorage(obj1, 32)
+	storageAddGet(t, s)
+}
+
+func storageAddGet(t *testing.T, s Storage) {
+	obj1 := testStruct{}
+	obj2 := testStruct{1, 2, true, false}
+
+	idx := s.Add(&obj1)
+	assert.Equal(t, idx, uint32(0), "Index of first insertion should be 0")
+
+	idx = s.Add(&obj2)
+	assert.Equal(t, idx, uint32(1), "Index of second insertion should be 1")
+
+	ret1 := (*testStruct)(s.Get(0))
+	assert.Equal(t, obj1, *ret1, "First element not as passed in")
+
+	ret2 := (*testStruct)(s.Get(1))
+	assert.Equal(t, obj2, *ret2, "Second element not as passed in")
+
+	ret2.Int64 = 1001
+	ret2 = (*testStruct)(s.Get(1))
+	assert.Equal(t, testStruct{1, 1001, true, false}, *ret2, "Manipulating element does not change data")
+
+	assert.Equal(t, []testStruct{{}, {1, 1001, true, false}}, ToSlice[testStruct](s), "Wrong extracted struct slice")
+}
+
+func TestByteStorageRemove(t *testing.T) {
+	ref := simpleStruct{}
+	s := NewByteStorage(ref, 32)
+
+	storageRemove(t, s)
+}
+
+func TestReflectStorageRemove(t *testing.T) {
+	ref := simpleStruct{}
+	s := NewReflectStorage(ref, 32)
+
+	storageRemove(t, s)
+}
+
+func storageRemove(t *testing.T, s Storage) {
+	for i := 0; i < 5; i++ {
+		obj := simpleStruct{i}
+		s.Add(&obj)
+	}
+
+	assert.Equal(t, uint32(5), s.Len(), "Wrong storage length")
+
+	s.Remove(4)
+	assert.Equal(t, uint32(4), s.Len(), "Wrong storage length")
+	assert.Equal(t, []simpleStruct{{0}, {1}, {2}, {3}}, ToSlice[simpleStruct](s), "Wrong slice after remove")
+
+	s.Remove(1)
+	assert.Equal(t, uint32(3), s.Len(), "Wrong storage length")
+	assert.Equal(t, []simpleStruct{{0}, {3}, {2}}, ToSlice[simpleStruct](s), "Wrong slice after remove")
+}
+
+func TestByteStorageDataSize(t *testing.T) {
+	ref := simpleStruct{}
+	s := NewByteStorage(ref, 1)
+
+	size := int(s.itemSize)
+
+	for i := 0; i < 5; i++ {
+		obj := simpleStruct{i}
+		s.Add(&obj)
+	}
+
+	assert.Equal(t, 5*size, len(s.data))
+
+	s.Remove(0)
+	assert.Equal(t, 5*size, len(s.data))
+	s.Remove(0)
+	assert.Equal(t, 5*size, len(s.data))
+
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 5*size, len(s.data))
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 5*size, len(s.data))
+
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 6*size, len(s.data))
+}
+
+func TestReflectStorageDataSize(t *testing.T) {
+	ref := simpleStruct{}
+	s := NewReflectStorage(ref, 1)
+
+	for i := 0; i < 5; i++ {
+		obj := simpleStruct{i}
+		s.Add(&obj)
+	}
+
+	assert.Equal(t, 5, int(s.cap))
+
+	s.Remove(0)
+	assert.Equal(t, 5, int(s.cap))
+	s.Remove(0)
+	assert.Equal(t, 5, int(s.cap))
+
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 5, int(s.cap))
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 5, int(s.cap))
+
+	s.Add(&simpleStruct{})
+	assert.Equal(t, 6, int(s.cap))
+}
+
+func TestNewByteStorage(t *testing.T) {
+	_ = NewByteStorage(simpleStruct{}, 32)
+}
+
+func TestNewReflectStorage(t *testing.T) {
+	_ = NewReflectStorage(simpleStruct{}, 32)
+}
+
+func BenchmarkIterByteStorage(b *testing.B) {
+	ref := testStruct{}
+	s := NewByteStorage(ref, 128)
+	for i := 0; i < 1000; i++ {
+		s.Add(&testStruct{})
+	}
+	assert.Equal(b, 1000, int(s.Len()))
+
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < int(s.Len()); j++ {
+			a := (*testStruct)(s.Get(uint32(j)))
+			_ = a
+		}
+	}
+}
+
+func BenchmarkIterReflectStorage(b *testing.B) {
+	ref := testStruct{}
+	s := NewReflectStorage(ref, 128)
+	for i := 0; i < 1000; i++ {
+		s.Add(&testStruct{})
+	}
+	assert.Equal(b, 1000, int(s.Len()))
+
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < int(s.Len()); j++ {
+			a := (*testStruct)(s.Get(uint32(j)))
+			_ = a
+		}
+	}
+}
+
+func BenchmarkIterSlice(b *testing.B) {
+	s := []testStruct{}
+	for i := 0; i < 1000; i++ {
+		s = append(s, testStruct{})
+	}
+	assert.Equal(b, 1000, len(s))
+
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < len(s); j++ {
+			a := s[j]
+			_ = a
+		}
+	}
+}
+
+func BenchmarkIterSliceInterface(b *testing.B) {
+	s := []interface{}{}
+	for i := 0; i < 1000; i++ {
+		s = append(s, testStruct{})
+	}
+	assert.Equal(b, 1000, len(s))
+
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < len(s); j++ {
+			a := s[j].(testStruct)
+			_ = a
+		}
+	}
+}
+
+func BenchmarkAddByteStorage(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := NewByteStorage(ref, 1024)
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s.Add(&ref)
+		}
+	}
+}
+
+func BenchmarkAddReflectStorage(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := NewReflectStorage(ref, 1024)
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s.Add(&ref)
+		}
+	}
+}
+
+func BenchmarkAddSlice(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := make([]testStruct, 0)
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s = append(s, ref)
+		}
+
+		b.StopTimer()
+		_ = s
+		b.StartTimer()
+	}
+}
+
+func BenchmarkAddSliceInterface(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := make([]interface{}, 0)
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s = append(s, ref)
+		}
+
+		b.StopTimer()
+		_ = s
+		b.StartTimer()
+	}
+}
+
+func BenchmarkRemoveByteStorage(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := NewByteStorage(ref, 1024)
+		for i := 0; i < 1000; i++ {
+			s.Add(&ref)
+		}
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s.Remove(0)
+		}
+	}
+}
+
+func BenchmarkRemoveReflectStorage(b *testing.B) {
+	ref := testStruct{}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := NewReflectStorage(ref, 1024)
+		for i := 0; i < 1000; i++ {
+			s.Add(&ref)
+		}
+		b.StartTimer()
+
+		for i := 0; i < 1000; i++ {
+			s.Remove(0)
+		}
+	}
+}
+
+func BenchmarkRemoveSlice(b *testing.B) {
+	ref := testStruct{}
+	template := make([]testStruct, 0)
+	for i := 0; i < 1000; i++ {
+		template = append(template, ref)
+	}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := append([]testStruct{}, template...)
+		b.StartTimer()
+
+		l := len(s) - 1
+		for i := 0; i < 1000; i++ {
+			s[0], s[l] = s[l], s[0]
+			s = s[:l]
+			l--
+		}
+
+		b.StopTimer()
+		_ = s
+		b.StartTimer()
+	}
+}
+
+func BenchmarkRemoveSliceInterface(b *testing.B) {
+	ref := testStruct{}
+	template := make([]interface{}, 0)
+	for i := 0; i < 1000; i++ {
+		template = append(template, ref)
+	}
+	for i := 0; i < b.N; i++ {
+		b.StopTimer()
+		s := append([]interface{}{}, template...)
+		b.StartTimer()
+
+		l := len(s) - 1
+		for i := 0; i < 1000; i++ {
+			s[0], s[l] = s[l], s[0]
+			s = s[:l]
+			l--
+		}
+
+		b.StopTimer()
+		_ = s
+		b.StartTimer()
+	}
+}