Vous pouvez souvent entendre en ligne que l'indexation dans une tranche, comme my_slice[i]c'est lent dans Rust, et vous devriez faire autre chose à la place pour les performances.

Les détails, cependant, sont flous. Il y a peu de points de repère et pratiquement aucune documentation sur la suppression de cette surcharge sans recourir au unsafecode.

Donc, après avoir optimisé un tas de caisses de haut niveau en supprimant les vérifications de limites (et en supprimant également le unsafecode de certaines d'entre elles), j'ai pensé que je devrais écrire les résultats et les techniques que j'ai découvertes.

Dans cet article, je vais couvrir:

1. Quel est le coût d'exécution typique des contrôles de limites sur l'indexation
2. Comment éviter les contrôles de limites sans unsafecode
3. Comment vérifier que les vérifications des limites ont été éliminées
4. Comment comparer et profiler le code Rust
5. Lorsqu'une vérification des limites est absolument nécessaire, comment construire la vérification des limites la moins chère possible

Considérez le code suivant :

L'accès au 7e élément du tableau est incorrect, car le tableau ne comporte que 4 éléments, il n'y a donc pas de 7e élément.

En C, cela conduirait à accéder à une mémoire aléatoire en dehors de la plage prévue, ce qui s'appelle un débordement de tampon .

Le fameux Heartbleed est un débordement de tampon, mais la plupart des vulnérabilités de ce type ne reçoivent pas de noms flashy car il y en a tellement . Pourtant, écrire en dehors de la plage prévue est un moyen très courant pour un attaquant d'exécuter son code sur votre machine et de faire littéralement tout ce qu'il veut - voler des informations de carte de crédit, extraire de la crypto-monnaie, vous espionner, etc. C'est pourquoi les dépassements de mémoire tampon sont considérés comme le vulnérabilité logicielle la plus dangereuse .

Pour éviter cela, Rust insère ce que l'on appelle des contrôles de limites sur chaque accès qui garantissent qu'un débordement de tampon ne se produit jamais - quelque chose comme ceci :

Si vous essayez d'accéder à un index invalide, un programme Rust paniquera au lieu de créer une vulnérabilité de sécurité.

Bien que cela soit excellent pour la sécurité, cela a un faible coût en termes de performances d'exécution, car il y a maintenant plus de code à exécuter par le processeur.

Les vérifications des limites vous ralentissent-elles réellement ?

L'impact réel des vérifications des limites sur les performances est étonnamment faible.

Le plus grand impact que j'ai jamais vu sur le code du monde réel en supprimant uniquement les vérifications de limites était de 15 %, mais les gains typiques se situent entre 1 % et 3 %, et même cela ne se produit que dans le code qui fait beaucoup de calculs.

Vous pouvez parfois constater un impact plus important (comme nous le verrons bientôt !) si la suppression des contrôles de limites permet au compilateur d'effectuer d'autres optimisations.

Pourtant, les performances du code qui n'effectue pas de grandes quantités de calculs de nombres ne seront probablement pas du tout affectées par les vérifications des limites .

Essayez-le vous-même !

Pendant que je publierai les résultats que j'ai obtenus, il n'y a rien de tel que d'essayer des choses par vous-même. J'ai donc préparé un référentiel avec tout le code et je fournirai toutes les commandes nécessaires pour que vous puissiez suivre.

Si vous avez déjà installé Rust , lancez ceci pour obtenir le code et tous les outils :

cargo install cargo-show-asm hyperfine
git clone https://github.com/Shnatsel/bounds-check-cookbook
cd bounds-check-cookbook
cargo build --release

Pour avoir un exemple simple à expérimenter, écrivons une fonction qui calcule les nombres de Fibonacci et les écrit dans un Vec :

Le compilateur est vraiment bon pour supprimer tout code qui n'est pas appelé et pour précalculer tout ce qu'il peut à l'avance. J'ai dû ajouter un mainavec beaucoup d'astuces pour m'assurer que cela ne se produise pas, et pour que nous puissions voir les vérifications des limites au moment de l'exécution.

Regardons l'assembly et voyons à quoi ressemblent les vérifications des limites :

cargo asm --rust --bin fibvec_naive_indexing fibonacci_vec

Vous pouvez le faire même si vous ne connaissez rien à l'assemblage ! Il suffit de regarder la quantité d'assemblage produite et de rechercher les noms de fonction.

Regardons d'abord la boucle interne chaude, la fib[i] = fib[i-1] + fib[i-2];partie simplement en la recherchant dans la sortie de cargo asm:

C'est ça? Ce ne sont que deux instructions !

Et en effet, si nous faisons défiler un peu, nous verrons plus de code attribué à cette fonction - tout n'est pas au même endroit :

Ce qui s'est passé ici est le compilateur décrivant le code qui est pris lorsque la vérification des limites échoue. Ce chemin de code conduit à une panique, et les paniques sont rares. Ainsi, le compilateur a mélangé le code de telle manière que nous ne chargeons même pas le code qui n'est exécuté que lors d'une panique jusqu'à ce que nous en ayons réellement besoin. Intelligent!

Bref, revenons à l'assemblée ! core::panicking::panic_bounds_checksemble être la panique sur l'échec de la vérification des limites, qui se produit dans l'assemblage attribué à notre ligne de code. Alors voilà à quoi ils ressemblent !

Voyons si le if length > 1 { fib[1] = 1; }bit en dehors de la boucle chaude a également une vérification des limites…

Pas de contrôle des limites ici ! Le compilateur était assez intelligent pour se rendre compte que lorsque lengthest strictement supérieur à 1, il est impossible que la vérification des limites échoue. Notre Vec appelé fiba également une longueur strictement supérieure à 1, et fib[1]est donc toujours dans les bornes.

Cependant, il ne semblait pas se rendre compte que la même chose s'appliquait à la boucle, en particulier à la fib[i] = fib[i-1] + fib[i-2];ligne.

Peut-être pouvons-nous l'aider ?

Aidez l'optimiseur

Nous allons apporter deux modifications au code pour permettre à l'optimiseur de prouver plus facilement que les vérifications des limites n'échouent jamais :

1. Au lieu d'indexer jusqu'à length, qui n'est qu'un nombre entier, nous allons indexer jusqu'à fib.len(), pour qu'il soit évident que l'index est toujours dans les limites.
2. Au lieu d'utiliser un Vec, nous allons en faire une tranche une fois et l'indexer dans la tranche. Cela rend plus clair que la longueur ne change pas.

Et vérifions-le avec cargo asm- la commande est dans le code ci-dessus :

Il est à nouveau divisé en deux parties pour une raison quelconque, mais la vérification des limites a disparu !

Mais est-ce plus rapide ? Découvrons-le!

$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000'

Benchmark 1: target/release/fibvec_naive_indexing 1000000000
  Time (mean ± σ):      3.612 s ±  0.040 s    [User: 1.435 s, System: 2.132 s]
  Range (min … max):    3.546 s …  3.693 s    10 runs
 
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
  Time (mean ± σ):      3.133 s ±  0.019 s    [User: 0.995 s, System: 2.103 s]
  Range (min … max):    3.106 s …  3.163 s    10 runs
 
Summary
  'target/release/fibvec_clever_indexing 1000000000' ran
    1.15 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'

C'est plus rapide, d'un énorme 15 % ! Ce n'est souvent pas une raison de se réjouir, mais c'est le plus grand coup de pouce que j'aie jamais vu en éliminant les vérifications des limites, donc c'est à peu près le meilleur que nous aurions pu espérer !

Et même si cet exemple était quelque peu artificiel, j'ai utilisé ces techniques pour accélérer la caisse fastblur de 15% . (Bien que j'ai d'abord réduit 6 fois plus de temps d'exécution par d'autres moyens ).

Mise à jour : l'exemple de fastblur a également été aidé par l'indexation dans une tranche au lieu d'un &mut Vec, plus d'informations ici . Ainsi, le gain de la suppression des vérifications des limites est en fait inférieur à 15 %.

À part : optimisations du compilateur

Maintenant, essayons également cela sur un processeur ARM 64 bits, juste pour confirmer…

$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000' 
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
  Time (mean ± σ):      3.320 s ±  0.024 s    [User: 1.131 s, System: 2.179 s]
  Range (min … max):    3.263 s …  3.346 s    10 runs
 
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
  Time (mean ± σ):      3.226 s ±  0.019 s    [User: 1.092 s, System: 2.127 s]
  Range (min … max):    3.209 s …  3.263 s    10 runs
 
Summary
  'target/release/fibvec_clever_indexing 1000000000' ran
    1.03 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'

Mais le montage sur ARM est vraiment court :

Aucun contrôle des limites en vue ! Et ce ne sont que 3 instructions, ce qui signifie très peu de travail à faire, donc ça devrait aller très vite !

Que se passe-t-il?

Rappelez-vous que la suppression des vérifications de limites en elles-mêmes n'a pas beaucoup d'importance. Vous ne pouvez voir une grande amélioration que si la suppression des contrôles de limites a permis au compilateur d'effectuer d'autres optimisations.

Si vous revenez en arrière et louchez sur l'assemblage x86 des fibonacci_vec vérifications sans limites, ce sont presque les mêmes lignes répétées encore et encore, ce qui ressemble étrangement à un déroulement de boucle .

Pourquoi est-il exécuté sur x86 et non sur ARM ? Je n'ai aucune idée! Cela devrait être - il s'agit d'une optimisation de base qui ne devrait en aucun cas être liée au processeur.

À titre de comparaison, j'ai essayé cela sur un processeur POWER9 , et le compilateur semble dérouler encore plus la boucle et hyperfine signale une accélération massive de 1.78 ± 0.04 times, donc je vais juste déposer un bogue pour rustc et laisser les gens qui savent comment fonctionnent les compilateurs s'en occuper il.

La conclusion importante pour nous est la suivante : les compilateurs d'optimisation résolvent un problème NP-difficile en très peu de temps, et il y a toujours des cas qu'ils ne gèrent pas exactement correctement.

Pire encore, les détails exacts changent entre les versions. Même si le compilateur s'améliore en moyenne, il peut régresser votre code spécifique ! La vectorisation automatique, par exemple, est notoirement instable, ce qui est frustrant car elle peut vous offrir de bien meilleures performances lorsqu'elle fonctionne.

J'ai trouvé que les optimisations qui suppriment les contrôles de limites sont très fiables - une fois que vous les faites fonctionner, elles ont tendance à continuer à fonctionner. Vous pouvez donc utiliser ces techniques et vous attendre généralement à ce qu'elles ne se cassent pas à l'avenir. Mais ce n'est que la partie responsable de la hausse de 3 % !

Étant donné que le déroulement de la boucle responsable de l'augmentation de 15 % fonctionne sur x86 mais pas sur ARM, je ne parierais pas sur son fonctionnement fiable à l'avenir. Telle est la triste réalité d'avoir quelque chose qui résout un problème NP-difficile en très peu de temps.

Heureusement, dans les programmes réels qui ne passent pas tout le temps d'exécution dans une seule boucle à chaud, les différences sont loin d'être aussi prononcées - les régressions à un endroit sont contrebalancées par des améliorations à un autre.

A part : Benchmarking

Alors vous vous demandez peut-être, pourquoi est-ce que j'utilise hyperfineet passe par tout ce problème d'écrire un non trivial main()?

Pourquoi est-ce que je n'utilise pas simplement cargo benchun critère ou quelque chose d'autre spécifiquement conçu pour l'analyse comparative ?

Cela a encore une fois à voir avec la tendance du compilateur à précalculer tout ce qu'il peut et à éliminer tout le code qui n'entraîne aucune modification de la sortie.

Si la valeur de retour d'une fonction n'est jamais utilisée et que la fonction ne panique pas, le compilateur la supprimera simplement !

C'est génial pour le code de production et terrible pour les benchmarks.

Vous pouvez essayer de lutter contre cela en enveloppant les entrées et les sorties dans std::hint::black_box(), mais il est difficile d'envelopper toutes les choses correctement, et on ne sait pas exactement quelles optimisations cela inhibe .

J'évite tout cela en créant un vrai binaire qui lit les entrées, et les entrées ne sont fournies que lorsque le programme est réellement exécuté, il n'y a donc aucun moyen pour le compilateur de précalculer quoi que ce soit. Il imprime également le résultat, de sorte que le compilateur ne peut pas supprimer la fibonacci_vecfonction en tant que code mort.

Et avoir des binaires autonomes facilite également l'inspection de l'assemblage et du profilage, comme vous le verrez bientôt !

D'un autre côté, je dois augmenter les longueurs de Vec pour obtenir des temps d'exécution facilement mesurables, et cela peut ne pas être représentatif de la façon dont ces fonctions fonctionnent sur de petits Vecs en raison des effets de cache CPU .

Maintenant, revenons à l'expérimentation des contrôles de limites…

Utilisez simplement des itérateurs

Les utilisateurs expérimentés de Rust m'ont probablement crié dessus tout le temps qu'ils ont lu cet article - jusqu'à présent, en tout cas !

Rust fournit des itérateurs pratiques qui vous permettent de travailler avec des collections sans vous soucier des vérifications des limites, des erreurs ponctuelles, etc.

Ils vous permettent également d'exprimer plus clairement ce que vous voulez accomplir - tant que vous pouvez vous souvenir des noms de tous les itérateurs ou toujours utiliser un IDE qui affiche la documentation, ce qui est un gros problème si vous me le demandez !

Alors allons-y et réécrivons notre code en utilisant des itérateurs. Nous avons besoin de fenêtres coulissantes sur notre Vec, et il y a un itérateur pratique pour cela appelé windows, alors essayons :

Oh oh ! Ça ne compile pas ! Le problème est que cela windows()ne nous donne que des tranches en lecture seule, nous ne pouvons pas écrire à travers elles. Pour la plupart des autres itérateurs, il existe une _mut()version correspondante qui donne des tranches modifiables, mais il n'y en a pas windows_mut()! Ce qui donne?

Il s'avère qu'il windows_mut()ne peut pas être implémenté comme un itérateur régulier dans Rust, car si vous deviez .collect()dire un Vec, vous vous retrouveriez avec de nombreuses tranches qui se chevauchent et mutables - mais Rust exige que chaque partie de la mémoire soit mutable à partir d'un seul endroit à la fois. temps!

Ce que nous recherchons s'appelle un soi-disant itérateur de flux qui ne peut pas être .collect()édité, mais il ne semble pas encore y avoir une telle chose dans la bibliothèque standard. Il va donc falloir modifier un peu notre code :

Cela fonctionne, et vous pouvez utiliser cargo asmpour confirmer qu'il n'y a pas de vérification des limites en cours ici. Sur Rust 1.65, il est légèrement plus rapide que notre tentative précédente sur ma machine, d'environ 2 %. Sur 1.66, c'est un autre gros coup de pouce :

$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000' 'target/release/fibvec_iterator 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
  Time (mean ± σ):      3.530 s ±  0.056 s    [User: 1.452 s, System: 2.027 s]
  Range (min … max):    3.450 s …  3.616 s    10 runs
 
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
  Time (mean ± σ):      3.111 s ±  0.058 s    [User: 1.037 s, System: 2.038 s]
  Range (min … max):    3.039 s …  3.207 s    10 runs
 
Benchmark 3: target/release/fibvec_iterator 1000000000
  Time (mean ± σ):      2.763 s ±  0.057 s    [User: 0.666 s, System: 2.078 s]
  Range (min … max):    2.686 s …  2.847 s    10 runs
 
Summary
  'target/release/fibvec_iterator 1000000000' ran
    1.13 ± 0.03 times faster than 'target/release/fibvec_clever_indexing 1000000000'
    1.28 ± 0.03 times faster than 'target/release/fibvec_naive_indexing 1000000000'

$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000' 'target/release/fibvec_iterator 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
  Time (mean ± σ):      3.324 s ±  0.024 s    [User: 1.160 s, System: 2.154 s]
  Range (min … max):    3.285 s …  3.354 s    10 runs
 
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
  Time (mean ± σ):      3.257 s ±  0.022 s    [User: 1.112 s, System: 2.136 s]
  Range (min … max):    3.232 s …  3.297 s    10 runs
 
Benchmark 3: target/release/fibvec_iterator 1000000000
  Time (mean ± σ):      2.968 s ±  0.025 s    [User: 0.782 s, System: 2.175 s]
  Range (min … max):    2.929 s …  3.011 s    10 runs
 
Summary
  'target/release/fibvec_iterator 1000000000' ran
    1.10 ± 0.01 times faster than 'target/release/fibvec_clever_indexing 1000000000'
    1.12 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'

Mais notez que nous avons dû modifier considérablement la façon dont nous implémentons le calcul ! Les itérateurs sont très pratiques si vous écrivez du code à partir de zéro, et vous devriez absolument les utiliser - mais ils peuvent être pénibles à intégrer dans un code existant. Et certains modèles ne peuvent pas du tout être exprimés avec des itérateurs !

Mise à jour : après la publication de cet article, la documentation de la bibliothèque standard a été mise à jour avec les instructions d'émulation de windows_mut(). Un exemple de calcul des nombres de Fibonacci peut être trouvé ici .

Et enfin, j'ai utilisé la forboucle avec un itérateur ici, mais dans ce cas, le compilateur peut manquer certaines optimisations "évidentes" . Si vous utilisez à la place .foreachsur l'itérateur, le compilateur devrait mieux optimiser le code . Ceci est particulièrement pertinent si vous avez une chaîne d'adaptateurs d'itérateur, quelque chose comme .skip().filter().take()ou même plus.

Donc, si vous vous retrouvez à écrire de longues chaînes d'itérateurs, cela peut valoir la peine de le comparer à une implémentation basée sur un index avec des conseils d'optimisation, comme celle que j'ai décrite précédemment. Ou comme ce qui suit…

Mettre une assertion devant la boucle chaude

Utilisons cette fonction que nous avons écrite.

Maintenant que nous avons un Vec plein de nombres de Fibonacci, nous pouvons écrire une fonction qui vérifie si un autre Vec a également des nombres de Fibonacci simplement en comparant les deux. Si notre Vec est suffisamment petit pour tenir dans le cache du processeur , cela pourrait être plus rapide que de refaire le calcul encore et encore !

Une implémentation naïve pourrait ressembler à ceci :

Vérifions l'assemblage :

Oh non, les vérifications des limites sont de retour ! La is_fibonacci()fonction les a dans la boucle chaude !

Nous devons vérifier les limites ici , car nous ne connaissons pas à l'avance les longueurs de l'une ou l'autre de ces tranches. C'est nécessaire pour l'exactitude! Mais ce que nous pouvons faire, c'est effectuer la vérification des limites une seule fois en dehors de la boucle, au lieu de pour chaque élément, ce qui rendra le coût négligeable.

Assurons-nous que les tailles sont les mêmes avant d'entrer dans la boucle et utilisons l'astuce consistant à itérer uniquement jusqu'à partir .len()du précédent :

Et voilà, plus de contrôles de limites à l'intérieur de la boucle chaude :

Voilà, c'est tout le montage attribué à la ligne d'indexation maintenant !

Cela peut également être réalisé avec un itérateur , mais en réalité, vous utiliserez simplement l' ==opérateur pour comparer les tranches . Le code est artificiel - montrer la technique d'optimisation est ce qui est important ici.

J'ai accéléré la caisse jpeg-decoder en utilisant cette approche, alors vérifiez cela si vous voulez voir des applications au code du monde réel. Là j'ai utilisé assert!des s au lieu de trancher, mais le principe est le même.

La grande chose à propos de cette approche est que vous ne pouvez pas avoir trop de assert! s - les redondants seront supprimés par le compilateur, tout comme les contrôles de limites !

L'inlining propage les contraintes entre les fonctions

Vous avez donc utilisé votre nouvelle is_fibonaccifonction brillante pendant un certain temps et avez décidé de diviser les éléments de comparaison en sa propre fonction pour la réutilisation :

Et maintenant, les vérifications des limites sont de retour ! La elements_are_equalfonction est une entité distincte et ne peut faire aucune hypothèse sur la façon dont elle est appelée (ou du moins quand elle l'a #[inline(never)]).

L'inlining se produit lorsque le compilateur copie le contenu de la fonction à l'endroit où elle est appelée, au lieu de simplement y placer un appel de fonction. (Inlining est son propre terrier de lapin qui va assez profondément, tout comme le cache CPU .)

Nous utilisons #[inline(never)]sur les fonctions dont nous voulons afficher l'assemblage afin que la fonction ne soit pas intégrée et ne fasse pas partie d'une autre fonction dans le code généré. (Bien qu'il soit théoriquement possible d'attribuer le code à des fonctions en ligne, cargo asmne le fait pas encore).

Au lieu de cela, nous allons utiliser #[inline(always)]for elements_are_equal()pour nous assurer que son contenu est copié is_fibonacci()et qu'il est optimisé ensemble - nous offrant les avantages s'ils sont séparés dans le code source, mais une seule entité pour l'optimiseur, de sorte que la connaissance des contraintes d'index serait propagé à travers les fonctions.

Nous avons échangé #[inline(never)]contre #[inline(always)]et les vérifications des limites devraient avoir disparu ! Vérifions :

$ cargo asm --rust --bin comparison_split_inline elements_are_equal
Error: No matching functions, try relaxing your search request

Mais on peut quand même vérifier le montage is_fibonacciet vérifier qu'il a fonctionné ! Les vérifications des limites sont de nouveau terminées !

Dans le monde réel, j'ai accéléré la randcaisse de 7% avec quelques assert!s et un #[inline(always)]- les mêmes techniques que celles présentées ici.

Voyons à quel point cette optimisation a réellement fait une différence ici :

$ hyperfine --warmup 3 --min-runs 20 'target/release/comparison_realistic 100000000 100000000' 'target/release/comparison_naive 100000000 100000000' 'target/release/comparison_clever 100000000 100000000' 'target/release/comparison_iterator 100000000 100000000'
Benchmark 1: target/release/comparison_realistic 100000000 100000000
  Time (mean ± σ):     729.8 ms ±  13.5 ms    [User: 193.8 ms, System: 532.5 ms]
  Range (min … max):   711.9 ms … 748.4 ms    20 runs
 
Benchmark 2: target/release/comparison_naive 100000000 100000000
  Time (mean ± σ):     739.8 ms ±  12.8 ms    [User: 206.5 ms, System: 529.1 ms]
  Range (min … max):   725.9 ms … 761.7 ms    20 runs
 
Benchmark 3: target/release/comparison_clever 100000000 100000000
  Time (mean ± σ):     736.2 ms ±  13.0 ms    [User: 210.0 ms, System: 521.7 ms]
  Range (min … max):   719.1 ms … 761.6 ms    20 runs
 
Benchmark 4: target/release/comparison_iterator 100000000 100000000
  Time (mean ± σ):     734.6 ms ±  10.9 ms    [User: 201.8 ms, System: 528.3 ms]
  Range (min … max):   724.3 ms … 760.7 ms    20 runs
 
Summary
  'target/release/comparison_realistic 100000000 100000000' ran
    1.01 ± 0.02 times faster than 'target/release/comparison_iterator 100000000 100000000'
    1.01 ± 0.03 times faster than 'target/release/comparison_clever 100000000 100000000'
    1.01 ± 0.03 times faster than 'target/release/comparison_naive 100000000 100000000'

D'accord, nous aurions probablement dû répondre à une question importante sur cette fonction avant de commencer à l'optimiser :

Cette fonction représente-t-elle même une partie suffisamment importante du temps d'exécution pour mériter d'être optimisée ?

A part : Profilage

Si nous rendons une fonction deux fois plus rapide, mais qu'elle ne représente que 2 % du temps d'exécution du programme, nous n'avons accéléré le programme que de 1 % !

Nous pouvons utiliser un profileur pour trouver où le temps est passé dans le programme, et donc quelle fonction serait une bonne cible pour l'optimisation.

Les langages de profilage qui se compilent en code natif, comme Rust, sont remarquablement mal documentés. Il existe une multitude d'outils dans divers états de délabrement, dont la plupart ne fonctionnent que sur un seul système d'exploitation, de sorte que le paysage peut être difficile à naviguer et est rempli de pièges. Voici donc un guide pour faire cela avec des outils modernes !

En guise de teasing, voici le résultat que nous allons obtenir :

Oui, je sais, ce n'est pas très lisible. Cliquez dessus!

Voir? C'est toute une interface utilisateur interactive pour visualiser les profils, directement dans le navigateur ! Ce que vous regardez est Firefox Profiler - qui fonctionne réellement dans n'importe quel navigateur, et c'est l'une des meilleures interfaces utilisateur de profileur que j'ai jamais utilisées.

La fonctionnalité qui tue partage les résultats en deux clics.

Je ne peux pas exagérer à quel point la fonctionnalité de partage est géniale et à quel point elle facilite la communication des résultats de performance. Si vous incluez un profil dans un rapport de bogue sur les performances, cela vous fait gagner beaucoup de temps , à vous et à celui qui finira par travailler à le corriger !

Interprétation des profils

Ce que nous regardons est un graphique de flamme . Chaque barre horizontale représente une fonction, et elle est aussi large que la part de temps d'exécution de la fonction.

Les barres sont empilées les unes sur les autres ; la barre du haut est appelée par la fonction représentée par une barre juste en dessous.

Les barres jaunes sont dans l'espace utilisateur et les barres oranges sont dans le noyau.

Par exemple, je peux dire que mainles appels fibonacci_vecqui à leur tour appellent le noyau, qui fait quelque chose avec des "pages" - qui doivent faire référence à des pages mémoire . Nous créons un Vec ici, donc ce doit être une allocation de mémoire.

Donc, apparemment, 51 % du temps de ce programme est consacré à l'allocation de mémoire, et 9 % supplémentaires à sa désallocation ! En fait hyperfine, nous en parlions plus tôt que nous passions beaucoup de temps dans le noyau - il rapporte useret syschronomètre, userétant notre programme et sysétant le noyau.

Notez que l'ordre des barres dans un graphique de flamme n'a pas de sens, il ne montre que le temps total passé dans une fonction donnée. Si vous voulez voir comment l'exécution du programme s'est réellement déroulée au lieu de visualiser les agrégats, passez à l'onglet "Stack Chart":

Cela montre que les appels dans le noyau fibonacci_vecsont répartis uniformément sur le temps d'exécution. Apparemment, le noyau provisionne progressivement la mémoire au lieu de nous servir une grosse allocation dès que nous le demandons. La désallocation à la fin, cependant, se produit en un seul morceau.

Les systèmes d'exploitation modernes provisionnent la mémoire uniquement lorsqu'elle est en cours d'écriture, ce que nous voyons ici. C'est aussi pourquoi vous pouvez essayer d'allouer 100 To de RAM et l'appel d'allocation initial réussira, mais votre processus sera tué si vous essayez d'écrire dans tout cela.

Capture des profils d'exécution

Voici comment créer l'un de ces magnifiques graphiques pour votre propre code.

Tout d'abord, le profileur a besoin de symboles de débogage pour attribuer des morceaux de code machine aux fonctions. Pour activer les symboles de débogage, ajoutez ceci à votre Cargo.toml :

[profile.release]
debug = true

Les autres étapes sont malheureusement spécifiques à la plateforme :

Profilage sur macOS

Il existe un profileur pratique qui affiche les résultats dans Firefox Profiler :

cargo install samply
samply record target/release/comparison_naive 100000000 100000000

Profilage sous Linux

Linux a un profileur très mature et flexible. L'inconvénient est qu'il est un peu trop flexible et qu'il peut être difficile de trouver les bons drapeaux.

Voici comment enregistrer un profil :

# --call-graph=dwarf tells the profiler use the debug symbols we added
sudo perf record --call-graph=dwarf target/release/comparison_naive 100000000 100000000

cargo install samply
sudo chown "$USER" perf.data # because we recorded the profile with `sudo`
samply load perf.data

Voir dans le noyau du système d'exploitation

Il y a une chose que Samply ne peut pas encore faire, et c'est rapporter où le temps est passé à l'intérieur du noyau. Ceci n'est nécessaire que si Samply affiche de larges barres orange sur le graphique de la flamme et que vous souhaitez comprendre ce qu'elles représentent.

Dans ce cas utilisez perf scriptpour visualiser le profil. Il est plus lent et moins précis, mais vous permet également de voir dans le noyau :

sudo perf script -F +pid > profile.perf

Les profils que j'ai montrés plus tôt ont été capturés à l'aide de cette méthode.

Profilage sous Windows

Voici la liste des bons outils de profilage gratuits disponibles sur Windows :

(Cette section a été intentionnellement laissée vide par Microsoft).

Intel VTune et AMD uProf sont gratuits, mais ne sont pas particulièrement géniaux - les interfaces utilisateur sont maladroites et il peut être difficile de les faire fonctionner en premier lieu (par exemple, vous devrez peut-être modifier certains paramètres dans le BIOS).

Heureusement, vous pouvez simplement utiliser les instructions Linux dans WSL2 ou toute autre machine virtuelle avec Linux.

Les résultats

La question à laquelle nous voulions répondre était donc :

is_fibonacci() représente-t-il même une partie suffisamment importante du temps d'exécution pour mériter une optimisation ?

Si vous ouvrez mon profil , vous pouvez voir dans les vues "Flame Graph" ou "Call Tree" que le programme a passé 13 % du temps dans is_fibonacci, et si vous en soustrayez tout le temps du noyau, fibonacci_vecil représente 23 % du temps.

Comme les temps d'exécution de ces deux fonctions sont à peu près comparables, il semble que la suppression des vérifications de limites is_fibonacciait effectivement très peu accéléré cette fonction.

Pour réitérer, ne voir qu'un léger coup de pouce de l'élimination des vérifications des limites est le résultat typique . C'est l'amélioration de 15% qui est l'anomalie !

Cela dit, examinons une dernière technique pour gérer les vérifications de limites.

Que se passe-t-il si je ne sais littéralement rien sur l'index ?

Jusqu'à présent, nous nous sommes appuyés sur certaines connaissances que nous avions sur les contraintes de notre index, ou avions une boucle où nous pouvions vérifier les limites une fois avant au lieu de le faire à chaque itération. Mais si…

Et si vous ne savez absolument rien sur l'index ?

Disons que l'index provient d'une entrée utilisateur non fiable, et vous ne pouvez absolument rien supposer à ce sujet. Vous devez effectuer une vérification des limites. Il n'y a pas d'autre moyen. Mais la fonction est plutôt chaude… et si vous pouviez l'accélérer ? Cela ne vous rapportera peut-être pas grand-chose, mais encore une fois, cela pourrait être le cas, et ce n'est qu'une vérification des limites et à quel point cela peut-il vraiment être inévitable ? !

Vous finissez par penser à votre énigme la nuit. Cette vérification des limites hante vos rêves. Vous narguer. Vous vous réveillez en sueur froide et décidez de faire quelque chose. Vous essayez panic = abortdans Cargo.toml, et peut-être que cela aide ou peut-être pas, cela pourrait être juste du bruit et les repères sont un mensonge et oh mon Dieu pourquoi avez-vous décidé de vous lancer dans la programmation ?!

Ne craignez rien, car je vais vous délivrer de cette situation difficile.

Nous allons créer. Le. Le moins cher. Possible. Bornes. Vérifier.

Observer.

Le. Le moins cher. Possible. Bornes. Vérifier.

Vous avez donc votre table de recherche pour les nombres de Fibonacci et une fonction nth_fibonacci()qui effectue simplement une recherche par index.

Facile, sauf que la fonction doit effectuer une vérification des limites car ses entrées sont complètement imprévisibles :

Regardez l'assemblée ! Juste, euh. Une seule ligne, en créant tellement:

Puisque nous ne savons rien de l'index, nous devons effectuer une vérification des limites. Mais nous pouvons le faire selon nos propres conditions.

L'instruction de branchement créée par ifs or peut être assez coûteuse, en ce qui concerne les instructions CPU ; nous avons déjà constaté son impact sur les benchmarks. Et s'il y avait une alternative moins chère ?

Rappelons-nous pourquoi nous avons besoin de vérifications des limites en premier lieu : nous voulons nous assurer que toutes les recherches sont confinées au Vec ou à la tranche avec laquelle nous travaillons - car si ce n'est pas le cas, nous obtenons Hearbleed ou pire . Mais une panique sur un accès invalide que les vérifications de limites habituelles créent n'est pas strictement obligatoire ; tant que tous les accès sont limités à la tranche avec laquelle nous travaillons, tout va bien.

Donc, techniquement, nous pourrions utiliser l' opérateur modulo , écrit comme %, pour limiter tous les accès à la tranche, comme ceci :

fibonacci[i % fibonacci.len()]

Malheureusement, l' %opérateur est également une instruction coûteuse, mais il existe un cas très particulier dont nous pouvons tirer parti. Si le diviseur est une constante et que l'on sait qu'il est une puissance de deux, tout compilateur valant ses octets l'optimisera en AND au niveau du bit , et les opérations au niveau du bit sont très bon marché.

Notre table de recherche ne contient que 100 nombres, ce qui n'est pas une puissance de deux, mais nous pouvons l'étendre à la puissance de deux la plus proche avec des valeurs fictives pour que tout fonctionne - nous avons déjà accepté des résultats erronés sur des accès invalides, nous autant aller jusqu'au bout !

Et ainsi notre code devient…

Vérifions le montage...

Oui!

Nous l'avons fait !

Ça y est ...! Le contrôle des limites le moins cher possible !

Nous avons légèrement gonflé l'utilisation de la mémoire et ne signalons plus les erreurs sur les accès invalides, mais nous avons atteint l'objectif d'accélérer notre fonction, même lorsque nous ne pouvions rien supposer sur l'index.

Que cela en vaille la peine… c'est à vous et à vos repères de décider.

Anti-modèles

Enfin, je veux jeter un coup d'œil à certains modèles que je continue de voir des gens écrire encore et encore, même s'ils les blessent au lieu de les aider.

debug_assert ! au lieu d'affirmer !

debug_assert!est supprimé en mode release. Ironiquement, cela rend le code plus lent : le compilateur ne peut plus rien présumer de la longueur de l'entrée et doit insérer les trois contrôles de limites en mode release !

Faites ceci à la place :

En règle générale, assert!la vérification des longueurs améliore les performances au lieu de les entraver. Il est très difficile d'en faire trop non plus - tous ceux qui sont redondants seront supprimés par l'optimiseur, tout comme les contrôles de limites !

En cas de doute, utilisez assert!à la place de debug_assert!.

Ou, si vous voulez être super-duper, assurez-vous de ne pas faire de travail supplémentaire :

Cela n'effectue également qu'une seule vérification des limites au lieu de trois.

Indexation non sécurisée par une valeur constante

Cela unsafe ne rend pas votre code plus rapide. En fait, en mode débogage, cela est plus lent que la version sécurisée car get_uncheckedcrée une surcharge d'appel de fonction et les optimisations qui le supprimeraient sont désactivées.

Faites ceci à la place :

Le compilateur optimise toujours l'indexation par une constante dans une tranche de longueur connue en mode release. Et en mode débogage, c'est encore plus rapide que unsafe.

Pensées d'adieu

Espérons que cette ménagerie de techniques pour gérer les vérifications de limites vous servira bien et que vous n'aurez jamais à recourir get_uncheckedet à risquer de créer des vulnérabilités d'exécution de code dans votre code.

Si vous souhaitez mettre en pratique ces techniques, vous pouvez rechercher sur Github une indexation non sécurisée et voir si vous pouvez la convertir en code sécurisé sans régresser les performances.

Bon piratage !