Partial evaluation is a program transformation technique that specializes a program with respect to part of its input. While the specialization is typically performed ahead-of-time, moving it to a later stage may expose additional opportunities and allow for faster residual programs to be constructed. In this thesis, we present a method for specializing programs at run-time, for compiled code, using an online partial evaluator. Although partial evaluation has several applications, the evaluation of the method primarily focuses on its performance benefits. The main research problem addressed in this thesis is that of incorporating an online partial evaluator in compiled code. The partial evaluator is a sourceto-source translator that takes and produces an abstract syntax tree (AST). Our approach consists of three parts, namely that of partially evaluating, obtaining a partially evaluable representation and run-time code emitting. Concretely, we use the concept of lifting to store an AST in the compiled code that the partial evaluator then specializes at run-time. The residual code is thereafter naively just-in-time (JIT) compiled through dynamically linking it back to the executable as a shared library. We evaluate the method on several programs and show that the specialized programs sometimes are faster even with a low recursion depth. Though, while the results are promising, the overhead is typically significant and therefore the break-even points are large. Further research, for example using an efficient JIT compiler, is required to better evaluate the performance benefits of the approach. / Partiell evaluering är en programtransformationsteknik som specialiserar ett program givet delar av dess indata. Typisk sätt specialiseras program innan de exekveras, men genom att flytta specialisering till då programmet körs kan ytterligare information utnyttjas och därmed snabbare residualprogram konstrueras. I det här examensarbetet presenteras en metod för att specialisera program i körtid med online partiell evaluering, specifikt för kompilerade program. Metoden utvärderas främst utefter prestanda, men det ska nämnas att partiell evaluering har fler tillämpningar än så. Det huvudsakliga problemet som examensarbetet undersöker är inkorporeringen av en programspecialiserare (partial evaluator) i kompilerad kod. Den programspecialiserare som används tar både som indata och producerar ett abstrakt syntaxträd (AST). Vårt tillvägagångssätt består av tre delar, nämligen programspecialisering, erhållning av en representation som kan specialiseras och slutligen kodgenerering i körtid. Mer specifikt används konceptet lyftning för att spara ett AST i den kompilerade koden som därefter partiellt evalueras av programspecialiseraren under körtid. Som ett sista steg just-in-time (JIT) kompileras residualprogrammet. Detta görs på ett naivt vis genom att programmet kompileras till ett delat bibliotek som därefter dynamiskt länkas tillbaka till huvudprogrammet. Metoden utvärderas på flera program och vi visar att de specialiserade programmen i vissa fall var snabbare och det även med små rekursionsdjup. Resultaten är lovande, men den overhead som metoden ger upphov till är ofta signifikant vilket gör att det krävs många iterationer innan det specialiserade programmet blir snabbare. Ytterligare forskning och tester, till exempel med en effektiv JIT kompilator, är nödvändig för att bättre kunna utvärdera metodens prestandafördelar.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-345164 |
| Date | January 2024 |
| Creators | Adamsson, Johan |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2024:13 |
Page generated in 0.0014 seconds