11407461872

Committed 18 Oct 2024 04:31PM UTC coverage: 55.857% (-0.05%) from 55.91%

Build # 11407461872

Build Type

Pull #3528

github

Committed by

web-flow

Commit Message

Merge b2582a4c5 into bb71676fd

Pull Request Pull Request #3528: [OpCode Benchmark] add benchmark files

Run Details

5761 of 8898 branches covered (64.74%)

Branch coverage included in aggregate %.

28 of 43 new or added lines in 5 files covered. (65.12%)

36 existing lines in 5 files now uncovered.

21697 of 40260 relevant lines covered (53.89%)

86510.45 hits per line

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

81.01

/src/Neo.VM/ReferenceCounter.cs

// Copyright (C) 2015-2024 The Neo Project.
//
// ReferenceCounter.cs file belongs to the neo project and is free
// software distributed under the MIT software license, see the
// accompanying file LICENSE in the main directory of the
// repository or http://www.opensource.org/licenses/mit-license.php
// for more details.
//
// Redistribution and use in source and binary forms with or without
// modifications are permitted.

using Neo.VM.StronglyConnectedComponents;
using Neo.VM.Types;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;

namespace Neo.VM
{
    /// <summary>
    /// Used for reference counting of objects in the VM.
    /// </summary>
    public sealed class ReferenceCounter : IReferenceCounter
    {
        // If set to true, all items will be tracked regardless of their type.
        private const bool TrackAllItems = false;

        // Stores items that are being tracked for references.
        // Only CompoundType and Buffer items are tracked.
        private readonly HashSet<StackItem> _trackedItems = new(ReferenceEqualityComparer.Instance);

        // Stores items that have zero references.
        private readonly HashSet<StackItem> _zeroReferred = new(ReferenceEqualityComparer.Instance);

        // Caches strongly connected components for optimization.
        private LinkedList<HashSet<StackItem>>? _cachedComponents;

        // Keeps the total count of references.
        private int _referencesCount = 0;

        /// <inheritdoc/>
        public int Count => _referencesCount;

        /// <summary>
        /// Determines if an item needs to be tracked based on its type.
        /// </summary>
        /// <param name="item">The item to check.</param>
        /// <returns>True if the item needs to be tracked, otherwise false.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static bool NeedTrack(StackItem item)
        {
            // Track all items if TrackAllItems is true.
#pragma warning disable CS0162
            if (TrackAllItems) return true;
#pragma warning restore CS0162

            // Track the item if it is a CompoundType or Buffer.
            if (item is CompoundType or Buffer) return true;
            return false;
        }

        /// <inheritdoc/>
        public void AddReference(StackItem item, CompoundType parent)
        {
            // Increment the reference count.
            _referencesCount++;

            // If the item doesn't need to be tracked, return early.
            // Only track CompoundType and Buffer items.
            if (!NeedTrack(item)) return;

            // Invalidate the cached components since the tracked items are changing.
            _cachedComponents = null;

            // Add the item to the set of tracked items.
            _trackedItems.Add(item);

            // Initialize the ObjectReferences dictionary if it is null.
            item.ObjectReferences ??= new Dictionary<CompoundType, StackItem.ObjectReferenceEntry>(ReferenceEqualityComparer.Instance);

            // Add the parent to the item's ObjectReferences dictionary and increment its reference count.
            if (!item.ObjectReferences.TryGetValue(parent, out var pEntry))
            {
                pEntry = new StackItem.ObjectReferenceEntry(parent);
                item.ObjectReferences.Add(parent, pEntry);
            }
            pEntry.References++;
        }

        /// <inheritdoc/>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void AddStackReference(StackItem item, int count = 1)
        {
            // Increment the reference count by the specified count.
            _referencesCount += count;

            // If the item doesn't need to be tracked, return early.
            if (!NeedTrack(item)) return;

            // Add the item to the set of tracked items and to the cached components if needed.
            if (_trackedItems.Add(item))
                _cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });

            // Increment the item's stack references by the specified count.
            item.StackReferences += count;

            // Remove the item from the _zeroReferred set since it now has references.
            _zeroReferred.Remove(item);
        }

        /// <inheritdoc/>
        public void AddZeroReferred(StackItem item)
        {
            // Add the item to the _zeroReferred set.
            _zeroReferred.Add(item);

            // If the item doesn't need to be tracked, return early.
            if (!NeedTrack(item)) return;

            // Add the item to the cached components and the set of tracked items.
            _cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });
            _trackedItems.Add(item);
        }

        /// <summary>
        /// Checks and processes items that have zero references.
        ///
        /// This method is used to check items in the zero-referred list and clean up those that are no longer needed.
        /// It uses Tarjan's algorithm to find strongly connected components and remove those with no references.
        ///
        /// Use this method periodically to clean up items with zero references and free up memory.
        /// </summary>
        /// <returns>The current reference count.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int CheckZeroReferred()
        {
            // If there are items with zero references, process them.
            if (_zeroReferred.Count > 0)
            {
                // Clear the zero_referred set since we are going to process all of them.
                _zeroReferred.Clear();

                // If cached components are null, we need to recompute the strongly connected components (SCCs).
                if (_cachedComponents is null)
                {
                    // Create a new Tarjan object and invoke it to find all SCCs in the tracked_items graph.
                    Tarjan tarjan = new(_trackedItems);
                    _cachedComponents = tarjan.Invoke();
                }

                // Reset all tracked items' Tarjan algorithm-related fields (DFN, LowLink, and OnStack).
                foreach (var item in _trackedItems)
                    item.Reset();

                // Process each SCC in the cached_components list.
                for (var node = _cachedComponents.First; node != null;)
                {
                    var component = node.Value;
                    var onStack = false;

                    // Check if any item in the SCC is still on the stack.
                    foreach (var item in component)
                    {
                        // An item is considered 'on stack' if it has stack references or if its parent items are still on stack.
                        if (item.StackReferences > 0)
                        {
                            onStack = true;
                            break;
                        }

                        if (item.ObjectReferences != null)
                        {
                            foreach (var entry in item.ObjectReferences.Values)
                            {
                                if (entry.References > 0 && entry.Item.OnStack)
                                {
                                    onStack = true;
                                    break;
                                }
                            }
                            if (onStack) break;
                        }
                    }

                    // If any item in the component is on stack, mark all items in the component as on stack.
                    if (onStack)
                    {
                        foreach (var item in component)
                            item.OnStack = true;
                        node = node.Next;
                    }
                    else
                    {
                        // Otherwise, remove the component and clean up the items.
                        foreach (var item in component)
                        {
                            _trackedItems.Remove(item);

                            // If the item is a CompoundType, adjust the reference count and clean up its sub-items.
                            if (item is CompoundType compound)
                            {
                                // Decrease the reference count by the number of sub-items.
                                _referencesCount -= compound.SubItemsCount;
                                foreach (var subitem in compound.SubItems)
                                {
                                    // Skip sub-items that are in the same component or don't need tracking.
                                    if (component.Contains(subitem)) continue;
                                    if (!NeedTrack(subitem)) continue;

                                    // Remove the parent reference from the sub-item.
                                    subitem.ObjectReferences!.Remove(compound);
                                }
                            }

                            // Perform cleanup for the item.
                            item.Cleanup();
                        }

                        // Move to the next component and remove the current one from the cached_components list.
                        var nodeToRemove = node;
                        node = node.Next;
                        _cachedComponents.Remove(nodeToRemove);
                    }
                }
            }

            // Return the current total reference count.
            return _referencesCount;
        }

        /// <inheritdoc/>
        public void RemoveReference(StackItem item, CompoundType parent)
        {
            // Decrement the reference count.
            _referencesCount--;

            // If the item doesn't need to be tracked, return early.
            if (!NeedTrack(item)) return;

            // Invalidate the cached components since the tracked items are changing.
            _cachedComponents = null;

            // Decrement the reference count for the parent in the item's ObjectReferences dictionary.
            item.ObjectReferences![parent].References--;

            // If the item has no stack references, add it to the zero_referred set.
            if (item.StackReferences == 0)
                _zeroReferred.Add(item);
        }

        /// <inheritdoc/>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void RemoveStackReference(StackItem item)
        {
            // Decrement the reference count.
            _referencesCount--;

            // If the item doesn't need to be tracked, return early.
            if (!NeedTrack(item)) return;

            // Decrement the item's stack references and add it to the zero_referred set if it has no references.
            if (--item.StackReferences == 0)
                _zeroReferred.Add(item);
        }
    }
}

1	// Copyright (C) 2015-2024 The Neo Project.
2	//
3	// ReferenceCounter.cs file belongs to the neo project and is free
4	// software distributed under the MIT software license, see the
5	// accompanying file LICENSE in the main directory of the
6	// repository or http://www.opensource.org/licenses/mit-license.php
7	// for more details.
8	//
9	// Redistribution and use in source and binary forms with or without
10	// modifications are permitted.
11
12	using Neo.VM.StronglyConnectedComponents;
13	using Neo.VM.Types;
14	using System.Collections.Generic;
15	using System.Linq;
16	using System.Runtime.CompilerServices;
17
18	namespace Neo.VM
19	{
20	/// <summary>
21	/// Used for reference counting of objects in the VM.
22	/// </summary>
23	public sealed class ReferenceCounter : IReferenceCounter
24	{
25	// If set to true, all items will be tracked regardless of their type.
26	private const bool TrackAllItems = false;
27
28	// Stores items that are being tracked for references.
29	// Only CompoundType and Buffer items are tracked.
30	private readonly HashSet<StackItem> _trackedItems = new(ReferenceEqualityComparer.Instance);	1,945✔
31
32	// Stores items that have zero references.
33	private readonly HashSet<StackItem> _zeroReferred = new(ReferenceEqualityComparer.Instance);	1,945✔
34
35	// Caches strongly connected components for optimization.
36	private LinkedList<HashSet<StackItem>>? _cachedComponents;
37
38	// Keeps the total count of references.
39	private int _referencesCount = 0;	1,945✔
40
41	/// <inheritdoc/>
42	public int Count => _referencesCount;	99,404✔
43
44	/// <summary>
45	/// Determines if an item needs to be tracked based on its type.
46	/// </summary>
47	/// <param name="item">The item to check.</param>
48	/// <returns>True if the item needs to be tracked, otherwise false.</returns>
49	[MethodImpl(MethodImplOptions.AggressiveInlining)]
50	private static bool NeedTrack(StackItem item)
51	{	209,631✔
52	// Track all items if TrackAllItems is true.
53	#pragma warning disable CS0162
54	if (TrackAllItems) return true;	209,631✔
55	#pragma warning restore CS0162
56
57	// Track the item if it is a CompoundType or Buffer.
58	if (item is CompoundType or Buffer) return true;	242,897✔
59	return false;	176,365✔
60	}	209,631✔
61
62	/// <inheritdoc/>
63	public void AddReference(StackItem item, CompoundType parent)
64	{	30,908✔
65	// Increment the reference count.
66	_referencesCount++;	30,908✔
67
68	// If the item doesn't need to be tracked, return early.
69	// Only track CompoundType and Buffer items.
70	if (!NeedTrack(item)) return;	58,646✔
71
72	// Invalidate the cached components since the tracked items are changing.
73	_cachedComponents = null;	3,170✔
74
75	// Add the item to the set of tracked items.
76	_trackedItems.Add(item);	3,170✔
77
78	// Initialize the ObjectReferences dictionary if it is null.
79	item.ObjectReferences ??= new Dictionary<CompoundType, StackItem.ObjectReferenceEntry>(ReferenceEqualityComparer.Instance);	3,170✔
80
81	// Add the parent to the item's ObjectReferences dictionary and increment its reference count.
82	if (!item.ObjectReferences.TryGetValue(parent, out var pEntry))	3,170✔
83	{	3,170✔
84	pEntry = new StackItem.ObjectReferenceEntry(parent);	3,170✔
85	item.ObjectReferences.Add(parent, pEntry);	3,170✔
86	}	3,170✔
87	pEntry.References++;	3,170✔
88	}	30,908✔
89
90	/// <inheritdoc/>
91	[MethodImpl(MethodImplOptions.AggressiveInlining)]
92	public void AddStackReference(StackItem item, int count = 1)
93	{	86,736✔
94	// Increment the reference count by the specified count.
95	_referencesCount += count;	86,736✔
96
97	// If the item doesn't need to be tracked, return early.
98	if (!NeedTrack(item)) return;	164,408✔
99
100	// Add the item to the set of tracked items and to the cached components if needed.
101	if (_trackedItems.Add(item))	9,064✔
102	_cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });	8,251!
103
104	// Increment the item's stack references by the specified count.
105	item.StackReferences += count;	9,064✔
106
107	// Remove the item from the _zeroReferred set since it now has references.
108	_zeroReferred.Remove(item);	9,064✔
109	}	86,736✔
110
111	/// <inheritdoc/>
112	public void AddZeroReferred(StackItem item)
113	{	12,068✔
114	// Add the item to the _zeroReferred set.
115	_zeroReferred.Add(item);	12,068✔
116
117	// If the item doesn't need to be tracked, return early.
118	if (!NeedTrack(item)) return;	12,068✔
119
120	// Add the item to the cached components and the set of tracked items.
121	_cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });	12,068✔
122	_trackedItems.Add(item);	12,068✔
123	}	12,068✔
124
125	/// <summary>
126	/// Checks and processes items that have zero references.
127	///
128	/// This method is used to check items in the zero-referred list and clean up those that are no longer needed.
129	/// It uses Tarjan's algorithm to find strongly connected components and remove those with no references.
130	///
131	/// Use this method periodically to clean up items with zero references and free up memory.
132	/// </summary>
133	/// <returns>The current reference count.</returns>
134	[MethodImpl(MethodImplOptions.AggressiveInlining)]
135	public int CheckZeroReferred()
136	{	15✔
137	// If there are items with zero references, process them.
138	if (_zeroReferred.Count > 0)	15✔
139	{	2✔
140	// Clear the zero_referred set since we are going to process all of them.
141	_zeroReferred.Clear();	2✔
142
143	// If cached components are null, we need to recompute the strongly connected components (SCCs).
144	if (_cachedComponents is null)	2✔
145	{	1✔
146	// Create a new Tarjan object and invoke it to find all SCCs in the tracked_items graph.
147	Tarjan tarjan = new(_trackedItems);	1✔
148	_cachedComponents = tarjan.Invoke();	1✔
149	}	1✔
150
151	// Reset all tracked items' Tarjan algorithm-related fields (DFN, LowLink, and OnStack).
152	foreach (var item in _trackedItems)	10✔
153	item.Reset();	2✔
154
155	// Process each SCC in the cached_components list.
156	for (var node = _cachedComponents.First; node != null;)	6✔
157	{	2✔
158	var component = node.Value;	2✔
159	var onStack = false;	2✔
160
161	// Check if any item in the SCC is still on the stack.
162	foreach (var item in component)	10✔
163	{	2✔
164	// An item is considered 'on stack' if it has stack references or if its parent items are still on stack.
165	if (item.StackReferences > 0)	2!
166	{	×
NEW 167	onStack = true;	×
168	break;	×
169	}
170
171	if (item.ObjectReferences != null)	2!
NEW 172	{	×
NEW 173	foreach (var entry in item.ObjectReferences.Values)	×
NEW 174	{	×
NEW 175	if (entry.References > 0 && entry.Item.OnStack)	×
NEW 176	{	×
NEW 177	onStack = true;	×
NEW 178	break;	×
179	}
NEW 180	}	×
NEW 181	if (onStack) break;	×
NEW 182	}	×
183	}	2✔
184
185	// If any item in the component is on stack, mark all items in the component as on stack.
186	if (onStack)	2!
187	{	×
NEW 188	foreach (var item in component)	×
189	item.OnStack = true;	×
190	node = node.Next;	×
191	}	×
192	else
193	{	2✔
194	// Otherwise, remove the component and clean up the items.
195	foreach (var item in component)	10✔
196	{	2✔
197	_trackedItems.Remove(item);	2✔
198
199	// If the item is a CompoundType, adjust the reference count and clean up its sub-items.
200	if (item is CompoundType compound)	2✔
201	{	2✔
202	// Decrease the reference count by the number of sub-items.
203	_referencesCount -= compound.SubItemsCount;	2✔
204	foreach (var subitem in compound.SubItems)	4,098✔
205	{	2,046✔
206	// Skip sub-items that are in the same component or don't need tracking.
207	if (component.Contains(subitem)) continue;	2,046✔
208	if (!NeedTrack(subitem)) continue;	4,092!
209
210	// Remove the parent reference from the sub-item.
211	subitem.ObjectReferences!.Remove(compound);	×
212	}	×
213	}	2✔
214
215	// Perform cleanup for the item.
216	item.Cleanup();	2✔
217	}	2✔
218
219	// Move to the next component and remove the current one from the cached_components list.
220	var nodeToRemove = node;	2✔
221	node = node.Next;	2✔
222	_cachedComponents.Remove(nodeToRemove);	2✔
223	}	2✔
224	}	2✔
225	}	2✔
226
227	// Return the current total reference count.
228	return _referencesCount;	15✔
229	}	15✔
230
231	/// <inheritdoc/>
232	public void RemoveReference(StackItem item, CompoundType parent)
233	{	27✔
234	// Decrement the reference count.
235	_referencesCount--;	27✔
236
237	// If the item doesn't need to be tracked, return early.
238	if (!NeedTrack(item)) return;	53✔
239
240	// Invalidate the cached components since the tracked items are changing.
241	_cachedComponents = null;	1✔
242
243	// Decrement the reference count for the parent in the item's ObjectReferences dictionary.
244	item.ObjectReferences![parent].References--;	1✔
245
246	// If the item has no stack references, add it to the zero_referred set.
247	if (item.StackReferences == 0)	1✔
248	_zeroReferred.Add(item);	1✔
249	}	27✔
250
251	/// <inheritdoc/>
252	[MethodImpl(MethodImplOptions.AggressiveInlining)]
253	public void RemoveStackReference(StackItem item)
254	{	77,846✔
255	// Decrement the reference count.
256	_referencesCount--;	77,846✔
257
258	// If the item doesn't need to be tracked, return early.
259	if (!NeedTrack(item)) return;	146,729✔
260
261	// Decrement the item's stack references and add it to the zero_referred set if it has no references.
262	if (--item.StackReferences == 0)	8,963✔
263	_zeroReferred.Add(item);	8,848✔
264	}	77,846✔
265	}
266	}

neo-project / neo / 11407461872

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