4935287491

Committed 10 May 2023 09:18AM CUT coverage: 100.0%. Remained the same

Build Type

push

github

Committed by GitHub

Commit Message

Replace Aos benchmarks plot for pointer iteration fix #284 (#285)

Run Details

3757 of 3757 relevant lines covered (100.0%)

84801.77 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.
        Nodes  []*archNode // 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
        getNodes func(f Filter) []*archNode // 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,
                        Nodes:  c.getNodes(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) addNode(node *archNode) {
        ln := len(c.filters)
        for i := 0; i < ln; i++ {
                e := &c.filters[i]
                if node.Matches(e.Filter) {
                        e.Nodes = append(e.Nodes, node)
                }
        }
}

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	Nodes []*archNode // 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	getNodes func(f Filter) []*archNode // 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 {	96✔
33	return Cache{	96✔
34	intPool: newIntPool[uint32](128),	96✔
35	indices: map[uint32]int{},	96✔
36	filters: []cacheEntry{},	96✔
37	}	96✔
38	}	96✔
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 {	19✔
48	if _, ok := f.(*CachedFilter); ok {	20✔
49	panic("filter is already cached")	1✔
50	}
51	id := c.intPool.Get()	18✔
52	c.filters = append(c.filters,	18✔
53	cacheEntry{	18✔
54	ID: id,	18✔
55	Filter: f,	18✔
56	Nodes: c.getNodes(f),	18✔
57	})	18✔
58	c.indices[id] = len(c.filters) - 1	18✔
59	return CachedFilter{f, id}	18✔
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 {	22✔
88	if idx, ok := c.indices[f.id]; ok {	43✔
89	return &c.filters[idx]	21✔
90	}	21✔
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) addNode(node archNode) {	1,272✔
98	ln := len(c.filters)	1,272✔
99	for i := 0; i < ln; i++ {	1,279✔
100	e := &c.filters[i]	7✔
101	if node.Matches(e.Filter) {	11✔
102	e.Nodes = append(e.Nodes, node)	4✔
103	}	4✔
104	}
105	}

mlange-42 / arche / 4935287491

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