lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Saturday 25, Pierre-Yves Gérardy wrote:
> On Sat, May 25, 2013 at 6:42 AM, Dirk Laurie <dirk.laurie@gmail.com> 
wrote:
> > 2013/5/25 Pierre-Yves Gérardy <pygy79@gmail.com>:
> > LUAI_MAXSTACK (see `luaconf.h`) less what you are already using.
> > Which depends.
> > 
> > It would be easy to do in C. The critical information is hidden
> > from the API, you only have `checkstack`. But even with that you
> > could extract the information by a bargaining process as the `#`
> > function does.
> 
> So you can't determine it from the Lua side.
> 
> I'm trying to write a max(array) function that's as fast as
> possible.
> 
> In Lua 5.1 and 5.2, and LuaJIT -joff, math.max(unpack(array)) is by
> far the fastest method, but it can blow up unpredictably.
> 
> I though that I could use a numeric threshold to decide whether to
> use unpack() or to iterate manually. Dispatching based on
> pcall(unpack,t) pays for tables with a length superior to ~30. I
> may use that.

unpack() lets you select a range to unpack from the table.  So you 
could pick a large but safe segment length to unpack.


local safe_len = 1000  -- tune this.
function array_max(array)
  local len = #array
  assert(len > 1, "Expected non-empty array")
  local off = 1
  local off_end = safe_len
  local max = array[1] -- seed max.
  repeat
    if off_end > len then off_end = len end
    local seg_max = math.max(unpack(array, off, off_end))
    if seg_max > max then
      max = seg_max
    end
    off = off + safe_len
    off_end = off_end + safe_len
  until off >= len
  return max
end
-- simple array max for validation.
function array_safe_max(array)
  local max = array[1]
  for i=2,#array do
    local val = array[i]
    if val > max then
      max = val
    end
  end
  return max
end

print('max:', array_max{ 1,2,3,4,5,6,7 })

math.randomseed(os.time())

local ary = {}
local N = 1000000
for i=0,N do
  ary[i] = math.random(0,2000000000)
end

local function bench(fmax, ary)
  local max
  local start = os.clock()
  for i=0,1000 do
    max = fmax(ary)
  end
  return max, os.clock() - start
end

print('max:     ', bench(array_max, ary))
print('safe_max:', bench(array_safe_max, ary))



-- 
Robert G. Jakabosky