Le code ci-dessous est-il équivalent en termes de performances?
La réponse est non .
Pour plus de détails et d'explications, je demande sous cat.
Bonjour, avant d'ouvrir le sujet, je voudrais me présenter.
Je m'appelle Iskander et de temps en temps j'envoie des commits au dépôt golang / go .
J'avais l'habitude de le faire au nom de l'équipe Intel Go , mais nos chemins divergeaient et maintenant je suis un contributeur indépendant. Récemment, j'ai travaillé en vk dans l'équipe infrastructure.
Pendant mon temps libre, je crée différents outils pour Go, tels que Go-Critic et Go-consistent . Je dessine également des gaufres .
Mesurez-le!
Procédez immédiatement à la comparaison et définissez la référence:
package benchmark import ( "strings" "testing" ) var s = "#string" func BenchmarkHasPrefixCall(b *testing.B) { for i := 0; i < bN; i++ { _ = strings.HasPrefix(s, "#") _ = strings.HasPrefix(s, "x") } } func BenchmarkHasPrefixInlined(b *testing.B) { for i := 0; i < bN; i++ { _ = len(s) >= len("#") && s[:len("#")] == "#" _ = len(s) >= len("x") && s[:len("x")] == "x" } }
Au lieu de vous recommander benchstat , je vais vous montrer benchrun .
Avec une seule commande, nous pouvons exécuter les deux benchmarks et obtenir une comparaison:
go-benchrun HasPrefixCall HasPrefixInlined -v -count=10 . Benchstat results: name old time/op new time/op delta HasPrefixCall-8 9.15ns ± 1% 0.36ns ± 3% -96.09% (p=0.000 n=10+9)
L'option avec incorporation manuelle est beaucoup plus rapide que le code obtenu en incorporant le corps de la fonction avec le compilateur. Essayons de comprendre pourquoi cela se produit.
strings.HasPrefix
Rappelez l'implémentation des strings.HasPrefix .
La fonction HasPrefix intégrée par le compilateur.
Vous pouvez le vérifier comme suit:
go build -gcflags='-m=2' strings 2>&1 | grep 'can inline HasPrefix'
Pour appeler strings.HasPrefix partir de l'option (A) nous obtenons le code machine suivant:
MOVQ (TLS), CX CMPQ SP, 16(CX) JLS more_stack fn_body: SUBQ $40, SP MOVQ BP, 32(SP) LEAQ 32(SP), BP XCHGL AX, AX MOVQ s+56(SP), AX CMPQ AX, $1 JGE compare_strings XORL AX, AX MOVB AL, ~ret1+64(SP) MOVQ 32(SP), BP ADDQ $40, SP return: RET compare_strings: MOVQ s+48(SP), AX MOVQ AX, (SP) LEAQ go.string."#"(SB), AX MOVQ AX, 8(SP) MOVQ $1, 16(SP) CALL runtime.memequal(SB) MOVBLZX 24(SP), AX JMP return more_stack: CALL runtime.morestack_noctxt(SB) JMP fn_body
Ignorez le fait que le code ressemble à des nouilles.
À quoi devez-vous faire attention:
strings.HasPrefix vraiment été inséré, aucun appel.- Pour comparer des chaînes,
runtime.memequal est runtime.memequal .
Mais qu'est-ce qui est alors généré pour la version intégrée manuellement, le code de l'exemple (B) ?
MOVQ s+16(SP), AX CMPQ AX, $1 JLT different_length MOVQ s+8(SP), AX CMPB (AX), $35 // 35 - "#" SETEQ AL return: MOVB AL, "".~ret1+24(SP) RET different_length: XORL AX, AX JMP 22
Et ici, le compilateur ne génère pas d'appel à runtime.memequal et un seul caractère est comparé directement. Idéalement, il aurait dû faire de même pour la première option.
Nous observons le côté faible de l'optimiseur Go, et nous l'analysons.
Optimisation de l'expression constante
La raison pour laquelle l'appel de strings.HasPrefix(s, "#") peut être optimisé est que l'argument préfixe est une constante. Nous connaissons sa longueur et son contenu. Cela n'a aucun sens d'appeler runtime.memequal pour les chaînes courtes, il est plus rapide de faire une comparaison des caractères "en place", en évitant un appel supplémentaire.
Comme vous le savez, les compilateurs ont généralement au moins deux parties: le frontend du compilateur et le backend du compilateur . Le premier fonctionne avec une vue de niveau supérieur, le second est plus proche de la machine et la vue intermédiaire ressemblera à un flux d'instructions. Plusieurs versions de Go ont déjà utilisé la représentation SSA pour les optimisations dans la partie backend du compilateur.
Le pliage constant, tel que {10*2 => 20} , est implémenté dans le backend. En général, la plupart des opérations associées à la réduction du coût de calcul des expressions se trouvent dans cette partie du compilateur. Mais il y a des exceptions.
Une exception est l'optimisation des comparaisons de chaînes constantes. Lorsque le compilateur voit une comparaison de chaîne (ou de sous-chaîne) dans laquelle l'un ou les deux opérandes sont des constantes, un code plus efficace est généré qu'un appel à runtime.memequal .
Vous pouvez voir le code source responsable de cela dans le fichier cmd / compile / internal / gc / walk.go: 3362 .
L'incorporation de fonctions se produit avant le lancement de ces optimisations, mais également dans la partie frontend du compilateur.
Il semblerait tout de même que cette optimisation ne fonctionne pas dans notre cas?
Comment Go intègre les appels de fonction
Voici comment l'incorporation se produira:
Lors de l'incorporation de fonctions, le compilateur attribue des arguments aux variables temporaires, ce qui rompt les optimisations, car l'algorithme dans walk.go ne voit pas les constantes, mais les arguments avec des variables. Voilà le problème.
Soit dit en passant, cela n'interfère pas avec les optimisations de backend que le SSA a à sa disposition. Mais il y a d'autres problèmes, par exemple, l'impossibilité de restaurer des constructions de langage de haut niveau pour leur comparaison efficace (le travail pour éliminer cet inconvénient est «prévu» depuis plusieurs années).
Un autre exemple: l'analyse d'échappement
Imaginez une fonction qui est importante pour allouer un tampon temporaire sur la pile:
func businessLogic() error { buf := make([]byte, 0, 16)
Puisque buf ne "s'exécute" pas, le compilateur peut allouer ces 16 octets sur la pile, sans allouer sur le tas. Encore une fois, tout cela grâce à la valeur constante lors de l'appel de make . Pour allouer de la mémoire sur la pile, il est important pour nous de connaître la taille requise, qui fera partie de la trame allouée à l'appel de fonction.
Supposons à l'avenir que nous voulions allouer des tampons temporaires de différentes tailles et encapsuler une logique dans les méthodes. Nous avons introduit une nouvelle abstraction et décidé d'utiliser le nouveau type tmpBuf . La fonction de conception est extrêmement simple:
func newTmpBuf(sizeHint int) tmpBuf { return tmpBuf{buf: make([]byte, 0, sizeHint)} }
Adaptation de l'exemple d'origine:
func businessLogic() error { - buf := make([]byte, 0, 16) + buf := newTmpBuf(16) // buf // . return nil }
Le constructeur sera incorporé, mais l'allocation sera désormais toujours sur le tas, pour la même raison que les arguments sont passés via des variables temporaires. L'analyse d'échappement verra make([]byte, 0, _sizeHint) qui ne correspond pas à ses modèles de reconnaissance pour make appels make optimisés.
Si nous avions «tout est comme des êtres humains», le problème n'existerait pas, après avoir newTmpBuf constructeur newTmpBuf il serait clair que la taille est toujours connue au stade de la compilation.
Cela dérange presque plus que la situation en comparant les chaînes.
Horizons Go 1.13
La situation peut être assez facilement corrigée et j'ai déjà envoyé la première partie de la décision .
Si vous pensez que le problème décrit dans l'article a vraiment besoin d'une solution, veuillez mettre un coup de pouce dans le problème correspondant .
Ma position est que l'incorporation de code avec vos mains simplement parce qu'il fonctionne plus rapidement dans la version actuelle de Go est erronée. Il est nécessaire de corriger ce défaut dans l'optimiseur, au moins au point où les exemples décrits ci-dessus fonctionnent sans régressions de performances inattendues.
Si tout se déroule comme prévu, cette optimisation sera incluse dans la version Go 1.13.
Merci de votre attention.
Addition: solution proposée
Cette section s'adresse aux plus courageux, à ceux qui ne se lassent pas de lire.
Nous avons donc plusieurs endroits qui fonctionnent moins bien lors de l'utilisation directe de variables au lieu de leurs valeurs. La solution proposée est d'introduire une nouvelle fonction dans le frontend de la partie compilateur, qui vous permet d'obtenir la dernière valeur liée par nom. Après cela, dans chaque optimisation qui attend une valeur constante, n'abandonnez pas lorsqu'une variable est détectée, mais recevez cet état précédemment enregistré.
La signature de notre nouvelle fonctionnalité pourrait ressembler à ceci:
func getConstValue(n *Node) *Node
La définition de Node se trouve dans le fichier syntax.go .
Chaque définition de variable a une balise Node avec une balise ONAME . Dans Node.Name.Defn plupart de ces variables ont une valeur d'initialisation.
Si Node déjà un littéral, vous n'avez rien à faire et nous renvoyons simplement n . S'il s'agit de ONAME (variable), vous pouvez essayer d'extraire la même valeur d'initialisation de n.Name.Defn .
Mais qu'en est-il des modifications entre déclarer et lire une variable pour laquelle nous appelons getConstValue ? Si nous nous limitons aux variables en lecture seule, alors il n'y a pas de problème. Le frontend de Go a déjà des drapeaux de nœuds spéciaux qui marquent des noms similaires. Si la variable a été modifiée, getConstValue ne renverra pas de valeur d'initialisation.
Les programmeurs, en règle générale, ne modifient pas les arguments d'entrée des types numériques et chaînes, ce qui permet de couvrir un nombre assez important de cas avec cet algorithme primitif.
Nous sommes maintenant prêts à envisager la mise en œuvre:
func getConstValue(n *Node) *Node {
Voici comment le code change, qui dépend des constantes:
- i := indexconst(r) + i := indexconst(getConstValue(r))
Super, et ça marche même:
n := 10 xs := make([]int, n)
Avant ce changement, l'analyse d'échappement ne pouvait pas obtenir la valeur 10 à n , c'est pourquoi j'ai fait une hypothèse sur la nécessité de placer xs sur le tas.
Le code ci-dessus est syntaxiquement similaire à la situation observée lors de l'incorporation. n peut être une variable temporaire qui est ajoutée lorsque l'argument est passé.
Malheureusement, il y a des nuances.
Nous avons résolu le problème des variables locales introduites via OAS , mais Go initialise les variables des fonctions intégrées via OAS2 . Pour cette raison, nous avons besoin d'un deuxième changement qui étend la fonction getConstValue et modifie légèrement le code de l'inliner lui-même, car, entre autres, OAS2 n'a pas de champ Defn approprié.
C'était une mauvaise nouvelle. Bonne nouvelle: la chaîne #gocontributing est apparue dans la langue russe , où vous pouvez partager vos idées et vos plans, poser des questions et discuter de tout ce qui concerne la participation au développement de Go.