Misinformed Cognoscenti

Magpie and an upcoming book

2009-10-05T19:43:00.003-04:00

I want to give a shout out to Robert Nystrom. He's a colleague at EA who is writing a book about Design Patterns for use in video games, which, to my knowledge, would be the first true book on Game Engine Architecture. Other books claim to be that but fall short of providing a valuable description of how to concoct a game engine architecture -- they merely present an example of one.

Bob also works on an interesting language called Magpie. It's really tempting to talk about his language but I don't want to steal his thunder, so go read what he has to write about it. I will mention, though, that his adoption of ML-style type inference makes me think that's the way to go.

He has nifty ideas about allowing coders to create infix operators. When I asked him if he came up with that notion, he tried to pass the idea off on older languages like Lisp that allow practically anything as an identifier, but I think he's got something new. And I want to steal his ideas.

By the way, he was also in a band.

So I guess today is Bob's day.

Concurrency in games: Prefer data parallelism to task parallelism

2009-09-08T12:31:00.015-04:00

Programmers, including game architects, have a weakness for interesting things, and this ends up complicating code, when simple code would work better.

I have been writing a series of articles about fluid simulation, which includes a discussion about parallelization using Intel Threading Building Blocks (TBB). That API advocates using data parallelism instead of its alternatives, task parallelism or instruction parallelism. And I agree with their approach, but it is very boring and therefore, to some extent, doomed in the face of programmers looking for something more challenging.

I used to research computational fluid dynamics, which entailed using massively parallel processing (MPP), and I had accounts on a lot of very large machines. My simulations and post-processing code (and most simulations that used those massive machines) used data parallelism, because it scales well, meaning that the same code works about as efficiently regardless of problem size or the number of CPU's available. The work automatically gets redistributed to suit both the problem size and the computer capacity.

Data parallelism basically means that if you have a loop that iterates over data, you divide the iterations across multiple threads. So if the loop has N iterations and M threads then each thread works on N/M of the iterations.

The problem with the simplest form of data parallelism is that to work properly, the result of each iteration must be independent of the results of all other iterations. Such "embarrassingly parallel" problems are trivial to parallelize -- so easy that one might think one could not be so lucky as to have enough such problems to use up all computational resources. So programmers, being career problem-solvers, inevitably gravitate towards solving the more general problem: task parallelism.

Task parallelism means that various tasks run on various threads, and from time to time, the threads synchronize and communicate. The synchronization requires special mediation using atomic operations. This is the most general form of parallelism, and it leads to many potential problems, such as deadlock.

At GDC in 2007, I saw a talk given by a lead programmer of a studio making games for Xenon and Cell, each of which have multiple processing cores. The talk focused on their nifty job manager and how successful they were at balancing computational load. He spoke for an hour on all the trials and tribulations, discussed extremely interesting load-balancing strategies, expounded on how to detect and diagnose deadlock, described why all the naive approaches fail or fall short, showed graphs of computational load, and the talk was fascinating. The audience was full of people who had either written their own job managers or were about to, inspired by the success of the speaker and enthused by how interesting it all is.

Interesting, but ultimately not the right way to spend a lot of time.

Task parallelism does not scale well. If the problem size increases then so must the code; a programmer must manually modify the algorithm to involve more subtasks. Likewise, if the number of CPU's varies, the code must change. One might argue with this claim and state that the job manager will balance the load automatically, given a pool of processors. Perhaps, but the job manager cannot use more threads than there are jobs. So, task parallelism is not scalable to the extent we require.

The Xenon and Cell have more processing units than previous consoles had, but only by a small amount -- under a dozen each. In contrast, MPP machines have hundreds or thousands of CPU's. When that new generation of consoles came out, accustomed to thinking of parallezing across vast numbers of CPU's, I felt these multi-core consoles were quaint, but annoying -- too many CPU's to ignore, too few to use without an uncomfortable amount of effort. Not to mention that they did not even agree on a memory model -- Xenon uses shared and PS3 uses distributed. So people wrote versatile and robust cross-platform job manager API's. And for a few years, people at GDC had something new to talk about.

Since everybody knows that not enough problems can use loop parallelism, why do I advocate it? We have problems that require synchronization -- the data has interdepencencies -- so we need task parallelism and job managers, right?

Yes and no.

Most data interdependencies for large problems that occur in virtual simulations follow a "reduction" pattern, or a "map-reduce" pattern. This means that the problem can be broken into 2 phases: One (map) which subdivides the problem into smaller, independent pieces, and another (reduce) which combines each divided piece to its original whole. This principle allows "divide-and-conquer" to work.

A great example is "merge sort". Merge sort recursively divides a list of items in half until the list of items is small enough to sort trivially. At that point, you have a binary tree of sorted sub-lists. A merge operation merges 2 sorted lists such that the result is also sorted. The merge operation is less complex (linear, in fact) than the sort operation, but the sort operation gets subdivided until complexity becomes trivial (i.e. constant time).

By analogy, map-reduce problems boil down to being able to figure out how to combine the results of multiple computations, efficiently.

It turns out that at least one company has hinged their success at least partially on being able to phrase problems such that they suit the map-reduce paradigm.

And my series of articles demonstrates that physical simulation between thousands of mutually interacting particles also fits the same paradigm.

I predict that when the number of processors increases to a "serious" quantity (dozens or more) then we'll see a shift away from interesting discussions of job managers and task parallelism, toward a far more commonplace practice of using data parallelism, and map-reduce will be as commonly applied, and about as worthy of discussion, as creating a class.

We'll still need task parallelism for niche tasks (like asynchronous file loading) but I'd like to see its importance recede compared to data parallelism. I'd like to see a relatively small number of persistent tasks, each of which uses data parallelism as the primary means of exploiting parallel hardware.

Game Engine Configuration Language, Part 6: Concrete Examples of Abstraction

2009-08-03T10:48:00.029-04:00

Abstract, general, concrete, special, group, set, individual, member. What do these terms mean? How can we define them? Why do we care?

Why is this series of articles, which is supposed to be about game engine architecture, so obsessed with configuration languages?

Because mastering abstraction will let you solve categories of problems, even problems you have not thought of yet. And more importantly, it will let you write the tools to let other people solve those problems. So striving for excellence in writing a configuration language is tantamount to being the ultimate team player and collaborator.

And furthermore you have to do so in a way that augments the underlying language and simplifies expressions of the problems at hand. If you end up just rewriting the underlying operating system and the C++ programming language, you will have failed. But you must be capable of making that mistake before you can make the game engine correctly. So, for now we will focus on how to create a system that supports abstraction, then later worry about how to make that more useful than the underlying system. (We will eventually realize that we need lots of little domain-specific languages, so we need to be able to write languages in our sleep.)

Abstraction comes in handy when you strive to solve problems that you have not thought of yet, so we need to nail it.

As I mentioned in article 5, Abelson summarizes a framework for abstraction in computer languages, which I paraphrased:

	Procedures	Data
Primitives	+, *, ==	numbers, strings, true/false
Means of Combination	if, while, algebraic expressions with more than one operator, ...	Arrays, lists, dictionaries
Means of Abstraction	function definitions	Classes

Today I just want to mention how this taxonomy fits with the FIEA game engine configuration language:

	Procedures	Data
Primitives	Action	int, float, vector, matrix
Means of Combination	ActionList	table (a.k.a. scope)
Means of Abstraction	Reaction	Entity (?)

(This table leaves out some details. For example, Action, Reaction and Entity are all tables (or, if you prefer, they have tables). So there is more to the story than this table shows. But that's okay; this table is meant to see how things fit together, not to describe the entire system.)

But how does Entity provide a means of data abstraction beyond what "table" provides? And why do I put a question mark there? What's missing from a table that Entity provides that allows a table to graduate from merely a means of combination into a means of abstraction?

For that matter, what does "abstraction" mean?

When solving problems, abstraction means that you have taken a collection of concrete things, found what they have in common and rephrased the problem so that you can use generalities instead of specifics, and still formulate a viable solution.

The question also relates to what "concrete" means. And this is where things unravel for a moment.

Those familiar with Object-Oriented Programming (OOP) might readily identify how the dichotomy of class-object correlates with abstract-concrete: A class defines how data is structured and how to perform operations on that data, and combined this defines a "type", which is abstract. An object, that is an instance of that class, which defines a "token", is concrete. So that seems to explain what "abstract" and "concrete" mean in the context of programming languages.

Almost, but not quite.

Again, those familiar with OOP with also know that an "abstract class" is one that cannot be instantiated and we usually call a class that can be instantiated a "concrete class". So here again we have the abstract-concrete dichotomy but in this context, both the abstract and the concrete are classes. Abstract classes have at least one pure virtual method and concrete classes define the bodies of all methods. This ambiguity seems to muddle the concept of "abstraction".

Ironically, in order to understand how these 2 different notions of abstraction fit together, we have to see what they have in common, that is, we have to make an abstraction of both forms of abstraction.

Aside from the pure fun of getting this far into mental orbit, why do we need to converge these 2 different notions of abstraction? Because our configuration language is prototype-oriented, not object-oriented, so the whole class-object dichotomy does not exist, and neither does the abstract-class-versus-concrete-class distinction. But those distinctions apparently have utility so we need to understand what features they provide so that we can provide them in our configuration language.

This exercise reminds me of trying to understand what "meaning" means. Or defining the term "define".

Let's introduce the term generalization because it means basically the same thing as "abstraction", and now that we've gotten philosophical and unveiled 2 different forms of abstraction, we need to anchor ourselves.

Also, let's make analogies to non-computing situations. What does "generalization" mean in real life? And what is the opposite of "generalization"?

The opposite of "generalization" is specialization.

Imagine trying to explain to somebody what "dad" means. You point to its father and say "dad".

Now imagine trying to explain to a baby what the word "that" means. What do you point at? What do you say?

So it seems we start with the specific and work our way towards the general. We cannot point to the general; we can hope that other people will have the same impression of what we mean when we generalize, and we can define the general in terms of collections of specifics.

By the way, we just made an attempt to define what "define" means; for a first pass we can say that a "definition" is an "association between a proxy and a thing", where the proxy (also called a definiendum) might be a word or symbol, and the thing (also called the definiens) could be anything -- abstract or concrete, general or specific -- and could include some combination of things. For our purposes, you could say that "define" means "associate".

When you define a thing, you refer to the components of the thing. So those components must also have a definition. Eventually you run into things that you cannot define in terms of other things, and those are the primitives, i.e. the things that are innate to the system, such as integers and addition.

Back to the question at hand: What do "abstract data types" have in common with "abstraction in object-oriented programming"? Abstract data types have virtual methods which effectively get bound at run-time. Meanwhile, the notion of abstraction means that you can have multiple objects of the same class, all of which respond to the same operations.

These both have in common the idea that objects have methods.

Data abstraction lets you specialize the details of a generalization of a verb. This is also known as polymorphism. In contrast, OOP abstraction simply lets you operate on multiple instances of the same class using the same verbs.

In both cases, "abstraction" amounts to using the same symbol (method/verb) to operate on different objects.

And to perform those operations, the procedure that defines the operation needs to know something about its operand (the data).

In C++ this basically amounts to saying that the method receives a "this" pointer.

So, in our configuration language, the difference between a "table" (the means of combination) and an Entity (a means of abstraction) is that the methods of an Entity have access to the particular object (i.e. table or Entity) upon which the method operates.

And that all comes back to binding, which I discussed ad nauseum in previous articles. But I wonder if I covered it sufficiently.

Game Engine Configuration Language, Part 5: Means of Abstraction

2009-07-06T12:59:00.080-04:00

We want use our game configuration language to express solutions to specific problems in a way that meshes well with the rest of the language. In other words, we want to be able to extend the language in a way that blurs the distinction between intrinsic features that came with the language, and ad hoc features added to solve specific problems. The language facilitates this seamless extension via its means of abstraction.

Part 2 explained primitive data and the means of combining data into user defined types, but procedures also have primitives and means of combination.

Abelson summarizes a framework for abstraction in computer languages, which I paraphrase here:

	Procedures	Data
Primitives	+, *, ==	numbers, strings, true/false
Means of Combination	if, while, ...	Arrays, lists, dictionaries
Means of Abstraction	function definitions	Classes

Means of Abstraction

The means of abstraction amounts to how a language allows a programmer to extend it such that the view of the problem takes on a form more natural to that particular problem, rather than how the language would otherwise natively express that problem.

Consider machine language, which expresses procedures in terms most suitable for a CPU to use: Instructions include loading values from memory and placing them into registers, storing values from registers into memory, comparing values in registers, conditionally branching based on values in registers, unconditionally jumping to an instruction at another address, and performing arithmetic. That's all -- just those 5 kinds of instructions (plus a few more used for debugging and low-level stuff not really germain to solving computational problems). This way of phrasing procedures makes a lot of sense for a typical Von Neuman architecture, which has physical objects like memory, registers and arithmetic units built into hardware. But imagine trying to write millions of lines of machine language. Even if you never had to worry about porting to multiple platforms, this scenario constitutes a nightmare because it provides no way to divide the problem into chunks that correspond to a more intuitive description of the problem.

(Be careful, assembly afficianados. If you use an assembler, especially one that has macros, then you're already skipping two steps ahead of the point where I currently stand, which is in machine language -- or perhaps even microcode -- not assembly.)

Machine languages pose at least two barriers to solving a problem concisely: They deny programmers even straightforward conveniences like compound algebraic expressions, and they do not facilitate dividing and chunking a problem into a hierarchy of multiple, nested, modular subproblems, each solved at a different level of detail. Likewise, machine language has no formal notion that multiple pieces of data belong to the same set, nor that an element of data can have a structure with multiple pieces.

Higher-level languages like C ameliorate the first problem by providing higher-level control-flow constructs like if-then, while and for statements, which reduce the tedium of phrasing such common ideas in machine language. Likewise primitive "container" data structures like arrays (in C) or tables (in JavaScript) allow for aggregation of data. But those means of combination do not give programmers the power to change the language, in that the operations on those structures look the same as operations on any other structure. Means of combination provide the mechanism to put certain things in one place, but not to treat those things as first-class entities.

(As an aside, I'll mention that this series of articles has not yet described the how the game engine configuration language provides the means of combining primitive operations, nor even what those primitive operations are. The answer, ironically, is easier to explain after understanding the means of abstraction, so bear with me.)

This is where yet higher-level constructs come in: The ability to define a function creates the possibility of altering the structure of a program so that its description operates at a level commensurate with the domain of the problem, rather than the domain of the machine. And taken a step further, object-oriented languages allow us to bundle procedures and data together.

So providing a means of abstraction includes providing the ability to define procedures and possibly associating those procedures with a user-defined data type.

Tables as prototypes

This topic might seem familiar because Part 2 described using tables as a means of combination, and an earlier, rambling article presented the notion of "prototypes" which resemble a combination of objects and classes. But those articles lacked sufficient emphasis on abstraction, and specifically, how we should express abstraction in the source language. This ends up being related to binding, so review that article too.

The problem at hand then boils down to the following sub-problems:

How does the language express defining a new subroutine?

How does the language express invoking those subroutines?

How does the language facilitate creating user-defined types?

Defining subroutines

Our game configuration language has notions of Actions and Reactions. Both are named and both access data which technically resides outside of the scope of those constructs, so at first glance they both seem like subroutines. But it makes more sense to think of Actions as both primitives and as a means of combination, i.e. as a way to express a collection of instructions. Indeed, primitive Actions are the primitive operations of this language, and they are usually implemented in native code. And compound Actions, those which execute their contents, constitute a means of combination, because it allows grouping clusters of Actions together and giving them an order. Indeed, control flow statements such as if-the, while and for statements are readily expressed as compound Actions.

(Note that since Actions are tables, in the is-a sense), it is always possible for an Action to contain another Action. But when you do that, it does not always constitute a proper "combination" in a meaningful sense because not all Actions invoke, or execute, the Actions they contain. The analogy in C would be a struct that contains function pointers. A struct cannot execute its contents, so such a struct would not be a "means of combination" for procedures.)

In contrast, a Reaction contains an Action (which, by extension, includes compound Actions) and also has a name and creates a temporary scope which automatically binds calling parameters to the names used within the Reaction (and its Actions). So in our paradigm, Reactions play the role of the means of abstracting procedures.

Our game configuration language therefore supports defining subroutines via defining Reactions, where the event plays the role of the arguments and the activation record provides a way of binding event data to names used in the procedure definition.

Calling functions

Now that we see that Reactions provide the means of abstraction, it is clear that invoking subroutines amounts to throwing events. Done and done.

User-defined types

There are at least two contexts in which subroutines can live: When the subroutine is a member of a table, and when it is not. When a subroutine is a member of a table, and it has access to the particular table that is involved in the invocation, mere "tables" graduate from a means of combination into a means of abstraction.

As described elsewhere, our game configuration language supports "tables". The neato thing about this choice is that this choice, plus the choice of treating expressions as tables, and allowing tables to include tables, allows us to treat tables as both a means of combination and as a means of data abstraction. This dual role of tables is possible partly because of the fact that tables can include tables and that reference variables can refer to tables.

To graduate from mere collections of data into abstract data types requires formally associating operations with the table, such that the table itself has its own set of operations.

The trick involved is one of binding, which I (perhaps prematurely) discussed in part 3. So there you have it.

Coming up

Abelson describes the notion of a means of capturing common patterns, which includes higher-order procedures (i.e. procedures that operate on or with other procedures) and inheritance. I have touched on the topic of procedures that define other procedures, which is related. But perhaps there is more to consider when invoking a procedure from within another procedure. We need to consider how to alter the language so it can bind a procedure at run time.

Metalinguistic abstraction entails thinking of programming as creating languages to solve categories of problems, and programs as evaluators of those languages. Each of those languages has its own primitives, means of combination and means of abstraction. So maybe we will visit this topic in another article although it seems to me that this whole blog constitutes a discussion of metalinguistic abstraction, inasmuch as the blog discusses how to write a language. But maybe we can come up with a discussed which could be entitled meta-metalinguistic abstraction, in which we consider how to make the game configuration language suitable for use in solving even more specialized problem domains. Let's see how deep we can recurse before it gets intolerably silly.

Further reading

http://mitpress.mit.edu/sicp/toc/toc.html

Game Engine Configuration Language Part 4: Visual Programming Languages

2009-05-03T11:06:00.104-04:00

Game engine configuration languages should facilitate programming for non-programmers (e.g. game designers) to allow them to create game mechanics and autonomous entity behaviors. This problem has arisen through much of the history of computer programming, and for decades, people have tried to make computer programming accessible. Lately that trend has continued with some interesting new attempts. I want to review these languages with the hope that we can identify patterns -- what works and what does not -- and hope this guides our attempts to make a game configuration language which lets non-technical game developers the ability to control the interaction mechanic and other aspects of gameplay.

We can divide computer programming into at least two major components: data flow and control flow. We can categorize languages in terms of whether they principally focus on providing instructions (so-called imperative languages) or descriptions (so-called declarative languages). Imperative languages read like recipes -- a sequence of instructions (called a procedure) for how to accomplish a task (called a process). In contrast, declarative languages describe what results should look like, what properties they have, and the computer infers how to accomplish that. We should consider which of these is easier to understand and see whether we can construct a language accordingly.

Non-programmers struggle with the syntax of computer programs -- the grammatical rules that dictate whether a given sentence fits into the computer language. Computer language syntax is usually rather unforgiving, pedantic and arcane; even very small, seemingly insignificant changes in punctuation can drastically alter the meaning of a program. People have therefore made tools which strive to eliminate the possibility of writing programs with bad syntax. Such languages are often visual, in which authoring programs feels like constructing a physical machine. So in addition to constructing a game configuration language, we should consider how to construct a UI that assists authoring programs in that language -- since perhaps that will guide us on how to write the language.

In the study of formal language theory, the Chomsky hierarchy identifies connections between kinds of languages and the machines that can process them. Some machines are simpler than others, and perhaps we can exploit this fact to construct simpler languages. The resulting language should be easier to understand and use. The drawback is that the processes might be restricted but perhaps that is a Good Thing; perhaps non-programmers should have some restrictions on what they can do. Or perhaps the language can expose more sophisticated features only as-needed, such that non-programmers can use only the more restrictive, easier aspects if they choose -- then graduate to more complicated features when they become familiar with how they work.

After reviewing other language, I will propose adopting certain paradigms for game configuration languages: For AI, combine a finite-state machine (FSM) with steering behaviors. The language should facilitate both declarative and imperative paradigms. The authoring GUI should let user decide which to use, and provide a user-friendly visual dataflow interface with limited capabilities in addition to a text-based interface that exposes more sophisticated functionality for more advanced users.

Background

This section lists a sampling of computer programming languages intended for non-programmers or non-traditional programmers.

Alice: "Alice is an innovative 3D programming environment that makes it easy to create an animation for telling a story, playing an interactive game, or a video to share on the web. Alice is a freely available teaching tool designed to be a student's first exposure to object-oriented programming. It allows students to learn fundamental programming concepts in the context of creating animated movies and simple video games. In Alice, 3-D objects (e.g., people, animals, and vehicles) populate a virtual world and students create a program to animate the objects." Apparently Alice accomplishes its goal but its approach seems inappropriate for game configuration. I also find the GUI extraordinarily busy and distracting. Before you can learn to "program", you need to go through a rather long tutorial on how to use the Alice GUI. So even if Alice makes programming concepts more accessible, it does so at the cost of having to learn a complex GUI. Alice is fashionable in academia and worth knowing about but I do not find it inspirational for designing game configuration languages.

Kodu: "Kodu is a new visual programming language made specifically for creating games. It is designed to be accessible for children and enjoyable for anyone. The programming environment runs on the Xbox, allowing rapid design iteration using only a game controller for input." Although I have not read it described this way, it seems to use subsumption architecture -- the same scheme used by the "fast, cheap and out of control" robots. The GUI is elegant, pretty and engaging. The GUI only reveals elements that make sense in the context of what the user is doing at that precide moment, therefore is quite uncluttered. The user would therefore not get distracted by irrelevant aspects of the GUI. Kodu also effectively uses an FSM-plus-steering architecture, which I advocate. I would, however, change at least one aspect of the Kodu GUI: The fact that the user is effectively creating an FSM is never made visually explicity; each "state" (which Kodu calls a "page") can have a rule that would cause a transition to another "state" -- but there is no visual representation that shows the transitions between states. Also, the states have no meaningful name; they're simply numbered pages. So I would add the ability to label states with a meaningful name. More on that later. But in summary, I suspect that a person who had never seen Kodu before could walk write up to Kodu and, just by playing around, figure out how to write rather sophisticated programs. That's amazing.

LabView: "LabVIEW is a graphical programming environment used by millions of engineers and scientists to develop sophisticated measurement, test, and control systems using intuitive graphical icons and wires that resemble a flowchart. LabVIEW offers unrivaled integration with thousands of hardware devices and provides hundreds of built-in libraries for advanced analysis and data visualization. The LabVIEW platform is scalable across multiple targets and operating systems, and since its introduction in 1986 has become an industry leader." Programming LabView resemblies creating a "factory floor" where you have "stations" that process data and "conveyer belts" that shuttle data between stations. (These are my terms.) A lot of dataflow lanaguages use this same idea.

Pure Data: "Pd (aka Pure Data) is a real-time graphical programming environment for audio, video, and graphical processing." To me, this resembles LabView.

Unreal Kismet: Yet another dataflow language -- this one specifically written for game configuration. Kismet also includes "events". Kismet control flow follows dataflow. As values pass from left-to-right, so does control flow (which is typical for a dataflow language). In addition, Kismet actions have "variables" which do not "flow" or cause processes to run; they just provide access to data. Resembles Virtools and I think that aside from the complexity of its GUI, this is worth studying further. Tutorials I read do not mention facilities for abstraction i.e. the ability to cluster a dataflow graph into a user-defined graph with fewer inputs. Many aspects of the FIEA game engine configuration language resemble what must be the underlying virtual machine for Kismet.

Virtools: Yet another dataflow language specifically for configuring simulations. Programs consist of "building blocks" (BB's), whose visual representation is arcane. Like dataflow nodes in other languages, BB's have inputs, outputs and variables, but the GUI does not label them so they just look like distracting decorations. Virtools also has "messages" which I believe are like events. I suspect the features of Virtools and Kismet are probably quite similar, but I find the Kismet GUI looks more intuitive -- but perhaps only slightly. Neither is obvious.

Further Reading

Have a look at these resources for more examples along the lines of the above systems:
Boshernitsan & Downes (1997): Visual Programming Languages: A Survey
ARK: Alternate Reality Kit (1986) for simulations, based on Smalltalk.

VIPR: Visual Imperative PRogramming (1994): Object-oriented. Nesting rings dominate diagrams. Inscrutible diagrams for anything more than trivial examples.

Prograph (1982): Object-oriented, imperative, dataflow determines flow control. Commercially available for a while. Shortcomings include messy diagram organization (user controlled) and unlabeled classes and inputs.

Forms/3: spreadsheet.

Cube: 3D programming language.

Nickerson (1994) Missing lots of figures which, for a survey of visual languages, is quite an impediment. Furthermore I was unable to find examples on the web of several topics covered there; one would probably have to obtain print versions of his references, and they are all out of print. What diagrams it contains are unreadable in some cases. It covers a lot of diagraming conventions.

H-graphs: expansion on detail of a state which contains substates.

PICT: resembles typical flowcharts.

Blox: puzzle pieces represent program structure.

Show-and-Tell: iteration results in a list of each value.

Programming in Pictures: Not imperative.

Garden: meta-language meant for constructing visual languages. Can build FSA, dataflow and flowchart languages.

Summary

Dataflow languages provide a visual programming environment which alleviates the problems of understanding and following pedantic computer language syntax. But the "visual grammar" can also be difficult to leanr, and diagrams for complicated procedures can become unwieldy. Loops difficult to implement because each block has no state, so input data needs to contain state (e.g. loop index variable), which is awkward in some dataflow languages, but others seem to solve this problem by discriminating between "variables" (which provide access to data) and "inputs" (which trigger control flow).

Although the hybrid dataflow-causes-control-flow paradigm seems to work, I wonder whether using signals/events/listeners introduces a lot of overhead for processing small signals. When messages point to huge arrays, overhead is acceptable but for single values, overhead costs more than the regular processing.

Dataflow languages can also model blocks as having explicit control-flow sockets in addition to having data sockets. The control-flow sockets depend on data, messages or signals. So each block effectively becomes something like a multiplexor or switch-case statement.

Game Engine Configuration Language, Part 3: Binding, revisited

2009-04-15T19:56:00.099-04:00

Introduction

In previous posts, I mentioned binding schemes and advocated using dynamic binding. I hereby retract that statement (at least partially) and revisit the topic in this article.

Consider how object-oriented languages express the association between data and its procedures, and how to invoke those procedures on an object: Make procedures "members" of the class (just as it has member variables). Member functions (a.k.a. methods) that refer to member variables do so implicitly by dereferencing a pointer to the current object. Inside the method definition, C++ expresses that as "this->mVar" where "this" is an implicit pointer variable that contains the address of the object.

Callers invoke methods using the syntax "object.Method()", where the address of "object" gets bound to "this" upon invocation. C++ takes this one step further and allows programmers to omit the "this->" portion of the syntax so that it appears as though the object itself is inside the scope of the function definition, and that the member variables are dynamically bound at runtime. (In fact, in a previous post I pointed out the similarity between this sort of binding and dynamic binding.) Object-oriented parlance calls this invocation technique "message passing" -- the caller passes the Method message to the object which receives and handles that message.

In a later article, I will discuss message passing but for now let's take a detour into name binding, because we need to sort that out before dealing with the reset of message passing semantics.

Background

Last time I covered the data type system in the game engine that FIEA graduate students write each year in the programming 2 class, including the primitive types (int, float, string, reference, pointer, etc.) and the means of combining them (tables with name-value pairs). I mentioned notions of "functions" and also tossed around the phrase "means of abstraction" (which refers to how we can extend our language) and now return to elaborate on those topics.

But before diving into those topics, I need to review a few other notions, and partially retract some of what I wrote last time, specifically the proposal that we use dynamic binding for function calls.

[Retraction: I stated in the previous post that functions do not need to be their own type. While that is true, the dynamic resolution needed to differentiate between tables and tables-that-are-functions incurs avoidable runtime overhead. Furthermore, the fact that tables-that-are-functions could be distinguished from tables-that-are-not-functions does not, as far as I can tell, improve the language in any way. So functions should be their own type. So that whole avenue was bone-headed and I regret having posted it.]

We need to understand the notion of "binding" -- associating a value with a name -- and the flavors of binding -- static and dynamic.

Binding

In a previous post I exposed the difference between static and dynamic binding, but I will briefly review those concepts, and clarify their differences with a pair of examples.

Binding refers to the process of associating a value with a name, i.e. associating an address with a symbol.

Static Binding (a.k.a. early binding) resolves which value goes with a name at compile time. In contrast, Dynamic Binding resolves names at runtime. The following example demonstrates the different between these approaches. Consider the following code (written in a made-up language):

procedure int procedure(int) MakeProc( int y )
{
return procedure int lambda( int y )
{
return x + y ; // What is the value of y?
}
}

procedure Caller()
{
int y = 5 ;
procedure newProc = MakeProc( 7 ) ;
int z = newProc( 3 ) ; // What is the value of z?
}

The value of "z" in the example above depends on whether the language uses static or dynamic binding. If it uses static binding, the answer is that y=7 inside lambda(because y comes from the value passed into MakeProc) and therefore z=7+3=10. If it uses dynamic binding, the answer is that y=5 inside lambda (because y comes from the calling environment, i.e. Caller) and therefore z=5+3=8. In the dynamic binding example, the value passed into MakeProc is not used.

This example reveals two aspects of dynamic binding which are bad: It violates the principle of least surprise (since it seems like y should be bound in the callee environment but is bound in the caller environment) and it means that the lookup for y occurs upon each invocation of newProc instead of once (at compile time).

Tricks that make static binding look dynamic

True dynamic binding implies performing symbol table lookups at runtime, which we want to avoid, because it is expensive.

In some situations, however, we want the appearance of dynamic binding. For example, we want "this" bound to the object receiving the message. And when the method is virtual we actually want to bind the method itself based on the type of the object, which gives the appearance of dynamic binding for the function -- not just its data.

But these forms of late binding are not truly dynamic in the sense that the names are resolved at runtime. In fact, the names are resolved at compile time, using a combination of tricks including offsets and pointer variables. So although the C++ style of quasi-dynamic binding increases the level of indirection, the binding occurs at compile-time. Some languages have true dynamic binding and perhaps that gives them an expressive power lacking in statically bound languages, but those languages elect to pay for that expressivity with reduced performance.

Though dynamic binding might give the language some elegance (because such languages can avoid trickery like using offsets and increased indirection), a game engine requires higher performance, so we cannot afford dynamic binding.

Let's take a look at some forms of quasi-dynamic binding and how compilers achieve the illusion of dynamic binding with the performance of static binding.

Binding local variables

Activation records include space for local variables. (Usually that record exists on a call stack.) All references to those local variables occur via indirect addressing, using indexes relative to the address of the top of the activation record. In other words, this uses a pointer and an offset. The offsets are effectively "baked" into the structure of the activation record, i.e. fixed at compile-time.

(In optimized builds for modern machines, local variables are likely to be in registers, but let us ignore this complication because it does not apply to virtualized languages such as our configuration language.)

Binding actual arguments to formal arguments

Actual arguments closely resemble local variables except that the caller provides initial values for those variables. But the code that references them also uses the same trick of using an address (stack pointer) and an offset from that address.

Binding member variables within methods

Member variables are accessed using an offset relative to the address of the object accessed. So once again, binding occurs using an address and an offset, but this time the address is the top of the object, not the activation record.

Binding virtual methods

Virtual methods are dereferenced by first accessing an offset from the address of the top of the object (i.e. just like a member variable) which is itself a pointer to a function table. Each method has an offset in that table, so requires yet another address-plus-offset dereference. So it's the same trick applied twice in a row.

Binding "free" variables

Free variables only exist in languages which allow the creation of functions at runtime. In such languages, the created function can refer to variables defined outside the scope of that function. In that case, the function has an associated "closure" which is a data record that includes the values of variables at the time the closure was created. The code inside the function effectively refers to those "free" variables by dereferencing the address of the closure, plus (you guessed it) an offset for the specific variable. So once again, this uses the address-plus-offset trick, with yet another record.

So in each case, statically-bound languages reuse the same trick (address-plus-offset) over and over, except that each case uses a different address:

Locals and arguments <-- --> address of activation record
Members <-- --> address of object
Virtual methods <-- --> address of object, then address of function pointer table
Free variables <-- --> address of closure

Abstracting from this pattern we can say that the compiled code always dereferences some member of some record, where the address of the record resides in a a pointer variable. The offsets are fixed at compile time (hence are statically bound) but the pointer variable is assigned at runtime (hence resembling dynamic binding). So although the cost is not as low as using immediate addressing, a pointer dereference certainly takes less time than a symbol table lookup. Also, if all of the offsets are contiguous then only the first pointer dereference is likely to have a high memory fetch cost; subsequent access to adjacent members are likely to be in cache already.

Tying this to the engine configuration language

The game configuration language will not use the exactly same techniques that a regular compiler uses but it we can perhaps take inspiration from those techniques. Clearly the recurring theme here involves dereferencing an address of a record (which, in our language, we call a "table") and an offset into that table. Our tables can indeed be referenced by offset, so this approach seems promising.

I leave the details for another post but this article clearly implies heading in a particular direction.

Game Engine Configuration Language, Part 2: Primitive data and means of combination

2009-03-02T16:05:00.055-05:00

Computer languages concern themselves with data, its properties and operations. Designing a language consists in part of designing a type system which entails notions of how to store, address and operate on data. Types define what you can and cannot do to data. Types also help manage complexity by organizing data into collections, and by providing a means to verify correctness. Furthermore, we discriminate between "primitive" types (which the system, whatever that is, operates on) and "user-defined" types, which the programmer creates within the language.

In designing a language meant to express the configuration of an interactive simulation with visualization, what primitive types should we support, and how shall we express the means of combining those primitives into compound types useful for a specific simulation? As with this entire series, we further constrain the solution to our problem to one which a graduate student can implement in a single semester.

Data Type System

As with other dynamically typed languages, variables in our game engine configuration language do not have types; values do.

The language provides no mechanism for defining a type. Our language is "prototype-oriented" (in contrast to object-oriented) so we make no distinction between "class" and "object".
In the parlance, our language has "structural equivalence under naming" which means that if 2 objects have members with the same name and type, and an operation exists which requires those properties, then in that sense the objects have the same "type". This is also called "duck typing".

Primitive Types

In "The Structure and Interpretation of Computer Programs", Abelson and Sussman state that for any computer language we should ask, what are the primitives and what are the means of combination? (They also ask, "what are the means of abstraction?" which we defer to another article.)

Primitive types are those which the system (either the hardware or the virtual machine) can process natively, i.e. without instructions from within the language.

Numbers, such as integers and real numbers, are the most common form of primitive, both in hardware and in computer languages. Computer hardware has arithmetic units that operate on integers and floating-point values, but these are separate units. The integer unit is distinct from the floating-point unit, and mixing those operations causes tremendous inefficiencies. We therefore strive to keep computations within a single realm and avoid conversion between those types. The configuration language should reflect that choice, so we discriminate between integers and floating-point values.

Integers come in many flavors, based on their size (byte, short, long) and range (signed, unsigned) but for the sake of simplicity and computational efficiency we restrict our configuration language to signed integers of the size the native machine handles most efficiently, i.e. a plain-old "int". Likewise, floating-point values come in a variety of precisions (half, single, double and quad) but gaming consoles typically treat only single-precision floats efficiently, therefore our configuration language only supports that flavor.

In contrast, Lua only supports a "number" type, and you can choose its representation at compile (e.g. int, float, double, long or whatever) but I find this too restrictive. Integers and floats have rather distinct usages and mixing them leads to grotesquely slow arithmetic operations.

Interactive simulations with visualization (such as video games) commonly require vector and matrix operations, and modern CPU's have special instructions (e.g. SSE, VMX) that operate on those types, so we incorporate "vector" and "matrix" as primitive types in our language. This again departs from the choice in most scripting languages, but in my opinion, to the detriment of speed.

Some languages (e.g. Lua, C++) treat Boolean values as primitives but we shall not since, following the same logic as above, the native hardware does not recognize a "Boolean" type -- it only operates on integers (which are a superset of booleans anyway). C++ restricts the value of "bool" to be 0 or 1, and I imagine that takes some overhead. We can have our system give some integers special treatment, though. We can adopt the convention that integers whose names start with "b" shall have a value of either 0 or 1, and in debug builds we shall assert on that condition. We can therefore be informed of departures from that, but in release builds we can avoid the computation overhead associated with that restriction. So we'll consider this the "trust but verify" policy of bools.

Means of Combination

Most computer languages support some means of combining primitive types into compound types, called "records", "user defined types", usually implemented as a list, structure or table. The various implementations have different properties.

Lists are extremely simple but not cache friendly and can only represent name-value pairs by nesting lists -- elegant but slow.

Structures order the data such that we can access members by an integer offset from the first element of the structure. This is the fastest technique since all the offsets can be computed at compile time.

Tables, or associative arrays, implemented as hash maps, allow access to each member by a "name" which is usually a string of human-readable characters, but sometimes is an integer (as in an array).

Array access is fast but access by name is more useful for abstraction. Lua uses a hybrid table with 2 subtables, one using a hash map, the other using an array, and uses a sophisticated algorithm to decide which subtable to use to store any given member. Our language should strive for the benefits of this approach, but in the interest of time we want a simpler solution. So in our language, hash tables represent records, but each element in each table is, in general, an array. Note that each element in that array has the same type, so this lacks the versatility of a Lua "array" in that, in a Lua array, each element can have a different type. But our language also supports that in the sense that our language supports arrays of references, and also supports a table whose index values can be any string, including a representation of a sequence of integers.

Structs provide the fastest access of these options, and we can obtain a similar fast access of offsets by using a dynamic array container to store values, and using a hash map to access the contents of that array by name. This fixed ordering implies that we can never delete members from a table (though we can remove values from any member, or otherwise make them "invisible") -- but I have never wanted to remove members from a table, and many languages do not support deleting members anyway. This array&table scheme lets us access any member by index (which is much faster than even hash table lookup). In many cases, we know that index because we can prescribe it at compile-time. For types defined in native code at compile-time, we can initially populate a table's attributes using a well-known order, and thereafter access those "prescribed attributes" by index. We can also still append more values to the same table, at runtime, so prescribing attributes at compile time does not restrict the utility or extensibility of the table. Furthermore, no script code needs to know or care about this optimization. It's a nice bonus for a very small price.

Functions and methods

[Note: In a subsequent post, I retract some of the proposals made in the following subsection: That functions do not need to have their own type. While this is technically true and I did try this notion on for size, and it does work as described below; the benefits, if any, do not outweigh their costs.]

[Also note that, in a subsequent post, I clarify the mechanism for binding actual arguments to formal arguments, and it turns out that the ideas expressed in this subsection suggest using something akin to dynamic binding which, although it has some nifty benefits, turn out not to do what I want. So in a way, I also retract yet more of the following subsection.]

Lua and most other computer languages represent procedures as their own type, distinct from other types. A procedure differs from other types in that it can be invoked. But in a dynamic language (such as our configuration language) this distinction only matters when invoking the procedure. I argue that this distinction is one that the runtime needs in order to execute the process, but not one which our language grammar needs to know about, because of the peculiar way in which we represent procedures.

In Alonzo Church's treatment of lambda-calculus, a function binds variables (parameters, a.k.a. arguments) to a scope. Parameters have 2 flavors: Formal parameters which the code in the function body sees and actual parameters, which the caller passes into the function. Usually, the meaning of those parameters depends on their order in the argument list. These are sometimes called "positional parameters", in contrast to passing parameters by name. In addition to parameters, functions also have "local variables" and "free variables". The local variables are defined within the scope of the function and "free variables" are defined outside the lexical scope of the procedure, somewhere in the "environment". When a function is created, the "free" variables are bound using a "closure", which is a topic for another article, and which some languages do not support, so let's ignore them for now. The remaining variables, the arguments and locals, are similar in that their lifetime matches the function call itself. When the function is not "active", those variables do not exist. When the function is "active", those variables exist. So those variables are part of the "activation record", which is a piece of memory valid only during the function call.

In our configuration language, we have not yet made a distinction between an "argument" and a local variable -- and until we find a reason to make such a distinction, we will avoid it. We shall (effectively) pass in parameters by virtue of establishing an "environment". In other words, it turns out that we can treat all 3 kinds of variables (free, local and bound) as the same thing -- a table. And indeed, the table is the procedure. In its present incarnation, our type system has no separate "function" type. It is just another table. Behind the scenes, it is a table that happens to know how to execute its content -- and not all tables know how to do that -- but we could equivalently say that all tables respond to messages, but most do nothing in response.

This treatment of functions as tables simplifies our system because we can copy functionality just as we can copy other properties -- and in a prototype-oriented language, that means we can assign behaviors to objects by copying them from something that already has that behavior. Nice!

References, Pointers and Passing Semantics

Imagine you want to write a function that changes the value of an argument. Maybe the function increments a variable, or swaps the values in 2 variables. You can only accomplish this by passing the variable itself (not its value) into a function. Languages can accomplish this using "pass-by-reference" or "pass-by-name". Suffice it to say that "pass-by-name" is problematic but that if we really want, we can support that by passing in a string, and looking up that string, at runtime, in the current environment. It's slow but powerful -- probably more powerful than we need most of the time. So let's consider pass-by-reference.

Technically, C only has pass-by-value, meaning that when you write the code associated with a function call, the values of the arguments are delivered to the function. While that is true, one of the value types in C is an address, which pointer variables can store. C provides a syntax for "dereferencing" pointers, meaning that the expression refers to what the pointer points to, i.e. its contents, a.k.a. the referent. So in this sense, C supports pass-by-reference semantics, even though the syntax differs.

Java, its pundits claim, has only pass-by-value semantics. But that is either pedantry or misleading, depending on your tolerance for misinformation. Either way, I call it "false". Their loophole is that some variables are primitive "value types" and some are object "reference types". That means that depending on the type of the value, the variable either contains the value itself, or simply points to the place in memory that contains the value -- and you as a programmer have little or no control over which is which. So if you write code that syntactically has the effect of changing the value in a variable, then the same syntax has drastically different meanings depending on the variable type. And I don't mean "drastically different meaning" in the prosaic sense that different types have different interpretations -- because when you swap 2 values, regardless of whether the values are integers or Canada geese, at the end of the day, you expect the 2 to be swapped. But in Java, that is not the case. Functions that operate on value types affect only local copies of the values, whereas functions that operate on reference types affect the referents themselves. So you can call that "pass-by-value" if you feel like living in denial and confusing would-be Java programmers, but I call it pass-by-reference, and I can usually sleep well at night.

In any case, we just want to answer the question, how should we facilitate authoring functions that can operate on referent values (not just copies of values passed in for temporary manipulation). Or put simply, what if we want to write a function that swaps 2 values? Once again, I take inspiration from asking, what does the underlying hardware support? The answer is that it supports addresses, i.e. pointers. Our language therefore supports these, in 2 flavors: references to other data (i.e. data that the configuration language understands, including primitives and tables) and opaque pointers to "native" data. The key here is that references can point to either primitives or tables.

What is this abomination of opaque pointers? Remember that our configuration language spans two realms: the script side, which we configure at runtime, and the native side, which we configure at compile time. In the interest of speed and memory, we sometimes (often) implement functionality in native code (i.e. C++) but which to expose only a fraction of its data to script (i.e. not all of that data is driven by configuration files). The "opaque pointer" gives us that out. Lua also supports this notion of opaque pointers, which it calls "user data".

Lua does not, as far as I know, support references to primitive types. Java and C# do effectively support passing primitives by reference, by creating an object manged by the garbage collected heap, which wraps the primitive value. In C# this is called "boxing" and it's build into the virtual machine. It's ludicrously slow, though, for something so simple -- so slow that you just wouldn't use it. So although those languages technically support the feature I describe, you wouldn't use it for a performance-sensitive application like interactive simulations.

Names and Strings

We can use a hash table to map names to values, but what if we want to find the name of a variable, given its "address" (e.g. index or offset or whatever) in a table? We have a few choices, and I consider this somewhat of an open issue because it's not yet clear which choice works best. The most obvious choices include "fast but messy" and "slow but simple". The fast-but-messy solution entails entangling data and names by having data point to their names, or by representing name-value pairs in a way that gives us fast access to both given an index or address. Sounds simple but I believe it is unnecessary -- especially when you consider that the name of a variable can often be discarded after parse time. That turns out to be a complicated subject. Anyway, in contrast, the slow-but-simple solution entails doing an exhaustive search through the table, to find the entry which matches the given address. "Exhaustive search" here sounds worse than it is, since the search tends to be localized to a single table, which rarely has more than a few members. Furthermore, we have to ask, why would we perform these "reverse lookups" anyway? Examples entail reflection and serialization. Do we need to perform those during the execution of the simulation, or only during authoring? If only during authoring then we can probably tolerate slow-but-simple. But during some copy operations, we might need reverse-lookup during the normal operation of a game. I'm not yet sure. Ask me later.

Usually, strings used for the names of table data do not change. Furthermore, those names tend to repeat, i.e. the names of members in one object tend to appear as the names of members in another object, because our system uses the prototype-oriented paradigm (i.e. objects tend to be copies of other objects). This means we can "recycle" strings by using a reference-counted string subsystem. This reduces memory usage since each unique string occurs only once. By clever use of reference counts and operator overloading, we can automate this so that the client code does nothing onerous to gain these benefits -- just use a different type, e.g. RString instead of String. Furthermore, when using these ref-counted strings, string comparisons reduce to comparing pointers, instead of the notoriously slow strcpy, which iterates over every character and performs at least 2 (usually 3) conditional branches per character. Nightmare. So, use ref-counted, consolidated strings for the "key" part of the key-value pair in the hash tables.

Summary

By gleaning examples from other scripting languages but paying close attention to the specific needs of our configuration language, we constructed a type system which is simple, powerful and efficient. It has familiar aspects, it supports the means of combination to allow runtime extension and its underlying implementation mirrors what the hardware supports natively. Even with the restriction that students have only 1 semester to implement this system, it should provide adequate functionality to serve as the basis of more sophisticated systems they develop in their professional careers after graduation.

Game Engine as Operating System, Part 2: The Actor Model of Concurrency

2009-02-02T20:35:00.147-05:00

ABSTRACT

The Actor model of concurrency readily lends itself for use in the FIEA game engine, which is already set up to be an event-driven system composed of entities (which resemble actors). This prepares the engine to exploit future massively parallel hardware platforms and avoids some of the worst problems of concurrency -- synchronization and deadlock -- and minimizes contention. The changes required do not affect the configuration language -- just isolated parts of the back-end and some environment access policies. But the asynchronous communication scheme required by a strict Actor model implementation can incur excessive performance hits for reply-request transactions so we probably have to make an exception for those transactions.

INTRODUCTION

In this series of articles, we review operating systems concepts in the context of making a game engine. Operating system concepts include process, memory and device management. Process management entails processes, threads, scheduling and synchronization. This article visits the topic of process management, and focuses on the Actor model of concurrency as it relates to game engine architecture.

In the Actor model, an actor is a computational entity which sends and receives messages, makes decisions and creates other actors. This bears some resemblance to entities in the FIEA game engine, which send and handle events, receive a share of CPU time each frame, and perform arbitrary processing.

Though some cursory attempts have been made to thread it, the FIEA game engine lacks an inherent concurrency infrastructure. Conventional wisdom suggests that computers of the future will have many more processing cores operating at about the same speed they do now. We therefore explore the possibility of formally adopting the Actor model of concurrency as an integral part of the FIEA game engine and its configuration language.

Related Articles

Ruben Vermeersch describes how using the Actor model is easier than threads.

The blog "Valued Lessons" has an article about message passing concurrency in Python.

James Leigh describes Utilizing a Multi-Core System with the Actor Model.

The SALSA Tutorial provides a description of the Actor model which focuses on practical use.

Gernot Heiser discusses the microkernel performance debate, which relates to this discussion in that microkernels are essentially message passing systems in an interprocess communication system.

THE CASE FOR ADOPTING THE ACTOR MODEL

The FIEA game engine processing model happens to resemble the Actor model - except that the engine is not (in its usual form) concurrent; although all the entities operate almost as though in an extremely simplified cooperative multitasking system with rudimentary time slicing, they do not actually operate in separate threads (though students have introduced actual multi-threading with some consideration for synchronization). With other changes afoot regarding how entities access their environment (with more strongly enforced scoping), switching to the Actor model might be easy.

But why bother? What would it buy us? And what would it cost?

Avoiding Deadlocks

The question should not be whether to support concurrency, but how. The fundamental problems boil down to deciding which processes to run on what threads, and how those threads should communicate (and synchronize). An obvious and common choice entails simply creating threads and running processes on them, communicating via shared memory which is synchronized via locks. This scheme, however common, invites dreaded deadlocks and contention issues. So although we definitely want concurrency, we would like a model free of deadlocks.

Recall the Coffman recipe for deadlocks:

The system must synchronize via mutex locks or their equivalent. This is unavoidable at some level but we can limit the number of locks.
Processes already holding a resource lock can request another lock, i.e. multiple locks are involved.
A process holding a lock cannot be forced to release that lock.
Multiple processes must attempt to obtain the same resource.

I boil this down to the following: Multiple processes must attempt to obtain multiple locks in different orders. You can avoid deadlock by strictly requiring that the order in which processes obtain locks is globally uniform. That is guaranteed to eliminate deadlocks but it poses some problems, such as being aware at all that this situation can arise; in large code-bases with multiple programmers, that is hard. Furthermore, obtaining locks in a strict order implies that in many situations, a process will obtain locks that it usually does not require, on the off chance that it might require it while holding another lock; this creates otherwise avoidable contention.

The Actor model breaks this chain by disrupting the hold-and-wait condition; actors never hold multiple locks because all of their communication with other actors (which is the only communication the model supports) happens via asynchronous message passing. From the perspective of the Actor, it never holds any locks, ever. So, no deadlocks.

Adopting a strict Actor model so implies that theoretical results written about that model apply to the engine. Although so far, I am not personally aware of thunderous earth-jiggling benefits of that fact, research into the Actor model is ongoing and perhaps somebody will conclude, using the Actor model solves Important Problems.

Each actor runs in its own thread and, as far as other actors are concerned, that could be on another machine on another planet. The language Erlang exploits this to support hot swapping code. As Vermeersch states, "To allow for non-stop application, Erlang support hot-swapping of code. This means that it is possible to replace code while executing a program, making it possible to do upgrades and maintenance without interrupting the running system." Imagine never again having to log off of WoW for a client or server upgrade. That's freaking cool.

Alright, so the Actor model looks attractive. How would we implement that in the FIEA game engine? And if the Actor model has a feature or limitation we do not like, what are the ramifications of departing from this model?

Buffering Messages

The Actor model specifically avoids posing requirements on how messages are ordered. In this regard, processes in such a model act like remote peers in a packet-switched network using UDP -- the deliver order is not guaranteed. The upside is that if a simulation based on the Actor-model actually uses a protocol upon UDP, then the network code will not have to spend extra effort ordering packets.

The downside is that sometimes you want to guarantee delivery order. Some systems (e.g. Scala) provide mechanisms for synchronous delivery (which can be used to guarantee delivery order), but the synchrony has the potential to violate the terms of our "no deadlocks" coupon.

The ordering could happen inside the "mailbox" implicitly associated with each actor. Messages could include ordering information. The actor could simply allow messages to queue up until a contiguous sequence of in-order arrives, at which point the actor can process them. This would not violate asynchronous delivery. It adds complication to the message processing subsystem but let us consider the problem effectively solved (in theory), should the need arise.

Often message-passing has the form of request-reply, where an entity simply wants information from another entity. In the strict Actor model, this transaction would require a pair of asynchronous messages, which can introduce undue latencies and inefficiencies.

Recall that part 1 described how asynchronous message passing introduces computational inefficiency; there are twice as many synchronizations happening (each of which entails an expensive context switch) and the message data has to be copied both into and out of the message buffer. In contrast, a synchronous request has only a single synchronization primitive and can avoid copying message data at all, if the replier processes the message immediately (which is likely). L4 exploits this to make great performance improvements over other microkernel designs (like Mach) which use asynchronous message passing.

Request-reply is a subset of the synchronous communication problem, in that we can make special exceptions to how the request is posed. We have several options:

Implement the policy that if a request is made, and the queried entity is occupied at the time of request, that the request simply fails, and that code must be written to handle that. This seems complicated and awkward. Worse, it could create livelock which is even worse that deadlock.
Rephrase request-reply cases so that any entity that might need information from another simply subscribes to that information and automatically receives it when it changes (i.e. uses observer a.k.a. publish-subscribe design pattern). This avoids latency at the risk of some possibly avoidable overhead, if the information is not needed each time it changes. This also avoids needing to treat the situation as a special case; the system described so far can already do this. Let's keep this in our back pocket.
Partition entities to run in the same thread, in which case contention would be impossible. This has the potential to have the least overhead since it avoids the need for a lock, but also increases the granularity of concurrency.
Allow synchronous communication only for request-reply transactions. This increases the chances of contention, though, since the requester has to wait on the replier, which in turn could be waiting on another replier. This seems like a recipe for deadlock: A replier could block while waiting on a reply from its requester (or in a transitive chain of requesters). (But L4 implements synchronous message passing, how does it avoid deadlock? By the intelligence and care of its authors.)

In practice, we can apply a combination of the above techniques, depending on the situation. Synchronous communication is the most efficient but it re-introduces the possibility of deadlock, so it misses one of the major advantages of the Actor model. Aside from the infamously poor performance, old microkernel systems are also notorious for deadlocking. Since this article argues in favor of adopting the Actor model based in part on the avoidance of deadlocks, it seems inappropriate to simply toss that feature out for the sake of performance. But performance is critical so we have a real dilemma here. It's an open issue and I welcome discussion.

Locality: Who can send messages to whom.

In the Actor model, actors do not share any data whatsoever. Only messages can route data between Actors. That implies no access to global variables or static methods in the traditional sense. I believe that would not impose undue issues, if pressed, but for the sake of efficiency I believe we could make exceptions for read-only data such as controller input and the current time.

HOW TO ADOPT THE ACTOR MODEL

The FIEA game engine can implement the Actor model with minimal change to the configuration language. Messages would be passed via the event system (as is done now). A restriction in scope resolution syntax and/or rules would disallow accesses to non-local data. Then behind the scenes we serialize the event system and can run each Actor in its own thread. Magic.

Heck, for the sake of debugging we could even randomly reorder events in the queue -- to test the robustness of message handling out of order.

A few other details. In "traditional" terms, each actor runs in its own thread and has only 1 lock -- a lock on itself. Effectively, every "reaction" in the actor is a critical section. Actors only process requests; their "process" is just a sequence of event handlers. That means that even the "update" loop itself would have to be written as a response to an "update" event, which gets thrown periodically. In other words, it would NOT suffice to consider each entity as a process that runs the "simulation" process all of the time, and handles messages on-demand. The "simulation" process would be just another event handler like any other. No big deal.

Also, rendering would require some intermediary since it involves sending data (a message) to yet another actor -- a special one which has a monopoly on the GPU. That's not trivial, but it also aligns with how rendering happens on multi-threaded game engines anyway. In fact, usually the rendering of an actor happens in a monolithic process (which we can model as an actor) which serializes all rendering. Essentially, rendering consists of populating vertex buffers and issuing draw calls. Populating vertex buffers can happen anywhere. Only the draw calls (and the associated render state setup) has to happen serially. So it seems prudent to isolate those two processes. And indeed the FIEA game engine already does that. It currently, however, happens to issue the draw calls as though it happens from the entity itself. That would have to change to a scheme with a single entity which mediates all draw call submission. The details of that subsystem constitute a topic for another post.

CONCLUSION

The benefits of the Actor model outweigh the costs so we could adopt it. The Actor model provides concurrency free of deadlocks and prepares the engine for the promised massively parallel game consoles of the future. The processing management subsystem of the FIEA game engine lends itself to using the Actor model with minimal changes to the configuration language.

This is just a start. We still have to consider process migration. For architectures like the PS3 and its weird little SPU homonculi, process migration is not just a whiz-bang nice-to-have, something akin to it is required. But it seems like such changes can happen behind the scenes and, once again, the configuration language would not have to change to support it.

PENDING ISSUE

It seems that we cannot have both the guarantee of a deadlock-free IPC system and also have efficient request-reply transactions, so this issue remains open for debate. I have proposed a few options for request-reply. Perhaps it would be appropriate to try some or all of them and see what works best. In any case, it makes for an excellent discussion topic. How should it work?

Post your comments!

Game Engine configuration languages: Part 1: Introduction

2008-12-24T23:09:00.168-05:00

ABSTRACT

Game engines include a framework for holding pieces and a configuration language for describing the details how to use those pieces to make a particular game. This blog covers those topics somewhat separately. The "Game Engine as Operating System" series describes the framework itself. This series entitled "Game Engine Configuration Languages" considers how to design a computer language to satisfy the requirements of a game engine. These topics are intricately related so this blog will alternate between the two topics.

INTRODUCTION

Game engines are a framework for creating interactive simulations with visualization. Visualization includes graphics rendering, audio playback and tactile feedback. Simulation includes physical and cognitive (i.e. "AI" or autonomous characters) aspects. Interaction primarily entails processing controller inputs to change game state. These elements are important but, taken in isolation, these are solved problems with ample attention. Not explicitly included in those elements, however is fun.

To fully answer questions about how to make a game engine which facilitates making something fun, we have to gather requirements from game designers to learn their process. This blog does not aim to discuss game design; I am not an expert in that area and have no great ambitions in that direction. But just has we do not have to become a artists to create tools in service of artists, we do not have to become game designers to create tools in service of designers. We do, however, have to understand their process and cater to their requests.

For the sake of making progress on the technical side, I will paraphrase relevant game design principles as I understand them, which is likely flawed and incomplete, but which will give us a starting point (from which we may later depart) in our attempt to provide superb tools for making great games.

The fun in games, one can argue, comes from structured game design paradigm and its successful application requires a focus on iteration of core gameplay mechanics (not just renderable assets).

Whereas the architecture of a game engine provides the components necessary to assemble a game, the configuration language of the engine describes how those pieces assemble.

Previous work

Existing professional game engines focus on rendering, physical simulation and run-time performance, not on usability or flexibility. Most game engines are best at making some characteristic game. We can consider separately complete game engines, game engines built upon middleware that provides many facilities, and scripting languages that provide the glue that binds middleware pieces into a coherent whole. I don't intend to evaluate game engines or middleware, only to review their properties and make the case that game engine technology needs to focus on a crucial missing element, which is a focus on rapid iterating on the gameplay mechanics themselves.

Complete game engines tend to have been extracted from some successful multi-level game which had a reasonable facility for changing game content, and therefore those engines tend to excel primarily at games that resemble the original game. Unreal does a good job at making character-based shooters and is famous for its great editor, but it is also infamous for being miserable to understand and extend. Warcraft does a good job at making top-down real-time strategy games. Likewise, Quake and Cry are well suited to making games that resemble the originals that made them famous. While it is probably possible to make (for example) a driving, role-playing or sports game using an FPS engine, it seems like the benefit gained would be marginal and much of the code that manifests the gameplay elements unique to the new game would exceed the code provided by the engine itself. Most of the overlap would come from rendering and physical simulation, not from gameplay or interaction.

Virtools seems like it might have the essential features I'm advocating. Check out this (somewhat dated) review of Virtools. It seems like Virtools has focused on building behaviors but they fall short in iterating on regular assets (like models, textures, etc.). And their support for character animation is limited. And Virtools lacks sufficient performance. But their model for building behaviors seems inspiring. Gregg Man summarizes by saying that Virtools (as of 2004 anyway) is good for prototyping but not for production. Although the focus of this blog is on the need for rapid prototyping, we need game engines that are good at both.

Middleware provides pieces of a game engine such as rendering (e.g. OGRE, Kaos, RenderWare, Kerkythea, Genesis3D, Irrlicht, Horde3D, Revolution3D, PhyreEngine, Avalon, Hilva), physical simulation (e.g. ODE, Bullet, Havok, PhysX, Newton, OPAL, SOFA, Tokamak), base components (e.g. RenderWare), sound (e.g. OpenAL, FMOD, Miles, PortAudio, SDL, DirectSound, ESD, Roar), AI (e.g. Kynogon, AI Implant, Brainiac, DirectAI, GALib, Spark, NightFall, Memetic, PathEngine). Let's consider these largely solved problems or at least problems with hordes of people addressing the remaining and emerging issues and leave those topics out of the present discussion.

This series focuses more on the glue that binds those pieces together, and in particular, the language used to express that glue. Scripting languages such as Lua and Python serve to create that glue and to some extent this series will review features of those languages. (Even if this series only elucidates how those languages work, at a fundamental level, then this text provides value in education which is, after all, my job.) But even scripting languages require sophisticated and specialized programming skills to use and we aim to open game configuration to non-technical (or, at least, less technical) developers such as artists and producers.

We might ultimately conclude that game engines need nothing more than Lua+OGRE+PhysX+whatever, and indeed obviously tons of successful, fantastic games have shipped using existing technologies. But I argue that the problem remaining is not to make great games, but to make making games better. The problem is one of optimization and (to some extent) commoditization. Innovation includes combining existing pieces in new ways. Let us aim to make the process of creating and tuning gameplay mechanics a primary goal and see whether we can derive a system that works for both prototyping and production.

GAME ENGINE CONFIGURATION LANGUAGE TOPICS

In this blog I have already touched on a few topics, seemingly at random, but those articles are bound by a cognitive structure and henceforth I plan to make that structure explicit. In the previous post, I already set the stage for viewing game engines through the analogy of an operating system (or reciprocally, one could imagine exploring operating system concepts through the construction of a game engine). Most of the remaining items on the list of potential future topics fall into the category of "programming language concepts" and indeed, game engines have many requirements which programming languages satisfy.

So henceforth I plan to maintain at least two threads of discussion: "Game engines as operating system" and "game engine configuration language".

All of these discussions have an undertone that the purpose of the particular game engine under focus is also by design written from scratch for the express purpose of teaching software engineering and computer science concepts, as well as exploring theoretical ideas for game engines proper. In other words, this is an academic discussion motivated by practical concerns. As with any other academic discussion, we will, for the sake of learning, sometimes deviate from conventional wisdom and common sense. With luck, sometimes that will lead to a real-world payoff, but usually it probably will not. But we may keep separate the hypothetical discussions and the choice of what to try by implementing in code; let's prefer practical solutions even if we sometimes allow ourselves to explore possibilities that seem like they're leading to something impractical.

In this series entitled "Game Engine Configuration Languages" I plan to discuss these topics:

Primitive elements: int, float, vector, matrix, table, procedure, reference, opaque pointer
Means of combination: hashed vector tables
Extensible parsing
Expression evaluation and virtual machine
Anonymous functions and closures
Declarative-procedural languages
Combining control flow and data flow into a single coherent system

Drag-and-drop / visual / dataflow programming
Visual language for automata / flow control

Futures
Continuations
Where do Lua and Python fit in?

A couple of topics span the gap between (what I have categorized as) operating system concepts and programming language concepts:

Cooperative multitasking -- while multitasking itself clearly falls under the category of an operating system concept, I intend to discuss aspects of how expressing concurrent tasks can (and perhaps should) be a fundamental aspect of a programming language (not only as a tacked-on library or via precompiler pragmas).
Threaded Code (not multi-threading) for expression evaluation -- this has more to do with how to implement a virtual machine, which ties into compiler construction, which is traditionally covered alongside programming language concepts. But the execution of code is related more to the underlying machine than to the high-level language used to create the code for that machine.

As these series progress, we should evolve a picture of what all game engines should include as facilities to access functionality. Assuming that a game engine already facilitates what a developer want to do, how do we provide access to that functionality to non-technical developers in such a way that facilitates both prototyping and production? And in particular, how can we facilitate creating and tuning gameplay mechanics?

Game Engine as Operating System: Part 1: Game loop versus kernel

2008-11-30T15:25:00.348-05:00

Game engines and operating systems share much in common. Both provide a thin layer of abstraction above the bare
hardware, providing facilities for managing computational resources such as processes, memory, files and other devices. Both have a core program (called a kernel in operating systems and informally called the game loop in game engines) that monitors and mediates processes that do the real work. Both tend to provide auxiliary (tangentially related) tools, libraries, scripting and user interface facilities that people think of being part of the system. And both provide the means to extend the system. Both game engines and operating systems provide an environment in which particular applications exist and operate.

[I vaguely remember that Doom provided something it called something like DoomOS, mention of which briefly scrolled by when you started Doom on a DOS machine. I can't find any mention of this on the internet so maybe I imagined this. If somebody can find a reference, please let me know, and if it turns out to be relevant to this article, I'll mention it here.]

When trying to explain the overarching principles and design of a game engine, I employ analogies. I spend 90 minutes of lecture time expounding the commonalities between game engine architecture and a theater, in an attempt to reveal a perspective on software architecture (in particular, game engine architecture) which includes not only what the audience experiences, but also involves actors, scenery builders, and prop makers and facilities people (janitors, electricians, plumbers, security guards, etc.). I expose this analogy in such a way to emphasize that only a tiny fraction of the real estate in a theater involves what the audience cognizes; most of the theater complex entails support functionality (seating, plumbing, wires, hallways, parking, docking bays, scenery shops, dressing rooms, lighting catwalks, scenery flies, sound and light booths, lobbies, concession stands, box office, etc.). By analogy I hope to drive home the point that most of the code in a game engine entails making and tuning the game (as opposed to playing the game). By describing these aspects of a theater I hope to ground game engine architecture in a familiar analogy to a physical space.

But still, year after year, I get feedback from students stating they go through the game engine architecture course without a sense of the big picture. Only at the end do students mentally assemble the various parts. Although one could dismiss their criticisms with, "at least they got the point eventually", one would hope to instill into students the tenets of top-down design. (Bottom-up design has its place also, but in a course aimed at teaching game engine architecture based on requirements gathering from stakeholders, top-down is more appropriate.)

Analogies provide a familiar map of conceptual terrain and help people orient themselves. Drawing an analogy between an operating system (which all computer users have used, and all FIEA programming students have studied as undergraduates) to a game engine (which nascent game programmers will write) helps clarify game engine architecture.

Operating system design is a relatively well-understood problem with relatively mature solutions, and since its goals resemble those of game engines, we can use OS design to guide game engine architecture design.

OS's have many parts and I will compare and contrast the structure of each of these parts in separate articles:

Process and thread management
Interprocess communication and synchronization
Process and CPU scheduling
Memory management
Device management
Storage and IO management
Access domains and security
Application development

Throughout these comparisons, we should keep an eye on how we can exploit operating system design principles to solve problems that occur in game engines, especially where game engines have traditionally struggled. Also, pay attention to ways the solutions provided by operating systems are inappropriate for game development, either because the problems lack sufficient overlap or because game development has much more specific problems requiring more focused solutions, and how this insight can help tackle the problems at hand.

The list of topics above is vast and would take volumes to exhaust -- but it is not my intent to write blog posts about how to perform (for example) memory and device management -- or at least, not under the heading of comparing OS's with game engines. I intend to focus on structure, i.e. how to set up a game engine such that these pieces can fall into place and result in an organized and elegant framework.

At their worst, game loops tend to be ad-hoc monolithic behemoths with hidden order-of-operation dependencies. They often resemble a novice programmer's first attempts at coding where all computations go into "main"; game loops often contain an outer "while" loop with a body consisting of a series of function calls. And if you swap the order of some of those calls, the code breaks in various ways, some catastrophic (which actually makes the problem easier to find and fix) or, at worst, subtle (like making the frame hitch a few times per second -- yes, that's happened to me). And if you add a new subsystem, often the "update" call gets tossed inside that gigantic loop. Where should it go? Under what situations should it run at all? What if you need to run something during loading screens when everything else is stopped? What if you want to stop running your new pet subsystem during pause screens? Unfortunately, much of the logic implementing these answers goes right into the main loop.

But what else would a game loop look like? How can we structure a game loop so that it works for every imaginable game, yet has elegant structure? Operating system kernels face the same problem. Imagine that each time you installed a new program onto your machine (or launched one), you had to modify the kernel, recompile, reboot and cross your fingers in hope that it doesn't panic.

OS's facilitate application processes so to make a meaningful analogy with a game engine, we should clarify what on the game engine side corresponds to a process or thread on the OS side. The answer depends on scope. Just as an application is a process that can have multiple threads, a game is a process that can have multiple entities and concurrent tasks. So, in this article, the analogous notion of an application or process will include the following:

simulation entities (e.g. bots, players, resources, assets) -- anything which has data and operations that act on that data
jobs -- self-contained tasks including code and data

The analogy between OS kernel and game engine main loop can get blurry. What maps to what? In a monolithic OS, the kernel treats internal modules (e.g. device drivers) and user processes quite separately. Likewise, a game engine has "internal" processes like input polling and "external" processes such as the physics, rendering, AI and controller handling for simulation entities. But even within OS concepts this distinction gets blurred; for example microkernels runs device drivers in user space -- so for a microkernel, device processing is "external" to the kernel. So the analogy actually works at multiple levels, in that we can treat various kinds of game processes as being either internal or external, where here "internal" could approximately mean game-agnostic and "external" means game-dependent.

This article focuses on kernel structure and how processes interact with the operating system. Maybe game engines can employ similar concepts and techniques -- or at least draw inspiration from OS design -- to provide structure and organization to the game loop.

Kernel structure

In "Operating System Concepts" (2005), Silberschatz, Galvin & Gagne categorized kernel structures as simple, layered, microkernel or modular. Let's consider each one as the basis for a game loop structure.

Simple

A simple game loop has no formal structure. This is a Bad Thing.

Game code call and dependency graphs often look like spaghetti. Code calls other code directly, regardless of what the caller and callee do. I have seen physics code calling AI code and vice-versa. I have seen rendering code call physics code and vice-versa. Everything seems to call UI code, and vice-versa. It's a mess.

As mentioned above, the main loop tends to have implicit and hidden order-of-operation dependencies that were neither intentional nor desirable. Sometimes the order of operations was well understood and planned but simply not documented. In other situations, the order of operations dependencies arose organically and only became apparent when somebody changed the order of operations, usually to try to fix a bug or add a feature, only to find that doing so mysteriously broke some other feature (and sometimes learning that took months, at which point the original cause was long past and therefore difficult to diagnose). Adding new subsystems tends to require hard-coding changes in the main loop.

The benefits of a "simple" main loop include that it's immediately obvious, by looking at the main loop code, what gets called (at least at the top layer). In contrast, more modular systems tend to use levels of indirection which hide such facts. By comparison, some C programmers complain that C++ code, with its method overriding and virtual functions, tends to hide which code really gets called. But as a veteran C and C++ coder I feel comfortable claiming that such complaints come only from the unenlightened and that after you get used to dealing with indirection habitually, the benefits of a decoupled system outweigh its lack of immediate transparency. So abandon simple main loops.

Layered

In a strictly layered system, code in one layer only has access to code in the layers below it. In principle, this simplifies writing and debugging because code at any given layer does not depend on layers outside of it. So the core layers tend to be smaller, simpler, easier to understand and easier to make correct.

Layered systems are fine once made but making them requires foresight, such as knowing which layer depends on what. That's not always obvious. Does the file system depend on the memory system, or vice-versa? It seems like the file system needs to store its contents in memory buffers, so file systems depend on memory systems. But if you want to collect statistics about memory usage and dump that information to a file, the dependencies become less clear. One might introduce a "logging" facility here to try to side-step the issue but that leads to a blind alley. In fact, this problem has a name, which is called a cross-cutting concern and the aspect-oriented programming paradigm attempts to address it. Layering presumes acyclic dependencies, which, while desirable, is not a reasonable expectation -- especially for fundamental services.

Modular

I worked on a game in which a system was developed to explicate module dependencies, but not order of operation dependencies. This system consisted of a collection of finite state automata which (as usual) consisted of a set of states and transitions. Each automata also had a collection of "modules" and each module could be associated with a state. Modules also contained a list of dependent modules. Modules had startup and shutdown operations. Whenever an automata transitioned from one state to another, the system made lists: Modules to shutdown, modules to startup and modules remaining intact. Also, each automata had a "process" which executed. The system could and did have multiple automata running "concurrently" (although behind the scenes they ran sequentially). This system organized and explicated dependencies and allowed extension of what ran in the "main loop" without changing main loop code, but did not provide any means to control the order the automata processes.

Furthermore, the execution of automata processes had no formal constraints, and code within each process tended to make function calls in all directions. So even though the "main loop" had structure, the rest of the code was still spaghetti.

One could argue that no amount of kernel structure can rescue application code from lacking structure. But can one provide an organization and communication framework that encourages proper modularity?

Microkernel

In operating systems, microkernel architectures isolate the bare minimum of code that must run in protected mode and relegate all other code (e.g. device drivers) to user space. So how do the various pieces (e.g. device drivers) communicate with each other in a microkernel? They use message passing. Game engines do not usually have dual-mode systems (or do they? Lua provides a "protected mode") but they have an analogous problem: the need for lightweight interprocess (or inter-entity) communication that maintains loose coupling but high performance.

I have heard arguments that formalizing and abstracting what could otherwise occur via a simple function call adds unnecessary overhead. I will argue against that simplified view and propose that the message passing formalism differs from its implementation, so that the formalism itself provides benefits without the drawbacks people naively assume come with the package.

The Mach and NT microkernels have a bad reputation for poor performance, but the L4 microkernel family proved that Mach's problems were due to implementation choices, not fundamental to the microkernel paradigm. The performance issues in Mach arose specifically because of its asynchronous interprocess communication scheme, which L4 addressed by passing messages synchronously and without excess copy and context switch overhead. A solution in a game system should take a page from the L4 book.

I advocate the use of a bare-bones game loop inspired by microkernel architectures, which provide these features:

Unified method to register and execute "processes" (configuring the game itself)
Providing formal coupling mechanisms to allow processes to communicate
Formal structure for augmenting the game engine itself

System calls and message passing

Operating systems provide services that user-mode applications use, and apps access these services using system calls. How system calls take place depend on who makes the request and who satisfies it.

Kernels implement system calls from user-space to kernel-space using interrupts (i.e. traps or hardware exceptions), where a process stores information (like the system call identifier and arguments) in registers and invokes a special instruction. The execution mode changes to protected, control passes to the kernel, and the kernel dispatches execution based on the system call identifier. For the most part, the interrupt mechanism has no useful analog in a game engine, but it's useful background information for contrasting with other modes of communication with the OS, which have more relevance to game engines.

Monolithic kernels treat intra-kernel communication (e.g. a device driver using the service of another kernel feature) as a regular function call, and since that has low overhead, they run fast. As mentioned above, however, monolithic kernels are unwieldy and unstable.

Microkernels unify all message passing via interprocess communication. That includes operations that, in a monolithic kernel, would be simple function calls. Message passing can be either asynchronous or synchronous. Asynchronous message passing allows processes to run independently yet still communicate. The kernel buffers all sent messages, providing them when the recipient can receive them. But asynchronous message passing comes with high costs: Context switches between protected and user modes happen twice as often, and message data gets copied twice as much. Synchronous message passing avoids those costs but imposes a restriction: Both threads must be ready to communicate simultaneously. Usually, that is the case, so this restriction does not cause undue limitations.

Event systems were the topic of an earlier post. Suffice it to say that I advocate providing an event system which supports both asynchronous and synchronous operation, and that for performance reasons you should prefer synchronous operation when it is possible.

Also, read up on the Io programming language. It uses event-based message passing abundantly.

Why wrap what could be implemented as a regular function call in an event? This seems especially useless when the operation is synchronous and bidirectional, i.e. when the called function returns a value. Benefits include debugging, logging and preparation for distributed computing. But those are topics for another post. The most immediate benefit comes from decoupling, or at least postponement of coupling; even if the sender and receiver (or caller and callee) have to know each other at run time, they do not need to know each other at compile-time. To send an event to a specific entity, the sender needs to know the entity's identifier, but it can discover that at run-time. Often, however, the sender of an event does not need to know the receiver, and that is where event-based message passing shines. In all cases, event-based message passing loosens coupling and looser coupling paves the way to more modular code, which is easier to understand, use, debug and maintain.

Game engine extension

One benefit of keeping the microkernel architecture is that all other operating system services (e.g. device drivers) have a unified interface for implementation and addition, which resembles any other user-mode process, like applications. We likewise expect the same benefit in our game engine. By stripping the game loop down to a bare minimum and facilitating inter-entity communication by message passing allows us to treat services (e.g. file, logging, network access, input handling, display, sound and so on) as any other entity. As far as the game loop is concerned, a device and a game entity act the same. Likewise, as far as any game entity is concerned, another game entity looks like a physical device.

Adding new devices and service subsystems therefore requires no changes to the game loop.

This might seem obvious, but rarely does a game engine use such a unified presentation for devices and game entities.

Analogy breakdown

As with all analogies, this one between game engines and operating systems eventually falls apart. (If the analogy held thoroughly then we wouldn't call it an analogy; we'd call the related things synonymous or homomorphic.) This particular analogy crumbles around the edges:

Operating systems have dual-mode operation which game engines lack and, as far as I can see, have no need for. That might change upon deeper consideration of the actor model of concurrency, but I'm not holding my breath.

Operating systems use timers to implement pre-emptive multitasking. Aside from timers being absent from game engines, the topic of multitasking is also more appropriate for a future article in this series that will focus on process scheduling.

Discussions of OS design also traditionally distinguish between policy and mechanism, the most common example of which is the notion that the kernel must perform the mechanism behind process and CPU scheduling, but the policies for doing so vary widely, and therefore should exist outside the microkernel. I can provide a strained analogy: Certain operations (such as rendering) require mediation but decisions like the number of rendering passes should depend on the particulars of individual games. But this analogy fails because the game loop itself does not need to perform the mediation. The problem is more apparent in OS kernels because of the protected/user dichotomy. For a game engine, no deep paradoxes exist as they do in an OS, and one could simply make more blanket statements like "make data-driven subsystems" and leave that discussion seperate from the game loop or game engine proper.

Conclusion

This article establishes the theme of comparing game engines to operating systems and sets up a chain of topics to explore in future articles. We now have a loose mapping between some pieces, such as game-loop / kernel, game-entity / process and a way to implement message passing to facilitate communication between entities. This article, in isolation, provides insufficient detail on how to implement these ideas, but this article is a setup -- a teaser -- for other posts in the same series. We have set the course to study operating systems to see what we can glean for use in game engine architecture design.

Future articles will explore how to structure process management, interprocess communication, process and task scheduling, device and I/O management, memory management, extension and customization, and integrating pieces into coherent wholes.

Prototype-based programming language with fast dynamic binding

2008-11-03T10:27:00.451-05:00

The game engine FIEA graduate students write each year (as part of their second programming class) uses a prototype-based programming paradigm that shares principles with object-oriented programming (OOP) but the limited version previously assigned lacks several desirable features, partly due to performance considerations. Prototype-based programming readily provides inheritance and encapsulation with no significant performance penalty but polymorphism and even common procedure calls can be expensive due to name resolution. As mentioned in Steve Yegge's article, "The Universal Design Pattern", prototype-based programming comes with some costs: performance and early verification. I want to explore the possibilities of creating a prototype-based programming language, intended for use in a game engine, that addresses the performance issue.

The FIEA game engine implements a very limited prototype-based programming language by using the prototype design pattern and composition to associate attributes with objects (called Entities). Attributes can be either prescribed at compile time or added at run time. The system uses factories to instantiate new objects. Each object implements a "clone" method (a virtual constructor) which duplicates the entity, its attributes and behaviors. Behaviors are something like procedures, implemented using the "strategy" design pattern (and we call these behaviors "Actions"), and objects use composition to contain lists of these behaviors. By cloning objects and modifying them, this simple system provides a simple form of inheritance. (By restricting access to members, we can encapsulate object members, although in some sense this provides no additional functionality, so the assignments omit this property.) The system is simple and somewhat powerful for its simplicity in that it allows game entities to have script-driven properties and behaviors.

The FIEA game engine contains a list of these Entities, and the simulation consists of processing each Entity for each frame by executing a special Action (dubbed the "sim" action). The game engine has a few other features but those are topics for future posts. Essentially (at least for the purpose of this post), the FIEA game engine consists of an ordered list of entities that have attributes and actions, and the "sim" action of each entity runs every frame.

[Note: In a subsequent post, I revisit binding and conclude that we really do want static binding after all. Furthermore, the presentation below suggests (without outright claiming so) that only dynamic binding allows closures, and certain other high-power language features like CPS. That is not the case; such features can be present with static binding. Despite these issues, the expositino below has considerably value and contains no explicit errors. So please read it, but beware that it suggests ideas which might not hold up to scrutiny.]

Past incarnations of this system use early (or static) binding (i.e. names are resolved when parsing configuration files and populating the system), so behavior execution runs relatively quickly, but the configuration language (I hesitate to call it a scripting language) lacks certain rudimentary features such as traditional procedure calls. The system lacks late (or dynamic) binding, i.e. there is no scope tree traversal to resolve names within the runtime environment, so this system lacks polymorphic "method calls" and closures. We could readily add dynamic binding but obvious general and simple solutions would entail run-time name resolution, which could be slow. (The system also has a scriptable event system which allows messages to be passed between Entities, and this provides method invocation somewhat akin to a limited form of how the programming language "Io" passes messages, but those invocations have excessive overhead.) The problem at hand entails adding more power (e.g. procedure calls) but without the performance costs associated with dynamic binding via scope traversal.

Actions in past incarnations of the FIEA game engine differ from traditional procedures in most other languages in that actions do not have positional parameters and cannot be invoked from another action; all parameters are accessed by name, and all actions are called by the core engine (not from script). (Actually, actions inside a "reaction" can be called from script, but ignore that for this post.) It might help to think of the former Entity-and-Action system as being closer to declarative than to imperative, inasmuch as the "language" used to define the system consisted of populating a tree with properties. The description language happens to be in XML and could probably just as well be in JSON. The motivation behind using only named properties and only sequences of predefined Actions has roots in the design goal of allowing a non-technical game developer (e.g. an artist or a producer) to assign attributes and behaviors via a drag-and-drop or other visual content creation user interface where the author does not need to know the syntax of a programming language. (Again, the notion of drag-and-drop programming is a topic for another post.) We therefore wish to preserve this trait of not requiring positional parameters in behavior configuration.

More common and fully-featured programming languages provide the ability to decompose problems into small pieces and solve them separately without the separation introducing undue overhead. In programming terms, it comes down to being able to make "local" function calls cheaply. ("Remote" function calls, which involve synchronizing execution across multiple cores, or accessing memory distributed across multiple cores, is a somewhat separate problem so let's leave that aside for now, except to mention that the existing event system is well-suited to that problem.) Introducing procedure calls into the FIEA game engine (polymorphic or not, late binding or early) should run fast, retain existing features and have a solution that can be implemented in a short amount of time (otherwise FIEA students would not have enough time to write it in a single semester).

Forms of dynamic binding and what they buy you:

The term "dynamic binding" has a variety of meanings depending on context so though I claimed that "the engine should have dynamic binding", the problem statement still requires quite a bit more refinement. Let's review various forms of dynamic binding and features they provide.

Procedure calls bind function arguments in the sense that the formal parameters are mapped to the actual parameters (or arguments) passed at the procedure call. This happens by placing values (in the scope of the caller) into registers or memory that are used locally within the procedure code (in the scope of the callee). This binding could be called static in the sense that the variables passed by the caller are determined at compile time. The only sense in which this binding is "dynamic" is in the limited (perhaps artificial, definitely not conventional) sense that semantically, the arguments refer to different variables at run time. And past FIEA engines lack even this rudimentary form of binding.

If a function can call itself or if a function can be called multiple times "simultaneously" then we say the language supports recursion. This implies that the same formal arguments can be bound to multiple sets of actual arguments (i.e. memory locations) simultaneously. If the mechanism used to pass arguments simply involved storing values into registers or fixed memory locations then a second simultaneous call to the same procedure would overwrite and obliterate the values in those locations, defeating any attempt to call recursively. To support recursion, usually procedure argument values are pushed onto a call stack at the caller side and extracted from the stack at the callee side. Just as with non-recursive function calls, this form of parameter binding does not conventionally get listed as dynamic binding.

Polymorphism via virtual function calls entails dynamic dispatch, i.e. which method gets called (i.e. receives the message passed) depends on the object on which that method is called (i.e. to which the message is passed). In this form of dynamic binding, the compiler cannot resolve which function to call so the decision is delayed until run time. In practice this happens by dereferencing a table of function pointers, and the object holds the address of the table -- so it actually involves a pair of pointer dereferences. Actually it usually involves three pointer dereferences since the object itself is usually referenced by a pointer. (If you had the object itself instead of a pointer to the object, then you wouldn't need polymorphism because you could resolve the method at compile-time.) But despite the fact that the function name gets bound at run time, the arguments are still bound at compile time; in this form of polymorphism, the function call always has the same "signature" or "form" i.e. the formal parameters are always the same, regardless of the object type.

The forms of dynamic binding discussed above apply to C++, Java and C#, but dynamic languages such as Lisp, Io and JavaScript include additional forms of dynamic binding. These include the dynamic lookup of so-called "free variables", the use of "continuations" instead of a call stack, and the use of "duck typing" to decide which methods shall handle messages passed to an object.

Prototype-based languages offer a form of inheritance where each object has a "parent" object used as a prototype to create the new object. The clone operation has at least two choices: Either have the child object hold a pointer to the parent or have the child duplicate all members (including all code and all data) of the parent. The former conserves memory, so seems desirable. If using that method then name resolution (i.e. binding) involves traversing parent pointers and looking for the attributes that match the name of the sought attribute. (Please read Steve Yegge's article for more detail.) Lookup therefore takes at least O(N) time where N is the number of ancestors the child has.

Some programming languages treat functions as first-class objects, meaning (among other things) they can be passed as arguments and returned as any other value. These so-called lambda functions are anonymous procedures which can be defined within the scope of another procedure. They can refer to at least 3 kinds of variables: local, arguments and "free". Free variables are those which are defined outside the context of the procedure body, e.g. inside the procedure containing the definition of the lambda function. (Formal language theory makes a distinction between bound and free variables although both require some form of binding, and in fact binding "free variables" entails a lookup which is more conventionally called "dynamic binding". In this nomenclature, "bound" variables refer to function arguments, which in the current context is admittedly confusing.) With lambda functions comes the problem (called the funarg problem) of deciding how to bind variables which are defined locally within the enclosing scope, after that scope as ostensibly disappeared. An example (in pseudocode) will help explain:

int procedure(int x) makeIncBy(int x)
{

return int lambda(int y)
{

return x + y ;

}

}
b = makeIncBy(1) ; // returns a procedure that adds 1 to its argument
b(2) ; // returns 3

In this example, makeIncBy is a procedure that takes an integer argument (x) and returns a procedure which is defined inside makeIncBy. The procedure it returns (which has no name) takes an integer argument (y) and returns an integer (the sum of x and y). The problem is, when makeIncBy returns, its local variable (x), which traditionally gets allocated on the call stack, would normally no longer exist, yet the lambda function refers to that variable. If x is allocated on the stack then when b(2) is called (which invokes the lambda function, which refers to x, defined outside the lambda), then it seems as though the attempt to reference "x" would yield undefined behavior (a euphemism for saying that some random memory location would be accessed, leading to tragedy). This is the funarg problem, and it has at least two solutions: Disallow free variables or use closures. A closure is a "scope" which is associated with a function, which is used to dynamically bind a variable. Resolving (i.e. binding) a free variable thus entails searching closures for the nearest one which maps a name to a value. This is "real" dynamic binding for variables, and with it comes great power, especially when you remember that in languages with closures, variables themselves can refer to functions. So this technique allows you to write functions that create functions from other functions.

As an alternative to using a call stack, the system can use continuation passing style (CPS) which allows for continuations and coroutines. At first glance, CPS seems like an extraordinarily overwrought notion and excruciatingly difficult to use to write programs. In fact, writing code in CPS style would lead to early insanity. But its purpose is not to be used by humans for authoring code, but as a way to translate code automatically, behind the scenes, to facilitate continuations. It is useful at this stage to note that a "continuation" includes a function and its arguments, and the caller will not know the "signature" of the function until run-time. This contrasts sharply with polymorphism as present in C++ where the function signature is static. This discussion rapidly deviates on a tangential topic so I will leave the rest for another post. Meanwhile, suffice it to say that CPS solves useful problems in interesting ways and the dynamic binding problem solved by closures applies there also.

It might seem like closures and CPS provide solutions in search of arcane problems, especially in the current context of deciding how to implement the ability to bind names in a scripting language for games. After all, since the goal is to make a scripting language that non-technical people can use to author games, then esoteric features like anonymous procedures and concurrent coroutines probably lie well outside the abilities of the intended audience. Perhaps. We should explore some possibilities and see where that leads, but we might eventually return to these more powerful techniques.

There is a form of polymorphism which effectively combines the dynamic binding schemes discussed so far. The examples above include dynamic binding of two kinds of names: functions and variables. C++ and its ilk use "dynamic dispatch", i.e. dynamic binding of functions. Prototype-based languages can use "parent" pointers and dynamic programming languages use "closures" to represent scopes or environments which map names to values, which can be used to bind variables dynamically. The object-oriented programming paradigm refers to "passing messages between objects"; it does not refer to "calling procedures". C++ implements message passing (or a limited form of it) as a procedure call, and the compiler checks to make sure the object being passed the message actually has a method to handle that message. But in dynamic prototype-based languages like JavaScript, you can pass any message to any object, regardless of whether the object has a method that handles that message. This allows a form of type system called duck typing. This provides an extremely flexible form of polymorphism.

Dynamic Binding Options:

What form of dynamic binding should the game engine support, and how should it be implemented? It is possible that "how" has multiple answers depending on the what. As "Io" shows, it is possible to unify all of them, but Io values simplicity and power over performance, whereas the FIEA game engine values simplicity and performance over power. So instead of deciding which of the features above we want, consider the list above to be a menu without prices. Our decision of which items to choose depends on their price. So let us determine the prices: What implementations can we concoct, and which seem both simple and computationally efficient?

The system needs a name-to-value map, which we will call the Environment.

Hierarchical environment

Former version of the FIEA game engine implemented the Environment as a single flat dictionary where names have 2 parts: context and instance. This presented the appearance of a hierarchical namespace but with constant-time lookup on any symbol.

Consider defining a struct called Scope which maps names to values. In principle, each scope contains other scope objects. This would form a tree of scopes, or a hierarchical namespace with an actually hierarchical structure in memory. Traversing this namespace usually happens from the leave nodes upward so instead of (or in addition to) each scope containing children, each child should contain a reference to its parent. Each object (Entity or Action) would contain a pointer to its local scope. As mentioned above, name lookups would require O(N) time where N is the depth of the child.

We can flatten the tree traversal using something akin to "Lambda lifting": Convert each variable that resides in a parent scope into a local variable in the scope associated with the Action. In other words, all non-local attributes become local to the scope of an object.

In a similar spirit, any non-local variables accessed by an Action can be bound using tree traversal, then the results can be cached into the Action's local scope for future accessed. (This resembles a copy-on-write policy, although its goals are different.) But since all the referents are known at compile-time there is no obvious reason to delay this operation until run-time.

Imagine that each Scope does not know its children, and that children only know their parents. Action invocations could include a pointer to another scope object and name resolution would require looking at the passed-in scope (and its parents) prior to using the scope statically associated with the Action. In this way, any variable (free, bound or local) could be redefined by the caller, upon invocation. I will call this notion "scope tree surgery" since it effectively replaces one branch of the tree with another branch from another part of the tree. (The analogy is somewhat strained because the result of the surgery is to have one branch refer to another; the attached limb is never removed from the other part of the tree.) This technique provides immense power, including and exceeding even the most esoteric forms of dynamic variable binding techniques discussed above, including argement passing and closures. For example, even Lisp does not provide a mechanism for rebinding local variables inside a function. How could this seemingly dangerous and atypical property be useful? In the context of a game engine, each variable (including locals) stores properties which control behaviors, and we aim to make all behaviors tunable via script. Phrased differently, using this technique, all variables in an Action act as though they are arguments, all of which have default values. The caller can choose to change those variables or leave them alone. From the caller perspective, there is no distinction between function arguments, locals, and free variables.

Unfortunately, in terms of performance, this raises the cost of name binding considerably. It includes not only the usual cost of lookup associated with a more conventional scope tree used with stack-based or CPS function calling, but also this notion of searching the "passed in" scope prior to the usual scope (and/or closure). That is, usually, function arguments are passed by position, e.g. on a stack, and the callee unpacks those arguments and places the passed-in values into the memory locations of what are tantamount to temporary local variables. That process involves no lookups, just linear scan-and-unpack which can be written and automated prior to run-time.

Regardless of whether dynamic binding requires a tree traversal (i.e. even if we use some flavor of tree flattening), and even if the local scope uses a hash table, name binding will require some sort of lookup that costs more than a pointer dereference, and as it is, even pointer dereferences get scornful looks from optimization czars. Former versions of the FIEA game engine avoided this cost by caching all prescribed parameters (i.e. those known at compile-time) into member variables of the Action class. And (as mentined above) most programming languages make this "lookup" trivial by making it a hard-coded (thought automatically generated) register-to-stack (and vice versa) transfer, which relies on function arguments being fixed in size and order, at compile time. We want to preserve the property that Action variables are assigned by name, not by position, but we want the speed of positional parameters and structures (which both amount to lookups by offset).

Perhaps we can have our cake and eat it too, by prescribing parameter order within scopes. Instead of caching parameter addresses into member variables (as was done in the past), each scope would contain an array of pointers to Datum, and at compile-time the ordering of those would be known. When an Action gets invoked, a "replacement" scope would be populated but its ordering would remain the same as it was at compile-time. This trick would only help for prescribed parameters and it has some fragility issues but most of that noise gets hidden from the end user and could potentially be automated with some clever tools.

There is also a concept of "late static binding" which essentially amounts to rebinding a static member variable used in a method defined in a base object which a derived object inherits. The notion of "static" member variables only applies in languages which separate classes from instances, which is not the case in prototype-based languages.

My analysis here is somewhat bottom-up which conflicts with the usual edict of designing top-down. Top-down design asks first "what do you want to accomplish?" then asks "how do you accomplish that?", so application designers get exacltly what they want. But bottom-up allows for more performance because it first asks "what simple pieces can we make that run fast?" and second asks "what can we make from these pieces?". In truth we need to alternate between these 2 strategies until we find a way to make what we want using pieces we can afford.

I have left several loose ends in this post; what about duck typing, CPS, lambda functions and closures? Do we want them? At what price? Those are open for discussion.

Meanwhile, this post has outlined a way to inject traditional procedure calls into the FIEA game engine, without adding to the cost of accessing prescribed parameters. The current topic of discussion becomes, does this seem sane?

Event system filter mechanism refinement

2008-09-09T12:56:00.023-04:00

Event systems aim to mediate communcation between software components while facilitating decoupling those components. Event systems avoid message senders from needing to know message recipients. They establish one-to-many relationships. Event systems tend to build upon the design patterns of "observer" and "mediator". The book "Distributed Event-Based Systems" (Muehl et al.) provides a taxonomy of cooperation models which illustrates the relationships between message senders and receivers, based on who initiates the transaction (consumer or producer) and whether the initial message recipient (addressee) is direct or indirect. Event systems are categorized as systems where the producer initiates communication and the recipient is indirect (i.e. sender does not know or care about the recipient).

Event systems work well when a single message can be used by multiple unrelated subsystems. Consider a simulation of a bunch of moving billiard balls which can collide, rebound from walls, and fall into pockets. An audio subsystem could subscribe to collision events to play a "click" sound when balls collide. Each ball can respond to collision events to apply an impulse to rebound from other balls and from walls. A gameplay system can monitor when balls fall into pockets to tally score and to remove balls from play.

Unfortunately, simple forms of event systems can distribute events to recipients who do not need every message of a given type. The problem of deciding what messages go to what recipients is called “filtering” and that’s the area where a simple event system needs refinement.

Reconsider the example problem. Each subsystem (physics, sound, gameplay) receives all collision events, but sometimes particular events are irrelevant to certain subsystems: A collision between a ball and a pocket should emit no sound. A collision between a ball and another ball should not cause any scoring change or remove balls from play. Also, all balls could receive all collision events between all ball pairs even if the ball is not involved in the pair. Such spurious, irrelevant events can be rejected by recipients after delivery but "post-delivery filtering" introduces avoidable overhead. If the number of billiard balls is large, the overhead can be larger than the legitimate processing time.

How can we augment an event system so that it has enough information to filter which recipients get which messages, in such a way that the event system remains generic and preserves desirable properties, e.g. that the sender does not know nor care about the receipients?

Several filter mechanisms have been implemented for event systems, including type-based, channels, subject-based and content-based.

The "observer" design patterns uses a subscription model tantamount to type-based filtering, where subscribers implement an interface which allows them to be notified of messages and they subscribe to the publisher via a subscription method. Each publisher object keeps a list of subscribers and notifies all subscribers when the appropriate event occurs. An event system built upon the "observer" and "mediator" design patterns therefore effectively uses type-based filtering. As revealed in the example above, type-based filtering still delivers all collision messages to all subsystems who care about particular subsets of collision messages, so we want to refine the system to use a better filtration mechanism.

Channels encompass sets of message types, and subscribers can subscribe to a channel, so they receive any message in the channel. Such a mechanism actually worsens the problem at hand in that we want to narrow the flow of communication, not widen it. Furthermore, the type-based system can already facilitate channels (although somewhat awkwardly) by subscribing a single object to multiple publishers. If it became useful, introducing the notion of channels would require only cosmetic changes to the event system; it would simply wrap the existing subscription interface with a sugar coating. At best, channels solve a different problem -- one not currently under consideration.

Subject-based filtering entails describing events and filters using keywords and filtration entails pattern matching. There are many problems with string-based approaches, including poor performance, ambiguity and rigidity. Read up on the subject if you want to know more, but for the immediate conversation I summarily dismiss this option.

Content-based filtering entails operating on the contents of the message itself. To be generic, the event messages have to be structured in a way that the event system can query, e.g. using name/value pairs. Furthermore, the filter itself has to be in a form the event system mediator can interpret, e.g. an expression language. This technique is quite powerful but also complicated and it's not clear that implementing a powerful, general mechanism like this provides any performance advantage over simply passing all recipients all messages of a given type, then letting the recipients decide whether each particular message is pertinent or not. (In the context where content-based filtering is employed -- distributed systems -- the message data and filtration expressions often reside on a different machine than the recipients, in which case the cost of distributing the messages is potentially much higher than for the present example, which runs within a single machine.)

Consider an extremely limited form of content-based filtering where each event message provides an integer (perhaps with arbitrary length) which we could call its "digest". The meaning of this value is unknown to the event mediator; only the publisher and subscribers assign meaning to this value. For example, it could be a unique identifier (e.g. each billiard ball could have an id), a bit field indicating various information (e.g. subtypes), a combination of these -- whatever. Meanwhile, each subscriber would provide a pair of integers: a mask and a value. When processing an event for delivery, the event mediator would apply the mask to the digest using bitwise-and, then compare the results to the value provided by the subscriber. Using this mechanism, the subscriber can state whether specific bits must be high or low, or whether some bits are irrelevant. Furthermore, the "identifier" and "subtype bit field" approaches can be merged together because, e.g., the upper N bits of the "digest" could correspond to "id" and the lower M bits could be the "subtype bit field". The important idea here is that the event mediator does not know or care what the bits mean -- only how to apply them as a filter. This system constitues an extremely simplified form of content-based filtering because it reduces the set of name/value pairs to bits (where names correspond to bit index ranges and values correspond to the bit values at those indices), and it reduces the filtration expression "language" to a single integer with a bitwise-and operator.

Sounds fast and simple -- elegant. Will it work? Is it sufficiently powerful to justify the addition?

[We'll discuss this at lunch on Friday, September 19, at Crispers in Winter Park Village.]

Update 2008sep19: Summary of lunch discussion:

Gabe, Dan, Aaron, Paul, Nathan and I attended. Everybody contributed to the discussion. Paul and Nathan reported their experiences with other event systems.

Paul described a channel-based system that he was not happy with, for reasons resembling those I pointed out in the blog -- insufficient filtering. The system he uses also has other issues, like massive switch-case filters within subscribers -- which misses one of the major points of using type-based filtering and one of the major benefits of event systems. He described an augmentation he implemented that took some inspiration from C# "delegates". His scheme uses C++ method pointers and uses the special and arcane .* and ->* method pointer invocation syntax. I have often thought about situations where that could be used but rarely (never?) seen it exploited, so this might be a good example of it. Paul also described a hypothetical system which involved layers of subscribers, each of which filter and selectively redistribute messages.

Nathan said his team evaluated Insomniac's Event/Delegate system but decided to write their own which uses type-based filtering, because their needs are simple. Their system suffers from the same problem described in the original post, that multiple subscriber objects receive messages of the proper type but not intended for that particular object. This situation apparently arises when the event system is used to postpone delivery -- i.e. where the publisher knows the subscriber. So to some extent one could claim this was out-of-domain usage for an event system, which is supposedly intended to decouple depencencies between systems, but in practice we all also use event systems to exploit the asynchronous nature, even with tight coupling between publisher and subscriber.

The Problem

2008-09-09T12:50:00.000-04:00

Programmers in the game industry face common problems but most knowledge is tribal and held close. The market is flooded with books and education programs which claim to teach game development but rarely do they dig deep. Some of us crave more in-depth discussions of more esoteric aspects of game programming which become apparent only after you've taken a few trips around the block, traveled the obvious routes, looked around and found yourself led astry. We want to speculate, learn and discuss what others have tried, try new ideas and evaluate alternatives.

Part of the goal of this discussion is to attempt to create a "reference architecture" for interactive simulations with visualization (including games, military and other simulations). All game engines share certain features and the game software development community would benefit from using a common language -- somewhat analogous to Design Patterns, but tailored specifically to problems that arise in game engine development.

This blog could have been a forum but this format organizes topics in a manner better suited to the intended purpose: Post a specific problem which is nevertheless generic to many game engines, summarize the conventional wisdom, present cases where the existing solution fails to solve particular relevant problems, suggest alternatives and poll for opinions.

I look forward to our conversations.