EgorBo
commented
1 week ago @EgorBot -intel -arm64 --runtimes net8.0 net9.0
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<bool> _binaryTrieBool = null!;
private IPBinaryTrie<IPAddress> _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<TLeaf>
{
private class Node<TNodeLeaf>
{
public Node<TNodeLeaf>? Branch0;
public Node<TNodeLeaf>? Branch1;
public bool IsLeaf;
public TNodeLeaf? NodeLeaf;
}
private readonly object _lock = new();
private Node<TLeaf> _rootIPv4;
private Node<TLeaf> _rootIPv6;
public IPBinaryTrie()
{
_rootIPv4 = new Node<TLeaf>();
_rootIPv6 = new Node<TLeaf>();
}
public TLeaf? Lookup(IPAddress address)
{
Span<byte> addressBuffer = stackalloc byte[16];
address.TryWriteBytes(addressBuffer, out int bytesWritten);
addressBuffer = addressBuffer.Slice(0, bytesWritten);
Node<TLeaf> trieRoot = address.AddressFamily == AddressFamily.InterNetwork ? _rootIPv4 : _rootIPv6;
TLeaf? result = LookupCore(addressBuffer, trieRoot);
return result;
}
private static TLeaf? LookupCore(ReadOnlySpan<byte> addressBuffer, Node<TLeaf> root)
{
Node<TLeaf> 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<TLeaf>? 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<byte> addressBuffer = stackalloc byte[16];
network.BaseAddress.TryWriteBytes(addressBuffer, out int bytesWritten);
addressBuffer = addressBuffer.Slice(0, bytesWritten);
lock (_lock)
{
Node<TLeaf> trieRoot = network.BaseAddress.AddressFamily == AddressFamily.InterNetwork ? _rootIPv4 : _rootIPv6;
AddOrUpdateCore(addressBuffer, network.PrefixLength, trieRoot, leaf);
}
}
private static void AddOrUpdateCore(ReadOnlySpan<byte> addressBuffer, int prefixLength, Node<TLeaf> root, TLeaf leaf)
{
Node<TLeaf> 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<TLeaf>? branch = ref (bit == 0 ? ref currentNode.Branch0 : ref currentNode.Branch1);
branch ??= new Node<TLeaf>();
currentNode = branch;
if (++currentBit == prefixLength)
{
currentNode.NodeLeaf = leaf;
currentNode.IsLeaf = true;
return;
}
}
}
}
}
iSazonov
JulieLeeMSFT
Description
I ran a performance comparison of my simple project and was surprised that the code runs noticeably slower on .Net 9.0 than on .Net 8.0. (35 ms vs 28 ms on my notebook) Moreover, a code (not my code) that I used as baseline (BinaryTrieBase) works almost the same, but my code is slower. The project: BinaryTrie.zip
Regression?
Yes.
Data