Exploring compiler parallelism with Go

Abstract

Parallel maskinvare har opplevd enorm vekst på bakgrunn av begrensningen i strømtetthet. Det har transformert måten programmere lager kode med høy ytelse. Det er lagt ned mye anstrengelse i oppgaver som er enkle å parallellisere; strukturerte data og SIMD operasjoner, som for eksempel lineær algebra. Mindre strukturerte data som utviser ujevnheter har vist seg å være vanskelig å parallellisere. Jeg undersøker i denne avhandlingen en kompilator skrevet i Go som er parallelliserbar. Jeg viser at det å parallellisere mange av kompilatorens interne rutiner reduserer kompileringstida med opp til 36% for større filer. Transformasjon av AST til SSA IR viser seg å være svært gunstig for parallellisering, fordi trestrukturer motsetter seg enkel parallellisering når man benytter tradisjonelle måter å traversere trærne på. Jeg viser at små filer kompilerer tregere når man introduserer parallellisering med flere goroutiner, i motsetning til større filer.

Til slutt presenterer jeg programmeringsspråket Go som et alternativ til C for introduksjonskurs i kompilatorteknikk ved universitetsnivå. Go har flere nyttige egenskaper som er innebygget. To av disse er svært sentrale datastrukturer i en kompilator: strenger og hash-tabeller. Jeg viser at en kompilator skrevet i Go vil ha færre linjer kode enn en tilsvarende kompilator skrevet i C.

The rise in popularity of general purpose parallel hardware, in the face of the power density wall, has transformed the way programmers create performant code. Much effort has been put into easily parallelisable, structured data access, SIMD operations, such as linear algebra. Less structured and erratic data formats have proven difficult to parallelise efficiently. I will be exploring the task of parallelising an elementary compiler using the Go programming language. I show that parallelising many of the compiler’s internal passes decreases compilation time of a reasonably large source file by 36%. Transforming the AST into an SSA IR is beneficial for parallelism, because tree structures subverts parallelism by traditional means of traversing the tree. I show that smaller source files slow down compilation time when using multiple goroutines, as compared to larger files with many functions.

Lastly, I present a case that the Go programming language is a suitable replacement for the C programming language for an introductory compiler construction course at university level. The Go programming language offers built-in datatypes, like strings and hashmaps, which are essential components of a compiler. Additionally I show that a Go programmed compiler should have fewer lines of code than the C equivalent.