lua in high performance apps

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

lua in high performance apps

Steve Dekorte-4

Has anyone here used lua in what might be a considered a long-running high performance app? For example, has anyone used lua for the AI of a real time strategy game with lua programs controlling each of a hundred or more units, 30 times a second?

Steve


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

John Belmonte-2
Steve Dekorte wrote:
> Has anyone here used lua in what might be a considered a long-running
> high performance app?
> For example, has anyone used lua for the AI of a real time strategy game
> with lua programs controlling each of a hundred or more units, 30 times
> a second?

I had every intention to, but came to the conclusion that it isn't practical
without the support of an incremental garbage collector.  The games that Lua
has been used in are non-real time from what I can tell.

-John



Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Steve Williams
> > Has anyone here used lua in what might be a considered a long-running
> > high performance app?
> > For example, has anyone used lua for the AI of a real time strategy game
> > with lua programs controlling each of a hundred or more units, 30 times
> > a second?
>
> I had every intention to, but came to the conclusion that it isn't
practical
> without the support of an incremental garbage collector.  The games that
Lua
> has been used in are non-real time from what I can tell.

Th AI in RTS games is not usually executed every frame.  The AI is generally
updated every ten frames or so or spread out over a couple of frames.  So
it's still real-time, but a slower form of real-time.

Steve 'Sly' Williams - Code Monkey - http://www.kromestudios.com



Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

John Belmonte-2
Steve Williams wrote:
> Th AI in RTS games is not usually executed every frame.  The AI is
generally
> updated every ten frames or so or spread out over a couple of frames.  So
> it's still real-time, but a slower form of real-time.

Hi,

Steve Dekorte's original post was specifically talking about updating every
frame / every other frame.

In an RTS with "background AI" like you mentioned, if the AI stalls for a
frame or so for a gc cycle it's no big deal.  That's different from a
real-time system with hard deadlines which is the case with my project, and
possibly what Steve meant by "high-performance app".

The good news is that while this may be a place Lua can't go right now, it's
mainly a limitation of the implementation rather than the spec.

-John



Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Joshua Jensen
In reply to this post by Steve Williams
> > > Has anyone here used lua in what might be a considered a long-running
> > > high performance app?
> > > For example, has anyone used lua for the AI of a real time strategy
game
> > > with lua programs controlling each of a hundred or more units, 30
times
> > > a second?
> >
> > I had every intention to, but came to the conclusion that it isn't
> practical
> > without the support of an incremental garbage collector.  The games that
> Lua
> > has been used in are non-real time from what I can tell.
>
> Th AI in RTS games is not usually executed every frame.  The AI is
generally
> updated every ten frames or so or spread out over a couple of frames.  So
> it's still real-time, but a slower form of real-time.

I've used Lua in real-time apps (read: games) with great success, but only
if I profile and understand where the bottlenecks in the Lua script are.

These are some optimization strategies I use (off the top of my head):

1) Local variables are very quick, since they are accessed by index.  If
possible, make global variables local (weird, eh?).  Seriously, it works
great and indexed access is always going to be faster than a hash lookup.
If a variable, say GameState, needs global scope for access from C, make a
secondary variable that looks like 'local GSLocal = GameState' and use
GSLocal within the module.  This technique can also be used for functions
that are called repetitively, too.
2) for loops are quite a bit faster than while loops, since they have
specialized virtual machine instructions.
3) In your C callback functions, use lua_rawcall() to call other functions.
The overhead of a setjmp() call for exceptions (and a few other things) is
avoided.  I would not recommend using lua_rawcall() outside of a callback in
case something goes wrong during execution.  Without the setjmp() call, the
error handler that exits the application is called.
4) If possible, in your C functions, try and use lua_rawget() and
lua_rawgeti() for table access, since it avoids the tag method checks.  Be
sure to use lua_rawgeti() for indexed access.  It's still a hash lookup, but
it's probably the fastest way to get there by index.
5) In C, use lua_ref() wherever possible.  lua_ref() behaves similarly to a
local variable in terms of speed.
6) Know that C strings passed into a Lua function (such as lua_getglobal())
from C are translated to a Lua string on entry.  If a string is to be reused
across multiple frames of the game, do a lua_ref() operation on it, too.

Above all, trace the virtual machine.  Know what it is doing.  I find that,
on average, Lua executes around 20 times slower than C (depending on the
operation, of course).  Use the C callbacks to your advantage in this
scenario, so Lua acts as glue and you can take advantage of a cool scripting
language.

Thanks!

Joshua Jensen
Author, Workspace Whiz! - A Visual Studio Add-in
http://workspacewhiz.com/


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Joshua Jensen
As a followup to this, I should also mention that I use Lua for a lot of
algorithm prototyping, since the scripts can be reloaded on the fly.  I
would guess the majority of the time, the code is later moved to C/C++ for
speed.

Thanks,
Joshua Jensen
Author, Workspace Whiz! - A Visual Studio Add-in
http://workspacewhiz.com/

> > > > Has anyone here used lua in what might be a considered a
long-running
> > > > high performance app?
> > > > For example, has anyone used lua for the AI of a real time strategy
> game
> > > > with lua programs controlling each of a hundred or more units, 30
> times
> > > > a second?
> > >
> > > I had every intention to, but came to the conclusion that it isn't
> > practical
> > > without the support of an incremental garbage collector.  The games
that
> > Lua
> > > has been used in are non-real time from what I can tell.
> >
> > Th AI in RTS games is not usually executed every frame.  The AI is
> generally
> > updated every ten frames or so or spread out over a couple of frames.
So
> > it's still real-time, but a slower form of real-time.
>
> I've used Lua in real-time apps (read: games) with great success, but only
> if I profile and understand where the bottlenecks in the Lua script are.
>
> These are some optimization strategies I use (off the top of my head):
>
> 1) Local variables are very quick, since they are accessed by index.  If
> possible, make global variables local (weird, eh?).  Seriously, it works
> great and indexed access is always going to be faster than a hash lookup.
> If a variable, say GameState, needs global scope for access from C, make a
> secondary variable that looks like 'local GSLocal = GameState' and use
> GSLocal within the module.  This technique can also be used for functions
> that are called repetitively, too.
> 2) for loops are quite a bit faster than while loops, since they have
> specialized virtual machine instructions.
> 3) In your C callback functions, use lua_rawcall() to call other
functions.
> The overhead of a setjmp() call for exceptions (and a few other things) is
> avoided.  I would not recommend using lua_rawcall() outside of a callback
in
> case something goes wrong during execution.  Without the setjmp() call,
the
> error handler that exits the application is called.
> 4) If possible, in your C functions, try and use lua_rawget() and
> lua_rawgeti() for table access, since it avoids the tag method checks.  Be
> sure to use lua_rawgeti() for indexed access.  It's still a hash lookup,
but
> it's probably the fastest way to get there by index.
> 5) In C, use lua_ref() wherever possible.  lua_ref() behaves similarly to
a
> local variable in terms of speed.
> 6) Know that C strings passed into a Lua function (such as
lua_getglobal())
> from C are translated to a Lua string on entry.  If a string is to be
reused
> across multiple frames of the game, do a lua_ref() operation on it, too.
>
> Above all, trace the virtual machine.  Know what it is doing.  I find
that,
> on average, Lua executes around 20 times slower than C (depending on the
> operation, of course).  Use the C callbacks to your advantage in this
> scenario, so Lua acts as glue and you can take advantage of a cool
scripting
> language.
>
> Thanks!
>
> Joshua Jensen
> Author, Workspace Whiz! - A Visual Studio Add-in
> http://workspacewhiz.com/
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

John Belmonte-2
In reply to this post by Joshua Jensen
Joshua Jensen wrote:
> I've used Lua in real-time apps (read: games) with great success, but only
> if I profile and understand where the bottlenecks in the Lua script are.
>
> These are some optimization strategies I use (off the top of my head):

Hi Joshua,

The term "real time" by itself is not very descriptive, and it probably
means something different to each of us.  What you are addressing is how to
write Lua scripts that execute quickly, and that is certainly important
know-how.  However Lua speed isn't the problem in my case-- I've found it
sufficiently fast for light use (for example calling a few hundred lines of
code per frame).  Independent of execution speed is the issue of time spent
collecting garbage, and whether that time is amortized or happens all at
once.  Regardless of how lightly I use Lua or how fast my script is, if a gc
cycle comes and causes a missed frame it's "game over".

Unfortunately the weight of the gc cycle is not necessarily related to how
much Lua code I'm executing.  For example if I've got a Lua library 10,000
lines in length with plenty of internal state, even if I'm only executing
100 lines of that library code per frame and being careful not to generate
much garbage, eventually that gc cycle will come (given an embedded system
with limited memory) and will have to scan all the objects in the Lua state.

-John



Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Steve Dekorte-4
In reply to this post by Joshua Jensen

On Monday, April 16, 2001, at 08:15 PM, Joshua Jensen wrote:

2) for loops are quite a bit faster than while loops, since they have
specialized virtual machine instructions.

By "for loop" do you mean lua 4.0's for loop or foreach() and foreachi()?
Anyone now how foreach and foreachi compare in speed to while or for?

Steve

Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Joshua Jensen
From: "Steve Dekorte" <[hidden email]>
Sent: Monday, April 16, 2001 10:13 PM
> On Monday, April 16, 2001, at 08:15 PM, Joshua Jensen wrote:
>
> > 2) for loops are quite a bit faster than while loops, since they have
> > specialized virtual machine instructions.
>
> By "for loop" do you mean lua 4.0's for loop or foreach() and foreachi()?
> Anyone now how foreach and foreachi compare in speed to while or for?

I mean the built-in for loop:

for i = 1, 1000, 1 do
   -- Stuff
end

As far as foreach and foreachi, a quick check of the source code reveals:

static int luaB_foreachi (lua_State *L) {
  int n, i;
  luaL_checktype(L, 1, LUA_TTABLE);
  luaL_checktype(L, 2, LUA_TFUNCTION);
  n = lua_getn(L, 1);
  for (i=1; i<=n; i++) {
    lua_pushvalue(L, 2);  /* function */
    lua_pushnumber(L, i);  /* 1st argument */
    lua_rawgeti(L, 1, i);  /* 2nd argument */
    lua_rawcall(L, 2, 1);
    if (!lua_isnil(L, -1))
      return 1;
    lua_pop(L, 1);  /* remove nil result */
  }
  return 0;
}

static int luaB_foreach (lua_State *L) {
  luaL_checktype(L, 1, LUA_TTABLE);
  luaL_checktype(L, 2, LUA_TFUNCTION);
  lua_pushnil(L);  /* first index */
  for (;;) {
    if (lua_next(L, 1) == 0)
      return 0;
    lua_pushvalue(L, 2);  /* function */
    lua_pushvalue(L, -3);  /* key */
    lua_pushvalue(L, -3);  /* value */
    lua_rawcall(L, 2, 1);
    if (!lua_isnil(L, -1))
      return 1;
    lua_pop(L, 2);  /* remove value and result */
  }
}

Based on what I see above, I'd wager that a straight for loop in Lua is a
lot faster than foreachi, if only for the reason that foreachi calls
lua_rawcall.  A 'for key, value in table' in Lua is probably also faster
than foreach for the same reason.  But I haven't benchmarked either to be
sure.

Thanks,
Josh
----------
Author, Workspace Whiz! - A Visual Studio Add-in
http://workspacewhiz.com/




Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Joshua Jensen
In reply to this post by John Belmonte-2
From: "John Belmonte" <[hidden email]>
Sent: Monday, April 16, 2001 10:07 PM
> Joshua Jensen wrote:
> > I've used Lua in real-time apps (read: games) with great success, but
only
> > if I profile and understand where the bottlenecks in the Lua script are.
> >
> > These are some optimization strategies I use (off the top of my head):
>
> The term "real time" by itself is not very descriptive, and it probably
> means something different to each of us.  What you are addressing is how
to
> write Lua scripts that execute quickly, and that is certainly important
> know-how.  However Lua speed isn't the problem in my case-- I've found it
> sufficiently fast for light use (for example calling a few hundred lines
of
> code per frame).  Independent of execution speed is the issue of time
spent
> collecting garbage, and whether that time is amortized or happens all at
> once.  Regardless of how lightly I use Lua or how fast my script is, if a
gc
> cycle comes and causes a missed frame it's "game over".

I absolutely agree on the garbage collection issue.

> Unfortunately the weight of the gc cycle is not necessarily related to how
> much Lua code I'm executing.  For example if I've got a Lua library 10,000
> lines in length with plenty of internal state, even if I'm only executing
> 100 lines of that library code per frame and being careful not to generate
> much garbage, eventually that gc cycle will come (given an embedded system
> with limited memory) and will have to scan all the objects in the Lua
state.

I don't remember the recent garbage collection threads, but I'll be sure to
read them.  In my high-speed loops, I try to ensure the same thing in Lua
that I do in C... that no allocations/deallocations are performed unless
absolutely necessary.  So I've never really run into a problem with the GC,
but it is of concern now to me based on your comments.

Thanks,
Josh
----------
Author, Workspace Whiz! - A Visual Studio Add-in
http://workspacewhiz.com/


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Ben Cooley
In reply to this post by Steve Williams
> > > Has anyone here used lua in what might be a considered a long-running
> > > high performance app?
> > > For example, has anyone used lua for the AI of a real time strategy
game
> > > with lua programs controlling each of a hundred or more units, 30
times
> > > a second?

I would suspect that lua has been used in real time strategy games, but
never as a way of controlling AI.  That's really not what lua is for.  Lua
is for programming level scripts, win scenarios, dialog, popups, descision
branch points, game interface panels, win/lose screens, etc.  It is also for
plugging non-realtime parameters into your C AI routines to tweak them,
loading AI tables and values as LUA table files, and debugging.

I would recommend having various AI behaviors written in C for which lua can
initialize and change, and also disable or enable at different points in the
game (non-real time).  I think that's where you'll find the greatest utility
for lua.   The behaviors can be more generic, and you can leave out all of
the 'tuning' values (i.e. speed, sighting distance, attack frequencies,
etc.) and just put them in a lua table file and read it in as your rules
file.

Ben Cooley



Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Mauricio Carneiro
> I would suspect that lua has been used in real time strategy games, but
> never as a way of controlling AI.  That's really not what lua is for.  Lua
> is for programming level scripts, win scenarios, dialog, popups, descision
> branch points, game interface panels, win/lose screens, etc.  It is also
for
> plugging non-realtime parameters into your C AI routines to tweak them,
> loading AI tables and values as LUA table files, and debugging.

    I can say that we tried to use LUA in the AI of the game Tainá. But it
really didn't work. It's not for that. We used LUA in level scripts (later
we changed it, but initially it was in lua) game interface, win/lose
screens. Even in animations bitmaps sequence. That's what lua is for.

[]s
Mauricio Oliveira Carneiro
http://www.tecgraf.puc-rio.br/~carneiro
Tecgraf - Puc-rio (http://www.tecgraf.puc-rio.br/)


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Nahuel Greco
On Wed, 18 Apr 2001 18:08:40 -0300
"Mauricio Carneiro" <[hidden email]> wrote:

> > I would suspect that lua has been used in real time strategy games, but
> > never as a way of controlling AI.  That's really not what lua is for.  Lua
> > is for programming level scripts, win scenarios, dialog, popups, descision
> > branch points, game interface panels, win/lose screens, etc.  It is also
> for
> > plugging non-realtime parameters into your C AI routines to tweak them,
> > loading AI tables and values as LUA table files, and debugging.
> 
>     I can say that we tried to use LUA in the AI of the game Tainá. But it
> really didn't work. It's not for that. We used LUA in level scripts (later
> we changed it, but initially it was in lua) game interface, win/lose
> screens. Even in animations bitmaps sequence. That's what lua is for.
> 

Uhhrm.. then.. what faster scripting language do you suggest?, i have see
in various benchmarks page that lua is one of the fastest.

And.. there is a URL for Taina?


_------------------------------------------------------------.
| Nahuel Greco                 Web Development - Open Source |
| http://www.codelarvs.com.ar  Game Programming - Research   |
| Freelance coding / sysadmin  Networking. The answer is 42. |
'------------------------------------------------------------'


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Mauricio Carneiro
> >     I can say that we tried to use LUA in the AI of the game Tainá. But
it
> > really didn't work. It's not for that. We used LUA in level scripts
(later
> > we changed it, but initially it was in lua) game interface, win/lose
> > screens. Even in animations bitmaps sequence. That's what lua is for.
> >
>
> Uhhrm.. then.. what faster scripting language do you suggest?, i have see
> in various benchmarks page that lua is one of the fastest.

    I end up using C directly for the AI algorithms. It was surely worthy.
If you really intend to use a scripting language, then, just try out with
lua. I think it's the best language for you to test.

> And.. there is a URL for Taina?

    Tainá is a game based on a brazilian movie (from the amazon forest). The
game is not yet being published because it is about to be released. The page
for the movie is at : http://www.taina.com.br/ . I believe the game will be
listed there in a few days. But it's being released this month in Brazil. I
don't know if it'll be published outside Brazil yet.

[]s
Mauricio Oliveira Carneiro (HoBBiT)
http://www.tecgraf.puc-rio.br/~carneiro
Tecgraf - Puc-rio (http://www.tecgraf.puc-rio.br/)


Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Ben Cooley
In reply to this post by Nahuel Greco
> Uhhrm.. then.. what faster scripting language do you suggest?, i have see
> in various benchmarks page that lua is one of the fastest.

None.  Low level AI functions and patterns should be programmed in C, for
speed.

However, Lua is great for setting decision branching, setting up patterns,
level scripting, and higher level control.

I would suggest you set up your A.I. routines as a set of behaviors in C,
and then configure the behaviors and their parameters in Lua.   For example,
one tank might have an attack range threshold, a movement pathfinder, etc.
The parameters for these could be set interactively in lua during testing
and game balancing, allowing the designers to get a good handle on them.  It
could also be set or changed by a lua script callback when a unit changes
modes (if the mode change isn't too frequent and there aren't too many
units).

You could also progam the high level 'strategy' of your AI in lua (as it
doesn't execute every frame).  For example, various threshold values in your
C code could signal events to your Lua scripts which would cause your lua
scripts to reevaluate what the AI player should be doing.

Anything that doesn't require frame by frame updating, or constant calls,
can (and probably should) be done in lua.  Anything that is time intensive
should be done in C or C++.

> And.. there is a URL for Taina?
>
>
> _------------------------------------------------------------.
> | Nahuel Greco                 Web Development - Open Source |
> | http://www.codelarvs.com.ar  Game Programming - Research   |
> | Freelance coding / sysadmin  Networking. The answer is 42. |
> '------------------------------------------------------------'
>
>


Reply | Threaded
Open this post in threaded view
|

RE: lua in high performance apps

Dirk Ringe
In reply to this post by Nahuel Greco
The AI of an RTS game can be divided into two parts:
- the low level part with lots of basic algorithms like A*. These algorithms
are very performance critical, since they will be called often and consists
of scanning large parts of the map and other data. A* is the best example,
but finding a foe or other stuff could fit also.
- the high level part, which evaluates the targets of the operations.
"Destroy this building" or "Extend the base" are common examples. It is all
about strategic decisions about the game. Also triggers (attack, when enemy
touches this point) come into play here. This part uses the low level part
and triggers behaviours, but does also select and parameterize them, but not
implement them.

Following such a division: low level is c and high level can be scripted
(where lua just fits perfectly), if a high level part is too expensive in
lua, then recode it in c.

Dirk

-----Original Message-----
From: [hidden email]
[[hidden email] Behalf Of Nahuel Greco
Sent: Thursday, April 19, 2001 12:55 AM
To: Multiple recipients of list
Subject: Re: lua in high performance apps


On Wed, 18 Apr 2001 18:08:40 -0300
"Mauricio Carneiro" <[hidden email]> wrote:

> > I would suspect that lua has been used in real time strategy games, but
> > never as a way of controlling AI.  That's really not what lua is for.
Lua
> > is for programming level scripts, win scenarios, dialog, popups,
descision
> > branch points, game interface panels, win/lose screens, etc.  It is also
> for
> > plugging non-realtime parameters into your C AI routines to tweak them,
> > loading AI tables and values as LUA table files, and debugging.
>
>     I can say that we tried to use LUA in the AI of the game Tainá. But it
> really didn't work. It's not for that. We used LUA in level scripts (later
> we changed it, but initially it was in lua) game interface, win/lose
> screens. Even in animations bitmaps sequence. That's what lua is for.
>

Uhhrm.. then.. what faster scripting language do you suggest?, i have see
in various benchmarks page that lua is one of the fastest.

And.. there is a URL for Taina?


_------------------------------------------------------------.
| Nahuel Greco                 Web Development - Open Source |
| http://www.codelarvs.com.ar  Game Programming - Research   |
| Freelance coding / sysadmin  Networking. The answer is 42. |
'------------------------------------------------------------'


Reply | Threaded
Open this post in threaded view
|

RE: lua in high performance apps

Jim Mathies-2
In reply to this post by Steve Dekorte-4
Title: RE: lua in high performance apps

what was your reasoning for not using it?  what problems did you have?

Regards,
Jim


> -----Original Message-----
> From: Mauricio Carneiro [[hidden email]]
> Sent: Wednesday, April 18, 2001 2:09 PM
> To: Multiple recipients of list
> Subject: Re: lua in high performance apps
>
>
> > I would suspect that lua has been used in real time
> strategy games, but
> > never as a way of controlling AI.  That's really not what
> lua is for.  Lua
> > is for programming level scripts, win scenarios, dialog,
> popups, descision
> > branch points, game interface panels, win/lose screens,
> etc.  It is also
> for
> > plugging non-realtime parameters into your C AI routines to
> tweak them,
> > loading AI tables and values as LUA table files, and debugging.
>
>     I can say that we tried to use LUA in the AI of the game
> Tainá. But it
> really didn't work. It's not for that. We used LUA in level
> scripts (later
> we changed it, but initially it was in lua) game interface, win/lose
> screens. Even in animations bitmaps sequence. That's what lua is for.
>
> []s
> Mauricio Oliveira Carneiro
> http://www.tecgraf.puc-rio.br/~carneiro
> Tecgraf - Puc-rio (http://www.tecgraf.puc-rio.br/)
>

Reply | Threaded
Open this post in threaded view
|

Re: lua in high performance apps

Steve Dekorte-4
In reply to this post by Joshua Jensen

Joshua Jensen wrote:
1) Local variables are very quick, since they are accessed by index.  If
possible, make global variables local (weird, eh?)...
This technique can also be used for functions...

I just got around to playing with this and it works great.
For example this code:

  local i, v = next(t, nil)
  while i do i, v = next(t, i) end

Is 10% faster if you make "next" a local:

  local next = next
  local i, v = next(t, nil)
  while i do i, v = next(t, i) end

I also did some other tests and found that foreach() is ~20% faster than the equivalent while loop, while foreachi() was ~20% slower than a while loop.

Steve