Optimizing record data structures in Racket

ABSTRACT

Built-in data structures are a key contributor to the performance of dynamic languages. Record data structures, or records, are one of the common advanced, but not easily optimizable built-in data structures supported by those languages. Records may be used in an object-oriented fashion or to implement object orientation itself.

In this paper, we analyze how records are used in different applications in the Scheme dialect Racket. Based on the data obtained, we suggest the application of existing optimization techniques for records and devise a new one for immutable boolean fields. Most of them can be applied to a wide range of record implementations in dynamic languages. We apply these optimizations to records in Pycket, an implementation of Racket. With one exception, microbenchmarks show a two-to ten-fold speed-up of our implementation over plain Racket.

References

1. D. Ancona, M. Ancona, A. Cuni, and N. Matsakis. "RPython: A Step Towards Reconciling Dynamically and Statically Typed OO Languages". In: Proc. of DLS 2007. DLS '07. Montreal, Quebec, Canada: ACM, 2007, pp. 53--64.
2. D. F. Bacon, S. J. Fink, and D. Grove. "Space- and timeefficient implementation of the Java object model". In: ECOOP 2002 --- Object-Oriented Programming. Ed. by B. Magnusson. Vol. 2374. LNCS. Springer, 2002, pp. 111--132.
3. S. Bauman, C. F. Bolz, R. Hirschfeld, V. Krilichev, T. Pape, J. Siek, and S. Tobin-Hochstadt. "Pycket: A Tracing JIT For a Functional Language". In: Proc. of ICFP 2015. ICFP '15. Vancouver, British Columbia, Canada: ACM, 2015.
4. C. F. Bolz, A. Cuni, M. Fijalkowski, and A. Rigo. "Tracing the meta-level: PyPy's tracing JIT compiler". In: Proc. of ICOOOLPS 2009. ACM. 2009, pp. 18--25.
5. C. F. Bolz, L. Diekmann, and L. Tratt. "Storage strategies for collections in dynamically typed languages". In: Proc. of OOPSLA 2013. ACM. 2013, pp. 167--182.
6. C. F. Bolz, A. Kuhn, A. Lienhard, N. D. Matsakis, O. Nierstrasz, L. Renggli, A. Rigo, and T. Verwaest. "Back to the future in one week---implementing a Smalltalk VM in PyPy". In: Self-Sustaining Systems. Springer, 2008, pp. 123--139.
7. C. F. Bolz, M. Leuschel, and D. Schneider. "Towards a Jitting VM for Prolog Execution". In: Proc. of PPDP 2010. PPDP '10. Hagenberg, Austria: ACM, 2010, pp. 99--108.
8. C. F. Bolz, T. Pape, J. Siek, and S. Tobin-Hochstadt. "Metatracing makes a fast Racket". In: Workshop on Dynamic Languages and Applications. 2014.
9. B. Cérat and M. Feeley. "Structure Vectors and their Implementation". In: Scheme and Functional Programming Workshop. 2014.
10. A. C. Davison and D. V. Hinkley. In: Bootstrap Methods and Their Application. Cambridge, 1997. Chap. 5.
11. M. Felleisen and D. P. Friedman. Control Operators, the SECD-machine, and the λ-calculus. Indiana University, Computer Science Department, 1986.
12. M. Flatt. Reference: Racket. Tech. rep. PLT-TR-2010-1. PLT Design Inc., 2010.
13. M. Flatt, R. Findler, and M. Felleisen. "Scheme with Classes, Mixins, and Traits". In: Programming Languages and Systems. Ed. by N. Kobayashi. Vol. 4279. LNCS. Springer, 2006, pp. 270--289.
14. D. Ingalls, T. Kaehler, J. Maloney, S. Wallace, and A. Kay. "Back to the future: the story of Squeak, a practical Smalltalk written in itself". In: ACM SIGPLAN Notices. Vol. 32. 10. ACM. 1997, pp. 318--326.
15. A. W. Keep and R. Dybvig. "A run-time representation of scheme record types". In: J Funct Program 24 (Special Issue 06 2014), pp. 675--716.
16. R. Mitchell, J. McKim, and B. Meyer. Design by contract, by example. Addison Wesley, 2001.
17. M. E. Noth. "Exploding Java Objects for Performance". PhD thesis. University of Washington, 2003.
18. T. Pape, C. F. Bolz, and R. Hirschfeld. "Adaptive Just-in-time Value Class Optimization: Transparent Data Structure Inlining for Fast Execution". In: Proc. of SAC 2015. Vol. 2. SAC '15. Salamanca, Spain: ACM, 2015.
19. A. Rigo and S. Pedroni. "PyPy's approach to virtual machine construction". In: Proc. of OOPSLA 2006. Portland, Oregon, USA: ACM, 2006, pp. 944--953.
20. G. J. Sussman and G. L. Steele Jr. "Scheme: A interpreter for extended lambda calculus". In: Higher-Order and Symbolic Computation 11.4 (1998).
21. V. Ureche, E. Burmako, and M. Odersky. "Late data layout: unifying data representation transformations". In: Proc. of OOPSLA 2014. ACM. 2014, pp. 397--416.
22. A. Wöß, C. Wirth, D. Bonetta, C. Seaton, H. Mössenböck, and C. Humer. "An Object Storage Model for the Truffle Language Implementation Framework". In: Proc. of PPPJ 2014. PPPJ '14. Cracow, Poland: ACM, 2014, pp. 133--144.
23. T. Würthinger, C. Wimmer, A. Wöß, L. Stadler, G. Duboscq, C. Humer, G. Richards, D. Simon, and M. Wolczko. "One VM to rule them all". In: Proc. Onward! 2013. ACM. 2013, pp. 187--204.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Record and block layout

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Just-in-time compilers

    • General programming languages

      • Language features

        • Classes and objects

        • Data types and structures