Golang vs. C#: performance characteristics (simple case study)

This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though). 

The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph.

The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below:

Some potential reasons for the performance gains from Go in this particular example are:

1. Language and Runtime Differences:

•    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).
•    Go has a simpler runtime with less overhead compared to the .NET runtime.
•    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios.

2. Data Structures:

•    Go's `map` is generally more efficient than C#'s `Hashtable`.
•    `Hashtable` in C# is a non-generic collection, which involves boxing/unboxing for value types, leading to performance overhead.
•    Go's `map` is implemented as a hash table with constant-time average complexity for basic operations.

3. Memory Allocation:

•    Go's memory allocator is highly optimized and can be more efficient for small allocations.
•    The Go version creates fewer objects, potentially reducing garbage collection pressure.

4. Type System:

•    Go's static typing and lack of inheritance can lead to more straightforward and potentially faster method dispatch.
•    C#'s dynamic features in `Hashtable` (like casting) can introduce performance overhead.

5. Compiler Optimizations:

•    Go's compiler might be applying more aggressive optimizations for this particular code structure.

6. Memory Layout:

•    Go's structs and slices often have better memory layout and cache coherence compared to C# objects.

7. No Boxing/Unboxing:

•    In the C# version, using `Hashtable` involves boxing value types (like `int`), which isn't necessary in the Go version.

8. Direct Access:

•    The Go version uses direct map access, while the C# version uses method calls (`ContainsKey`, `Add`) which might have slightly more overhead.

Granted, this doesn't mean necessarily that one language is overall more performant than the other. It just means that in general the use of Hashtable in C#, although very easy to be used, might lead to performance degradations in some particular cases. Cheers, ACC

Problem

Count the Number of Good Nodes - LeetCode

3249. Count the Number of Good Nodes

Medium

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

A node is good if all the subtrees rooted at its children have the same size.

Return the number of good nodes in the given tree.

A subtree of treeName is a tree consisting of a node in treeName and all of its descendants.

 

Example 1:

Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

Output: 7

Explanation:

All of the nodes of the given tree are good.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]

Output: 6

Explanation:

There are 6 good nodes in the given tree. They are colored in the image above.

Example 3:

Input: edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]

Output: 12

Explanation:

All nodes except node 9 are good.

 

Constraints:

• 2 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• The input is generated such that edges represents a valid tree.

C#

public class Solution {
    private Hashtable CreateGraphFromEdges(int[][] edges)
    {
        Hashtable graph = new Hashtable();
        for (int i = 0; i < edges.Length; i++)
        {
            for (int j = 0; j < edges[i].Length; j++)
            {
                int from = edges[i][j];
                int to = edges[i][(j + 1) % edges[i].Length];

                if (!graph.ContainsKey(from)) graph.Add(from, new Hashtable());
                Hashtable connections = (Hashtable)graph[from];
                if (!connections.ContainsKey(to)) connections.Add(to, true);
            }
        }
        return graph;
    }

    public int CountGoodNodes(int[][] edges)
    {
        Hashtable graph = CreateGraphFromEdges(edges);
        int countGoodNodes = 0;
        CountGoodNodes(graph, 0, new Hashtable(), ref countGoodNodes);
        return countGoodNodes;
    }

    public int CountGoodNodes(Hashtable graph, 
                              int currentNode, 
                              Hashtable visitedNodes,
                              ref int countGoodNodes)
    {
        if (visitedNodes.ContainsKey(currentNode)) return 0;
        visitedNodes.Add(currentNode, true);

        if (!graph.ContainsKey(currentNode)) //Leaf
        {
            countGoodNodes++;
            return 1;
        }

        Hashtable children = (Hashtable)graph[currentNode];
        bool first = true;
        int numberNodesPerChild = 0;
        int numberNodes = 1;
        bool isNodeGood = true;

        foreach (int child in children.Keys)
        {
            if (visitedNodes.ContainsKey(child)) continue;

            int n = CountGoodNodes(graph, child, visitedNodes, ref countGoodNodes);
            if (first)
            {
                numberNodesPerChild = n;
                first = false;
            }
            else if (n != numberNodesPerChild)
            {
                isNodeGood = false;
            }
            numberNodes += n;
        }

        if (isNodeGood) countGoodNodes++;
        return numberNodes;
    }
}

Golang

package main

func CreateGraphFromEdges(edges [][]int) map[int]map[int]bool {
	graph := make(map[int]map[int]bool)
	for _, edge := range edges {
		for j := range edge {
			from := edge[j]
			to := edge[(j+1)%len(edge)]
			if _, exists := graph[from]; !exists {
				graph[from] = make(map[int]bool)
			}
			graph[from][to] = true
		}
	}
	return graph
}

func countGoodNodes(edges [][]int) int {
	graph := CreateGraphFromEdges(edges)
	countGoodNodes := 0
	countGoodNodesRecursive(graph, 0, make(map[int]bool), &countGoodNodes)
	return countGoodNodes
}

func countGoodNodesRecursive(graph map[int]map[int]bool, currentNode int, visitedNodes map[int]bool, countGoodNodes *int) int {
	if visitedNodes[currentNode] {
		return 0
	}
	visitedNodes[currentNode] = true
	if _, exists := graph[currentNode]; !exists { // Leaf
		*countGoodNodes++
		return 1
	}
	children := graph[currentNode]
	first := true
	numberNodesPerChild := 0
	numberNodes := 1
	isNodeGood := true
	for child := range children {
		if visitedNodes[child] {
			continue
		}
		n := countGoodNodesRecursive(graph, child, visitedNodes, countGoodNodes)
		if first {
			numberNodesPerChild = n
			first = false
		} else if n != numberNodesPerChild {
			isNodeGood = false
		}
		numberNodes += n
	}
	if isNodeGood {
		*countGoodNodes++
	}
	return numberNodes
}