4942034631

Committed 10 May 2023 10:57PM CUT coverage: 100.0%. Remained the same

Build # 4942034631

Build Type

push

github

Committed by GitHub

Commit Message

Optimize query creation and cached queries (#288)

Run Details

169 of 169 new or added lines in 9 files covered. (100.0%)

3768 of 3768 relevant lines covered (100.0%)

84592.23 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.
}

// 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)},
                })
        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)
                        }
                        continue
                }
                e.Archetypes.Add(arch)
        }
}

// Removes an archetype.
//
// Iterates over all filters and removes the archetype from the resp. entry where the filter matches.
func (c *Cache) removeArchetype(arch *archetype) {
        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.Remove(arch)
                        }
                        continue
                }
                e.Archetypes.Remove(arch)
        }
}

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

mlange-42 / arche / 4942034631

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