Memento mori: dynamic allocation-site-based optimizations

ABSTRACT

Languages that lack static typing are ubiquitous in the world of mobile and web applications. The rapid rise of larger applications like interactive web GUIs, games, and cryptography presents a new range of implementation challenges for modern virtual machines to close the performance gap between typed and untyped languages. While all languages can benefit from efficient automatic memory management, languages like JavaScript present extra thrill with innocent-looking but difficult features like dynamically-sized arrays, deletable properties, and prototypes. Optimizing such languages requires complex dynamic techniques with more radical object layout strategies such as dynamically evolving representations for arrays. This paper presents a general approach for gathering temporal allocation site feedback that tackles both the general problem of object lifetime estimation and improves optimization of these problematic language features. We introduce a new implementation technique where allocation mementos processed by the garbage collector and runtime system efficiently tie objects back to allocation sites in the program and dynamically estimate object lifetime, representation, and size to inform three optimizations: pretenuring, pretransitioning, and presizing. Unlike previous work on pretenuring, our system utilizes allocation mementos to achieve fully dynamic allocation-site-based pretenuring in a production system. We implement all of our techniques in V8, a high performance virtual machine for JavaScript, and demonstrate solid performance improvements across a range of benchmarks.

References

1. W. Ahn, J. Choi, T. Shull, M. J. Garzarán, and J. Torrellas. Improving javascript performance by deconstructing the type system. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, 2014.
2. A. W. Appel. Simple generational garbage collection and fast allocation. Softw. Pract. Exper., 19(2), Feb. 1989.
3. D. F. Bacon, P. Cheng, and V. T. Rajan. Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for java. SIGPLAN Not., 38(7):81–92, June 2003. ISSN 0362-1340.. URL http://doi.acm.org/ 10.1145/780731.780744.
4. S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinely, and J. E. B. Moss. Pretenuring for java. SIGPLAN Not., 36(11), Oct. 2001.
5. S. M. Blackburn, M. Hertz, K. S. McKinley, J. E. B. Moss, and T. Yang. Profile-based pretenuring. ACM Trans. Program. Lang. Syst., 29(1), Jan. 2007.
6. C. F. Bolz, L. Diekmann, and L. Tratt. Storage strategies for collections in dynamically typed languages. SIGPLAN Not., 48(10), Oct. 2013.
7. G. Chen, M. Kandemir, N. Vijaykrishnan, M. J. Irwin, B. Mathiske, and M. Wolczko. Heap compression for memory-constrained java environments. SIGPLAN Not., 38 (11):282–301, Oct. 2003. ISSN 0362-1340.. URL http: //doi.acm.org/10.1145/949343.949330.
8. P. Cheng, R. Harper, and P. Lee. Generational stack collection and profile-driven pretenuring. SIGPLAN Not., 33(5), May 1998.
9. M. De Wael, S. Marr, and W. De Meuter. Data interface + algorithms = efficient programs: Separating logic from representation to improve performance. In Proceedings of the 9th International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems PLE, ICOOOLPS ’14, 2014.
10. L. P. Deutsch and A. M. Schiffman. Efficient implementation of the smalltalk-80 system. In Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL ’84, 1984.
11. Futuremark. PeaceKeeper, 2014.
12. J. Y. Gil and I. Maman. Micro patterns in java code. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’05, 2005.
13. J. Y. Gil and Y. Shimron. Smaller footprint for java collections. In Proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications Companion, OOPSLA ’11, 2011.
14. Google Inc. V8 design, 2013. URL https://code. google.com/p/v8/design.
15. Google Inc. Octane, 2013. URL https://developers. google.com/octane.
16. I. Gouy. NBody, 2011.
17. T. L. Harris. Dynamic adaptive pre-tenuring. In Proceedings of the 2Nd International Symposium on Memory Management, ISMM ’00, 2000.
18. M. Hertz, S. M. Blackburn, J. E. B. Moss, K. S. McKinley, and D. Stefanovi´c. Generating object lifetime traces with merlin. ACM Trans. Program. Lang. Syst., 28(3), May 2006.
19. W. Huang, W. Srisa-an, and J. M. Chang. Dynamic pretenuring schemes for generational garbage collection. In Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS ’04, 2004.
20. R. Hundt. Havlak, 2014. URL https://code.google. com/p/multi-language-bench/source/ browse/trunk/src/havlak.
21. Joyent Inc. Node.js, 2014. URL http://nodejs.org/.
22. JS-X.com. WindScorpionSolve, 2005. URL http://www.js-x.com/page/javascripts\ _\_example.html?view=1068.
23. M. Jump, S. M. Blackburn, and K. S. McKinley. Dynamic object sampling for pretenuring. In Proceedings of the 4th International Symposium on Memory Management, ISMM ’04, 2004.
24. R. Macnak. ParserCombinators, 2013.
25. S. Marion, R. Jones, and C. Ryder. Decrypting the java gene pool. In Proceedings of the 6th International Symposium on Memory Management, ISMM ’07, 2007.
26. D. McNamee. Soft3d, 2008. URL www.deanmcnamee. com.
27. Mozilla. Kraken, 2013. URL https:// krakenbenchmark.mozilla.org.
28. R. Odaira, K. Ogata, K. Kawachiya, T. Onodera, and T. Nakatani. Efficient runtime tracking of allocation sites in java. In Proceedings of the 6th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE ’10, 2010.
29. J. B. Sartor, S. M. Blackburn, D. Frampton, M. Hirzel, and K. S. McKinley. Z-rays: Divide arrays and conquer speed and flexibility. SIGPLAN Not., 45(6):471–482, June 2010. ISSN 0362-1340.. URL http://doi.acm.org/10.1145/ 1809028.1806649.
30. M. L. Seidl and B. G. Zorn. Segregating heap objects by reference behavior and lifetime. SIGPLAN Not., 33(11), Oct. 1998.
31. O. Shacham, M. Vechev, and E. Yahav. Chameleon: Adaptive selection of collections. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’09, 2009.
32. J. Singer, G. Brown, M. Luján, and I. Watson. Towards intelligent analysis techniques for object pretenuring. In Proceedings of the 5th International Symposium on Principles and Practice of Programming in Java, PPPJ ’07, 2007.
33. S. Tilkov and S. Vinoski. Node.js: Using javascript to build high-performance network programs. IEEE Internet Computing, 14(6):80–83, Nov. 2010. ISSN 1089-7801.
34. D. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the First ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, SDE 1, 1984.
35. D. Ungar and F. Jackson. An adaptive tenuring policy for generation scavengers. ACM Trans. Program. Lang. Syst., 14 (1), Jan. 1992.
36. D. Ungar and R. B. Smith. Self: The power of simplicity. SIGPLAN Not., 22(12), Dec. 1987.
37. G. Xu. Resurrector: A tunable object lifetime profiling technique for optimizing real-world programs. SIGPLAN Not., 48 (10), Oct. 2013.
38. G. Xu and A. Rountev. Detecting inefficiently-used containers to avoid bloat. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’10, 2010.
39. A. Zakai. Emscripten: An llvm-to-javascript compiler. In Proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications Companion, OOPSLA ’11, pages 301–312, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0942-4.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers