Last active
January 13, 2026 03:12
-
-
Save MisterKidX/31e2f8693d48dc2efd3ae79a00152707 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using BenchmarkDotNet.Attributes; | |
| using BenchmarkDotNet.Running; | |
| class OOPNode | |
| { | |
| public List<OOPNode> Neighbors = new List<OOPNode>(); | |
| public int value = 0; | |
| } | |
| struct DODGraph | |
| { | |
| public int[] Nodes; | |
| // input: index range of node i [i, i + 1), output: the range on EdgeTargets | |
| public int[] EdgeSlice; | |
| // input: edge slice range of node i, output: node index of connected node | |
| public int[] Edges; | |
| } | |
| [MemoryDiagnoser] | |
| public class GraphTraversalBenchmark | |
| { | |
| private OOPNode[] totalOOPNodes; | |
| private DODGraph dodGraph; | |
| private const int NodeCount = 10000; | |
| private const int MaxEdgesPerNode = 5; | |
| private Random rng = new Random(42); | |
| [GlobalSetup] | |
| public void Setup() | |
| { | |
| // ---- OOP graph | |
| // create nodes | |
| totalOOPNodes = new OOPNode[NodeCount]; | |
| for (int i = 0; i < NodeCount; i++) | |
| totalOOPNodes[i] = new OOPNode(); | |
| // map nodes in cyclic non-directional graph | |
| for (int i = 0; i < NodeCount; i++) | |
| { | |
| int edgeCount = rng.Next(0, MaxEdgesPerNode + 1); | |
| for (int e = 0; e < edgeCount; e++) | |
| { | |
| int target = rng.Next(0, NodeCount); | |
| totalOOPNodes[i].Neighbors.Add(totalOOPNodes[target]); | |
| } | |
| } | |
| // ---- DOD graph | |
| // create it based on the oop graph | |
| dodGraph.Nodes = new int[NodeCount]; | |
| List<int> edges = new List<int>(); | |
| dodGraph.EdgeSlice = new int[NodeCount + 1]; | |
| int edgeIndex = 0; | |
| for (int i = 0; i < NodeCount; i++) | |
| { | |
| dodGraph.EdgeSlice[i] = edgeIndex; | |
| int edgeCount = totalOOPNodes[i].Neighbors.Count; | |
| for (int e = 0; e < edgeCount; e++) | |
| { | |
| // get the neighbor of the current oop node and get its index | |
| edges.Add(Array.IndexOf(totalOOPNodes, totalOOPNodes[i].Neighbors[e])); | |
| // this is how the slicing is created | |
| edgeIndex++; | |
| } | |
| } | |
| dodGraph.EdgeSlice[NodeCount] = edgeIndex; | |
| dodGraph.Edges = edges.ToArray(); | |
| } | |
| [Benchmark] | |
| public void TraverseOOP() | |
| { | |
| for (int i = 0; i < totalOOPNodes.Length; i++) | |
| { | |
| for (int j = 0; j < totalOOPNodes[i].Neighbors.Count; j++) | |
| { | |
| totalOOPNodes[i].Neighbors[j].value ^= i + j; | |
| } | |
| } | |
| } | |
| [Benchmark] | |
| public void TraverseDOD() | |
| { | |
| for (int i = 0; i < dodGraph.EdgeSlice.Length - 1; i++) | |
| { | |
| int start = dodGraph.EdgeSlice[i]; | |
| int end = dodGraph.EdgeSlice[i + 1]; | |
| for (int e = start; e < end; e++) | |
| { | |
| dodGraph.Nodes[i] ^= i + e; | |
| } | |
| } | |
| } | |
| } | |
| public class Program | |
| { | |
| public static void Main() | |
| { | |
| var summary = BenchmarkRunner.Run<GraphTraversalBenchmark>(); | |
| } | |
| } | |
| //| Method | Mean | Error | StdDev | Allocated | | |
| //| ------------ | ---------:| ---------:| ---------:| ----------:| | |
| //| TraverseOOP | 70.37 us | 1.399 us | 1.497 us | - | | |
| //| TraverseDOD | 44.24 us | 0.826 us | 0.812 us | - | | |
| // 40% increase in performance | |
| // that's when the graph is even traversed linearly in OOP! (not node by neighbors) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment