Posts Tagged ‘video’
The “Rocks!” game is a spaceship shooter game for 2 simultaneous players on the same Android tablet:
The code is open source and is extensively commented. I plan to write a tutorial from it:
The game also compiles to run in the desktop.
Here’s a running session of the game (with a much faster speed):
For a glimpse at the runtime costs of Céu, I created a simple application with SDL that animates 10000 rectangles on the screen.
My hypothesis is that lines of execution in Céu (a.k.a trails) are cheap and should be used carelessly, even for simple activities such as waiting for a single event and terminating. This way, the testing application in Céu has a peek of 40000 trails active at the same time, which are all visited by the scheduler on every frame.
I compare the implementation in Céu with a simpler application in C to serve as a benchmark.
The application in raw C is damn simple:
- Declares a vector of 10000 rectangles.
- Initializes each to 10×10 width/height, a random (x,y) position, and a random x velocity.
- Animates them continuously, restarting from left when reaching the right side of the screen.
- Achieved FPS = 120 .
- The program has 5 lines of execution:
- On SDL_QUIT event: terminates the application.
- Every frame: clears the screen.
- Every 40ms: creates 30 new Rect organisms.
- after 30s: kills all of them at once and restart the process
- Every frame: updates the screen.
- Every second: calculates the FPS.
(technically they are 7 lines of execution because (3) and (5) are split in two)
- The class Rect has 4 lines of execution:
- Every 200ms: varies the rectangle width, height, r, g, b (with a random epsilon).
- Every frame: animates the rectangle respecting its velocity, terminating when it reaches the end of the screen.
- Every frame: redraws the rectangle on screen.
- On termination: runs a simple finalizer (which maintains the number of organisms alive).
- Achieved FPS = 107 . (when 10000 rectangles are on screen)
The main differences between the two implementations are marked in bold above and are summarized as follows:
- The rectangles in Céu are allocated dynamically: in the peek, we have 750 rectangles being allocated (in the left side) and reclaimed (in the right side) every second.
- Each rectangle on screen (10000 at most) has 4 active trails, all of which are visited by the scheduler every frame (4 x 10000 = 40000 lightweight threads active at the same time).
- Finally, every 30 seconds the program restarts the spawning loop, killing all 10000 active organisms at once, running the associated finalizers, and reclaiming all memory.
Céu is a source-to-source compiler that generates single-threaded ansi-C code. This way, the generated code for the test application, although incomprehensible, can be compiled with gcc and tested in any computer that has SDL2:
% gcc download_code.c -lSDL2 .
The simple SDL application in C is used as a benchmark to compare to a more complex application written in Céu, which shows a decrease around 10% in FPS.
Although the application in C could be re-implemented to achieve the same functionality (for a more strict comparison), the initial numbers are already satisfactory and make the point that the trail-oriented programming style of Céu is realistic, even in a highly dynamic scenario.
The basic prerequisite to build dynamic applications is language support to deal with abstractions and code reuse. Programming languages provide a multitude of abstraction mechanisms, from simple abstract data types, to OO classes. Regarding an abstraction, an effective mechanism should provide means to deal with at least the following points:
- Hide its internal implementation details.
- Expose a uniform programming interface to manipulate it.
- Control its life cycle.
As an example, to build an ADT in C, one can define a struct, hide it with a typedef, expose functions to manipulate it, and control instances with local variables or malloc/free. Classes extend ADTs with richer mechanisms such as inheritance and polymorphism. Furthermore, the life cycle of an object is typically controlled automatically through a garbage collector.
Abstractions in Céu are created through organisms, which basically reconcile threads and objects into a single concept:
- An organism has intrinsic execution, being able to react to the environment on its own.
- An organism exposes properties and actions in order to interact with other organisms during its life cycle.
Like an object, an organism exposes properties and methods (events in Céu) that can be accessed and invoked (emitted in Céu) by other instances. Like a thread, an organism has its own line(s) of execution, with persistent local variables and execution state.
In contrast, an object method call typically shares the same execution context with its calling method. Likewise, a thread does not expose fields or methods.
The program below defines the class HelloWorld and executes two instances of it:
class HelloWorld with var int id; // organism interface do // organism body every 1s do _printf("[%d] Hello world!\n", this.id); end end var HelloWorld hello1, hello2; hello1.id = 1; hello2.id = 2; await FOREVER; .
The behavior can be visualized in the video on the right. The top-level code creates two instances of the class HelloWorld, initializes the exposed id fields, and then awaits forever. As organisms have “life”, the two instances react to the environment autonomously, printing the “Hello world!” message every second.
Note in the example that organisms are simply declared as normal variables, which are automatically spawned by the language runtime to execute in parallel with its enclosing block.
In the following variation, we add the event stop in the class interface and include another line of execution in the organism body:
class HelloWorld with var int id; event void stop; do par/or do every 1s do _printf("[%d] Hello world!\n", this.id); end with await this.stop; end end var HelloWorld hello1, hello2; hello1.id = 1; hello2.id = 2; await 3s500ms; emit hello1.stop; hello2.id = 5; await 2s; emit hello2.stop; await FOREVER; .
Now, besides printing the message every second, each organism also waits for the event stop in parallel. The par/or construct splits the running line of execution in two, rejoining when any of them terminate. (Céu also provides the par/and construct.)
After the top-level code instantiates the two organisms, it waits 3s500ms before taking the actions in sequence. At this point, the program has 5 active lines of execution: 1 in the top-level and 2 for each of the instances. Each organism prints its message 3 times before the top-level awakes from 3s500ms.
Then, the top-level emits the stop event to the first organism, which awakes and terminates. It also changes the id of the second organism and waits more 2s. During this period the second organism prints its message 2 times more (now with the id 5).
Note that although the first organism terminated its body, its reference hello1 is still visible. This way, the organism is still alive and its fields can be accessed normally (but now resembling a “dead” C struct).
Lines of execution in Céu are known as trails and differ from threads in the very fundamental characteristic of how they are scheduled.
Céu is a synchronous language based on Esterel, in which lines of execution advance together with a unique global notion of time.
In practical terms, this means that Céu can provide seamless lock-free shared-memory concurrency. It also means that programs are deterministic and have reproducible execution. As a tradeoff, concurrency in Céu is not suitable for algorithmic-intensive activities as there is no automatic preemption among trails.
In contrast, asynchronous models have time independence among lines of execution, but either require synchronization primitives to acquire shared resources (e.g. locks and semaphores in pthreads), or completely forbid shared access in favor of message passing (e.g processes and channels in actor-based languages). In both cases, ensuring deterministic execution requires considerable programming efforts.
The post entitled “The case for synchronous concurrency” illustrates these differences in practical terms with an example.
Céu organisms reconcile objects and threads in a single abstraction mechanism.
Classes specify the behavior of organisms, hiding implementation details and exposing an interface in which they can be manipulated by other organisms.
In the next post, I’ll show how Céu can control the life cycle of organisms with lexical scope in three different ways: local variables, named allocation, and anonymous allocation.
Click here to watch the talk about LuaGravity presented in the Lua Workshop’09.