Lua is a well-known scripting language, popular among many programmers, most notably in the gaming industry. The only data-structuring mechanism in Lua is an associative array called table. Lua 5.0, introduced an implementation with hybrid tables that combine both a hash table and a dynamically growing array. All this is hidden from the user, who uses just simple interface for the tables. In this talk we will examine the implementation and performance of Lua’s Tables from a theoretical point of view. We consider various worst-case and probabilistic scenarios. Interestingly, we uncover some problematic situations for a simple, yet unusual, probabilistic model: the cost of performing T such operations is proved to be at least of order Ω(T log T) with high probability, instead of O(T).
Joint work with Conrado Martínez and Cyril Nicaud.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne