Predictable garbage collection with Lua

In one of my previous posts I talked about how you can make the Lua garbage collector (GC) more predictable in running time. This is a virtue that is highly valued in a GC used in games where you don’t have the luxury of going over you frame time. In that post I described a solution to the problem which works fine most of the time, leaving little space for garbage collection times that will hurt the framerate. However I ended that post with a promise to provide a better solution and in this post, I deliver.

The ideal situation would be to have the GC run for a specific amount of time. This way the game engine will be able to assign exact CPU time to the GC based on the situation. For example one strategy would be to give a constant amount of time to the GC per frame. Lets say 2ms every frame. Or it can be more clever and take into consideration other parameters, like the amount of time it took to do the actual frame. Is there enough time left for this frame? If there is, spend some for GC, if not, hold it for the next frame when things might not be too tight. Other parameters can be memory thresholds, memory warnings, etc.

All of the above depend on a GC that can be instructed to run for an exact amount of time. This kind of GC is what we call a realtime GC. And Lua does not have one. However it turns out that we can get very close to realtime with minor changes to the Lua GC.

The patch below modifies the behavior of the GC in the way we need it:

--- a/src/lgc.c
+++ b/src/lgc.c
@@ -609,15 +617,14 @@ static l_mem singlestep (lua_State *L) {
 
 void luaC_step (lua_State *L) {
   global_State *g = G(L);
-  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
-  if (lim == 0)
-    lim = (MAX_LUMEM-1)/2;  /* no limit */
   g->gcdept += g->totalbytes - g->GCthreshold;
+  double start = getTime();
+  double end = start + (double)g->gcstepmul / 1000.0;  
   do {
-    lim -= singlestep(L);
+    singlestep(L);
     if (g->gcstate == GCSpause)
       break;
-  } while (lim > 0);
+  } while (getTime() < end);
   if (g->gcstate != GCSpause) {
     if (g->gcdept < GCSTEPSIZE)
       g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/

The only missing part from the patch above is the getTime() that can be something like this:

double getTime() {
    struct timeval tp;
    gettimeofday(&tp, NULL);
    return (tp.tv_sec) + tp.tv_usec/1000000.0;
}

I guess however that everyone will want to use their own time function.

The patch modifies the code so that is stops based on a time limit and not based on a calculated target memory amount to be freed. The simplicity of the patch also comes from the fact that we “reuse” the STEPMUL parameter that is no longer used to carry the aggressiveness of the GC. We now use it to hold the exact duration we want the GC to run in milliseconds. So the usage will be this:

lua_gc(L, LUA_GCSETSTEPMUL, gcMilliSeconds);
lua_gc(L, LUA_GCSTEP, 0);

The above code will run the GC for gcMilliSeconds ms. This way you will never be out of your frame time budget, because the garbage collection took a little longer to execute. Problem solved!

From Python to Lua

(This blog was originaly posted at #AltDevBlogADay)

All game developers, sooner or later, learn to appreciate scripting languages. That magical thing that allows for letting others do your job, better scaling of the team, strengthening the game code/engine separation, sandboxing, faster prototyping of ideas, fault isolation, easy parametrization, etc. Every game has to be somehow data driven to be manageable, and stopping at simple configuration files, with many different custom parsers, without going the extra mile of adding a full scripting language, is 90% of the times a bad design choice. 

Today the developer can choose from a large variety of scripting languages, or even go crazy and implement one on his own. It happens that the most favored language for game developers is Lua. Its easy to understand why Lua is the favorite but other options are used as well. For example Python and the lately upcoming force of  Javascript.

Here I would like to share some of my experience of moving a game engine from Python to Lua. Continue reading

Sylphis3D lighting, shadows, physics demonstration

This is some “memory lane” kind of post. As you probably already know, I am working on an iOS port of Sylphis3d lately and I have been going through some old videos from Sylphis3D. I must admit the feeling is overwhelming. All those nights strugling with algorithms, data structures, broken drivers, experimental scripting… The vibrant community of people surrounding the project starving for more info on the progress. I really miss those days. I would like to share one of the oldest videos with you. The video below was “shot” in 2003 and is now of historical value! It features per-pixel normal mapped lighting with realtime shadows from every light in the scene, coupled with realistic physics. Note that this was more than one year before DOOM 3 came out… Enjoy!

Something moving in the shadows…

I have been spending quite some time the last months working on a port of the Sylphis3d game engine to the iPhone. I am now to a point that the thing works really nicely. I will not get into details about the changes that I did to the engine for the purpose (I will keep that for an other post), but I want to get the word out that it is final: WE ARE MAKING A GAME 😀

I don’t think I can stress out how excited I am about this. After too much struggling we finaly have an original consept, a good game design, and the team to make it true! The game is based on a wild idea I had some time ago, based on which we created a beautiful game concept. With the help of the artistic nature of Vangelis Bobolas and the soundscapes of the out-of-this-world music composer Thanasis Lightbridge, we are on the right track!

I can’t uncover much at the moment, but I believe we have something totally original and fun cooking in the oven 😉

Getting Started Again… True Megatexture

Greetings everybody!

It been a long time since this blog was updated, I know! Well I was kind of busy lately. Looking for a job, finding a job, then doing the job and finally trying to get some free time for summer vacation and free time projects. You know that getting a new job always makes things a bit harder until you get comfortable. The good thing is that now work has stabilized and I finally start to have some free time.

I’m not going to write a lot here at this time. I just wanted to let you know that I’m well and good. I’m also planing to start working on Sylphis3D again in a more committed and persistent manner.

Regarding Sylphis3D I would also like to inform you that I’m working on something big! You probably know my opinion on megatexture on terrain. Well I managed to think of an algorithm to apply megatextures on any kind of geometry. Yes you heard correct! The new Sylphis3D will have totally virtual texturing.

You will be able to apply any size texture on any kind of mesh with no impact on performance! Would you like to apply a 4096×4096 texture on that talisman the player wears just in case someone gets so close to see it? It ok! It doesn’t hurt! Go ahead! It’s up to you! At the moment I am at implementation stage and things seem that will work out just fine! Stay tuned…

24 hours and 3GB later…

Its been almost 24 hours since the release of Sylphis3D and the sourceforge shows that 3GBytes were downloaded already about 10 e-mails expressing unbounded appreciation and some very nice comments. People are already jumping in to help with the website, doing changes and cleaning up the mess!

I would like to thank every one of you for your good wishes and I hope the best for you, too.

Tomorrow the Release

The time has come… tomorrow is the release day of Sylphis3D as an open source project. I’m very excited for this new begining! This is going to be my biggest contribution to the open source community until now.

The source that is going to be released counts ~45000 lines of code in C++ and Python counted with SLOCCount and the development cost was evaluated at $1.500.000 !!!

Oh.. well…. 🙂

sylphis3d, release, open source, GPL, 3d, engine, opengl

Open Sourcing Progress Update

As an update, I inform you that I’m pasting the license on the source files and getting the release ready. I’m going to publish on the sourceforge site where the Sylphis Generalized Triangle optimizer is published at the CVS. The engine is going to be hosted using SVN. Maybe there will be downloadable versions too, but I’m not sure yet. So get your SVN clients ready…

… until then happy Easter people!!

Opensource License

The last days I’m spending most of my time considering open source licenses and what would be the appropriate license for Sylphis3D. I must say that it is a very brain-melting procedure. I can see now why I could never became a lawyer!

I initially started considering two licenses, the GPL and the BSD. These are both approved open source licenses by the FSF. GPL is the defacto open source license today and has proven its value. Most of open source software today is released under the GPL, including Linux. The license was proven to be able to protect and empower the freedom of the software, by forcing code to be contributed back to the original GPLed software. The BSD on the other side is a more liberal license. Requires for the adopters of the code to make no more than to mention the code that was used. They are not required to release their code back. This is looked upon by some open source people because it allows closed source projects to benefit from open source, without ever contributing back. The classic example here is the Windows operating system that used the networking stack of the freeBSD operating system; no code was ever contributed back by Microsoft.

The problem with GPL is that it is not an easy solution when it comes to 3D game engines. A GPLed engine Continue reading