Dot.Blog

C#, XAML, Xamarin, UWP/Android/iOS

C# - Les optimisations du compilateur dans le cas du tail-calling

Les optimisations du compilateurs C# ne sont pas un sujet de discussion très courant, en tout cas on voit très nettement que le fait d'avoir quitté l'environnement Win32 pour l'environnement managé de .NET a fait changer certaines obsessions des codeurs... Ce n'est pas pour autant que le sujet a moins d'intérêt ! Nous allons voir cela au travers d'une optimisation particulière appelée "tail-calling" (appel de queue, mais je n'ai pas trouvé de traduction française, si quelqu'un la connaît, qu'il laisse un commentaire au billet).

Principe

On appelle "tail-calling" un mécanisme d'optimisation du compilateur qui permet d'économiser les instructions exécutées en même temps que des accès à la pile. Les circonstances dans lesquelles le compilateur peut utiliser cette optimisation sont celles où une méthode se termine par l'appel d'une autre, d'où le nom de tail-calling (appel de queue).

Prenons l'exemple suivant :

static public void Main()
{
    Go();
}
 
static public void Go()
{
    Première();
    Seconde();
    Troisième();
}
 
static public void Troisième()
{
}

Dans cet exemple le compilateur peut transformer l'appel de Troisième() en un appel de queue (tail-calling). Pour mieux comprendre regardons l'état de la pile au moment de l'exécution de Seconde()  : Seconde()-Go()-Main()

Quand Troisième() est exécutée il devient possible, au lieu d'allouer un nouvel emplacement sur la pile pour cette méthode, de simplement remplacer l'entrée de Go() par Troisième(). La pile ressemble alors à Troisième()-Main().

Quand Troisième() se terminera elle passera l'exécution à Main() au lieu de transférer le trait à Seconde() qui immédiatement devra le transférer à Main().

C'est une optimisation assez simple qui, cumulée tout au long d'une application, et ajoutée aux autres optimisations, permet de rendre le code exécutable plus efficace.

Quand l'optimisation est-elle effectuée ?

La question est alors de savoir quand le compilateur décide d'appliquer l'optimisation de tail-calling. Mais dans un premier temps il faut se demander de quel compilateur nous parlons.... Il y existe en effet deux compilateurs dans .NET, le premier prend le code source pour le compiler en IL alors que le second, le JIT, utilisera ce code IL pour créer le code natif. La compilation en IL peut éventuellement placer certains indices qui permettront de mieux repérer les cas où le tail-calling est applicable mais c'est bien entendu dans le JIT que cette optimisation s'effectue.

Il existe de nombreuses règles permettant au JIT de décider s'il peut ou non effectuer l'optimisation. Voici un exemple de règles qui font qu'il n'est pas possible d'utiliser le tail-calling (par force cette liste peut varier d'une implémentation à l'autre du JIT) :

  • L'appelant ne retourne pas directement après l'appel;
  • Il y a une incompatibilité des arguments passés sur la pile entre l'appelant et l'appelé ce qui imposerait une modification des arguments pour appliquer le tail-calling;
  • L'appelant et l'appelé n'ont pas le même type de retour (données de type différents, void);
  • L'appel est est transformé en inline, l'inlining étant plus efficace que le tail-calling et ouvrant la voie à d'autres optimisations;
  • La sécurité interdit ponctuellement d'utiliser l'optimisation;
  • Le compilateur, le profiler, la configuration ont coupé les optimisations du JIT.

Pour voir la liste complète des règles, jetez un oeil à ce post.

Intérêt de connaitre cette optimisation ?

Normalement les optimisations du JIT ne sont pas un sujet intéressant au premier chef le développeur. D'abord parce qu'un environnement managé comme .NET fait qu'à la limite ce sont les optimisations du code IL qui regarde directement le développeur et beaucoup moins la compilation native qui peut varier d'une plateforme à l'autre pour une même application. Ensuite il n'est pas forcément judicieux de se reposer sur les optimisations du JIT puisque, justement, ce dernier peut être différent sans que l'application ne le sache.

Qui s'intéresse à l'optimisation du tail-calling alors ? Si vous écrivez un profiler c'est une information intéressante, mais on n'écrit pas un tel outil tous les jours... Mais l'information est intéressante lorsque vous déboguez une application car vous pouvez vous trouver face à une pile d'appel qui vous semble "bizarre" ou "défaillante" car il lui manque l'une des méthodes appelées !

Et c'est là que savoir qu'il ne faut pas chercher dans cette direction pour trouver le bug peut vous faire gagner beaucoup de temps... Savoir reconnaître l'optimisation de tail-calling évite ainsi de s'arracher les cheveux dans une session de debug un peu compliquée si on tombe en plus sur un pile d'appel optimisée. Un bon debug consiste à ne pas chercher là où ça ne sert à rien (ou à chercher là où c'est utile, mais c'est parfois plus difficile à déterminer !), alors rappelez-vous du tail-calling !

Et stay tuned !

nota: le présent billet est basé sur un post de l'excellent blog ASP.NET Debugging

blog comments powered by Disqus