Repository: mlange-42/arche (go)

Issue:
Remove restriction to 64 component types?
Currently, Arche is limited to 64 component types per world due to the use of `uint64` for bit masks.

This could be extended to 128 types by using a pair of `uint46`, or ti an unlimited number by using some `BitSet` implementation.

Performance overhead should not be too big, as bit masks are mainly used for archetype handling.

* [ ] Implement it
* [ ] Test performance impact

Pull request description:
Big bitmask -- up to 128 components
Replaced the `uint64` bitmask by a 128 bit bitmask

Fixes #73

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 3b11128..22bb428 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -10,6 +10,7 @@
 * Added method `World.Stats()` for inspecting otherwise inaccessible world statistics (#67)
 * Entities can be initialized with components, via ID as well as using generics (#76)
 * A listener function can be registered to the world, for notification on entity changes (#77)
+* Support for up to 128 distinct component types per world (was limited to 64 before) (#78)
 
 ### Other
 
diff --git a/ecs/bit_pool.go b/ecs/bit_pool.go
index 0af9a93..d0721c5 100644
--- a/ecs/bit_pool.go
+++ b/ecs/bit_pool.go
@@ -23,7 +23,7 @@ func newBitPool() bitPool {
 func (p *bitPool) Get() uint8 {
 	if p.available == 0 {
 		if p.length >= MaskTotalBits {
-			panic("run out of the maximum of 64 bits")
+			panic("run out of the maximum of 128 bits")
 		}
 		b := p.length
 		p.bits[p.length] = b
diff --git a/ecs/bitmask.go b/ecs/bitmask.go
index abc433e..245383b 100644
--- a/ecs/bitmask.go
+++ b/ecs/bitmask.go
@@ -1,14 +1,18 @@
 package ecs
 
+import "math/bits"
+
 // MaskTotalBits is the size of Mask in bits.
 //
 // It is the maximum number of component types that may exist in any [World].
-const MaskTotalBits = 64
-
-// BitMask is a 64 bit bitmask.
-type BitMask uint64
+const MaskTotalBits = 128
+const wordSize = 64
 
-var nibbleToBitsSet = [16]uint{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}
+// BitMask is a 128 bit bitmask.
+type BitMask struct {
+	lo uint64
+	hi uint64
+}
 
 // NewBitMask creates a new bitmask from a list of IDs.
 //
@@ -24,44 +28,55 @@ func NewBitMask(ids ...ID) BitMask {
 // Get reports if bit index defined by ID is true or false.
 //
 // The return will be always false for bit >= [MaskTotalBits].
-func (e BitMask) Get(bit ID) bool {
-	mask := BitMask(1 << bit)
-	return e&mask == mask
+func (b BitMask) Get(bit ID) bool {
+	if bit < wordSize {
+		mask := uint64(1 << bit)
+		return b.lo&mask == mask
+	}
+	mask := uint64(1 << (bit - wordSize))
+	return b.hi&mask == mask
 }
 
 // Set sets the state of bit index to true or false.
 //
 // This function has no effect for bit >= [MaskTotalBits].
-func (e *BitMask) Set(bit ID, value bool) {
+func (b *BitMask) Set(bit ID, value bool) {
+	if bit < wordSize {
+		if value {
+			b.lo |= uint64(1 << bit)
+		} else {
+			b.lo &= uint64(^(1 << bit))
+		}
+	}
 	if value {
-		*e |= BitMask(1 << bit)
+		b.hi |= uint64(1 << (bit - wordSize))
 	} else {
-		*e &= BitMask(^(1 << bit))
+		b.hi &= uint64(^(1 << (bit - wordSize)))
 	}
 }
 
+// IsZero returns whether no bits are set in the bitmask.
+func (b BitMask) IsZero() bool {
+	return b.lo == 0 && b.hi == 0
+}
+
 // Reset changes the state of all bits to false.
-func (e *BitMask) Reset() {
-	*e = 0
+func (b *BitMask) Reset() {
+	b.lo = 0
+	b.hi = 0
 }
 
 // Contains reports if other mask is a subset of this mask.
-func (e BitMask) Contains(other BitMask) bool {
-	return e&other == other
+func (b BitMask) Contains(other BitMask) bool {
+	return b.lo&other.lo == other.lo && b.hi&other.hi == other.hi
 }
 
 // ContainsAny reports if any bit of other mask is a subset of this mask.
-func (e BitMask) ContainsAny(other BitMask) bool {
-	return e&other != 0
+func (b BitMask) ContainsAny(other BitMask) bool {
+	return b.lo&other.lo != 0 || b.hi&other.hi != 0
 }
 
 // TotalBitsSet returns how many bits are set in this mask.
-func (e BitMask) TotalBitsSet() uint {
-	var count uint
-
-	for e != 0 {
-		count += nibbleToBitsSet[e&0xf]
-		e >>= 4
-	}
-	return count
+func (b BitMask) TotalBitsSet() int {
+	return bits.OnesCount64(uint64(b.hi)) + bits.OnesCount64(uint64(b.lo))
 }
diff --git a/ecs/query.go b/ecs/query.go
index fd743b6..11cb60a 100644
--- a/ecs/query.go
+++ b/ecs/query.go
@@ -48,7 +48,7 @@ type MaskPair struct {
 // Matches matches a filter against a mask
 func (f MaskPair) Matches(bits BitMask) bool {
 	ex := f.Exclude.BitMask
-	return bits.Contains(f.Mask.BitMask) && (ex == 0 || !bits.ContainsAny(ex))
+	return bits.Contains(f.Mask.BitMask) && (ex.IsZero() || !bits.ContainsAny(ex))
 }
 
 // QueryIter is the interface for iterable queries
diff --git a/ecs/registry.go b/ecs/registry.go
index 6557ed9..ddc8469 100644
--- a/ecs/registry.go
+++ b/ecs/registry.go
@@ -19,7 +19,7 @@ func newComponentRegistry() componentRegistry {
 func (r *componentRegistry) RegisterComponent(tp reflect.Type, totalBits int) ID {
 	id := ID(len(r.Components))
 	if int(id) >= totalBits {
-		panic("maximum of 64 component types exceeded")
+		panic("maximum of 128 component types exceeded")
 	}
 	r.Components[tp] = id
 	r.Types[id] = tp
diff --git a/ecs/world.go b/ecs/world.go
index 723747d..7584046 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -59,10 +59,10 @@ func FromConfig(conf Config) World {
 		bitPool:    newBitPool(),
 		registry:   newComponentRegistry(),
 		archetypes: pagedArr32[archetype]{},
-		locks:      BitMask(0),
+		locks:      BitMask{},
 		listener:   nil,
 	}
-	w.createArchetype(0)
+	w.createArchetype(BitMask{})
 	return w
 }
 
@@ -95,7 +95,7 @@ func (w *World) NewEntity(comps ...ID) Entity {
 	}
 
 	if w.listener != nil {
-		w.listener(ChangeEvent{entity, 0, arch.Mask, comps, nil, arch.Ids, 1})
+		w.listener(ChangeEvent{entity, BitMask{}, arch.Mask, comps, nil, arch.Ids, 1})
 	}
 	return entity
 }
@@ -139,7 +139,7 @@ func (w *World) NewEntityWith(comps ...Component) Entity {
 	}
 
 	if w.listener != nil {
-		w.listener(ChangeEvent{entity, 0, arch.Mask, ids, nil, arch.Ids, 1})
+		w.listener(ChangeEvent{entity, BitMask{}, arch.Mask, ids, nil, arch.Ids, 1})
 	}
 	return entity
 }
@@ -364,7 +364,7 @@ func (w *World) Exchange(entity Entity, add []ID, rem []ID) {
 
 // IsLocked returns whether the world is locked by any queries.
 func (w *World) IsLocked() bool {
-	return w.locks != 0
+	return !w.locks.IsZero()
 }
 
 // RegisterListener registers a func(e ChangeEvent) to the world.
@@ -527,7 +527,7 @@ func (w *World) closeQuery(query *queryIter) {
 }
 
 func (w *World) checkLocked() {
-	if w.locks != 0 {
+	if !w.locks.IsZero() {
 		panic("attempt to modify a locked world")
 	}
 }
diff --git a/generic/util.go b/generic/util.go
index 42aaddc..ca7368d 100644
--- a/generic/util.go
+++ b/generic/util.go
@@ -19,7 +19,7 @@ func toIds(w *ecs.World, types []reflect.Type) []ecs.ID {
 }
 
 func toMask(w *ecs.World, types []reflect.Type) ecs.Mask {
-	mask := ecs.BitMask(0)
+	mask := ecs.BitMask{}
 	for _, t := range types {
 		mask.Set(ecs.TypeID(w, t), true)
 	}


Test patch:
diff --git a/ecs/bitmask_test.go b/ecs/bitmask_test.go
index 8191835..3121565 100644
--- a/ecs/bitmask_test.go
+++ b/ecs/bitmask_test.go
@@ -9,7 +9,7 @@ import (
 func TestBitMask(t *testing.T) {
 	mask := NewBitMask(ID(1), ID(2), ID(13), ID(27))
 
-	assert.Equal(t, uint(4), mask.TotalBitsSet())
+	assert.Equal(t, 4, mask.TotalBitsSet())
 
 	assert.True(t, mask.Get(1))
 	assert.True(t, mask.Get(2))
@@ -32,7 +32,7 @@ func TestBitMask(t *testing.T) {
 	assert.True(t, mask.Contains(other2))
 
 	mask.Reset()
-	assert.Equal(t, uint(0), mask.TotalBitsSet())
+	assert.Equal(t, 0, mask.TotalBitsSet())
 
 	mask = NewBitMask(ID(1), ID(2), ID(13), ID(27))
 	other1 = NewBitMask(ID(1), ID(32))
@@ -41,3 +41,27 @@ func TestBitMask(t *testing.T) {
 	assert.True(t, mask.ContainsAny(other1))
 	assert.False(t, mask.ContainsAny(other2))
 }
+
+func TestBitMask128(t *testing.T) {
+	for i := 0; i < MaskTotalBits; i++ {
+		mask := NewBitMask(ID(i))
+		assert.Equal(t, 1, mask.TotalBitsSet())
+		assert.True(t, mask.Get(ID(i)))
+	}
+	mask := BitMask{}
+	assert.Equal(t, 0, mask.TotalBitsSet())
+
+	for i := 0; i < MaskTotalBits; i++ {
+		mask.Set(ID(i), true)
+		assert.Equal(t, i+1, mask.TotalBitsSet())
+		assert.True(t, mask.Get(ID(i)))
+	}
+
+	mask = NewBitMask(ID(1), ID(2), ID(13), ID(27), ID(63), ID(64), ID(65))
+
+	assert.True(t, mask.Contains(NewBitMask(ID(1), ID(2), ID(63), ID(64))))
+	assert.False(t, mask.Contains(NewBitMask(ID(1), ID(2), ID(63), ID(90))))
+
+	assert.True(t, mask.ContainsAny(NewBitMask(ID(6), ID(65), ID(111))))
+	assert.False(t, mask.ContainsAny(NewBitMask(ID(6), ID(66), ID(90))))
+}
diff --git a/ecs/world_test.go b/ecs/world_test.go
index f583447..1964f35 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -531,7 +531,7 @@ func Test1000Archetypes(t *testing.T) {
 	ids[9] = ComponentID[testStruct9](&w)
 
 	for i := 0; i < 1024; i++ {
-		mask := BitMask(i)
+		mask := BitMask{uint64(i), 0}
 		add := make([]ID, 0, 10)
 		for j := 0; j < 10; j++ {
 			id := ID(j)
@@ -554,6 +554,8 @@ func Test1000Archetypes(t *testing.T) {
 }
 
 func TestTypeSizes(t *testing.T) {
+	printTypeSize[Entity]()
+	printTypeSize[BitMask]()
 	printTypeSize[World]()
 	printTypeSizeName[pagedArr32[archetype]]("PagedArr32")
 	printTypeSize[archetype]()