CODEWITHSUNDEEP
lualua-tablemetatable
1hunch1kill
1hunch1kill

Reputation: 520

time complexity of metatable in Lua when accessing

local cls = {base = "base"}
local ins = {}
cls.__index = cls
setmetatable(ins, cls)

What is the time complexity of accesssing ins.base?

Upvotes: 2

Views: 1153

Answers (1)

Colonel Thirty Two
Colonel Thirty Two

Reputation: 26599

You can expect O(1) time complexity from the official Lua implementation.

The code for __index is roughly equivalent to this Lua code, taken from the manual:

 function gettable_event (table, key)
   local h
   if type(table) == "table" then
     local v = rawget(table, key)
     if v ~= nil then return v end
     h = metatable(table).__index
     if h == nil then return nil end
   else
     h = metatable(table).__index
     if h == nil then
       error(···)
     end
   end
   if type(h) == "function" then
     return (h(table, key))     -- call the handler
   else return h[key]           -- or repeat operation on it
   end
 end

The __index lookup itself has no loops, and since Lua tables are backed by hash tables, table lookups are usually a constant-time operation.

Upvotes: 3

Related Questions