Miniboxing: Improving the Speed to Code Size Tradeoff in Parametric Polymorphism Translations

Parametric polymorphism enables code reuse and type safety. Underneath the uniform interface exposed to programmers, however, its low level implementation has to cope with inherently non-uniform data: value types of different sizes and semantics (bytes, integers, floating point numbers) and reference types (pointers to heap objects). On the Java Virtual Machine, parametric polymorphism is currently translated to bytecode using two competing approaches: homogeneous and heterogeneous. Homogeneous translation requires boxing, and thus introduces indirect access delays. Heterogeneous translation duplicates and adapts code for each value type individually, producing more bytecode. Therefore bytecode speed and size are at odds with each other. This paper proposes a novel translation that significantly reduces the bytecode size without affecting the execution speed. The key insight is that larger value types (such as integers) can hold smaller ones (such as bytes) thus reducing the duplication necessary in heterogeneous translations. In our implementation, on the Scala compiler, we encode all primitive value types in long integers. The resulting bytecode approaches the performance of monomorphic code, matches the performance of the heterogeneous translation and obtains speedups of up to 22x over the homogeneous translation, all with modest increases in size.

Published in:
Proceedings of the ACM SIGPLAN 2013 Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA'13)
Presented at:
ACM SIGPLAN 2013 Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA'13), Indianapolis, Indiana, USA, October 26-31, 2013

 Record created 2013-08-11, last modified 2018-03-17

Publisher's version:
Download fulltextPDF
Download fulltextPNG
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)