A Probabilistic Model Revealing Shortcomings in Lua's Hybrid Tables

08/29/2022
by   Conrado Martínez, et al.
0

Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua, is an associative array called a table. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hash table and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable. All this is transparent to the user, which has a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua's tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p>1/2 and delete a key with probability 1-p: the cost of performing T such operations is proved to be Ω(Tlog T) with high probability, instead of linear in T.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset