Are Maps Really Efficient in Go?

Vishakha Sainani

4 min read

·

4 days ago

--

Listen

Share

So recently I was solving a leetcode problem, the problem was to find the minimum xor path value in a grid.
Problem link if you’re interested to solve it before reading further: Leetcode 3882

And I solved it using memoization, so understand the problem first, to solve it I assumed that every row, col and the xor value till that point in the grid is a seperate state that could be maintained.

So I went with creating a map to store the value of that state and if I come across the same state again I would just use the map value and not calculate it again, simple right?

Here’s my solution of it:

func minCost(grid [][]int) int {
 memo := make(map[[3]int]int)
 return findXORDFS(grid, 0, 0, 0, memo)
}

func findXORDFS(grid [][]int, row, col, xor int, memo map[[3]int]int) int {
 m, n := len(grid), len(grid[0])

 if row >= m || col >= n {
  return math.MaxInt
 }

 xor ^= grid[row][col]

 if row == m-1 && col == n-1 {
  return xor
 }

 state := [3]int{row, col, xor}
 if result, ok := memo[state]; ok {
  return result
 }

 right := findXORDFS(grid, row, col+1, xor, memo)
 down := findXORDFS(grid, row+1, col, xor, memo)

 result := min(right, down)
 memo[state] = result

 return result
}

Looks correct, and is correct. But the issue was it hit TLE.

Then I used 3d slice instead of a map

3d slice solution:

func minCost(grid [][]int) int {
    ans := math.MaxInt

    isVisited := make([][][]bool, len(grid))
 for i := range isVisited {
  isVisited[i] = make([][]bool, len(grid[0]))
  for j := range isVisited[i] {
   isVisited[i][j] = make([]bool, 1024)
  }
 }

    findXORdfs(grid, isVisited, 0, 0, 0, &ans)

    return ans
}

func findXORdfs(grid [][]int, isVisited [][][]bool, row, col, xor int, ans *int) {
    if row >= len(grid) || col >= len(grid[0]) {
        return 
    }

    if isVisited[row][col][xor] {
        return
    }
    isVisited[row][col][xor] = true
    
 xor = xor ^ grid[row][col]

 if row == len(grid)-1 && col == len(grid[0])-1 {
  *ans = min(xor, *ans)
        return
 }


 //right
 findXORdfs(grid, isVisited, row+1, col, xor, ans)

 //down
 findXORdfs(grid, isVisited, row, col+1, xor, ans)
}

This one is correct too and passes all test cases.

But why did this happen, both the solutions are following the exact same approach.

And shouldn’t maps be faster and efficient than slices? Because of the O(1) lookup.

That’s the caveat here.

In Go, maps are not always efficient, there are many concepts that apply here so let’s look at them one by one.

Lookup in Slice:

When accessing an element in a slice, Go uses the index to locate the corresponding memory address.

Conceptually, for a one-dimensional slice:

Address = BaseAddress + (Index x ElementSize).

For a multidimensional slice, Go performs multiple indexing operations.

Lookup in a Map:

At a high level, a Go map is a hash table.

Unlike a slice, where the index directly determines the memory location, a map needs to determine where a key belongs.

Go replaced its older map implementation with an implementation based on Swiss Tables. Swiss Table is a hash-table.

The key idea is to organize entries into groups and use compact metadata to find potential matches efficiently.

Instead of checking every key individually, Go can use metadata to eliminate multiple candidates at once.

A Go map uses hashing to locate a key.

Conceptually:

1. Go receives the key.
2. Calculates its hash.
3. Uses the hash to identify the relevant bucket.
4. Searches the bucket for the matching key.
5. Returns the associated value.

Map lookup has expected (O(1)) complexity, but involves more work than direct indexing.

Insertion in 3d slice:

A slice insertion here is simply an assignment to an existing memory location.

There is no need to calculate a hash or find an appropriate bucket.

Insertion in map:

When inserting a new key, Go needs to:

1. Calculate the key’s hash.
2. Identify the appropriate bucket.
3. Check whether the key already exists.
4. Insert the key-value pair.
5. Potentially perform additional work related to bucket growth.

Map insertion is also expected (O(1)), but has additional overhead.

Also updating an existing map entry is generally cheaper than inserting a new one.

Memory Allocation:

In slice, we allocate memory beforehand for all possible states.

Advantages:

• Predictable memory requirements.
• No need to dynamically insert individual states.
• Each innermost boolean slice has a fixed size.

However, a multidimensional Go slice is not one contiguous block of memory. Each slice is a descriptor pointing to its own underlying array.

While maps allocate and manage their internal hash table.

As new entries are added:

• Buckets are populated.
• Additional capacity may be allocated.
• The map may grow and reorganize its storage.

This introduces memory-management overhead.

Also, maps do not necessarily allocate memory for every possible key upfront, which can actually make them more memory-efficient when the state space is sparse.

Cache Locality:

This is one of the more interesting performance differences.

Slices have better potential cache locality. Slices store their elements in contiguous underlying arrays.

For example:

values := []int{10, 20, 30, 40, 50}

These elements are stored next to each other in memory.

When the CPU accesses one element, nearby elements may also be brought into the CPU cache. This is called spatial locality.

In our DFS problem, repeatedly accessing nearby grid positions and their state arrays can benefit from this.

While maps are less predictable memory access. Maps use hash buckets to organize entries. Accessing a key requires locating the appropriate bucket using its hash. The resulting memory accesses are less predictable than sequential or direct array indexing. This can reduce cache efficiency, particularly for workloads involving frequent lookups.

However, Go’s map implementation is optimized, and cache performance depends on the workload and key distribution. A map is not automatically cache-inefficient.

So now we know a map can be theoretically optimal but still not be the most efficient choice for a particular problem.