Extremely fast language for controlling scripting
I'm writing a real time particle system, the editor is done in C# while the actual particle effects it creates will be used in my C++ game framework.
Instead of having a limited number of effects and the like, I have gone down the path to script to particles to enable unlimited flexibility.
Right now I'm using LUA to script to them. The way I'm doing it is by specifying a creation and update function (e.g. CreateFireParticle and UpdateFireParticle) with the update function being called for each particle on each frame.
The problem is, with 2,000+ particles being updated per frame the particle system begins to slow down.. 10,000 it's unbearable :(
I know it is the updating and not the rendering (without logic I can draw 100,000 with a wonderful frame rate).
So, what alternatives do I have?
I was thinking of .Net, I could write my particle logic in C# which could be JIT'ed (by Mono or .NET), but don't know the overhead of calling managed code from inside my native C++ framework. Especially since it's real time and the particles will be many.
The other alternative I was thinking was using assembly. It is extremely easy to ship an assembler with my particle editor, and since particle logic isn't too huge I don't at all mind writing short simple hand optimized assembly routines.
There are ways to make LUA run as native code, such as LuaJIT and I think google made a LLVM compiler for it.
You can also use other 'native' scripting implementations, like V8 javascript.
You can also use other 'native' scripting implementations, like V8 javascript.
Or write your own compiler. You can skim through the Kaleidoscope-Tutorial on the LLVM site to see you how can use LLVM as a jitter. But you don't have to handcode a full parser (while funny, it is also error-prone and your grammer is clumsier to extend). Keyword into the direction of parser/scanner generators: boost.spirit, bison/bison++/bisonc++, ANTLR, flex/flex++ [dunno if there is a flexc++, but i think I've seen it on freshmeat recently], boost.regex.
Btw, LLVM will do all optimizations [that you can dream of] for you; you really only need to emit a simple parse tree and delegate the rest to LLVM. In some cases, LLVM will outperform gcc and msvc binaries.
Writing a small domain-specific programming language is not too hard. Actually, it took me less than a month of spare time coding (as in 1-2 hrs per day) to code the compiler for what you see on the right, and with which you can get what you see on the left:
I divided the compiler into a classical frontend/backend solution (but yet I don't have a llvm target, but it won't be too hard to emit llvm-'values' from my syntax tree that happens to be executable), so that LISP-lookalike language (which has nothing to do with LISP but the syntax) is not mandatory. Note that my domain is very limited: I only need functions of the form (x_0, x_1, ..., x_n) -> y, i.e. arbitrary input value count, one output value; further, it's strictly functional (so in the image you see a strictly functional implementation of the mandelbrot), because it could be subject to heavy parallelization later and shouldn't suffer from sideeffects. The applications of my code are generating heightmaps, interpolators in material stacks, probability distributions (later needed e.g. for the placement of plants and trees), and some more.
Assembler is not really portable, and if your project should be long-lived, either try out the optimization I proposed in my first post, or write a domain specific programming language, or ship a full compiler with your app for the windows version. For the Unix versions, you can virtually rely on an installed C compiler (I've done that for kicks in the past: my class took C++ code, and compiled it to a native shared object (dll), et voila, I had shader scripting for my ray tracer).
Btw, LLVM will do all optimizations [that you can dream of] for you; you really only need to emit a simple parse tree and delegate the rest to LLVM. In some cases, LLVM will outperform gcc and msvc binaries.
Writing a small domain-specific programming language is not too hard. Actually, it took me less than a month of spare time coding (as in 1-2 hrs per day) to code the compiler for what you see on the right, and with which you can get what you see on the left:
I divided the compiler into a classical frontend/backend solution (but yet I don't have a llvm target, but it won't be too hard to emit llvm-'values' from my syntax tree that happens to be executable), so that LISP-lookalike language (which has nothing to do with LISP but the syntax) is not mandatory. Note that my domain is very limited: I only need functions of the form (x_0, x_1, ..., x_n) -> y, i.e. arbitrary input value count, one output value; further, it's strictly functional (so in the image you see a strictly functional implementation of the mandelbrot), because it could be subject to heavy parallelization later and shouldn't suffer from sideeffects. The applications of my code are generating heightmaps, interpolators in material stacks, probability distributions (later needed e.g. for the placement of plants and trees), and some more.
Assembler is not really portable, and if your project should be long-lived, either try out the optimization I proposed in my first post, or write a domain specific programming language, or ship a full compiler with your app for the windows version. For the Unix versions, you can virtually rely on an installed C compiler (I've done that for kicks in the past: my class took C++ code, and compiled it to a native shared object (dll), et voila, I had shader scripting for my ray tracer).
You can use phresnel method and compile your particle logic into asm using the intermeidary LLVM architecture, that works, or you can write it in C#, which is fast enough if you have the jit compiler (don't know of mono has jit).
If you want to stick with Lua you'll have to optimize it using a scheduler of some sort. That is each particle that needs to be updated needs to create a timeline which then it can plug events into the scheduler which then will best optimize the update of the particles at any particular time, that way it can avoid polling the particles state. The scheduler can spread out updates to minimize too many particles updating at once also more efficiently use the cpu.
Using such a technique in conjunction with LuaJit you should be able to update ~10k just fine.
Though I suggest not using Lua for controlling large amounts of particles since for the most part particles are so simple you don't need a full fledged scripting engine for their logic. Most of them are just a chain of simple operations ( ie scaling, interpolation between 2 values, color cylcing, etc.. ) on a timeline. It would be more effective to create a low level particle engine and create callbacks into Lua or any scripting system on particular particle events and take advantage of the scripting engine that way ( ie when rain particles hit ground they spawn dirt puffs, or if they hit metal they spawn water splatter etc.. ).
Good Luck!
-ddn
If you want to stick with Lua you'll have to optimize it using a scheduler of some sort. That is each particle that needs to be updated needs to create a timeline which then it can plug events into the scheduler which then will best optimize the update of the particles at any particular time, that way it can avoid polling the particles state. The scheduler can spread out updates to minimize too many particles updating at once also more efficiently use the cpu.
Using such a technique in conjunction with LuaJit you should be able to update ~10k just fine.
Though I suggest not using Lua for controlling large amounts of particles since for the most part particles are so simple you don't need a full fledged scripting engine for their logic. Most of them are just a chain of simple operations ( ie scaling, interpolation between 2 values, color cylcing, etc.. ) on a timeline. It would be more effective to create a low level particle engine and create callbacks into Lua or any scripting system on particular particle events and take advantage of the scripting engine that way ( ie when rain particles hit ground they spawn dirt puffs, or if they hit metal they spawn water splatter etc.. ).
Good Luck!
-ddn
It sounds like the best way to approach the problem would be to more effectively exploit the parallelism of the system. That is, it sounds like right now you're doing this:
The problem there being that you have to call processParticle 2000 times if you have 2000 particles. Now, imagine the following instead:
In that example, P.VX represents not the x velocity of one particle, but the x velocities of all the particles. And doing A+B does not entail a single addition, but rather adding all values of A to the corresponding values of B. The point is to sharply decrease the number of things that actually have to be done per-frame in Lua; the vectorized addition would be done in C.
function processParticle(p, dT) p.vy = p.vy + GRAVITY * dT p.x = p.x + p.vx * dT p.y = p.y + p.vy * dTendfor i,p in ipairs(particles) do processParticle(p)end
The problem there being that you have to call processParticle 2000 times if you have 2000 particles. Now, imagine the following instead:
function processAllParticles(P, dT) P.VY = P.VY + GRAVITY * dT P.X = P.X + P.VX * dT P.Y = P.Y + P.VY * dTend
In that example, P.VX represents not the x velocity of one particle, but the x velocities of all the particles. And doing A+B does not entail a single addition, but rather adding all values of A to the corresponding values of B. The point is to sharply decrease the number of things that actually have to be done per-frame in Lua; the vectorized addition would be done in C.
If each particle potentially has its own behavior (a behavior hook) then you cant use only the simple parallel scheme (high level LUA call, C doing vector of particles) . One or more behavior routines would have to exist 'scripted' so that a pool of variable use particles could be implimented.
There is a small C ( http://en.wikipedia.org/wiki/Tiny_C_Compiler ) which could
compile a DLL on the fly to native code containing all the behavior routines needed for all the particle flavors.
If you dont need runtime compile you can also create a simplified script language
using C/CPP macros (which again could be compiled to a DLL ...)
Quote:Original post by wodinoneeye
If each particle potentially has its own behavior (a behavior hook) then you cant use only the simple parallel scheme (high level LUA call, C doing vector of particles) .[...]
You can use the parallel scheme by writing a parameterized kitchen sink particle scheme. This avoids branching and makes your particle algorithm embarrassingly parallel.
Quote:There is a small C ( http://en.wikipedia.org/wiki/Tiny_C_Compiler ) which could compile a DLL on the fly to native code containing all the behavior routines needed for all the particle flavors.
Personally, I think using a full C compiler is a kind of shotgun solution. On the other hand, you could dig into the source code and modify/restrict the allowed syntax a bit so no user can misuse C's power. Thinking about that writing a C parser is relatively easy, the latter shouldn't be too hard, in case the source code is nice.
Otoh, I bet that the backend LLVM (or maybe the whole compiler clang), produces way faster code.
Quote:If you dont need runtime compile you can also create a simplified script language using C/CPP macros (which again could be compiled to a DLL ...)
I guess if you don't need runtime compilation, you can just write down plain C/C++.
edit: on the second glimpse, I think I got what you mean. But how do you guarantee that the user doesn't misuse the power of C/C++? How would your scripting languages look like if it is based on Macro Machinery?
Or: If that solution is chosen, why not use a real text preprocessor? (sidenote: the c preprocessor is not a general text preprocessor, as it has some c related features).
Or: If your solution would be to use a real text preprocessor, why not use bison (or another EBNF-based parser generator) in a way that it just writes code to stdout or some other stream? That would be really simple, and all dangerous constructs are filtered out, or better, undefined, by default.
I was thinking of the soultion for something more complicated which the usual parameterized particle system could handle (especially if the partical pool is shared amongs many different effects (fire/snowflakes/rain/leaves/explosions/smoke/etc ...
which if you tried to parameterize in the shaders would be a humongus mess
of generalization.
The Macro method would not be very debugging friendly short of just easy to notice 'non' particle script items being visible in the 'script' code.
The reason for not straight away using C/C++ directly would be to limit the language to only whats needed for the particles processing (the precanned functionality) so that less specialized (and complex) native code would be
avoided.
Also such a language might be easier to setup versus the 'build a real language
and compiler/interpretor' which would be a project in itself.
It might all be a moot point because many of the particle types I listed
above would require very different rendering effects -- requiring them to be grouped in batches for efficiency. You could still use Macros for the tic delta
processing (to build the hook each batch uses) though its getting almost as easy
to just write it all in C as the extra interface work of the all the flavors of macro calls is about the same amount of work and same readability level.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement