Which is hypothetically faster?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
Jasoco
Inner party member
Posts: 3650
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Which is hypothetically faster?

Post by Jasoco » Wed Jan 09, 2013 2:27 am

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?

User avatar
verilog
Citizen
Posts: 97
Joined: Thu Nov 03, 2011 3:15 am
Contact:

Re: Which is hypothetically faster?

Post by verilog » Wed Jan 09, 2013 3:19 am

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
Prole
Posts: 44
Joined: Sat Dec 15, 2012 7:55 am

Re: Which is hypothetically faster?

Post by rexjericho » Wed Jan 09, 2013 3:27 am

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))

User avatar
Inny
Party member
Posts: 652
Joined: Fri Jan 30, 2009 3:41 am
Location: New York

Re: Which is hypothetically faster?

Post by Inny » Wed Jan 09, 2013 4:45 am

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.

User avatar
Jasoco
Inner party member
Posts: 3650
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Re: Which is hypothetically faster?

Post by Jasoco » Wed Jan 09, 2013 5:53 am

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.

User avatar
Xgoff
Party member
Posts: 211
Joined: Fri Nov 19, 2010 4:20 am

Re: Which is hypothetically faster?

Post by Xgoff » Wed Jan 09, 2013 6:21 am

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

User avatar
Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

Re: Which is hypothetically faster?

Post by Robin » Wed Jan 09, 2013 10:55 am

Inny wrote: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.
Help us help you: attach a .love.

rexjericho
Prole
Posts: 44
Joined: Sat Dec 15, 2012 7:55 am

Re: Which is hypothetically faster?

Post by rexjericho » Wed Jan 09, 2013 5:54 pm

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.

User avatar
Inny
Party member
Posts: 652
Joined: Fri Jan 30, 2009 3:41 am
Location: New York

Re: Which is hypothetically faster?

Post by Inny » Wed Jan 09, 2013 11:57 pm

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.

User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Which is hypothetically faster?

Post by kikito » Thu Jan 10, 2013 8:51 am

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
When I write def I mean function.

Post Reply

Who is online

Users browsing this forum: No registered users and 12 guests