Quel est le moyen le plus rapide d'incrémenter une carte ?

Question

J'ai remarqué un facteur de vitesse de 3x pour les deux méthodes d'incrémentation suivantes pour map[int]int variables :

rapide : myMap[key]++

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

Cela n'est probablement pas surprenant car, du moins naïvement, dans le second cas, j'ordonne à Go d'accéder deux fois à myMap. Je suis simplement curieux : quelqu'un qui connaît le compilateur Go peut-il m'aider à comprendre la différence entre ces opérations sur les cartes ? Et en connaissant le fonctionnement du compilateur, existe-t-il une astuce plus rapide pour incrémenter les maps ?

edit : en local, la différence est moins prononcée, mais toujours présente :

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)

}

Sortie :

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

Edit2 : Comme suggéré, j'ai extrait le code machine. Voici les extraits pertinents

Pour 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)

Pour 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)

Curieusement, ++ n'appelle même pas l'accès à la carte ! ++ est clairement une opération plus simple d'un ordre de 2 ou 3. Ma capacité à analyser la machine s'arrête là, donc si quelqu'un a une idée de ce qui se passe, je serais ravi de l'entendre

Answer 1

Le compilateur Go gc est un compilateur optimisant. Il est continuellement amélioré. Par exemple, pour Go1.11,

Aller à la question : cmd/compile : Nous pouvons éviter l'accès supplémentaire à la carte dans "m[k] op= r" #23661

S'engager à aller de l'avant : 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.

Résultats pour votre code :

go1.10 :

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

go1.11 :

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

---

La réponse générale à votre question est d'être simple, explicite et évident dans votre code. Le compilateur aura alors plus de facilité à reconnaître un modèle commun optimisable.