Compact Representations for Arrays in Lua

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.