4958046752

Committed 12 May 2023 10:55AM CUT coverage: 100.0%. Remained the same

Build Type

push

github

Committed by GitHub

Commit Message

Refine architecture section on entity relations (#294)

Run Details

3782 of 3782 relevant lines covered (100.0%)

84279.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/ecs/cache.go

package ecs

// Cache entry for a [Filter].
type cacheEntry struct {
        ID         uint32              // Filter ID.
        Filter     Filter              // The underlying filter.
        Archetypes pointers[archetype] // Nodes matching the filter.
        Indices    map[*archetype]int  // Map of archetype indices for removal.
}

// Cache provides [Filter] caching to speed up queries.
//
// Access it using [World.Cache].
//
// For registered filters, the relevant archetypes are tracked internally,
// so that there are no mask checks required during iteration.
// This is particularly helpful to avoid query iteration slowdown by a very high number of archetypes.
// If the number of archetypes exceeds approx. 50-100, uncached filters experience a slowdown.
// The relative slowdown increases with lower numbers of entities queried (below a few thousand).
// Cached filters avoid this slowdown.
//
// Further, cached filters should be used for complex queries built with package [github.com/mlange-42/arche/filter].
//
// The overhead of tracking cached filters internally is very low, as updates are required only when new archetypes are created.
type Cache struct {
        indices       map[uint32]int              // Mapping from filter IDs to indices in filters
        filters       []cacheEntry                // The cached filters, indexed by indices
        getArchetypes func(f Filter) []*archetype // Callback for getting archetypes for a new filter from the world
        intPool       intPool[uint32]             // Pool for filter IDs
}

// newCache creates a new [Cache].
func newCache() Cache {
        return Cache{
                intPool: newIntPool[uint32](128),
                indices: map[uint32]int{},
                filters: []cacheEntry{},
        }
}

// Register a [Filter].
//
// Use the returned [CachedFilter] to construct queries:
//
//        filter := All(posID, velID)
//        cached := world.Cache().Register(&filter)
//        query := world.Query(&cached)
func (c *Cache) Register(f Filter) CachedFilter {
        if _, ok := f.(*CachedFilter); ok {
                panic("filter is already cached")
        }
        id := c.intPool.Get()
        c.filters = append(c.filters,
                cacheEntry{
                        ID:         id,
                        Filter:     f,
                        Archetypes: pointers[archetype]{c.getArchetypes(f)},
                        Indices:    nil,
                })
        c.indices[id] = len(c.filters) - 1
        return CachedFilter{f, id}
}

// Unregister a filter.
//
// Returns the original filter.
func (c *Cache) Unregister(f *CachedFilter) Filter {
        idx, ok := c.indices[f.id]
        if !ok {
                panic("no filter for id found to unregister")
        }
        filter := c.filters[idx].Filter
        delete(c.indices, 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.filters[last] = cacheEntry{}
        c.filters = c.filters[:last]

        return filter
}

// Returns the [cacheEntry] for the given filter.
//
// Panics if there is no entry for the filter's ID.
func (c *Cache) get(f *CachedFilter) *cacheEntry {
        if idx, ok := c.indices[f.id]; ok {
                return &c.filters[idx]
        }
        panic("no filter for id found")
}

// Adds a node.
//
// Iterates over all filters and adds the node to the resp. entry where the filter matches.
func (c *Cache) addArchetype(arch *archetype) {
        if !arch.HasRelation() {
                for i := range c.filters {
                        e := &c.filters[i]
                        if !e.Filter.Matches(arch.Mask) {
                                continue
                        }
                        e.Archetypes.Add(arch)
                }
                return
        }

        for i := range c.filters {
                e := &c.filters[i]
                if !e.Filter.Matches(arch.Mask) {
                        continue
                }
                if rf, ok := e.Filter.(*RelationFilter); ok {
                        if rf.Target == arch.RelationTarget {
                                e.Archetypes.Add(arch)
                                // Not required: can't add after removing,
                                // as the target entity is dead.
                                // if e.Indices != nil { e.Indices[arch] = int(e.Archetypes.Len() - 1) }
                        }
                        continue
                }
                e.Archetypes.Add(arch)
                if e.Indices != nil {
                        e.Indices[arch] = int(e.Archetypes.Len() - 1)
                }
        }
}

// Removes an archetype.
//
// Can only be used for archetypes that have a relation target.
// Archetypes without a relation are never removed.
func (c *Cache) removeArchetype(arch *archetype) {
        for i := range c.filters {
                e := &c.filters[i]

                if e.Indices == nil && e.Filter.Matches(arch.Mask) {
                        c.mapArchetypes(e)
                }

                if idx, ok := e.Indices[arch]; ok {
                        swap := e.Archetypes.RemoveAt(idx)
                        if swap {
                                e.Indices[e.Archetypes.Get(int32(idx))] = idx
                        }
                        delete(e.Indices, arch)
                }
        }
}

func (c *Cache) mapArchetypes(e *cacheEntry) {
        e.Indices = map[*archetype]int{}
        for i, arch := range e.Archetypes.pointers {
                if arch.HasRelation() {
                        e.Indices[arch] = i
                }
        }
}

1	package ecs
2
3	// Cache entry for a [Filter].
4	type cacheEntry struct {
5	ID uint32 // Filter ID.
6	Filter Filter // The underlying filter.
7	Archetypes pointers[archetype] // Nodes matching the filter.
8	Indices map[*archetype]int // Map of archetype indices for removal.
9	}
10
11	// Cache provides [Filter] caching to speed up queries.
12	//
13	// Access it using [World.Cache].
14	//
15	// For registered filters, the relevant archetypes are tracked internally,
16	// so that there are no mask checks required during iteration.
17	// This is particularly helpful to avoid query iteration slowdown by a very high number of archetypes.
18	// If the number of archetypes exceeds approx. 50-100, uncached filters experience a slowdown.
19	// The relative slowdown increases with lower numbers of entities queried (below a few thousand).
20	// Cached filters avoid this slowdown.
21	//
22	// Further, cached filters should be used for complex queries built with package [github.com/mlange-42/arche/filter].
23	//
24	// The overhead of tracking cached filters internally is very low, as updates are required only when new archetypes are created.
25	type Cache struct {
26	indices map[uint32]int // Mapping from filter IDs to indices in filters
27	filters []cacheEntry // The cached filters, indexed by indices
28	getArchetypes func(f Filter) []*archetype // Callback for getting archetypes for a new filter from the world
29	intPool intPool[uint32] // Pool for filter IDs
30	}
31
32	// newCache creates a new [Cache].
33	func newCache() Cache {	97✔
34	return Cache{	97✔
35	intPool: newIntPool[uint32](128),	97✔
36	indices: map[uint32]int{},	97✔
37	filters: []cacheEntry{},	97✔
38	}	97✔
39	}	97✔
40
41	// Register a [Filter].
42	//
43	// Use the returned [CachedFilter] to construct queries:
44	//
45	// filter := All(posID, velID)
46	// cached := world.Cache().Register(&filter)
47	// query := world.Query(&cached)
48	func (c *Cache) Register(f Filter) CachedFilter {	22✔
49	if _, ok := f.(*CachedFilter); ok {	23✔
50	panic("filter is already cached")	1✔
51	}
52	id := c.intPool.Get()	21✔
53	c.filters = append(c.filters,	21✔
54	cacheEntry{	21✔
55	ID: id,	21✔
56	Filter: f,	21✔
57	Archetypes: pointers[archetype]{c.getArchetypes(f)},	21✔
58	Indices: nil,	21✔
59	})	21✔
60	c.indices[id] = len(c.filters) - 1	21✔
61	return CachedFilter{f, id}	21✔
62	}
63
64	// Unregister a filter.
65	//
66	// Returns the original filter.
67	func (c Cache) Unregister(f CachedFilter) Filter {	9✔
68	idx, ok := c.indices[f.id]	9✔
69	if !ok {	10✔
70	panic("no filter for id found to unregister")	1✔
71	}
72	filter := c.filters[idx].Filter	8✔
73	delete(c.indices, f.id)	8✔
74		8✔
75	last := len(c.filters) - 1	8✔
76	if idx != last {	9✔
77	c.filters[idx], c.filters[last] = c.filters[last], c.filters[idx]	1✔
78	c.indices[c.filters[idx].ID] = idx	1✔
79	}	1✔
80	c.filters[last] = cacheEntry{}	8✔
81	c.filters = c.filters[:last]	8✔
82		8✔
83	return filter	8✔
84	}
85
86	// Returns the [cacheEntry] for the given filter.
87	//
88	// Panics if there is no entry for the filter's ID.
89	func (c Cache) get(f CachedFilter) *cacheEntry {	25✔
90	if idx, ok := c.indices[f.id]; ok {	49✔
91	return &c.filters[idx]	24✔
92	}	24✔
93	panic("no filter for id found")	1✔
94	}
95
96	// Adds a node.
97	//
98	// Iterates over all filters and adds the node to the resp. entry where the filter matches.
99	func (c Cache) addArchetype(arch archetype) {	28,795✔
100	if !arch.HasRelation() {	30,008✔
101	for i := range c.filters {	1,222✔
102	e := &c.filters[i]	9✔
103	if !e.Filter.Matches(arch.Mask) {	15✔
104	continue	6✔
105	}
106	e.Archetypes.Add(arch)	3✔
107	}
108	return	1,213✔
109	}
110
111	for i := range c.filters {	27,607✔
112	e := &c.filters[i]	25✔
113	if !e.Filter.Matches(arch.Mask) {	28✔
114	continue	3✔
115	}
116	if rf, ok := e.Filter.(*RelationFilter); ok {	38✔
117	if rf.Target == arch.RelationTarget {	21✔
118	e.Archetypes.Add(arch)	5✔
119	// Not required: can't add after removing,	5✔
120	// as the target entity is dead.	5✔
121	// if e.Indices != nil { e.Indices[arch] = int(e.Archetypes.Len() - 1) }	5✔
122	}	5✔
123	continue	16✔
124	}
125	e.Archetypes.Add(arch)	6✔
126	if e.Indices != nil {	10✔
127	e.Indices[arch] = int(e.Archetypes.Len() - 1)	4✔
128	}	4✔
129	}
130	}
131
132	// Removes an archetype.
133	//
134	// Can only be used for archetypes that have a relation target.
135	// Archetypes without a relation are never removed.
136	func (c Cache) removeArchetype(arch archetype) {	27,421✔
137	for i := range c.filters {	27,445✔
138	e := &c.filters[i]	24✔
139		24✔
140	if e.Indices == nil && e.Filter.Matches(arch.Mask) {	28✔
141	c.mapArchetypes(e)	4✔
142	}	4✔
143
144	if idx, ok := e.Indices[arch]; ok {	32✔
145	swap := e.Archetypes.RemoveAt(idx)	8✔
146	if swap {	12✔
147	e.Indices[e.Archetypes.Get(int32(idx))] = idx	4✔
148	}	4✔
149	delete(e.Indices, arch)	8✔
150	}
151	}
152	}
153
154	func (c Cache) mapArchetypes(e cacheEntry) {	4✔
155	e.Indices = map[*archetype]int{}	4✔
156	for i, arch := range e.Archetypes.pointers {	8✔
157	if arch.HasRelation() {	8✔
158	e.Indices[arch] = i	4✔
159	}	4✔
160	}
161	}

mlange-42 / arche / 4958046752

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous