C n'est pas un langage de bas niveau

Votre ordinateur n'est pas une version rapide de PDP-11

Bonjour, Habr!

Je m'appelle Anton Dovgal, je suis développeur C (et pas seulement) chez Badoo.

Je suis tombé sur un article de David Chiznell, chercheur à l'Université de Cambridge, dans lequel il conteste l'opinion généralement acceptée selon laquelle C est un langage de bas niveau, et ses arguments m'ont paru suffisamment intéressants.

À la lumière des vulnérabilités récemment découvertes, Meltdown et Spectre devraient prendre le temps de découvrir les raisons de leur apparition. Ces deux vulnérabilités exploitaient l'exécution spéculative d'instructions par des processeurs et permettaient à un attaquant de recevoir des résultats via des canaux tiers. Des vulnérabilités dans les fonctionnalités du processeur, ainsi que d'autres, ont été ajoutées afin que les programmeurs C continuent de croire qu'ils programment dans un langage de bas niveau, bien que cela n'ait pas été le cas depuis des décennies.

Les fabricants de processeurs ne sont pas seuls dans ce domaine. Les développeurs de compilateurs C / C ++ ont également contribué.

Qu'est-ce qu'une langue de bas niveau?

L'informaticien américain et premier lauréat du prix Turing Alan Perlis a donné la définition suivante:

"Un langage de programmation est de bas niveau si les programmes écrits dessus nécessitent une attention au non essentiel."

Bien que cette définition fasse référence à C, elle ne permet pas de comprendre ce que les gens veulent voir dans un langage de bas niveau. Diverses propriétés font que les gens considèrent le langage comme bas. Imaginez une échelle de langages de programmation avec l'assembleur à une extrémité et une interface avec un ordinateur d'entreprise à l'autre. Les langues de bas niveau sont plus proches du fer, tandis que les langues de haut niveau sont plus proches de la façon dont les gens pensent.

Pour être «plus proche du matériel», le langage doit fournir des abstractions qui correspondent aux abstractions de la plateforme cible. Il est facile de prouver que C était un langage de bas niveau dans PDP-11. L'exécution séquentielle des programmes, un espace d'adressage plat, même les opérateurs pré et post-incrémentation, tombaient parfaitement sur les modes d'adressage PDP-11.

Émulateurs PDP-11 rapides

La principale raison des vulnérabilités de Spectre et Meltdown est que les créateurs des processeurs ne se sont pas contentés de fabriquer des processeurs rapides, ils ont créé des processeurs rapides avec une interface PDP-11. Ceci est important car il permet aux programmeurs C de continuer à croire que leur langage est proche du matériel.

Le code C fournit un automate abstrait principalement séquentiel (jusqu'à C11, il est complètement séquentiel, si les extensions non standard sont exclues). La création d'un nouveau thread est un appel à une fonction de bibliothèque, une opération assez coûteuse. Par conséquent, les processeurs, désireux de continuer à exécuter du code C, s'appuient sur le parallélisme au niveau de l'instruction (ILP). Ils analysent les opérations voisines et effectuent des opérations indépendantes en parallèle. Cela complique considérablement les processeurs et entraîne une augmentation de la consommation d'énergie, mais permet aux programmeurs d'écrire principalement du code séquentiel. En revanche, les processeurs graphiques (GPU) atteignent des performances élevées d'une autre manière: ils nécessitent l'écriture de programmes parallèles.

Une concurrence élevée au niveau de la commande est la cause directe de Spectre et Meltdown. Le processeur Intel moderne exécute jusqu'à 180 instructions simultanément (contrairement à la machine séquentielle C abstraite, qui s'attend à ce que l'instruction précédente soit exécutée avant que la suivante ne démarre). Une heuristique typique du code C montre qu'il y a une branche en moyenne pour sept instructions. Si vous voulez garder le pipeline d'instructions complet, vous devez deviner les 25 prochaines branches. Cela, à son tour, ajoute de la complexité - le processeur calcule d'abord la branche incorrectement devinée, puis renvoie les résultats des calculs, ce qui affecte négativement la consommation d'énergie. Ces données lancées ont des résultats indirects visibles, qui ont été utilisés dans les attaques Spectre et Meltdown.

Renommer les registres consomme beaucoup d'énergie et de puces dans les processeurs modernes. Il ne peut pas être désactivé ou sa consommation d'énergie réduite, ce qui le rend incommode à l'ère du silicium noir , lorsque les transistors sont faibles, mais les transistors impliqués sont une ressource précieuse. Ce périphérique est absent du GPU, où la concurrence est obtenue en utilisant des threads au lieu d'essayer d'exécuter en parallèle du code initialement séquentiel. Si les instructions n'ont pas de dépendances à reconstruire, il n'est pas non plus nécessaire de renommer les registres.

Prenons un autre élément fondamental de la conception C: la mémoire plate. Cela n'existe pas depuis quelques décennies. Un processeur moderne a souvent trois niveaux de mise en cache entre les registres et la mémoire principale, réduisant ainsi le temps nécessaire pour accéder à cette dernière.

Le cache est caché au programmeur et donc inaccessible à C.L'utilisation efficace du cache est l'un des moyens d'accélérer l'exécution du code sur un processeur moderne, mais il est complètement caché de la machine abstraite et les programmeurs sont obligés de s'appuyer sur la connaissance des détails de l'implémentation du cache (par exemple, deux alignés 64 bits les valeurs peuvent apparaître sur une ligne du cache) pour écrire du code efficace.

Optimisation C

L'une des caractéristiques communes attribuées aux langues de bas niveau est la vitesse. En particulier, ils devraient être faciles à traduire en code rapide sans compilateur compliqué. L'argument selon lequel un compilateur suffisamment intelligent peut rendre un langage rapide est souvent ignoré par les partisans de C lorsqu'ils parlent d'autres langages.

Malheureusement, en utilisant une simple traduction, vous ne pouvez pas obtenir de code rapide à partir de C.
Les architectes de processeurs font des efforts héroïques pour créer des puces capables d'exécuter rapidement du code C. Mais les niveaux de performances que les programmeurs s'attendent à voir ne sont atteints qu'avec l'aide d'optimisations incroyablement complexes effectuées par le compilateur.
Le compilateur Clang (y compris les parties correspondantes de LLVM) comprend environ 2 millions de lignes de code. Pour l'analyse et la transformation du code, nécessaires à l'accélération de C, environ 200 000 lignes de code sont nécessaires (hors commentaires et lignes vierges).

Par exemple, pour traiter une grande quantité de données en C, vous devez écrire une boucle qui traite chaque élément séquentiellement. Pour l'exécution optimale de ce cycle sur un processeur moderne, le compilateur doit déterminer que les itérations du cycle sont indépendantes les unes des autres. Le mot clé restrict peut aider dans ce cas - il garantit que les écritures sur un pointeur n'interfèrent pas avec la lecture d'un autre pointeur. Ces informations en C sont beaucoup plus limitées que dans un langage tel que Fortran, qui est la principale raison pour laquelle C n'a pas été en mesure de les sortir du calcul haute performance.

Une fois que le compilateur a déterminé que les itérations sont indépendantes les unes des autres, l'étape suivante est une tentative de vectorisation du résultat, car le débit des processeurs modernes est quatre à huit fois plus élevé pour le code vectorisé que pour le code scalaire. Un langage de bas niveau pour de tels processeurs aurait ses propres types vectoriels de longueur arbitraire. De tels types sont présents dans la représentation LLVM intermédiaire, car il est toujours plus facile de diviser de grandes opérations avec des vecteurs en plusieurs petites que de construire de plus grandes opérations vectorielles.

À ce stade, les optimiseurs doivent faire face aux règles de mémoire C. C garantit que les structures avec le même préfixe peuvent être utilisées de manière interchangeable, et donne accès aux champs de champs décalés des structures dans le langage. Cela signifie que le compilateur ne peut pas modifier l'ordre des champs dans la structure ou ajouter un alignement pour améliorer la vectorisation (par exemple, transformer une structure de tableaux en un tableau de structures ou vice versa). Ce n'est généralement pas un problème dans les langages de bas niveau, où il est possible de contrôler l'emplacement des champs dans la structure, mais cela rend la tâche d'accélération de C. plus difficile.

C nécessite également un alignement à la fin de la structure, car il garantit qu'il n'y a pas d'alignement dans les tableaux. L'alignement est une partie assez complexe de la spécification C, qui interagit mal avec les autres parties du langage. Par exemple, vous devriez pouvoir comparer deux structures à l'aide de la méthode de comparaison sans type (c'est-à-dire la fonction memcmp ()), de sorte que la copie de la structure doit également être alignée. Dans certains cas, la copie de l'alignement prend beaucoup de temps.

Considérez les deux optimisations de base que le compilateur C produit: SROA (remplacement scalaire des agrégats, remplacement scalaire des agrégats) et ouverture de boucle .

SROA essaie de remplacer les structures et les tableaux de taille fixe par des variables distinctes. Cela permet au compilateur de traiter leur accès indépendamment les uns des autres et d'ignorer l'opération, s'il est évident que son résultat n'est pas utilisé. Dans certains cas, l'effet indirect de cette optimisation est de supprimer l'alignement.

La deuxième optimisation, l'ouverture de la boucle, convertit la boucle avec la condition en une condition avec différentes boucles dans les deux branches. Cela change l'ordre d'exécution par opposition à l'affirmation que le programmeur sait ce qui sera exécuté dans un langage de bas niveau. Et cela crée également de sérieux problèmes avec la façon dont C gère les variables non définies et le comportement non défini.

En C, une variable non initialisée a une valeur non définie, qui peut être différente à chaque appel. Ceci est important car il vous permet d'implémenter le recyclage paresseux des pages mémoire. Par exemple, dans FreeBSD, l'implémentation malloc () indique au système que les pages ne sont plus utilisées et que le système utilise la première entrée de la page comme preuve que ce n'est pas le cas. Faire appel à la mémoire nouvellement allouée peut obtenir l'ancienne valeur, puis le système d'exploitation peut réutiliser la page de mémoire, puis la remplacer par une page remplie de zéros la prochaine fois que vous écrivez à un autre endroit de la page. Le deuxième appel au même endroit sur la page obtiendra une valeur nulle.

Si la condition utilise une valeur non définie, le résultat n'est pas non plus défini - tout peut arriver. Imaginez une optimisation de boucle ouverte où une boucle est exécutée zéro fois. Dans l'original, la boucle entière est du code mort. Dans la version ouverte, il y a maintenant une condition avec une variable qui ne peut pas être initialisée.
Par conséquent, le code mort peut être converti en un comportement non défini. Ce n'est là qu'une des nombreuses optimisations qui, lorsqu'elles explorent plus en profondeur la sémantique de C, ne sont pas fiables.

En fin de compte, vous pouvez faire fonctionner le code C rapidement, mais seulement après avoir passé des milliers d'années-homme à créer un compilateur suffisamment intelligent. Mais cela n'est possible que si certaines règles de la langue sont violées. Les créateurs de compilateurs permettent aux programmeurs C d'imaginer qu'ils écrivent du code "proche du matériel", mais ils doivent générer du code machine qui se comporte différemment afin que les programmeurs continuent de croire qu'ils écrivent dans un langage rapide.

Comprendre C

L'un des attributs de base d'un langage de bas niveau est que les programmeurs peuvent facilement comprendre comment une machine de langage abstrait est transférée vers une machine physique. C'était certainement le cas sur PDP-11, où les expressions C étaient traduites en une ou deux instructions. De même, le compilateur place les variables dans les emplacements de pile et convertit les types simples en compréhensibles pour PDP-11.

Depuis lors, les implémentations C sont devenues beaucoup plus compliquées - pour maintenir l'illusion que C est facilement porté sur une plate-forme matérielle et s'exécute rapidement. En 2015, une enquête auprès des programmeurs C, des auteurs de compilateurs et des membres du comité de normalisation a montré qu'il y avait des problèmes pour comprendre C. Par exemple, ce langage permet à une implémentation d'ajouter un alignement aux structures (mais pas aux tableaux) pour garantir que tous les champs sont correctement alignés pour la plate-forme cible. Si vous remplissez cette structure de zéros puis spécifiez une valeur pour certains champs, y aura-t-il des zéros dans les bits d'alignement? Selon l'enquête, 36% étaient sûrs qu'ils le feraient et 29% ne connaissaient pas la réponse. Selon le compilateur et le niveau d'optimisation, cela peut être vrai (ou non).

Ceci est un exemple assez banal, mais de nombreux programmeurs donnent la mauvaise réponse ou ne peuvent pas répondre du tout.

Si vous ajoutez des pointeurs, la sémantique de C devient encore plus confuse. Le modèle BCPL était assez simple: toutes les significations sont des mots. Chaque mot est soit une donnée, soit une adresse en mémoire. La mémoire est un tableau plat de cellules indexées par adresse.

Le modèle C permet la mise en œuvre de différentes plates-formes, y compris des architectures segmentées, où le pointeur peut être composé d'ID de segment et de décalages, ainsi que de machines virtuelles avec un garbage collector. La spécification C limite les opérations de pointeur autorisées pour éviter les problèmes avec de tels systèmes. La réponse au rapport de défauts 260 mentionne l'origine du pointeur:

«Les implémentations peuvent suivre l'origine d'un ensemble de bits et gérer ceux qui contiennent une valeur non définie différemment de ceux qui en contiennent un spécifique. "Ils peuvent gérer les pointeurs différemment selon leur origine, même s'ils sont identiques en termes de valeur binaire."

Malheureusement, le mot "origine" est absent de la spécification C11, donc les compilateurs décident eux-mêmes de ce qu'il signifie. GCC et Clang, par exemple, diffèrent quant à savoir si le pointeur qui a été converti en entier et en arrière conserve son origine. Les compilateurs peuvent décider que deux pointeurs vers les résultats de malloc () donnent toujours un résultat négatif lors de la comparaison, même s'ils pointent vers la même adresse.

Ces malentendus ne sont pas purement académiques. Par exemple, des vulnérabilités ont déjà été observées, qui résultaient du débordement d'un entier signé (comportement non défini en C) ou du déréférencement d'un pointeur avant de le vérifier pour NULL , malgré le fait que le compilateur a été informé que le pointeur ne pouvait pas être NULL.

S'il y a de tels problèmes, il est difficile de s'attendre à ce qu'un programmeur comprenne parfaitement comment un programme C se traduit par l'architecture appropriée.

Présentation d'un processeur pas pour C

Les correctifs proposés pour protéger contre Spectre et Meltdown provoquent une grave dégradation des performances, annulant toutes les réalisations de la microarchitecture au cours de la dernière décennie. Il est peut-être temps d'arrêter de réfléchir à la façon d'accélérer le code C et de penser à la place à de nouveaux modèles de programmation sur des processeurs conçus pour la vitesse.

Il existe de nombreux exemples d'architectures qui ne se sont pas concentrées sur le code C traditionnel et sur lesquelles s'inspirer. Par exemple, les processeurs orientés multithreading tels que Sun / Oracle UltraSPARC Tx ne nécessitent pas autant de cache pour occuper leurs actionneurs. Les processeurs de recherche ont étendu ce concept à un très grand nombre de threads prévus par le matériel. L'idée clé est qu'avec suffisamment de threads, le processeur peut suspendre les threads en attente de données et remplir les actionneurs avec des instructions provenant d'autres threads. Le problème est que les programmes C ont généralement très peu de threads.

SVE (Scalar Vector Extensions, extensions de vecteur scalaire) d'ARM est un autre travail similaire de Berkeley, qui offre un aperçu de l'interface améliorée entre le programme et le matériel. Les blocs de vectorisation réguliers implémentent des opérations avec des vecteurs de taille fixe et s'attendent à ce que le compilateur adapte l'algorithme à la taille spécifiée. En revanche, l'interface SVE invite le programmeur à décrire indépendamment le niveau de parallélisme et attend du matériel qu'il l'adapte aux actionneurs disponibles. Son utilisation en C est difficile car l'auto-vectoriseur doit calculer le parallélisme en fonction des boucles dans le code.

Les caches sont volumineux, mais ce n'est pas la seule raison de leur complexité. Le protocole de prise en charge de la cohérence du cache est l'un des composants les plus complexes d'un processeur moderne. La majeure partie de la difficulté vient du fait de devoir maintenir un langage dans lequel les données peuvent être partagées et modifiables. Comme exemple opposé, nous pouvons utiliser une machine abstraite de style Erlang, où chaque objet est soit local soit immuable. Le protocole de cohérence d'antémémoire pour un tel système n'aurait que deux cas: les données mutables et les données partagées. Le cache du flux de programme qui a été transféré vers un autre processeur doit être explicitement désactivé, mais c'est une opération relativement rare.

Les objets immuables peuvent simplifier encore plus les caches et rendre certaines opérations moins coûteuses. Dans un projet Maxwell de Sun Labs, il a été noté que les objets dans le cache et les objets récemment créés sont presque toujours les mêmes. Si des objets meurent avant d'être exclus du cache, vous ne pouvez pas les écrire dans la mémoire principale et ainsi économiser de l'énergie. Le projet Maxwell proposait un garbage collector qui fonctionnait dans le cache et vous permettait de recycler rapidement la mémoire. Avec des objets immuables sur le tas et la pile mutable, le garbage collector devient une machine d'état très simple, qui est facilement implémentée dans le matériel et vous permet d'utiliser efficacement un cache relativement petit.

Un processeur conçu uniquement pour la vitesse, et non pour le compromis entre la vitesse et la prise en charge C, devrait probablement prendre en charge un grand nombre de threads, avoir de grands blocs de vectorisation et un modèle de mémoire plus simple. Il sera difficile d'exécuter du code C sur un tel processeur, par conséquent, étant donné le volume de l'ancien code C dans le monde, il est peu probable qu'il ait un succès commercial.

Dans le domaine du développement logiciel, il existe un mythe selon lequel la programmation parallèle est difficile. Alan Kay serait très surpris d'entendre cela: il a appris aux enfants à utiliser le modèle de l'acteur, avec lequel ils ont écrit des programmes sur plus de 200 streams. Cela est également inconnu des programmeurs Erlang, qui écrivent souvent des programmes avec des milliers de composants parallèles. Il est plus correct de dire que la programmation parallèle est difficile dans un langage avec une machine abstraite comme C. Et si vous faites attention à la prédominance du matériel parallèle (des processeurs multicœurs aux GPU multicœurs), alors c'est juste une autre façon de dire que C ne convient pas au matériel moderne fournir.