Local iterator functions slower than global?

[Limey]

Hello all!

Sorry for my first post being a question. I usually do a quick search and find a solution to anything i need so, never needed an account.

Since I started using Lua I've been led to believe that localizing functions is always faster, but reciently I've been creating some convenience modules and found something strange with the Lua 'iterator' functions when localized.

Some example code:

Code: Select all

local lua_pairs = pairs
local lua_ipairs = ipairs
local lua_next = next

local love_timer = love.timer

local count = 10000000

function love.load()
    local tbl1, tbl2 = { }, { }
    for i = 1, count do
        tbl1["id:" .. i] = i
        tbl2[i] = i
    end

    collectgarbage("collect")
    love_timer.sleep(2)
    print("\nPAIRS:")

    local start1 = love_timer.getTime()
    for k,v in lua_pairs(tbl1) do end
    print("\tLOCAL:", love_timer.getTime() - start1)

    local start2 = love_timer.getTime()
    for k,v in pairs(tbl1) do end
    print("\tGLOBAL:", love_timer.getTime() - start2)

    collectgarbage("collect")
    love_timer.sleep(2)
    print("\nKEYED NEXT:")

    local start3 = love_timer.getTime()
    for k,v in lua_next,tbl1 do end
    print("\tLOCAL:", love_timer.getTime() - start3)

    local start4 = love_timer.getTime()
    for k,v in next,tbl1 do end
    print("\tGLOBAL:", love_timer.getTime() - start4)

    collectgarbage("collect")
    love_timer.sleep(2)
    print("\nIPAIRS:")

    local start5 = love_timer.getTime()
    for k,v in lua_ipairs(tbl2) do end
    print("\tLOCAL:", love_timer.getTime() - start5)

    local start6 = love_timer.getTime()
    for k,v in ipairs(tbl2) do end
    print("\tGLOBAL:", love_timer.getTime() - start6)

    collectgarbage("collect")
    love_timer.sleep(2)
    print("\nINDEX NEXT:")

    local start7 = love_timer.getTime()
    for k,v in lua_next,tbl2 do end
    print("\tLOCAL:", love_timer.getTime() - start7)

    local start8 = love_timer.getTime()
    for k,v in next,tbl2 do end
    print("\tGLOBAL:", love_timer.getTime() - start8)

    collectgarbage("collect")
    love_timer.sleep(2)
    print("\nINDEX FOR:")

    local start9 = love_timer.getTime()
    for i = 1, count do local v = tbl2[i] end
    print("\tTIME:", love_timer.getTime() - start9)
end

function love.keypressed(key, code)
    if key == "escape" then
        love.event.quit()
    end
end

My results running the code above on an i7-6700K (stock):

Code: Select all

PAIRS:
    LOCAL:  1.4657853993122
    GLOBAL: 0.081412906292826

KEYED NEXT:
    LOCAL:  1.4963958139997
    GLOBAL: 0.081174023915082

IPAIRS:
    LOCAL:  0.039344312623143
    GLOBAL: 0.017881943611428

INDEX NEXT:
    LOCAL:  0.18253194889985
    GLOBAL: 0.032720755320042

INDEX FOR:
    TIME:   0.020053090527654

As you can see GLOBAL is faster than LOCAL in all cases. Now, I understand 10 million is a ridiculous number of items, but the same is true at 10k.

My results with count set to 10k:

Code: Select all

PAIRS:
    LOCAL:  0.0020962886046618
    GLOBAL: 0.00049156113527715

KEYED NEXT:
    LOCAL:  0.0020934783387929
    GLOBAL: 0.00048823980614543

IPAIRS:
    LOCAL:  0.00019698217511177
    GLOBAL: 8.4566883742809e-005

INDEX NEXT:
    LOCAL:  0.00079431594349444
    GLOBAL: 0.0001573811750859

INDEX FOR:
    TIME:   9.9640572443604e-005

So, the question is. What is causing this slowdown between local and global variables?

Note: I tried a similar test with the 'math' library and there was an obvious advantage to localization. I'm also on some nice meds right now so, i could just be having a Homer Simpson moment.

[ivan]

It might have something to do with how LuaJit optimizes these loops.
Running with vanilla Lua there is no difference between local/global pairs.
Here is an alternative version of your tests (in milliseconds):

Code: Select all

local clock = function() return love.timer.getTime()*1000 end
--local clock = function() return os.clock()*1000 end

function test(func, ...)
  collectgarbage("collect")
  local m1 = collectgarbage("count")
  local t1 = clock()
  func(...)
  local t2 = clock()
  local m2 = collectgarbage("count")
  return t2 - t1, m2 - m1
end

local tests = {}

local L_pairs = pairs
function tests.L_pairs(t)
  for k,v in L_pairs(t) do end
end

function tests.G_pairs(t)
  for k,v in pairs(t) do end
end

local L_ipairs = ipairs
function tests.L_ipairs(t)
  for k,v in L_ipairs(t) do end
end

function tests.G_ipairs(t)
  for k,v in ipairs(t) do end
end

local L_next = next
function tests.L_next(t)
  for k,v in L_next,t do end
end

function tests.G_next(t)
  for k,v in next,t do end
end

function tests.numeric(t)
  for i = 1, #t do local v = t[i] end
end

local tbl1, tbl2 = { }, { }
for i = 1, 1000000 do
  tbl1["id:" .. i] = i
  tbl2[i] = i
end

print('table')
for k, v in pairs(tests) do
  local dt, dm = test(v, tbl1)
  local res = string.format("%s  %f  %f", k, dt, dm)
  print(res)
end

print('list')
for k, v in pairs(tests) do
  local dt, dm = test(v, tbl2)
  local res = string.format("%s  %f  %f", k, dt, dm)
  print(res)
end

Generally speaking, locals provide an advantage only if you use them to avoid look-ups via the "." and [] operators:

Code: Select all

local cos = math.cos
local cos = math['cos']

The conclusion is that numerically-indexed lists are typically faster to iterate compared to using string keys.
The numeric for loop and ipairs are clearly the fastest ways to iterate tables.

[Azhukar]

http://wiki.luajit.org/Bytecode-2.0#cal ... g-handling

Note: The Lua parser heuristically determines whether pairs() or next() might be used in a loop. In this case, the JMP and the iterator call ITERC are replaced with the specialized versions ISNEXT and ITERN.

ISNEXT verifies at runtime that the iterator actually is the next() function, that the argument is a table and that the control variable is nil. Then it sets the lowest 32 bits of the slot for the control variable to zero and jumps to the iterator call, which uses this number to efficiently step through the keys of the table.

If any of the assumptions turn out to be wrong, the bytecode is despecialized at runtime back to JMP and ITERC.

Code: Select all

local a = 0 
local function dumbPairs(...)
	a = a + 1
	return pairs(...)
end

local pairs = dumbPairs

local getTime = love.timer.getTime

function love.load()
	local test = {}
	for i=1,1000000 do
		test["id:"..i] = i
	end
	local t

	t = getTime()
	for k,v in dumbPairs(test) do end
	t = getTime() - t
	print("dumpPairs:", t)

	t = getTime()
	for k,v in pairs(test) do end
	t = getTime() - t
	print("pairs:", t)

	print(a)
end

Essentially a text parser problem. If it's called pairs/next it gets optimized, otherwise not.

[zorg]

I would still test how fast localizing ipairs, pairs and next is when the locals used have the same names...

[Azhukar]

I would still test how fast localizing ipairs, pairs and next is when the locals used have the same names...

pairs() and ipairs() are called exactly once per loop, to generate the 3 variables used by the for loop. You'd save at most a single index operation on _G per loop.
next() is called each iteration, however it is passed only a single time into the for loop and then called each iteration. In other words, you'd again save only a single _G index operation per loop. Theoretically the best performance would be:

Code: Select all

local next = next
for k,v in next,t,nil do end

The localization of next in this case would have negligible effect.

[drunken_munki]

local lua_pairs = pairs
local lua_ipairs = ipairs
local lua_next = next

should be:

local pairs = pairs
local ipairs = ipairs
local next = next

Though it will botch your expirement unless you reorder the tests to be global first, then create the locals and test them together.

Either 50/50 chance the tests will be the same timings or very close in either direction, and not distorted like the results you are seeing.

Perhaps we would need to create a set of say 10 tests of 1 million iterations for each one, average the set up and we could reason which is faster. My money is still on locals, even if by a little bit.

[zorg]

pairs() and ipairs() are called exactly once per loop, to generate the 3 variables used by the for loop. You'd save at most a single index operation on _G per loop.
next() is called each iteration, however it is passed only a single time into the for loop and then called each iteration. In other words, you'd again save only a single _G index operation per loop. Theoretically the best performance would be:

Code: Select all

local next = next
for k,v in next,t,nil do end

The localization of next in this case would have negligible effect.

Well, one could still localize it to the file scope instead, or the scope just outside the loop body; there might still be some speedup, or there might be not.

[Azhukar]

To clarify, I didn't mean "localize it right before using it".

See http://wiki.luajit.org/Numerical-Comput ... ance-Guide the part about "Do not try to second-guess the JIT compiler."

[drunken_munki]

I reorganised the test, try this:

Code: Select all

local math       = math
local timer      = love.timer

local count       = 10000000
local experiments = 10

local verbose    = false
local sleep      = 0.1
local idp        = 5


--- Round double to given decimal place
-- Does not handle idp 0, use math.floor(num + 0.5)
local function roundVal(num, idp)
  local mult = 10 ^ idp
  return math.floor(num * mult + 0.5) / mult
end


function love.load()
  print("Start.")
  local tbl1, tbl2 = { }, { }
  for i = 1, count do
    tbl1["id:" .. i] = i
    tbl2[i] = i
  end
  
  local tSet = 0
  
  ----------------------------------------------------------------------------
  print("\n-- BENCHMARK, INDEX FOR -- :")
  collectgarbage("collect")
  timer.sleep(sleep)
  
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for i = 1, count do local v = tbl2[i] end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  
  ----------------------------------------------------------------------------
  print("\n-- GLOBAL -- :")
  collectgarbage("collect")
  timer.sleep(sleep)
  
  print("\t\npairs:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in pairs(tbl1) do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  -- 
  print("\t\nkeyed  next:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in next, tbl1 do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  -- 
  print("\t\niPairs:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in ipairs(tbl2) do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  -- 
  print("\t\nindex next:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in next,tbl2 do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  
  ----------------------------------------------------------------------------
  print("\n-- LOCAL -- :")
  collectgarbage("collect")
  timer.sleep(sleep)
  
  local pairs  = pairs
  local next   = next
  local ipairs = ipairs
  
  print("\t\npairs:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in pairs(tbl1) do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  --
  print("\t\nkeyed  next:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in next, tbl1 do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  -- 
  print("\t\niPairs:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in ipairs(tbl2) do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  -- 
  print("\t\nindex next:")
  tSet = 0
  for i = 1, experiments do
    local start = timer.getTime()
    for k,v in next,tbl2 do end
    local t = timer.getTime() - start
    tSet = tSet + t
    if verbose then print("\t #"..i, roundVal(t, idp)) end
  end
  print("\t mean", roundVal(tSet / experiments, idp))
  
  
  print("\nDone.")
end

function love.keypressed(key, code)
  if key == "escape" then
    love.event.quit()
  end
end

[Limey]

Thanks for the replies.

So, after shuffling a few things around and renaming the variables to match the function name, I got the results i was expecting the first time.

Results at 10 million count.

Code: Select all

GLOBAL:
    PAIRS:  0.13402068451978
    NEXT:   0.08351737074554
    IPAIRS: 0.0078097935765982

LOCAL:
    PAIRS:  0.11848362046294
    NEXT:   0.081355676753446
    IPAIRS: 0.0085062570869923

I had no idea variable name mattered when localizing. Is this also true for other functions, like, 'math.cos' var name should be 'cos' or, 'love.graphics.draw' var name should be 'draw'?

Thanks for the help.