13751358310

Committed 09 Mar 2025 06:32PM CUT coverage: 99.43%. Remained the same

Build # 13751358310

Build Type

push

github

Committed by

web-flow

Commit Message

Add Zenodo DOI and how to cite (#168)

Run Details

6456 of 6493 relevant lines covered (99.43%)

27231.61 hits per line

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

97.83

/ecs/cache.go

package ecs

import "math"

type cacheID uint32

const maxCacheID = math.MaxUint32

// Cache entry for a [Filter].
type cacheEntry struct {
        id      cacheID         // Entry ID.
        filter  Batch           // The underlying filter.
        indices map[tableID]int // Map of table indices for removal.
        tables  []tableID       // Tables matching the filter.
}

// cache provides [Filter] caching to speed up queries.
//
// 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 (noticeable below a few thousand entities).
// Cached filters avoid this slowdown.
//
// 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[cacheID]int  // Mapping from filter IDs to indices in filters
        filters []cacheEntry     // The cached filters, indexed by indices
        intPool intPool[cacheID] // Pool for filter IDs
}

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

func (c *cache) getEntry(id cacheID) *cacheEntry {
        return &c.filters[c.indices[id]]
}

// Register a [Filter].
func (c *cache) register(storage *storage, batch *Batch) cacheID {
        // TODO: prevent duplicate registration
        id := c.intPool.Get()
        index := len(c.filters)
        c.filters = append(c.filters,
                cacheEntry{
                        id:      id,
                        filter:  *batch,
                        tables:  storage.getTableIDs(batch),
                        indices: nil,
                })
        c.indices[id] = index
        return id
}

func (c *cache) unregister(id cacheID) {
        idx, ok := c.indices[id]
        if !ok {
                panic("no filter for id found to unregister")
        }
        delete(c.indices, 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]
}

// Adds a table.
//
// Iterates over all filters and adds the node to the resp. entry where the filter matches.
func (c *cache) addTable(storage *storage, table *table) {
        arch := &storage.archetypes[table.archetype]
        if !table.HasRelations() {
                for i := range c.filters {
                        e := &c.filters[i]
                        if !e.filter.filter.matches(&arch.mask) {
                                continue
                        }
                        e.tables = append(e.tables, table.id)
                }
                return
        }

        for i := range c.filters {
                e := &c.filters[i]
                if !e.filter.filter.matches(&arch.mask) {
                        continue
                }
                if !table.Matches(e.filter.relations) {
                        continue
                }
                e.tables = append(e.tables, table.id)
                if e.indices != nil {
                        e.indices[table.id] = len(e.tables) - 1
                }
        }
}

// Removes a table.
//
// Can only be used for tables that have a relation target.
// Tables without a relation are never removed.
func (c *cache) removeTable(storage *storage, table *table) {
        if !table.HasRelations() {
                return
        }
        arch := &storage.archetypes[table.archetype]
        for i := range c.filters {
                e := &c.filters[i]

                if e.indices == nil && e.filter.filter.matches(&arch.mask) {
                        c.mapTables(storage, e)
                }

                if idx, ok := e.indices[table.id]; ok {
                        lastIndex := len(e.tables) - 1
                        swapped := idx != lastIndex
                        if swapped {
                                e.tables[idx], e.tables[lastIndex] = e.tables[lastIndex], e.tables[idx]
                        }
                        e.tables = e.tables[:lastIndex]
                        if swapped {
                                e.indices[e.tables[idx]] = idx
                        }
                        delete(e.indices, table.id)
                }
        }
}

func (c *cache) mapTables(storage *storage, e *cacheEntry) {
        e.indices = map[tableID]int{}
        for i, tableID := range e.tables {
                table := &storage.tables[tableID]
                if table.HasRelations() {
                        e.indices[tableID] = i
                }
        }
}

func (c *cache) Reset() {
        for i := range c.filters {
                c.filters[i].tables = nil
        }
        c.indices = map[cacheID]int{}
        c.filters = c.filters[:0]
        c.intPool.Reset()
}

1	package ecs
2
3	import "math"
4
5	type cacheID uint32
6
7	const maxCacheID = math.MaxUint32
8
9	// Cache entry for a [Filter].
10	type cacheEntry struct {
11	id cacheID // Entry ID.
12	filter Batch // The underlying filter.
13	indices map[tableID]int // Map of table indices for removal.
14	tables []tableID // Tables matching the filter.
15	}
16
17	// cache provides [Filter] caching to speed up queries.
18	//
19	// For registered filters, the relevant archetypes are tracked internally,
20	// so that there are no mask checks required during iteration.
21	// This is particularly helpful to avoid query iteration slowdown by a very high number of archetypes.
22	// If the number of archetypes exceeds approx. 50-100, uncached filters experience a slowdown.
23	// The relative slowdown increases with lower numbers of entities queried (noticeable below a few thousand entities).
24	// Cached filters avoid this slowdown.
25	//
26	// The overhead of tracking cached filters internally is very low, as updates are required only when new archetypes are created.
27	type cache struct {
28	indices map[cacheID]int // Mapping from filter IDs to indices in filters
29	filters []cacheEntry // The cached filters, indexed by indices
30	intPool intPool[cacheID] // Pool for filter IDs
31	}
32
33	// newCache creates a new [cache].
34	func newCache() cache {	208✔
35	return cache{	208✔
36	intPool: newIntPool[cacheID](128),	208✔
37	indices: map[cacheID]int{},	208✔
38	filters: []cacheEntry{},	208✔
39	}	208✔
40	}	208✔
41
42	func (c cache) getEntry(id cacheID) cacheEntry {	28✔
43	return &c.filters[c.indices[id]]	28✔
44	}	28✔
45
46	// Register a [Filter].
47	func (c cache) register(storage storage, batch *Batch) cacheID {	32✔
48	// TODO: prevent duplicate registration	32✔
49	id := c.intPool.Get()	32✔
50	index := len(c.filters)	32✔
51	c.filters = append(c.filters,	32✔
52	cacheEntry{	32✔
53	id: id,	32✔
54	filter: *batch,	32✔
55	tables: storage.getTableIDs(batch),	32✔
56	indices: nil,	32✔
57	})	32✔
58	c.indices[id] = index	32✔
59	return id	32✔
60	}	32✔
61
62	func (c *cache) unregister(id cacheID) {	28✔
63	idx, ok := c.indices[id]	28✔
64	if !ok {	29✔
65	panic("no filter for id found to unregister")	1✔
66	}
67	delete(c.indices, id)	27✔
68		27✔
69	last := len(c.filters) - 1	27✔
70	if idx != last {	28✔
71	c.filters[idx], c.filters[last] = c.filters[last], c.filters[idx]	1✔
72	c.indices[c.filters[idx].id] = idx	1✔
73	}	1✔
74	c.filters[last] = cacheEntry{}	27✔
75	c.filters = c.filters[:last]	27✔
76	}
77
78	// Adds a table.
79	//
80	// Iterates over all filters and adds the node to the resp. entry where the filter matches.
81	func (c cache) addTable(storage storage, table *table) {	491✔
82	arch := &storage.archetypes[table.archetype]	491✔
83	if !table.HasRelations() {	852✔
84	for i := range c.filters {	366✔
85	e := &c.filters[i]	5✔
86	if !e.filter.filter.matches(&arch.mask) {	9✔
87	continue	4✔
88	}
89	e.tables = append(e.tables, table.id)	1✔
90	}
91	return	361✔
92	}
93
94	for i := range c.filters {	153✔
95	e := &c.filters[i]	23✔
96	if !e.filter.filter.matches(&arch.mask) {	28✔
97	continue	5✔
98	}
99	if !table.Matches(e.filter.relations) {	27✔
100	continue	9✔
101	}
102	e.tables = append(e.tables, table.id)	9✔
103	if e.indices != nil {	15✔
104	e.indices[table.id] = len(e.tables) - 1	6✔
105	}	6✔
106	}
107	}
108
109	// Removes a table.
110	//
111	// Can only be used for tables that have a relation target.
112	// Tables without a relation are never removed.
113	func (c cache) removeTable(storage storage, table *table) {	13✔
114	if !table.HasRelations() {	13✔
115	return	×
116	}	×
117	arch := &storage.archetypes[table.archetype]	13✔
118	for i := range c.filters {	35✔
119	e := &c.filters[i]	22✔
120		22✔
121	if e.indices == nil && e.filter.filter.matches(&arch.mask) {	25✔
122	c.mapTables(storage, e)	3✔
123	}	3✔
124
125	if idx, ok := e.indices[table.id]; ok {	31✔
126	lastIndex := len(e.tables) - 1	9✔
127	swapped := idx != lastIndex	9✔
128	if swapped {	13✔
129	e.tables[idx], e.tables[lastIndex] = e.tables[lastIndex], e.tables[idx]	4✔
130	}	4✔
131	e.tables = e.tables[:lastIndex]	9✔
132	if swapped {	13✔
133	e.indices[e.tables[idx]] = idx	4✔
134	}	4✔
135	delete(e.indices, table.id)	9✔
136	}
137	}
138	}
139
140	func (c cache) mapTables(storage storage, e *cacheEntry) {	3✔
141	e.indices = map[tableID]int{}	3✔
142	for i, tableID := range e.tables {	6✔
143	table := &storage.tables[tableID]	3✔
144	if table.HasRelations() {	6✔
145	e.indices[tableID] = i	3✔
146	}	3✔
147	}
148	}
149
150	func (c *cache) Reset() {	1✔
151	for i := range c.filters {	2✔
152	c.filters[i].tables = nil	1✔
153	}	1✔
154	c.indices = map[cacheID]int{}	1✔
155	c.filters = c.filters[:0]	1✔
156	c.intPool.Reset()	1✔
157	}

mlange-42 / ark / 13751358310

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