什么是增加Map速度最快的方法？

Question

我注意到在对map[int]int变量的两个增量方法中，存在3倍速度因子：

快速方式：myMap[key]++ 慢速方式：myMap[key]=myMap[key]+1 这可能并不令人惊讶，因为至少从表面上看，在第二种情况下，我指示Go两次访问myMap。 我只是好奇：熟悉Go编译器的任何人能帮助我理解地图上这些操作之间的差异吗？ 有了如何编译器工作的知识，是否有更快的技巧来增加地图？

编辑：在本地运行时，差异较小，但仍然存在。

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)

}

输出：

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

编辑2：建议我转储了机器代码。以下是相关片段。

对于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)

对于 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)

奇怪的是，++甚至不调用map访问！ ++显然比2或3个订单简单。 我的机器解析能力到此为止，如果有人了解情况，我很想听听。

- kapaw

---

这很令人惊讶，因为如果你查看编译器的输出，这两种形式是完全相同的。 - Vorsprung

您可以使用 go tool objdump 命令来查看生成的机器码，例如 go tool objdump -S -s "main.main" ./example1。 - dm03514

这可能是go vet不断提示我使用++语句的原因。 - RickyA

@kapaw：“我注意到一个3倍的速度因素：++花费了8.1739809秒 y=y+1花费了17.9079386秒。我无法重现或理解你的结果。请查看我的答案获取真实结果：++花费了7.995184419秒 y=y+1花费了10.259916484秒。” - peterSO

@dm03514 我在 go version go1.11 windows/amd64 上运行了这个程序。现在我想起来了，我应该在 Linux 上检查一下是否相同。这可能会解释为什么我的 y=y+1 和 @perterSO 报告的结果相差6秒。 - kapaw

Answer 1

Go语言的gc编译器是一款优化编译器，它在不断地改进中。例如，在Go1.11版本中：

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

Go提交记录：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.

您的代码运行结果如下：

go1.10:

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

go1.11:

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

---

回答你的问题，通常来说，在编写代码时要简单、明确和显而易见。这样编译器就更容易识别出可优化的常见模式。

- peterSO