Which is hypothetically faster?

[Jasoco]

The following two pieces of code are functionally identical, right? Both take a set of numbers and return the lowest of the set.

Code: Select all

function lowest(v1, v2, v3)
	if v1 < v2 and v1 < v3 then return v1 elseif v2 < v1 and v2 < v3 then return v2 else return v3 end
end

Code: Select all

return math.min(v1, v2, v3)

But is one faster than the other? Especially if performing the same call hundreds of times per frame?

Just curious as for a while I had created my own function (above) and only today learned that math.min and math.max can accept more than two variables. So I thought to myself, why not use the proper math functions.

Or is it a moot point really?

[verilog]

Hi Jasoco,
I haven't carried out any formal test, but according to this (test 4). math.min/max are somewhat slower than the pure comparison approach.

[rexjericho]

math.min() does seem to run slightly slower than your lowest() function. One advantage of the lowest() function is that it knows exactly how many values it is given, whereas math.min() dies not, and must loop through each number to find the minimum. For me, the lowest() function takes about 95% of the time to calculate the minimum than the math.min() function takes.

Update!: It seems that if you localize the math.min() function, it runs even faster than the lowest function. math.min() now runs at about 95% of the time lowest() takes.

Code: Select all

function lowest(v1, v2, v3)
   if v1 < v2 and v1 < v3 then return v1 elseif v2 < v1 and v2 < v3 then return v2 else return v3 end
end

local n = 1000000
local x = 0
local min = math.min

-- time lowest() function
x = os.clock()
for i=0,n do 
  lowest(math.random(-100,100), math.random(-100,100), math.random(-100,100))
end
print(string.format("lowest() elapsed time: %.2f", os.clock() - x))

-- time math.min() function
x = os.clock()
for i=0,n do 
  min(math.random(-100,100), math.random(-100,100), math.random(-100,100))
end
print(string.format("math.min() elapsed time: %.2f", os.clock() - x))

[Inny]

So, a bit of a primer as to how Lua works, which I'm kind of paraphrasing Roberto from the book Lua Gems. Local is fastest, because it's stored in one of Lua's registers. There's about 200 of them, so don't overuse the local keyword, or keep your functions small. _G is in an implied register, so looking up _G and a register are equally fast. Top level libraries are contained in _G's table, so _G["math"] is slower than math being localized, because it involves a table lookup. math["min"] requires two table lookups and a register lookup. So, before we even get to the functions, lowest is doing better than math.min because of one less table lookup. Localize math.min, which a lot of people do, and the lookups get bypassed.

Now, for the real meat of why math.min is slower, is because this is how math.min is implemented:

Code: Select all

static int math_min (lua_State *L) {
  int n = lua_gettop(L);  /* number of arguments */
  lua_Number dmin = luaL_checknumber(L, 1);
  int i;
  for (i=2; i<=n; i++) {
    lua_Number d = luaL_checknumber(L, i);
    if (d < dmin)
      dmin = d;
  }
  lua_pushnumber(L, dmin);
  return 1;
}

There's a loop, and this luaL_checknumber API call is verifying the arguments. The proper lua implementation of min would be this:

Code: Select all

function min(dmin, ...)
  assert(type(dmin)=="number")
  local N = select('#', ...)
  for i = 1, N do
    local d = select(i, ...)
    assert(type(d)=="number")
    if d < dmin then dmin = d end
  end
  return dmin
end

Jasoco's lowest function is faster because it does less.

[Jasoco]

Interesting. Especially the part about localizing the math functions. Which I do now. I didn't know localizing functions like this could help so much.

Every tiny bit of speed helps when working with 3D math calculations.

[Xgoff]

function calls are somewhat expensive (especially since the standard vm doesn't inline them), so if something can be done without a function call it will probably be cheaper to do it that way. pure-lua bitwise ops would be a pretty big exception to this, though.

obviously this doesn't really apply if you're using luajit (as long as the code is jitted), in which case you should trust the compiler and just use the obvious/idiomatic way

[Robin]

Jasoco's lowest function is faster because it does less.

I thought the conclusion was that math.min is faster than lowest if localised. (My guess, because it is written in C and uses less Lua opcodes.)

In practice, it probably won't matter anyway.

[rexjericho]

My assumption that math.min is faster than lowest when localized was incorrect. During the test, I should have localized both math.min and lowest, but missed localizing the lowest function. If both are localized, lowest is still faster, just because it does less than math.min.

[Inny]

I took it upon myself to do my own test of math.min versus a simple custom min function. Here's the code:

Code: Select all

function run_test(minfn, count)
  local res
  for i = 1, count do
    res = minfn(1, 2)
  end
  assert(res==1)
end

local fns = {
  mathmin = math.min,
  my_min = function(x, y)
    if x < y then return x else return y end
  end
}

local to_test = select(1, ...) or "mathmin"
local count = select(2, ...) or 50000000
print("Testing "..to_test.." "..count)
run_test(fns[to_test], count)
print("Done.")

And here's the runs. My min function first:

Code: Select all

billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua my_min 1000000
Testing my_min 1000000
Done.

real	0m0.123s
user	0m0.120s
sys	0m0.004s
billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua my_min 10000000
Testing my_min 10000000
Done.

real	0m1.129s
user	0m1.124s
sys	0m0.000s
billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua my_min 50000000
Testing my_min 50000000
Done.

real	0m5.722s
user	0m5.708s
sys	0m0.000s

And now Math.min:

Code: Select all

billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua mathmin 1000000
Testing mathmin 1000000
Done.

real	0m0.126s
user	0m0.128s
sys	0m0.000s
billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua mathmin 10000000
Testing mathmin 10000000
Done.

real	0m1.157s
user	0m1.152s
sys	0m0.000s
billy@gizmo:~/Depot/Code/lua$ time lua profile_min.lua mathmin 50000000
Testing mathmin 50000000
Done.

real	0m5.815s
user	0m5.800s
sys	0m0.000s

My version of min appears to beat math.min, but in a photo finish it's by less than a hair on a nose. Barely worth the effort.

This is why you profile before you optimize.

[kikito]

I just added my own version of min to ginni's test:

Code: Select all

local fns = {
   ...
   min2 = function(a,b) return a < b and a or b end
}

I was expecting it to be slightly faster than the if-based implementation, since Lua's tail call should be helping.

Surprisingly, it turned out to be slower than regular math.min!

Code: Select all

➜  ~  time lua profile_min.lua min2 50000000
Testing min2 50000000
Done.
lua profile_min.lua min2 50000000  6.61s user 0.01s system 99% cpu 6.623 total
➜  ~  time lua profile_min.lua mathmin 50000000
Testing mathmin 50000000
Done.
lua profile_min.lua mathmin 50000000  6.05s user 0.00s system 99% cpu 6.056 total
➜  ~  time lua profile_min.lua my_min 50000000
Testing my_min 50000000
Done.
lua profile_min.lua my_min 50000000  5.98s user 0.00s system 99% cpu 5.982 total