Les compilateurs utilisent-ils le multithreading pour des temps de compilation plus rapides?

Si je me souviens bien de mon cours sur les compilateurs, le compilateur typique a le plan simplifié suivant:

• Un analyseur lexical analyse (ou appelle une fonction de numérisation) le code source caractère par caractère
• La chaîne de caractères d'entrée est vérifiée par rapport au dictionnaire des lexèmes pour la validité
• Si le lexème est valide, il est alors classé comme le jeton auquel il correspond
• L'analyseur valide la syntaxe de la combinaison de jetons; jeton par jeton .

Est-il théoriquement possible de diviser le code source en quartiers (ou quel que soit le dénominateur) et de multithreader le processus de numérisation et d'analyse? Existe-t-il des compilateurs utilisant le multithreading?

Les grands projets logiciels sont généralement composés de nombreuses unités de compilation qui peuvent être compilées de manière relativement indépendante, et donc la compilation est souvent parallélisée à une granularité très approximative en appelant le compilateur plusieurs fois en parallèle. Cela se produit au niveau des processus du système d'exploitation et est coordonné par le système de génération plutôt que par le compilateur proprement dit. Je me rends compte que ce n'est pas ce que vous avez demandé, mais c'est la chose la plus proche de la parallélisation dans la plupart des compilateurs.

Pourquoi donc? Eh bien, une grande partie du travail des compilateurs ne se prête pas facilement à la parallélisation:

• Vous ne pouvez pas simplement diviser l'entrée en plusieurs morceaux et les lexer indépendamment. Pour plus de simplicité, vous voudriez diviser les limites de lexme (de sorte qu'aucun thread ne démarre au milieu d'une lexme), mais la détermination des limites de lexme nécessite potentiellement beaucoup de contexte. Par exemple, lorsque vous sautez au milieu du fichier, vous devez vous assurer que vous n'avez pas sauté dans un littéral de chaîne. Mais pour vérifier cela, vous devez examiner essentiellement tous les personnages qui l'ont précédé, ce qui représente presque autant de travail que de lexiquer simplement pour commencer. En outre, le lexing est rarement le goulot d'étranglement dans les compilateurs pour les langues modernes.
• L'analyse est encore plus difficile à paralléliser. Tous les problèmes de division du texte d'entrée pour lexing s'appliquent encore plus à la division des jetons pour l'analyse --- par exemple, déterminer où commence une fonction est fondamentalement aussi difficile que d'analyser le contenu de la fonction pour commencer. Bien qu'il puisse également y avoir des moyens de contourner cela, ils seront probablement d'une complexité disproportionnée pour le peu d'avantages. L'analyse n'est pas non plus le plus gros goulot d'étranglement.
• Après avoir analysé, vous devez généralement effectuer une résolution de nom, mais cela conduit à un énorme réseau de relations entrelacées. Pour résoudre un appel de méthode ici, vous devrez peut-être d'abord résoudre les importations dans ce module, mais celles-ci nécessitent la résolution des noms dans une autre unité de compilation, etc. Idem pour l'inférence de type si votre langue l'a.

Après cela, cela devient un peu plus facile. La vérification et l'optimisation de type et la génération de code pourraient, en principe, être parallélisées à la granularité de la fonction. Je connais encore peu ou pas de compilateurs qui font cela, peut-être parce que faire n'importe quelle tâche en même temps est assez difficile. Vous devez également considérer que la plupart des grands projets logiciels contiennent tellement d'unités de compilation que l'approche «exécuter un tas de compilateurs en parallèle» est entièrement suffisante pour garder tous vos cœurs occupés (et dans certains cas, même une batterie de serveurs entière). De plus, dans les grandes tâches de compilation, les E / S disque peuvent être autant un goulot d'étranglement que le travail réel de compilation.

Cela dit, je connais un compilateur qui parallèle le travail de génération et d'optimisation de code. Le compilateur Rust peut diviser le travail principal (LLVM, qui inclut en fait des optimisations de code qui sont traditionnellement considérées comme "milieu de gamme") entre plusieurs threads. C'est ce qu'on appelle des "unités de code-gen". Contrairement aux autres possibilités de parallélisation discutées ci-dessus, cela est économique car:

1. Le langage a des unités de compilation plutôt grandes (par exemple, C ou Java), donc il peut y avoir moins d'unités de compilation en vol que vous n'en avez de cœurs.
2. La partie qui est parallélisée prend généralement la grande majorité du temps de compilation.
3. Le travail backend est, pour la plupart, embarrassant parallèle - il suffit d'optimiser et de traduire en code machine chaque fonction indépendamment. Il y a bien sûr des optimisations inter-procédurales, et les unités de codegen les gênent et ont donc un impact sur les performances, mais il n'y a pas de problèmes sémantiques.

La compilation est un problème "embarrassamment parallèle".

Personne ne se soucie du temps de compilation d'un fichier. Les gens se soucient du temps de compilation de 1000 fichiers. Et pour 1000 fichiers, chaque cœur du processeur peut facilement compiler un fichier à la fois, gardant tous les cœurs totalement occupés.

Astuce: "make" utilise plusieurs cœurs si vous lui donnez l'option de ligne de commande appropriée. Sans cela, il compilera un fichier après l'autre sur un système à 16 cœurs. Ce qui signifie que vous pouvez le compiler 16 fois plus rapidement en modifiant d'une ligne vos options de génération.