Compact Representations for Arrays in Lua
Resumo
Several languages use a tagged representation for values, so that each value carries its own type during runtime. Lua, in particular, represents each value by a structure with two fields: A union for the values themselves and a byte with the tag. Despite its simplicity, this representation has a big drawback: Due to alignment restrictions, it typically wastes more than 40% of memory in padding. This waste is specially expensive for large arrays. In this work, we discuss alternative implementations for Lua arrays that eliminate this waste and evaluate them regarding performance, with a special focus on code overhead and memory locality. The presented data structures are quite generic, and can be used not only in the Lua interpreter, but in any program that needs arrays of tagged values.
Referências
Simon Marlow (editor). 2010. Haskell 2010 Language Report.
Free Software Foundation [n.d.]. GNU C Language Manual. 15.6 Packed Structures. Free Software Foundation. [link]
Roberto Ierusalimschy, Luiz H. de Figueiredo, andWaldemar Celes. 2005. The Implementation of Lua 5.0. Journal of Universal Computer Science 11, 7 (2005), 1159–1176. DOI: 10.3217/jucs-011-07-1159 (SBLP 2005).
Roberto Ierusalimschy, Luiz H. de Figueiredo, andWaldemar Celes. 2007. The Evolution of Lua. In HOPL III: Proceedings of the Third ACMSIGPLAN Conference on History of Programming Languages (San Diego, CA). ACM, New York, NY, 2.1–2.26. DOI: 10.1145/1238844.1238846
ISO 2000. International Standard: Programming languages — C. ISO. ISO/IEC 9899:1999(E).
Xavier Leroy, Damien Doligez, Alain Frisch, Jacques Garrigue, Didier Rémy, KC Sivaramakrishnan, and Jérôme Vouillon. 2023. The OCaml System, release 5.1. INRIA.
Robert Nystrom. 2021. Crafting Interpreters. Genever Benning, Chapter § 30.3 NaN Boxing, 590–601. ISBN 978-0-9905829-3-9.
