Efficient floating-point number handling for dynamically typed scripting languages

ABSTRACT

Typical implementations of dynamically typed languages treat floating-point numbers, or flonums, in a "boxed" form, since those numbers don't fit in a natural machine word if a few bits in the word are reserved for type tags. The naïve implementations allocate every instance of flonums in the heap, thus incur large overhead on numerically intensive computations. Compile-time type inference could eliminate boxing of some flonums, but it would be costly for highly dynamic scripting languages, in which a compiler runs every time a script is executed.

We suggest two modified stack machine architectures that avoid heap allocations for most intermediate flonums, and can be relatively easily retrofitted to existing stack-based VMs. The basic idea is to have an arena for intermediate flonums that works as a part of extended stack or as a nursery. Like typical VMs, flonums are tagged pointers that point to native floating-point numbers, but when a new flonum is pushed onto the VM's stack, it actually points to a native floating-point number placed in the arena. Heap allocation only occurs when the flonum pointer needs to be moved to the heap. The two architectures differ in the strategies to manage the arena.

We implemented and evaluated those strategies in a Scheme implementation"Gauche." Both strategies showed 30%-140% speed up in numerical computation intensive benchmarks, eliminating 99.8% of heap-allocation of intermediate flonums, with little penalty in non-numerical benchmarks. Profiling showed the speed improvement came from the elimination of flonum allocation and garbage collection.

REFERENCES

• 1: H. G. Baker. Cons should not cons its arguments, part ii: Cheney on the m.t.a. ACM Sigplan Notices, 30(9):17--20, September 1995.
• 2: C. Chambers, D. Ungar, and E. Lee. An efficient implementation of self a dynamically-typed object-oriented language based on prototypes. In OOPSLA '89: Conference proceedings on Object-oriented programming systems, languages and applications, pages 49--70, New York, NY, USA, 1989. ACM.
• 3: R. J. Fateman, K. A. Broughan, D. K. Willcock, and D. Rettig. Fast floating-point processing in common lisp. ACM Trans. on Mathematical Software, 21(1):26--62, March 1995.
• 4: R. Ierusalimschy, L. H. de Figueiredo, and W. Celes. The implementation of lua 5.0. Journal of Universal Computer Science, 11(7):1159--1176, 2005.
• 5: S. Kawai. Gluing things together - scheme in the real-time CG content production. In Proceedings of ILC2002, the International Lisp Conference, pages 342--348, 2002.
• 6: R. Kelsey. Tail-recursive stack disciplines for an interpreter. NU-CCS-93-03, March 1993.
• 7: B. Lewis. An on-the-fly bytecode compiler for tcl. In Proc. 4th Intl. Tcl/Tk Workshop, pages 103--114. USENIX, 1996.
• 8: T. Lindahl and K. Sagonas. Unboxed compilation of floating point arithmetic in a dynamically typed language environment. In Implementation of Functional Languages: Proc. of the 14th International Workshop number 2670 in LNCS, pages 134--149. Springer, September 2002.
• 9: K. Sasada. A lightweight representation of floating-point numbers on ruby interpreter. In Proceedings of the workshop of programming and programming languages (PPL2008), Sendai, Japan, March 2008.
• 10: K. Sasada, Y. Matsumoto, A. Maeda, and M. Namiki. YARV: Yet another rubyvm. the implementation and evaluation. IPSJ Transaction on Programming, 47(SIG 2 (PRO 28)):57--73, February 2006.
• 11: M. Serrano and M. Feeley. Storage use analysis and its applications. In Proc. ICFP '96: the first ACM SIGPLAN international conference on Functional programming, pages 50--61, 1996.
• 12: G. L. Steele, editor. Common Lisp: the Language, 2nd Edition. Digital Press, 1990.
• 13: K. Umemura. Floating-point number lisp. Software---Practice and Expecience, 21(10):1015--1026, October 1991.
• 14: W. F. Wong. Optimizing floating point operations in scheme. Computer Languages, 25(2):89--102, 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Experimentation, Languages