What is the fastest way to increment a map?

Question

I noticed a 3x speed factor for the two following increment methods for map[int]int variables:

fast: myMap[key]++

slow: myMap[key]=myMap[key]+1

This probably isn't surprising because, at least naively, in the second case I'm directing Go to access myMap twice. I'm just curious: Can anyone familiar with the Go compiler help me understand the difference between these operations on maps? And with knowledge of how the compiler works, is there a faster trick to increment maps?

edit: running locally the difference is less pronounced, but still present:

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {

    x, y := make(map[int]int), make(map[int]int)
    x[0], y[0] = 0, 0
    steps := int(math.Pow(10, 9))

    start1 := time.Now()
    for i := 0; i < steps; i++ {
        x[0]++
    }
    elapsed1 := time.Since(start1)
    fmt.Println("++ took", elapsed1)

    start2 := time.Now()
    for i := 0; i < steps; i++ {
        y[0] = y[0] + 1
    }
    elapsed2 := time.Since(start2)

    fmt.Println("y=y+1 took", elapsed2)

}

Output:

++ took 8.1739809s
y=y+1 took 17.9079386s

Edit2: As suggested I dumped the machine code. Here are the relevant snippets

For x[0]++

0x4981e3              488d05b6830100          LEAQ runtime.types+95648(SB), AX
  0x4981ea              48890424                MOVQ AX, 0(SP)
  0x4981ee              488d8c2400020000        LEAQ 0x200(SP), CX
  0x4981f6              48894c2408              MOVQ CX, 0x8(SP)
  0x4981fb              48c744241000000000      MOVQ $0x0, 0x10(SP)
  0x498204              e8976df7ff              CALL runtime.mapassign_fast64(SB)
  0x498209              488b442418              MOVQ 0x18(SP), AX
  0x49820e              48ff00                  INCQ 0(AX)

For y[0] = y[0] + 1

0x498302              488d0597820100          LEAQ runtime.types+95648(SB), AX
  0x498309              48890424                MOVQ AX, 0(SP)
  0x49830d              488d8c24d0010000        LEAQ 0x1d0(SP), CX
  0x498315              48894c2408              MOVQ CX, 0x8(SP)
  0x49831a              48c744241000000000      MOVQ $0x0, 0x10(SP)
  0x498323              e80869f7ff              CALL runtime.mapaccess1_fast64(SB)
  0x498328              488b442418              MOVQ 0x18(SP), AX
  0x49832d              488b00                  MOVQ 0(AX), AX
  0x498330              4889442448              MOVQ AX, 0x48(SP)
  0x498335              488d0d64820100          LEAQ runtime.types+95648(SB), CX
  0x49833c              48890c24                MOVQ CX, 0(SP)
  0x498340              488d9424d0010000        LEAQ 0x1d0(SP), DX
  0x498348              4889542408              MOVQ DX, 0x8(SP)
  0x49834d              48c744241000000000      MOVQ $0x0, 0x10(SP)
  0x498356              e8456cf7ff              CALL runtime.mapassign_fast64(SB)
  0x49835b              488b442418              MOVQ 0x18(SP), AX
  0x498360              488b4c2448              MOVQ 0x48(SP), CX
  0x498365              48ffc1                  INCQ CX
  0x498368              488908                  MOVQ CX, 0(AX)

Oddly enough, ++ doesn't even call map access! ++ is clearly a simpler operation by an order of 2 or 3. My ability to parse machine ends there, so if anyone has insight into what's going on, I'd love to hear it

Answer 1

The Go gc compiler is an optimizing compiler. It is continuosly being improved. For example, for Go1.11,

Go Issue: cmd/compile: We can avoid extra mapaccess in "m[k] op= r" #23661

Go commit: 7395083136539331537d46875ab9d196797a2173

cmd/compile: avoid extra mapaccess in "m[k] op= r"

Currently, order desugars map assignment operations like

    m[k] op= r

into

    m[k] = m[k] op r

which in turn is transformed during walk into:

    tmp := *mapaccess(m, k)
    tmp = tmp op r
    *mapassign(m, k) = tmp

However, this is suboptimal, as we could instead produce just:

    *mapassign(m, k) op= r

One complication though is if "r == 0", then "m[k] /= r" and "m[k] %=
r" will panic, and they need to do so *before* calling mapassign,
otherwise we may insert a new zero-value element into the map.

It would be spec compliant to just emit the "r != 0" check before
calling mapassign (see #23735), but currently these checks aren't
generated until SSA construction. For now, it's simpler to continue
desugaring /= and %= into two map indexing operations.

Fixes #23661.

Results for your code:

go1.10:

++ took 10.258130907s
y=y+1 took 10.233823639s

go1.11:

++ took 7.995184419s
y=y+1 took 10.259916484s

---

The general answer to your question is to be simple, explicit, and obvious in your code. The compiler then has an easier task to recognize a common optimizable pattern.