18761516878

Committed 23 Oct 2025 08:43PM UTC coverage: 68.56% (-0.3%) from 68.825%

Build # 18761516878

Build Type

Pull #55

github

Committed by

ghettovoice

Commit Message

Memory usage optimizations

- use abnf.Nodes by pointer
- use multiError by pointer and allocc only when needed
- use small abnf.Nodes for children nodes
- use chunk of input for cache key

Pull Request Pull Request #55: Memory usage optimizations

Run Details

97 of 121 new or added lines in 4 files covered. (80.17%)

1 existing line in 1 file now uncovered.

1509 of 2201 relevant lines covered (68.56%)

55.04 hits per line

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

51.33

/node.go

package abnf

import (
        "bytes"
        "encoding/binary"
        "hash"
        "hash/fnv"
        "sync"
        "sync/atomic"
        "unsafe"

        lru "github.com/hashicorp/golang-lru/v2"
)

// Node represents a single node in a tree generated by [Operator].
type Node struct {
        Key      string
        Pos      uint
        Value    []byte
        Children Nodes
}

// String returns the node's value as string.
func (n *Node) String() string {
        if n == nil {
                return ""
        }
        return string(n.Value)
}

// Len returns length of the node's value.
func (n *Node) Len() int {
        if n == nil {
                return 0
        }
        return len(n.Value)
}

// IsEmpty returns true if the node's value length = 0.
func (n *Node) IsEmpty() bool { return n == nil || len(n.Value) == 0 }

// Contains returns whether the subtree contains the given key.
func (n *Node) Contains(key string) bool {
        if n == nil {
                return false
        }
        _, ok := n.GetNode(key)
        return ok
}

// GetNode recursively searches a node with the given key starting from itself.
// Returns found node or nil if not found.
func (n *Node) GetNode(key string) (*Node, bool) {
        if n == nil {
                return nil, false
        }
        if n.Key == key {
                return n, true
        }
        return n.Children.Get(key)
}

// GetNodes recursively searches all nodes with the given key starting from itself.
func (n *Node) GetNodes(key string) Nodes {
        if n == nil {
                return nil
        }

        var ns Nodes
        if n.Key == key {
                ns = append(ns, n)
        }
        ns = append(ns, n.Children.AllByKey(key)...)
        return ns
}

// Compare compares node values via [bytes.Compare].
// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
func (n *Node) Compare(other *Node) int {
        if n == other {
                return 0
        } else if n == nil {
                return -1
        } else if other == nil {
                return 1
        }
        return bytes.Compare(n.Value, other.Value)
}

var nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]

// EnableNodeCache initializes the node cache.
// If size is 0, it will be set to 1024.
// By default, the cache is disabled.
// It does nothing if the cache is already enabled.
// Call this function before using any [Operator], usually in the [init].
func EnableNodeCache(size uint) {
        if nodeCache.Load() != nil {
                return
        }

        if size == 0 {
                size = 1024
        }

        cache, _ := lru.New[uint64, *Node](int(size))
        nodeCache.Store(cache)
}

// ResizeNodeCache resizes the node cache.
// If size is 0, it will be set to 1024.
// It does nothing if the cache is disabled.
// It is safe to call this function from multiple goroutines.
func ResizeNodeCache(size uint) {
        if size == 0 {
                size = 1024
        }

        if cache := nodeCache.Load(); cache != nil {
                cache.Resize(int(size))
        }
}

// DisableNodeCache disables the node cache and purges all cached nodes.
// It does nothing if the cache is already disabled.
// It is safe to call this function from multiple goroutines.
func DisableNodeCache() {
        if cache := nodeCache.Swap(nil); cache != nil {
                cache.Purge()
        }
}

type nodeCacheKey struct {
        hash.Hash64
        buf [8]byte
}

var nodeCacheKeyPool = sync.Pool{
        New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },
}

func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...*Node) *nodeCacheKey {
        ck := nodeCacheKeyPool.Get().(*nodeCacheKey)
        ck.writeBase(key, pos, len, input)
        ck.writeChildKeys(0, ns...)
        return ck
}

func (ck *nodeCacheKey) free() {
        if ck == nil {
                return
        }

        ck.Reset()
        nodeCacheKeyPool.Put(ck)
}

func (ck *nodeCacheKey) writeBase(key string, pos, length uint, input []byte) {
        ck.Write(unsafeStringToBytes(key))

        binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))
        ck.Write(ck.buf[:])

        binary.BigEndian.PutUint64(ck.buf[:], uint64(length))
        ck.Write(ck.buf[:])

        if len(input) == 0 || length == 0 {
                return
        }

        start := int(pos)
        if start >= len(input) {
                return
        }
        end := min(start+int(length), len(input))
        ck.Write(input[start:end])
}

func (ck *nodeCacheKey) writeChildKeys(depth uint, ns ...*Node) {
        for _, n := range ns {
                binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))
                ck.Write(ck.buf[:])
                ck.Write(unsafeStringToBytes(n.Key))
                ck.writeChildKeys(depth+1, n.Children...)
        }
}

func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }

// unsafeStringToBytes converts string to []byte without allocation
// WARNING: The returned byte slice must not be modified
func unsafeStringToBytes(s string) []byte {
        return *(*[]byte)(unsafe.Pointer(&struct {
                string
                int
        }{s, len(s)}))
}

func loadNode(k *nodeCacheKey) (*Node, bool) {
        cache := nodeCache.Load()
        if cache == nil {
                return nil, false
        }

        n, ok := cache.Get(k.hash())
        if !ok {
                return nil, false
        }
        return n, true
}

func storeNode(k *nodeCacheKey, n *Node) {
        cache := nodeCache.Load()
        if cache == nil {
                return
        }

        cache.Add(k.hash(), n)
}

func loadOrStoreNode(k *nodeCacheKey, newNode func() *Node) *Node {
        defer k.free()

        cache := nodeCache.Load()
        if cache == nil {
                return newNode()
        }

        if n, ok := loadNode(k); ok {
                return n
        }

        n := newNode()
        storeNode(k, n)
        return n
}

// Nodes represents a list of nodes.
type Nodes []*Node

func (ns *Nodes) Len() int {
        if ns == nil {
                return 0
        }
        return len(*ns)
}

// Contains returns whether the subtree contains the given key.
func (ns *Nodes) Contains(key string) bool {
        if ns == nil {
                return false
        }

        for _, n := range *ns {
                if n.Key == key || n.Children.Contains(key) {
                        return true
                }
        }
        return false
}

// Get recursively searches a node with the given key.
func (ns *Nodes) Get(key string) (*Node, bool) {
        if ns == nil {
                return nil, false
        }

        for _, n := range *ns {
                if n.Key == key {
                        return n, true
                }
                if n, ok := n.Children.Get(key); ok {
                        return n, true
                }
        }
        return nil, false
}

// All returns all nodes in the list.
func (ns *Nodes) All() Nodes {
        if ns == nil {
                return nil
        }
        return *ns
}

// GetAll recursively searches all nodes with the given key.
func (ns *Nodes) AllByKey(key string) Nodes {
        if ns == nil {
                return nil
        }

        var nodes Nodes
        for _, n := range *ns {
                if n.Key == key {
                        nodes = append(nodes, n)
                }
                nodes = append(nodes, n.Children.AllByKey(key)...)
        }
        return nodes
}

// Best returns a node with the longest value or nil if the list is empty.
func (ns *Nodes) Best() *Node {
        if ns == nil || len(*ns) == 0 {
                return nil
        }

        best := (*ns)[0]
        for _, n := range (*ns)[1:] {
                if n.Len() > best.Len() {
                        best = n
                }
        }
        return best
}

// Compare compares two best nodes.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
func (ns *Nodes) Compare(other *Nodes) int {
        if ns == nil || other == nil {
                return 0
        }
        return ns.Best().Compare(other.Best())
}

func (ns *Nodes) Append(n ...*Node) {
        *ns = append(*ns, n...)
}

// NodesCap is a initial capacity of a new nodes list.
var NodesCap = 10

var nodesPool = &sync.Pool{
        New: func() any {
                ns := make(Nodes, 0, NodesCap)
                return &ns
        },
}

// NewNodes returns a new nodes list from the pool.
func NewNodes() *Nodes {
        return nodesPool.Get().(*Nodes)
}

// Clear clears the nodes list.
func (ns *Nodes) Clear() {
        if ns == nil {
                return
        }

        clear(*ns)
        *ns = (*ns)[:0]
}

// Free returns the nodes list to the pool.
func (ns *Nodes) Free() {
        ns.Clear()

        if ns == nil || cap(*ns) == 0 || cap(*ns) > 10*NodesCap {
                return
        }

        nodesPool.Put(ns)
}

type nodesSorter Nodes

func (ns *nodesSorter) Len() int { return len(*ns) }

func (ns *nodesSorter) Less(i, j int) bool {
        return len((*ns)[i].Value) > len((*ns)[j].Value) ||
                len((*ns)[i].Children) > len((*ns)[j].Children) ||
                (*ns)[i].Pos < (*ns)[j].Pos ||
                (*ns)[i].Key < (*ns)[j].Key
}

func (ns *nodesSorter) Swap(i, j int) { (*ns)[i], (*ns)[j] = (*ns)[j], (*ns)[i] }

1	package abnf
2
3	import (
4	"bytes"
5	"encoding/binary"
6	"hash"
7	"hash/fnv"
8	"sync"
9	"sync/atomic"
10	"unsafe"
11
12	lru "github.com/hashicorp/golang-lru/v2"
13	)
14
15	// Node represents a single node in a tree generated by [Operator].
16	type Node struct {
17	Key string
18	Pos uint
19	Value []byte
20	Children Nodes
21	}
22
23	// String returns the node's value as string.
24	func (n *Node) String() string {	3✔
25	if n == nil {	3✔
26	return ""	×
27	}	×
28	return string(n.Value)	3✔
29	}
30
31	// Len returns length of the node's value.
32	func (n *Node) Len() int {	48✔
33	if n == nil {	48✔
34	return 0	×
35	}	×
36	return len(n.Value)	48✔
37	}
38
39	// IsEmpty returns true if the node's value length = 0.
40	func (n *Node) IsEmpty() bool { return n == nil \|\| len(n.Value) == 0 }	×
41
42	// Contains returns whether the subtree contains the given key.
43	func (n *Node) Contains(key string) bool {	×
44	if n == nil {	×
45	return false	×
46	}	×
47	_, ok := n.GetNode(key)	×
48	return ok	×
49	}
50
51	// GetNode recursively searches a node with the given key starting from itself.
52	// Returns found node or nil if not found.
53	func (n Node) GetNode(key string) (Node, bool) {	3✔
54	if n == nil {	3✔
55	return nil, false	×
56	}	×
57	if n.Key == key {	4✔
58	return n, true	1✔
59	}	1✔
60	return n.Children.Get(key)	2✔
61	}
62
63	// GetNodes recursively searches all nodes with the given key starting from itself.
64	func (n *Node) GetNodes(key string) Nodes {	×
65	if n == nil {	×
66	return nil	×
67	}	×
68
69	var ns Nodes	×
70	if n.Key == key {	×
71	ns = append(ns, n)	×
72	}	×
NEW 73	ns = append(ns, n.Children.AllByKey(key)...)	×
74	return ns	×
75	}
76
77	// Compare compares node values via [bytes.Compare].
78	// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
79	func (n Node) Compare(other Node) int {	35✔
80	if n == other {	35✔
81	return 0	×
82	} else if n == nil {	35✔
83	return -1	×
84	} else if other == nil {	35✔
85	return 1	×
86	}	×
87	return bytes.Compare(n.Value, other.Value)	35✔
88	}
89
90	var nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]
91
92	// EnableNodeCache initializes the node cache.
93	// If size is 0, it will be set to 1024.
94	// By default, the cache is disabled.
95	// It does nothing if the cache is already enabled.
96	// Call this function before using any [Operator], usually in the [init].
97	func EnableNodeCache(size uint) {	×
98	if nodeCache.Load() != nil {	×
99	return	×
100	}	×
101
102	if size == 0 {	×
103	size = 1024	×
104	}	×
105
106	cache, _ := lru.New[uint64, *Node](int(size))	×
107	nodeCache.Store(cache)	×
108	}
109
110	// ResizeNodeCache resizes the node cache.
111	// If size is 0, it will be set to 1024.
112	// It does nothing if the cache is disabled.
113	// It is safe to call this function from multiple goroutines.
114	func ResizeNodeCache(size uint) {	×
115	if size == 0 {	×
116	size = 1024	×
117	}	×
118
119	if cache := nodeCache.Load(); cache != nil {	×
120	cache.Resize(int(size))	×
121	}	×
122	}
123
124	// DisableNodeCache disables the node cache and purges all cached nodes.
125	// It does nothing if the cache is already disabled.
126	// It is safe to call this function from multiple goroutines.
127	func DisableNodeCache() {	×
128	if cache := nodeCache.Swap(nil); cache != nil {	×
129	cache.Purge()	×
130	}	×
131	}
132
133	type nodeCacheKey struct {
134	hash.Hash64
135	buf [8]byte
136	}
137
138	var nodeCacheKeyPool = sync.Pool{
139	New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },	56✔
140	}
141
142	func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...Node) nodeCacheKey {	276✔
143	ck := nodeCacheKeyPool.Get().(*nodeCacheKey)	276✔
144	ck.writeBase(key, pos, len, input)	276✔
145	ck.writeChildKeys(0, ns...)	276✔
146	return ck	276✔
147	}	276✔
148
149	func (ck *nodeCacheKey) free() {	276✔
150	if ck == nil {	276✔
151	return	×
152	}	×
153
154	ck.Reset()	276✔
155	nodeCacheKeyPool.Put(ck)	276✔
156	}
157
158	func (ck *nodeCacheKey) writeBase(key string, pos, length uint, input []byte) {	276✔
159	ck.Write(unsafeStringToBytes(key))	276✔
160		276✔
161	binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))	276✔
162	ck.Write(ck.buf[:])	276✔
163		276✔
164	binary.BigEndian.PutUint64(ck.buf[:], uint64(length))	276✔
165	ck.Write(ck.buf[:])	276✔
166		276✔
167	if len(input) == 0 \|\| length == 0 {	347✔
168	return	71✔
169	}	71✔
170
171	start := int(pos)	205✔
172	if start >= len(input) {	205✔
NEW 173	return	×
NEW 174	}	×
175	end := min(start+int(length), len(input))	205✔
176	ck.Write(input[start:end])	205✔
177	}
178
179	func (ck nodeCacheKey) writeChildKeys(depth uint, ns ...Node) {	705✔
180	for _, n := range ns {	1,014✔
181	binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))	309✔
182	ck.Write(ck.buf[:])	309✔
183	ck.Write(unsafeStringToBytes(n.Key))	309✔
184	ck.writeChildKeys(depth+1, n.Children...)	309✔
185	}	309✔
186	}
187
188	func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }	×
189
190	// unsafeStringToBytes converts string to []byte without allocation
191	// WARNING: The returned byte slice must not be modified
192	func unsafeStringToBytes(s string) []byte {	585✔
193	return ([]byte)(unsafe.Pointer(&struct {	585✔
194	string	585✔
195	int	585✔
196	}{s, len(s)}))	585✔
197	}	585✔
198
199	func loadNode(k nodeCacheKey) (Node, bool) {	×
200	cache := nodeCache.Load()	×
201	if cache == nil {	×
202	return nil, false	×
203	}	×
204
205	n, ok := cache.Get(k.hash())	×
206	if !ok {	×
207	return nil, false	×
208	}	×
209	return n, true	×
210	}
211
212	func storeNode(k nodeCacheKey, n Node) {	×
213	cache := nodeCache.Load()	×
214	if cache == nil {	×
215	return	×
216	}	×
217
218	cache.Add(k.hash(), n)	×
219	}
220
221	func loadOrStoreNode(k nodeCacheKey, newNode func() Node) *Node {	276✔
222	defer k.free()	276✔
223		276✔
224	cache := nodeCache.Load()	276✔
225	if cache == nil {	552✔
226	return newNode()	276✔
227	}	276✔
228
229	if n, ok := loadNode(k); ok {	×
230	return n	×
231	}	×
232
233	n := newNode()	×
234	storeNode(k, n)	×
235	return n	×
236	}
237
238	// Nodes represents a list of nodes.
239	type Nodes []*Node
240
241	func (ns *Nodes) Len() int {	213✔
242	if ns == nil {	213✔
NEW 243	return 0	×
NEW 244	}	×
245	return len(*ns)	213✔
246	}
247
248	// Contains returns whether the subtree contains the given key.
NEW 249	func (ns *Nodes) Contains(key string) bool {	×
NEW 250	if ns == nil {	×
NEW 251	return false	×
NEW 252	}	×
253
NEW 254	for _, n := range *ns {	×
255	if n.Key == key \|\| n.Children.Contains(key) {	×
256	return true	×
257	}	×
258	}
259	return false	×
260	}
261
262	// Get recursively searches a node with the given key.
263	func (ns Nodes) Get(key string) (Node, bool) {	6✔
264	if ns == nil {	6✔
NEW 265	return nil, false	×
NEW 266	}	×
267
268	for _, n := range *ns {	11✔
269	if n.Key == key {	6✔
270	return n, true	1✔
271	}	1✔
272	if n, ok := n.Children.Get(key); ok {	4✔
273	return n, true	×
274	}	×
275	}
276	return nil, false	5✔
277	}
278
279	// All returns all nodes in the list.
280	func (ns *Nodes) All() Nodes {	345✔
281	if ns == nil {	345✔
NEW 282	return nil	×
NEW 283	}	×
284	return *ns	345✔
285	}
286
287	// GetAll recursively searches all nodes with the given key.
NEW 288	func (ns *Nodes) AllByKey(key string) Nodes {	×
NEW 289	if ns == nil {	×
NEW 290	return nil	×
NEW 291	}	×
292
293	var nodes Nodes	×
NEW 294	for _, n := range *ns {	×
295	if n.Key == key {	×
296	nodes = append(nodes, n)	×
297	}	×
NEW 298	nodes = append(nodes, n.Children.AllByKey(key)...)	×
299	}
300	return nodes	×
301	}
302
303	// Best returns a node with the longest value or nil if the list is empty.
304	func (ns Nodes) Best() Node {	81✔
305	if ns == nil \|\| len(*ns) == 0 {	81✔
306	return nil	×
307	}	×
308
309	best := (*ns)[0]	81✔
310	for _, n := range (*ns)[1:] {	105✔
311	if n.Len() > best.Len() {	25✔
312	best = n	1✔
313	}	1✔
314	}
315	return best	81✔
316	}
317
318	// Compare compares two best nodes.
319	// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
320	func (ns Nodes) Compare(other Nodes) int {	35✔
321	if ns == nil \|\| other == nil {	35✔
NEW 322	return 0	×
NEW 323	}	×
324	return ns.Best().Compare(other.Best())	35✔
325	}
326
327	func (ns Nodes) Append(n ...Node) {	411✔
328	ns = append(ns, n...)	411✔
329	}	411✔
330
331	// NodesCap is a initial capacity of a new nodes list.
332	var NodesCap = 10
333
334	var nodesPool = &sync.Pool{
335	New: func() any {	74✔
336	ns := make(Nodes, 0, NodesCap)	74✔
337	return &ns	74✔
338	},	74✔
339	}
340
341	// NewNodes returns a new nodes list from the pool.
342	func NewNodes() *Nodes {	247✔
343	return nodesPool.Get().(*Nodes)	247✔
344	}	247✔
345
346	// Clear clears the nodes list.
347	func (ns *Nodes) Clear() {	562✔
348	if ns == nil {	562✔
349	return	×
350	}	×
351
352	clear(*ns)	562✔
353	ns = (ns)[:0]	562✔
354	}
355
356	// Free returns the nodes list to the pool.
357	func (ns *Nodes) Free() {	247✔
358	ns.Clear()	247✔
359		247✔
360	if ns == nil \|\| cap(ns) == 0 \|\| cap(ns) > 10*NodesCap {	247✔
361	return	×
362	}	×
363
364	nodesPool.Put(ns)	247✔
365	}
366
367	type nodesSorter Nodes
368
369	func (ns nodesSorter) Len() int { return len(ns) }	27✔
370
371	func (ns *nodesSorter) Less(i, j int) bool {	65✔
372	return len((ns)[i].Value) > len((ns)[j].Value) \|\|	65✔
373	len((ns)[i].Children) > len((ns)[j].Children) \|\|	65✔
374	(ns)[i].Pos < (ns)[j].Pos \|\|	65✔
375	(ns)[i].Key < (ns)[j].Key	65✔
376	}	65✔
377
378	func (ns nodesSorter) Swap(i, j int) { (ns)[i], (ns)[j] = (ns)[j], (*ns)[i] }	56✔

ghettovoice / abnf / 18761516878

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