en en en pt es en en en en cv az en en en en en en en en en ne en en en pt en en fr en en pt en en en en en en en en fr en en en en cs en en en en en en en en en en en en en en en en en zh nl en en en en en en en en en en en en en en it en en en en en en en pt en en en en en en en en en en en en en en en en
For those not familiar with this blog, my PhD research is focused on the optimization of programs written in dynamically typed programming languages, JavaScript (JS) in particular. In JS, every arithmetic operator and every object property access needs to do dynamic dispatch based on the type of its operands. For instance, the addition operator can work on integers, strings and floating point values. It can actually accept values of any type as operands. The types of both inputs are implicitly tested at run time so that the correct behavior can be chosen. Much of these type tests are redundant, because even in a dynamically typed programming language like JavaScript, most variables don’t change type over the execution of a program.
Earlier this year, my first paper about Basic Block Versioning (BBV) was accepted at ECOOP 2015. BBV is a JIT code generation technique I’ve been working on which is very effective for eliminating redundant dynamic type tests. In this first paper, we (my advisor and I) were able to show that our technique eliminates 71% of dynamic type tests across our set of benchmarks, resulting in significant performance improvements. Last week, I submitted a paper about an interprocedural extension to BBV. This extends on the original work we did by generalizing the technique to propagate type information through function calls, about function parameters and return types as well.
The improvements are quite striking. We’re now able to eliminate 94.3% of dynamic type tests on average, and we eliminate more than 80% of type tests on every benchmark. To put things in perspective, I decided to compare this result with what’s achievable using a static type analysis. I devised a scheme to give me an upper bound on the number of type tests a static analysis could possibly eliminate. First, execute all the benchmarks and record the result of each type tests. Then, re-execute the benchmarks with the type tests that always evaluate to the same result removed. This is equivalent to using a static type analysis with access to “perfect” information about which type tests are going to be redundant. The resuls of this experiment are shown in the graph below:
I was very pleased when I first saw these results. The “perfect” static analysis eliminates, on average, 91.7% of type tests, which is less than what we achieve with interprocedural BBV. You might be wondering how this is possible, how BBV can possibly eliminate more type tests than what should be an upper bound on the number of type tests that can be eliminated. The main point is that the analysis is just an oracle that tells us whether any given type test is going to be redundant and safe to eliminate or not. In contrast, BBV has the power to selectively duplicate sections of code, which makes it possible to eliminate even more type tests.
The main reason that code duplication (or versioning), is useful, is that it allows BBV to separate out contextual information which wasn’t present in the original untransformed program. If you want a simple example, think of a loop where some variable x is an integer in the first iteration, and then becomes a string in every subsequent iteration. A traditional type analysis will see that this variable could be either an integer or a string, and conclude that we don’t know what type this variable will have at run time. In contrast, BBV might be able to unroll the first iteration of the loop, and know that it will be integer in this first iteration, and a string in every other iteration, thus eliminating all type tests on the variable x.
There are interesting implications to the results obtained with BBV, in my opinion. I was recently talking to someone at Facebook about HHVM, their virtual machine for PHP and Hack. They were telling me that Hack has gradual typing, and that this information isn’t yet used to optimize code in HHVM. Based on the results I got, I would say that there is probably no real need to type-annotate code in order to improve performance. Gradual typing can be useful for documentation, tools and safety, but it doesn’t really offer performance advantages. BBV can already eliminate over 94% of type tests on average, and this is only the beginning, there are still many easy ways to further improve upon these results. Alternatively, flipping what I just said on its head, if a JIT compiler can known the types of most variables at code generation time, the type assertions introduced by gradual typing can be implemented at little to no cost.
From → Grad studies, Higgs
Is tcl/tk JIT-compiled? Can you point me to some specific source code?
> Is tcl/tk JIT-compiled?
Yes, into a bytecode representation that is executed by the execution engine.
> Can you point me to some specific source code?
You can find the source distro bundles from this page http://www.tcl.tk/software/tcltk/, however as far as pointing you to a specific file, that I can not do. Several of the core maintainers do hang out in the Usenet group comp.lang.tcl and so if you were to post specific source questions there they would likely respond with more useful answers than I can.
Nice result. The biggest performance problem of type tags isn’t the checking, but the tagging and pointer chasing. So there might be bigger performance gains possible yet. Do you have any ideas on how to do this with BBV?
My implementation does unboxing of local variables automatically and stores object properties unboxed. Pointer-chasing, I think this is an unsolved problem in dynamic languages. You would need something like automatic object inlining. People have worked on it, there are a few publications on the topic, but AFAIK, no major compiler does it. It’s a problem people have paid no attention to.
Have Static Languages Won? | Pointers Gone Wild
Dualismus hardwaru a softwaru, strojů a virtuálních strojů | Funkcionálně.cz
ZetaVM, my new compiler project | Pointers Gone Wild
Leave a Reply Cancel reply
Enter your comment here...
Fill in your details below or click an icon to log in:
Email (required) (Address never made public)
You are commenting using your WordPress.com account. ( Log Out /  Change )
You are commenting using your Twitter account. ( Log Out /  Change )
You are commenting using your Facebook account. ( Log Out /  Change )
Notify me of new comments via email.
Notify me of new posts via email.
« There’s Too Many Programming Languages!
All Hope is Not Lost for Flying Cars »
Typed vs Untyped Virtual Machines
Minimalism in Programming Language Design
Democracy, Dictatorships and Access to Information
Code that Doesn’t Rot
The Internet Changed My Life
What’s Could You Use Tesla Bot For?
NoiseCraft: a Browser-Based Visual Programming Language for Sound & Music
Art Artificial Intelligence Artificial Life Assembly Biology Compilers Creativity D Language Electronics Future Game Development Genetic Algorithms Grad studies Graphics Higgs JavaScript Microcontrollers Microprocessors Music Programming Programming Languages Psychology Rant Robotics Tachyon Technology Uncategorized work x86 Zeta
Archives Select Month June 2022  (1) May 2022  (1) March 2022  (1) February 2022  (2) January 2022  (2) December 2021  (1) June 2021  (1) February 2021  (2) December 2020  (1) September 2020  (1) January 2020  (1) November 2019  (2) October 2019  (2) June 2019  (1) January 2019  (1) December 2018  (1) May 2018  (2) February 2018  (1) January 2018  (1) December 2017  (1) October 2017  (1) June 2017  (1) April 2017  (1) January 2017  (1) December 2016  (1) November 2016  (2) September 2016  (2) May 2016  (1) March 2016  (1) February 2016  (2) January 2016  (1) November 2015  (4) October 2015  (1) September 2015  (3) August 2015  (2) July 2015  (3) June 2015  (1) May 2015  (3) April 2015  (2) March 2015  (1) February 2015  (1) December 2014  (1) November 2014  (2) October 2014  (2) September 2014  (3) July 2014  (3) May 2014  (1) April 2014  (1) March 2014  (1) February 2014  (1) January 2014  (3) December 2013  (3) October 2013  (2) September 2013  (1) August 2013  (2) July 2013  (3) June 2013  (2) May 2013  (3) March 2013  (2) February 2013  (1) January 2013  (3) December 2012  (4) November 2012  (1) October 2012  (1) September 2012  (3) July 2012  (4) June 2012  (2) May 2012  (2) April 2012  (4) March 2012  (2) February 2012  (3) January 2012  (6) December 2011  (2) November 2011  (3) October 2011  (8) September 2011  (4) August 2011  (3)