11297318421

Committed 11 Oct 2024 06:16PM UTC coverage: 55.91% (+0.001%) from 55.909%

Build # 11297318421

Build Type

push

github

Committed by

web-flow

Commit Message

[Neo VM] optimize newstruct (#3525)

* optimize newstruct

* use Array.Fill

* Update src/Neo.VM/JumpTable/JumpTable.Compound.cs

---------

Co-authored-by: Shargon <shargon@gmail.com>

Run Details

5774 of 8906 branches covered (64.83%)

Branch coverage included in aggregate %.

9 of 9 new or added lines in 1 file covered. (100.0%)

10 existing lines in 1 file now uncovered.

21709 of 40250 relevant lines covered (53.94%)

86529.6 hits per line

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

87.8

/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/>
        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>
        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 (StackItem item in _trackedItems)
                    item.Reset();

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

                    // Check if any item in the SCC is still on the stack.
                    foreach (StackItem 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 || item.ObjectReferences?.Values.Any(p => p.References > 0 && p.Item.OnStack) == true)
                        {
                            on_stack = true;
                            break;
                        }
                    }

                    // If any item in the component is on stack, mark all items in the component as on stack.
                    if (on_stack)
                    {
                        foreach (StackItem item in component)
                            item.OnStack = true;
                        node = node.Next;
                    }
                    else
                    {
                        // Otherwise, remove the component and clean up the items.
                        foreach (StackItem 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 (StackItem 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/>
        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	public void AddStackReference(StackItem item, int count = 1)
92	{	86,736✔
93	// Increment the reference count by the specified count.
94	_referencesCount += count;	86,736✔
95
96	// If the item doesn't need to be tracked, return early.
97	if (!NeedTrack(item)) return;	164,408✔
98
99	// Add the item to the set of tracked items and to the cached components if needed.
100	if (_trackedItems.Add(item))	9,064✔
101	_cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });	8,251!
102
103	// Increment the item's stack references by the specified count.
104	item.StackReferences += count;	9,064✔
105
106	// Remove the item from the _zeroReferred set since it now has references.
107	_zeroReferred.Remove(item);	9,064✔
108	}	86,736✔
109
110	/// <inheritdoc/>
111	public void AddZeroReferred(StackItem item)
112	{	12,068✔
113	// Add the item to the _zeroReferred set.
114	_zeroReferred.Add(item);	12,068✔
115
116	// If the item doesn't need to be tracked, return early.
117	if (!NeedTrack(item)) return;	12,068✔
118
119	// Add the item to the cached components and the set of tracked items.
120	_cachedComponents?.AddLast(new HashSet<StackItem>(ReferenceEqualityComparer.Instance) { item });	12,068✔
121	_trackedItems.Add(item);	12,068✔
122	}	12,068✔
123
124	/// <summary>
125	/// Checks and processes items that have zero references.
126	///
127	/// This method is used to check items in the zero-referred list and clean up those that are no longer needed.
128	/// It uses Tarjan's algorithm to find strongly connected components and remove those with no references.
129	///
130	/// Use this method periodically to clean up items with zero references and free up memory.
131	/// </summary>
132	/// <returns>The current reference count.</returns>
133	public int CheckZeroReferred()
134	{	15✔
135	// If there are items with zero references, process them.
136	if (_zeroReferred.Count > 0)	15✔
137	{	2✔
138	// Clear the zero_referred set since we are going to process all of them.
139	_zeroReferred.Clear();	2✔
140
141	// If cached components are null, we need to recompute the strongly connected components (SCCs).
142	if (_cachedComponents is null)	2✔
143	{	1✔
144	// Create a new Tarjan object and invoke it to find all SCCs in the tracked_items graph.
145	Tarjan tarjan = new(_trackedItems);	1✔
146	_cachedComponents = tarjan.Invoke();	1✔
147	}	1✔
148
149	// Reset all tracked items' Tarjan algorithm-related fields (DFN, LowLink, and OnStack).
150	foreach (StackItem item in _trackedItems)	10✔
151	item.Reset();	2✔
152
153	// Process each SCC in the cached_components list.
154	for (var node = _cachedComponents.First; node != null;)	6✔
155	{	2✔
156	var component = node.Value;	2✔
157	bool on_stack = false;	2✔
158
159	// Check if any item in the SCC is still on the stack.
160	foreach (StackItem item in component)	10✔
161	{	2✔
162	// An item is considered 'on stack' if it has stack references or if its parent items are still on stack.
163	if (item.StackReferences > 0 \|\| item.ObjectReferences?.Values.Any(p => p.References > 0 && p.Item.OnStack) == true)	2!
UNCOV 164	{	×
UNCOV 165	on_stack = true;	×
UNCOV 166	break;	×
167	}
168	}	2✔
169
170	// If any item in the component is on stack, mark all items in the component as on stack.
171	if (on_stack)	2!
UNCOV 172	{	×
UNCOV 173	foreach (StackItem item in component)	×
UNCOV 174	item.OnStack = true;	×
UNCOV 175	node = node.Next;	×
UNCOV 176	}	×
177	else
178	{	2✔
179	// Otherwise, remove the component and clean up the items.
180	foreach (StackItem item in component)	10✔
181	{	2✔
182	_trackedItems.Remove(item);	2✔
183
184	// If the item is a CompoundType, adjust the reference count and clean up its sub-items.
185	if (item is CompoundType compound)	2✔
186	{	2✔
187	// Decrease the reference count by the number of sub-items.
188	_referencesCount -= compound.SubItemsCount;	2✔
189	foreach (StackItem subitem in compound.SubItems)	4,098✔
190	{	2,046✔
191	// Skip sub-items that are in the same component or don't need tracking.
192	if (component.Contains(subitem)) continue;	2,046✔
193	if (!NeedTrack(subitem)) continue;	4,092!
194
195	// Remove the parent reference from the sub-item.
UNCOV 196	subitem.ObjectReferences!.Remove(compound);	×
UNCOV 197	}	×
198	}	2✔
199
200	// Perform cleanup for the item.
201	item.Cleanup();	2✔
202	}	2✔
203
204	// Move to the next component and remove the current one from the cached_components list.
205	var nodeToRemove = node;	2✔
206	node = node.Next;	2✔
207	_cachedComponents.Remove(nodeToRemove);	2✔
208	}	2✔
209	}	2✔
210	}	2✔
211
212	// Return the current total reference count.
213	return _referencesCount;	15✔
214	}	15✔
215
216	/// <inheritdoc/>
217	public void RemoveReference(StackItem item, CompoundType parent)
218	{	27✔
219	// Decrement the reference count.
220	_referencesCount--;	27✔
221
222	// If the item doesn't need to be tracked, return early.
223	if (!NeedTrack(item)) return;	53✔
224
225	// Invalidate the cached components since the tracked items are changing.
226	_cachedComponents = null;	1✔
227
228	// Decrement the reference count for the parent in the item's ObjectReferences dictionary.
229	item.ObjectReferences![parent].References--;	1✔
230
231	// If the item has no stack references, add it to the zero_referred set.
232	if (item.StackReferences == 0)	1✔
233	_zeroReferred.Add(item);	1✔
234	}	27✔
235
236	/// <inheritdoc/>
237	public void RemoveStackReference(StackItem item)
238	{	77,846✔
239	// Decrement the reference count.
240	_referencesCount--;	77,846✔
241
242	// If the item doesn't need to be tracked, return early.
243	if (!NeedTrack(item)) return;	146,729✔
244
245	// Decrement the item's stack references and add it to the zero_referred set if it has no references.
246	if (--item.StackReferences == 0)	8,963✔
247	_zeroReferred.Add(item);	8,848✔
248	}	77,846✔
249	}
250	}

neo-project / neo / 11297318421

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