EgorBot for EgorBo in #108058

[EgorBot]

Processing https://github.com/dotnet/runtime/issues/108058#issuecomment-2363982521 command:

Command

-intel -arm64 --runtimes net8.0 net9.0 ```cs using System.Net; using System.Net.Sockets; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args); public class IPNetworkCollection { private readonly TrieNode _root = new(); internal void Add(IPNetwork network) { var ipAddressBytes = network.BaseAddress.GetAddressBytes(); var prefixLength = network.PrefixLength; TrieNode currentNode = _root; for (int i = 0; i < prefixLength; i++) { int bit = GetBit(ipAddressBytes, i); if (currentNode.Children[bit] == null) currentNode.Children[bit] = new TrieNode(); currentNode = currentNode.Children[bit]; } currentNode.IsTerminal = true; } private static int GetBit(byte[] bytes, int index) { int byteIndex = index / 8; int bitIndex = index % 8; return (bytes[byteIndex] >> (7 - bitIndex)) & 1; } private class TrieNode { public TrieNode[] Children { get; } = new TrieNode[2]; public bool IsTerminal { get; set; } } } [MemoryDiagnoser] public class Benchmarks { private IPAddress _a4 = null!; private IPBinaryTrie _binaryTrieBool = null!; private IPBinaryTrie _binaryTrieIPAddress = null!; private IPNetworkCollection _bbelius = null!; [GlobalSetup] public void Setup() { _a4 = IPAddress.Parse("28.0.18.3"); _binaryTrieBool = new(); _binaryTrieBool.AddOrUpdate(IPNetwork.Parse("28.0.18.0/24"), true); _binaryTrieIPAddress = new(); _binaryTrieIPAddress.AddOrUpdate(IPNetwork.Parse("28.0.18.0/24"), IPAddress.Parse("1.1.1.1")); _bbelius = new(); _bbelius.Add(IPNetwork.Parse("28.0.18.0/24")); } [Benchmark] public void BinaryTrieBool() => _binaryTrieBool.Lookup(_a4); } public sealed class IPBinaryTrie { private class Node { public Node? Branch0; public Node? Branch1; public bool IsLeaf; public TNodeLeaf? NodeLeaf; } private readonly object _lock = new(); private Node _rootIPv4; private Node _rootIPv6; public IPBinaryTrie() { _rootIPv4 = new Node(); _rootIPv6 = new Node(); } public TLeaf? Lookup(IPAddress address) { Span addressBuffer = stackalloc byte[16]; address.TryWriteBytes(addressBuffer, out int bytesWritten); addressBuffer = addressBuffer.Slice(0, bytesWritten); Node trieRoot = address.AddressFamily == AddressFamily.InterNetwork ? _rootIPv4 : _rootIPv6; TLeaf? result = LookupCore(addressBuffer, trieRoot); return result; } private static TLeaf? LookupCore(ReadOnlySpan addressBuffer, Node root) { Node currentNode = root; TLeaf? result = default; int currentBit = 0; for (int i = 0; i < addressBuffer.Length; i++) { for (int j = 7; j >= 0; j--) { currentBit++; int bit = (addressBuffer[i] >> j) & 1; Node? branch = bit == 0 ? currentNode.Branch0 : currentNode.Branch1; if (branch is null) return result; currentNode = branch; if (currentNode.IsLeaf) result = currentNode.NodeLeaf; } } return result; } public void AddOrUpdate(IPNetwork network, TLeaf leaf) { Span addressBuffer = stackalloc byte[16]; network.BaseAddress.TryWriteBytes(addressBuffer, out int bytesWritten); addressBuffer = addressBuffer.Slice(0, bytesWritten); lock (_lock) { Node trieRoot = network.BaseAddress.AddressFamily == AddressFamily.InterNetwork ? _rootIPv4 : _rootIPv6; AddOrUpdateCore(addressBuffer, network.PrefixLength, trieRoot, leaf); } } private static void AddOrUpdateCore(ReadOnlySpan addressBuffer, int prefixLength, Node root, TLeaf leaf) { Node currentNode = root; int currentBit = 0; for (int i = 0; i < addressBuffer.Length; i++) { for (int j = 7; j >= 0; j--) { int bit = (addressBuffer[i] >> j) & 1; ref Node? branch = ref (bit == 0 ? ref currentNode.Branch0 : ref currentNode.Branch1); branch ??= new Node(); currentNode = branch; if (++currentBit == prefixLength) { currentNode.NodeLeaf = leaf; currentNode.IsLeaf = true; return; } } } } } ```

(EgorBot will reply in this issue)

[EgorBot]

Benchmark results on AzureIntel

BenchmarkDotNet v0.14.0, Ubuntu 22.04.5 LTS (Jammy Jellyfish)
Intel Xeon Platinum 8370C CPU 2.80GHz, 1 CPU, 4 logical and 2 physical cores
  Job-LBMSOL : .NET 8.0.8 (8.0.824.36612), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI
  Job-RGYDOX : .NET 9.0.0 (9.0.24.43107), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

Method	Runtime	Mean	Error	Ratio	Allocated	Alloc Ratio
BinaryTrieBool	.NET 8.0	25.75 ns	0.081 ns	1.00	-	NA
BinaryTrieBool	.NET 9.0	27.56 ns	0.071 ns	1.07	-	NA

BDN_Artifacts.zip

[EgorBot]

cc @EgorBo (logs)

[EgorBot]

Benchmark results on AzureAmpere

BenchmarkDotNet v0.14.0, Ubuntu 22.04.5 LTS (Jammy Jellyfish)
AzureAmpere
  Job-NSJOVW : .NET 8.0.8 (8.0.824.36612), Arm64 RyuJIT AdvSIMD
  Job-UDXIJY : .NET 9.0.0 (9.0.24.43107), Arm64 RyuJIT AdvSIMD

Method	Runtime	Mean	Error	Ratio	Allocated	Alloc Ratio
BinaryTrieBool	.NET 8.0	39.31 ns	0.012 ns	1.00	-	NA
BinaryTrieBool	.NET 9.0	38.16 ns	0.015 ns	0.97	-	NA

BDN_Artifacts.zip

[EgorBot]

cc @EgorBo (logs)