C stack overflow in Lua 5.4 in ackermann benchmark

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

C stack overflow in Lua 5.4 in ackermann benchmark

Eduardo Barthel
For a long time I've used the following example to benchmark tail calls in Lua 5.1, 5.2, 5.3 and LuaJIT.

```
local function ack(m, n)
  if m == 0 then
    return n + 1
  end
  if n == 0 then
    return ack(m - 1, 1)
  end
  return ack(m - 1, ack(m, n - 1))
end

local res = ack(3,10)
print(res)
assert(res == 8189)
```

However I've just noticed that Lua 5.4 fails to execute this, with the following error:

```
lua5.4: benchmarks/lua/ackermann.lua:16: C stack overflow
stack traceback:
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
... (skipping 1958 levels)
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in function <benchmarks/lua/ackermann.lua:2>
(...tail calls...)
benchmarks/lua/ackermann.lua:16: in upvalue 'ack'
benchmarks/lua/ackermann.lua:16: in local 'ack'
benchmarks/lua/ackermann.lua:19: in main chunk
```

While benchmark runs fine in Lua 5.1, 5.2, 5.3, LuaJIT and Ravi in Lua 5.4 it does not.

I've tried to use the patches for Lua 5.4 bugs, but it didn't improve the situation.
Then I saw that the default LUAI_MAXCSTACK is much lower now than it was in Lua 5.3. Why did the default value change? Is there any performance degradation when it is set too high now? 

Reply | Threaded
Open this post in threaded view
|

Re: C stack overflow in Lua 5.4 in ackermann benchmark

Roberto Ierusalimschy
> For a long time I've used the following example to benchmark tail calls in
> Lua 5.1, 5.2, 5.3 and LuaJIT.
>
> ```
>
> However I've just noticed that Lua 5.4 fails to execute this, with the
> following error:
>
> ```
> lua5.4: benchmarks/lua/ackermann.lua:16: C stack overflow
> ...

Add the following in the first line of the script:

if debug.setcstacklimit then
  assert(debug.setcstacklimit(30000))
end

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: C stack overflow in Lua 5.4 in ackermann benchmark

Andrew Gierth
In reply to this post by Eduardo Barthel
>>>>> "Eduardo" == Eduardo Bart <[hidden email]> writes:

 Eduardo> For a long time I've used the following example to benchmark
 Eduardo> tail calls in Lua 5.1, 5.2, 5.3 and LuaJIT.

 Eduardo> ```
 Eduardo> local function ack(m, n)
 Eduardo>   if m == 0 then
 Eduardo>     return n + 1
 Eduardo>   end
 Eduardo>   if n == 0 then
 Eduardo>     return ack(m - 1, 1)
 Eduardo>   end
 Eduardo>   return ack(m - 1, ack(m, n - 1))

The inner ack() in this expression is not a tail call. So you need
enough available stack to cope with the number of times it will recurse
through this specific path.

The difference in 5.4 is that Lua-to-Lua function calls now consume
space on the C stack (for a stack frame of luaV_execute), which was not
the case in earlier versions.

--
Andrew.