Doctoral thesis : Design and Implementation of Thread-Level Speculation in JavaScript Engines

[ PDF ] [ presentation ]

The following papers are included in this thesis

Paper 1

J.K. Martinsen and H. Grahn, "A Methodology for Evaluating JavaScript Execution Behavior in Interactive Web Applications", to appear in proceding of the 9th ACS/IEEE International Conference on Computer Systems And Applications (AICCSA 2011), December 2011, Sharm El-Sheikh, Egypt

Abstract

JavaScript has gone from being a mechanism forproviding dynamic web pages to an important component ofmany web applications. Currently one of the most popular typeof web applications is so-called social networks, e.g., Facebook, Twitter, and MySpace. However, the workload and execution behavior of JavaScript in this context have not been fully exploredor understood.In this paper we present a methodology for characterizing the JavaScript execution behavior in interactive web applicationsusing deterministic execution of use cases. Then, we apply this methodology to evaluate a set of social network applications and compare their behavior to a set of established JavaScript benchmarks. Our results confirm previous studies that the execution behavior of social networks differ from established benchmarks. In addition, we identify one novel difference not published before, i.e., the use of anonymous functions in webapplications.

PDF ][ bibtex ][ conference ]

Paper 2

J.K Martinsen, H. Grahn, and A. Isberg, "Evaluating four aspects of JavaScript execution behavior in benchmarks and web applications", Research Report No. 2011:03, Blekinge Institute of Technology, Sweden, July 2011, ISSN: 1103-1581.

A shorter version is published in the proceeding of the 11th International conference on Web Engineering (ICWE 2011), Lecture Notes in Computer Science No. 6757, paged 399-402, June 2011, Cypres

Abstract

JavaScript is a dynamically typed and object-based scripting language with runtime evaluation. It has emerged as an important language for client-side computation of web applications. Previous studies have shown differences in behavior between established JavaScript benchmarks and real-world web applications. However, there still remain several important aspects to explore.
In this study, we compare the JavaScript execution behavior of four application classes, i.e., four established JavaScript benchmark suites, the first pages of the top 100 sites on the Alexa list, 22 different use cases for Facebook, Twitter, and Blogger, and finally, demo applications for the
emerging HTML5 standard. Our results extend previous studies by identifying the importance of anonymous and eval functions, showing that just-in-time compilation often decreases the performance of real-world web applications, and a detailed bytecode instruction mix evaluation.

PDF ][ bibtex ][ conference ][ poster ]

Paper 3

J.K. Martinsen and H. Grahn, "Thread Level Speculation as an optimization technique in Web Applications for embedded mobile devices - Initial Results", appeared in proceeding of the 6th IEEE International Symposium on Industrial Embedded Systems (SIES'11), pp. 83-86, June 2011, Västerås, Sweden.

Abstract

Web Applications have become increasingly popular as they allow developers to use an uniform platform for user interactions. The dynamic programming language JavaScript used in most Web Applications has performance penalties, that have been addressed by traditional optimization techniques. We have found that while the performance gain of such techniques are positive for a set of established benchmarks, it often fails to improve the performance of real-life Web Applications. We suggest Thread-Level Speculation (TLS) at the JavaScript function level to automatically extract parallelism to gain performance. There have been multiple TLS proposals in both hardware and software, but little work has been done within JavaScript. Currently we are implementing our TLS ideas in a state-of-the-art JavaScript engine targeted for embedded mobile devices

PDF ][ bibtex ][ workshop ][ poster ]

Paper 4

J.K. Martinsen, H. Grahn, and A. Isberg, "Enhancing JavaScript Performance in Web Applications Using Speculation", IEEE Internet Computing - special issue on "Virtualization", 17(2):10-19, March/April 2013.

Abstract

JavaScript lets developers provide client-side interactivity in Web applications, but because it is sequential, it can't take advantage of multicore processors. Thread-level speculation (TLS) addresses this issue by enabling the speculation of JavaScript function calls and thus exploits the parallel performance potential multicore processors provide. The authors implemented TLS in the Squirrelfish JavaScript engine, which is part of the WebKit browser environment. They evaluate their approach using 15 popular Web applications on an eight-core computer, and show significant speed-ups without any modifications to the JavaScript source code.

[ PDF ] [ Open access ] [ bibtex ] [ journal ]

Paper 5

J.K. Martinsen, H. Grahn, and A. Isberg, "Heuristics for Thread-Level Speculation in Web Applications", IEEE Computer Architecture Letters, Vol. XX, No. YY, pp. XX-YY, doi 10.1109/L-CA.2013.26. (published on-line 20 November 2013)

Abstract

JavaScript is a sequential programming language, and Thread-Level Speculation has been proposed to dynamically extract parallelism in order to take advantage of parallel hardware. In previous work, we have showed significant speed-ups with a simple on/off speculation heuristic. In this paper, we propose and evaluate three heuristics for dynamically adapt the speculation: a 2-bit heuristic, an exponential heuristic, and a combination of these two. Our results show that the combined heuristic is able to both increase the number of successful speculations and decrease the execution time for 15 popular web applications.

[ PDF ] [ bibtex ] [ journal ]

Paper 6

J.K. Martinsen, H. Grahn, and A. Isberg, ”The Effect of Parameter Tuning in Thread-
Level Speculation in JavaScript Engines”, (revised version resubmitted)

Abstract

JavaScript is a sequential programming language that has a large potential for parallel execution in web applications. Thread-Level Speculation has been suggested to take advantage of this, but it has a large memory overhead. In this paper, we evaluate the effects of tuning various parameters for Thread-Level Speculation. Our results indicate that 32--128 MB memory, 16 threads, and a speculation depth of 4--16 levels are enough to reach most of the performance increase, and that nested speculation is necessary in order to archive a high Thread-Level Speculation performance in web applications.

[ PDF ] [ bibtex ] [ journal ]

Paper 7

J.K. Martinsen, H. Grahn, A. Isberg, and H.Sundström, "Reducing Memory in Software-Based Thread-Level Speculation for JavaScript Virtual Machine Execution of Web Applications", submitted for publication and patent filed

Abstract

Thread-Level Speculation has been used to take advantage of multicore processors in virtual execution environments for the sequential JavaScript scripting language. While the results are promising the memory overhead has so far been high. In this paper, we make the following contributions: (i) We propose to reduce memory usage by limiting the checkpoint depth, (ii) we present an in-depth study of the effects of limiting the checkpoint depth in Thread-Level Speculation, and (iii) we propose an adaptive heuristic to dynamically adjust the number of checkpoints. We evaluate our techniques using 15 web applications on an 8-core computer. The results show that we reduce the memory overhead for Thread-Level Speculation by over 90% as compared to storing all checkpoints. At the same time, the performance is often better than when we store all checkpoints and at worst 4% slower.

[ PDF ] [ bibtex ] [ conference ]

Paper 8

J.K. Martinsen, H. Grahn, and A. Isberg, "Combining Thread-Level Speculation and Just-In-Time Compilation in Google’s V8 JavaScript engine", submitted for publication

Abstract

Thread-Level Speculation (TLS) can be used to take advantage of multicore architectures 
for JavaScript in web applications. We extend previous studies with these main contributions; we implement TLS in the state-of-the-art JIT-enabled JavaScript engine V8 and the Chromium web browser both from Google instead of using an interpreted JavaScript engine. We evaluate the TLS+JIT combination on 15 very popular web applications, 20 HTML5 demos from the JS1K competition, and 4 Google Maps use-cases. The performance is evaluated on 2, 4, and 8 cores. The results clearly show that it is possible to successfully combine Thread-Level Speculation and Just-in-time compilation (TLS+JIT). This makes it possible to take advantage of multicore architectures for web applications while hiding the details of parallel programming from the programmer of web applications. Further, our results show an average speedup for the TLS+JIT combination by a factor of almost 3 on 4 cores and over 4 on 8 cores, without changing any of the JavaScript source code.

PDF ] [ bibtex ] [ journal ]

Paper 9

J.K. Martinsen, H. Grahn, A. Isberg and S. Drincic "Performance and Power Usage of Thread-Level Speculation in the V8 JavaScript Engine", submitted for publication

Abstract

Thread-Level Speculation can exploit parallelism in JavaScript for web applications with a significant speedup. So far all the measurements have been made on an x86 based workstation with a dual quadcore processor. In this paper, we measure the effects of Thread-Level Speculation on a Sony Xperia Z1 smartphone with a quadcore processor. We measure both the execution time and the power usage on a large number of web applications, the Google maps application and on HTML5 applications. We show that we are able to significantly reduce the execution time, and perhaps equally important on devices with a limitied amount of battery, we show that we reduce the power usage.

[ PDF ] [ bibtex ] [ journal ]

The following papers are related but not included in this thesis

Paper 10

J.K. Martinsen and H. Grahn "Thread-Level Speculation for Web Applications", appeared in proceeding of the Second Swedish Workshop on Multi-Core Computing (MCC-09), pages 80-88, November 2009, Uppsala, Sweden.

Abstract

Thread Level Speculation (TLS) has been suggested as a mean to automatically (or semi-automatically) extract parallelism from sequential programs. While there have been multiple attempts both in hardware and software to implement real time TLS, to the best of our knowledge all attempts have so far been on a byte code level or with statically typed languages.
In this study, we examine the potential of TLS for
Web Applications, using the popular scripting language JavaScript(JS).We have chosen to execute the programs by traversing their parse trees, taking advantage of information
from the programming language that are normally lost when compiled to, e.g., byte code.
We have performed a test where we automatically have
divided the execution of the parsing tree among 1, 2, 4, and 8 cores for four benchmark programs. We have found that this approach has a small number of rollbacks (i.e. error correction when speculation fails) and significantly increases the performance of our benchmarks.

[ PDF ] [ bibtex ] [ workshop ]

Paper 11

J.K. Martinsen and H. Grahn "A Comparative Evaluation of the Execution Behavior of JavaScript Benchmarks and Real-World Web Applications", appeared in poster proceeding of the 28th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance-2010), pages 27-28, November 2010, Namur, Belgium. (poster presentation)

Abstract

In this study, we argue that the execution behavior of the current JavaScript benchmarks differs from the behavior of real-world Web Applications. We have compared the first 100 Web Applications in the Alexa top-sites list and 5 Facebook use cases, against three established JavaScript benchmark suites, i.e., Dromaeo, SunSpider, and V8. Our measurements indicate that the JavaScript eval function is important in most Web Applications, the scripts associated with Web Applications may change between page visits to the same page, anonymous functions are used more extensively for in Web Applications, and the workload of Web Applications often differ significantly from the workload found in many of the benchmarks.

[ PDF ] [ bibtex ] [ conference ] [ poster ]

Paper 12

J.K. Martinsen, H. Grahn, and A. Isberg,, "A Comparative Evaluation of JavaScript Execution Behavior", appeared in proceeding of the 11th Int'l Conference on Web Engineering (ICWE 2011), Lecture Notes in Computer Science No. 6757, pp. 399-402, June 2011, Paphos, Cyprus.

Abstract

JavaScript is a dynamically typed, object-based scripting language with runtime evaluation. It has emerged as an important language for client-side computation of web applications. Previous studies indicate some differences in execution behavior between established benchmarks and real-world web applications. Our study extends previous studies by showing some consequences of these differences. We compare the execution behavior of four application classes, i.e., four JavaScript benchmark suites, the first pages of the Alexa top-100 web sites, 22 use cases for three social networks, and demo applications for the emerging HTML5 standard. Our results indicate that just-in-time compilation often increases the execution time for web applications,
and that there are large differences in the execution behavior between benchmarks and web applications at the bytecode level.

[ PDF ][ bibtex ][ conference ]

Paper 13

J.K. Martinsen and H. Grahn, "An alternative optimization technique for JavaScript engines", appeared in proceeding of the Third Swedish Workshop on Multi-Core Computing (MCC-10), pages 155-160, November 2010, Göteborg, Sweden.

Abstract

Thread-Level Speculation at function level has been suggested as a method to automatically (or semi-automatically) extract parallelism from sequential programs. While there have been multiple implementations in both hardware and software, little work has been done in the context of dynamic programming languages such as JavaScript. In this paper we evaluate the effects of a simple Thread-Level Speculation approach, implemented on top of the Rhino1 7R2 JavaScript engine. The evalauation is done using the well known JavaScript benchmark suite V8. More specifically, we have measured the effects of our null return value prediction approach for function calls, conflicts with variables in a global scope, and the effects on the execution time. The results show that our strategy to speculate on return values is successful, that conflicts with global variables occur, and for several applications are the execution time improved, while the performance decrease for some applications due to speculation overhead.

[ PDF ][ bibtex ][ workshop ]

Paper 14

J.K. Martinsen, H. Grahn, and A. Isberg, "The Effect of Thread-Level Speculation on a Set of Well-known Web Applications", appeared in proceeding of the Fourth Swedish Workshop on Multi-Core Computing (MCC-11), pages 57-62, November 2011, Linköping, Sweden.

Abstract

Previous studies have shown that there are large differences between the workload of established JavaScript benchmarks and popular Web Applications. It has also been shown that popular optimization techniques, such as just-in-time compilation, many times degrade the performance of Web Applications. Further, since JavaScript is a sequential language it cannot take advantage of multicore processors. In this paper, we propose to use Thread-Level Speculation (TLS) as an alternative optimization technique for Web Applications written in JavaScript. Our TLS approach is based on speculation at the function level. We have implemented TLS inWebKit, a state-of-the-art web browser and JavaScript engine. Our results show speedups between 2 and 8 on eight cores for seven popular Web Applications, without any JavaScript source code changes at all. The results also show few roll-backs and the additional memory requirements for our speculation is up to 17.8 MB for the studied Web Applications.

[ PDF ][ bibtex ][ workshop ]

Paper 15

J.K. Martinsen, H. Grahn, and A. Isberg, "A Limit Study of Thread-Level Speculation in JavaScript Engines - Initial Results", appeared in proceeding of the Fifth Swedish Workshop on Multi-Core Computing (MCC-12), pages 75-82, November 2012, Stockholm, Sweden.

Abstract

JavaScript is a programming language for interactive clientside functionalities in web applications. It is a sequential programming language, so it cannot take advantage of multicore processors. Previously Thread-Level Speculation has been used to take advantage of multicore processors for JavaScript execution in web applications with promising results execution time wise, but with a large memory overhead. In this study we have evaluated the effects of limiting the amount of memory, the number of threads and the depth of speculation in Thread-Level Speculation. Our results indicate that we can tune these parameters to improve execution time and reduce the memory overhead.

[ PDF ][ bibtex ][ workshop ]

Paper 16

J.K. Martinsen, H. Grahn, and A. Isberg, "Preliminary Results of Combining Thread-Level Speculation and Just-in-Time Compilation in Google's V8", appeared in proceeding of the Sixth Swedish Workshop on Multi-Core Computing (MCC-13), pages 37-40, November 2013, Halmstad, Sweden

Abstract

We present the first implementation of Thread-Level Speculation in combination with Just-in-time compilation. The implementation is done in Google’s V8, a well-known JavaScript engine, and evaluated on 15 popular web application executing on 2, 4, and 8 core computers. Our results show an average speedup of 1.55 on 4 cores, without any JavaScripts code modifications. Further, we have found that the Just-in-time compilation time is significant, and that most functions are lazely compiled (approximately 80%). Further, V8 contains features that are advantageous in Thread-Level Speculation.

[ PDF ][ bibtex ][ workshop ]

Paper 17

J.K. Martinsen "Evaluating JavaScript Execution Behavior and Improving the Performance of Web Applications with Thread-Level Speculation", Licentiate thesis, December 2011, Blekinge, Sweden

Abstract

This thesis addresses two issues: (i) The execution behavior of JavaScript in established benchmarks and in real-world Web Applications and (ii) whether Thread-Level Speculation is a suitable technique for taking advantage of multicore systems in Web Applications written in JavasScript.

The first key result is that JavaScript execution behavior by the benchmarks and the JavaScript execution behavior by the Web Applications differ in several important aspects. For instance Web Applications often use function types such as anonymous and eval functions. Our results also show that just-in-time compilation often increases the execution time of Web Applications, despite that just-in-time compilation decreases the execution time for most of the benchmarks.

The second key result is that our implementation of Thread-Level Speculation shows that it can be used to take advantage of multicore systems for Web Applications. We have measured the effect on the execution time for a set of Web Applications, and found that we are able to reduce JavaScript execution time more than 8 times compared to the sequential version on a dual quad core computer. For our use-cases we found that we used between 1.1 and 33.0 MB to store information associated with speculation. 

[ PDF ][ bibtex ][ defence ]

Paper 18

J.K. Martinsen, H. Grahn, and A. Isberg, "An Argument for Thread-Level Speculation and Just-in-Time Compilation in the Google's V8 JavaScript Engine", to appeared in proceeding of the Computing Frontier 2014 conference, May 2014, Cagliari, Italy

Abstract

Thread-Level Speculation can be used to take advantage of multicore architectures for web applications. We have implemented Thread-Level Speculation in the state-of-the-art JavaScript engine V8 instead of using an interpreted JavaScript engine. We evaluate the implementation with  the Chromium web browser on 15 popular web applications for 2, 4, and 8 cores. The results show that it is beneficial to combine Thread-Level Speculation and Just-in-time compilation and that it is possible to take advantage of multicore architectures while hiding the details of parallel programming from the programmer of web applications.

PDF ][ bibtex ][ conference ]

Redigera
Share Dela