Never Too Many Asserts

My friend Keisuke says an assert is like a circuit breaker. It does no harm to be in the circuit when things are operating normally. But when the voltage goes out of bounds, your program stops.

We all accept that a defect costs more to fix the later it is discovered. If you have already checked in, it affects your coworkers. If you have already shipped you will have to go through a new release or public patch. The tenets of extreme programming are that if something is good, taking it to an extreme is probably better. So if we catch a defect in an assert while we are actually developing nothing could be better. If our coworkers "protect" their modules with asserts, we can be more confident that our use of their stuff is legitimate. And we can go faster, and have a more reliable system.

I like to use a number of different kinds of asserts:

• External Interface (ASSERT_EI): validates that the parameters to a method that is expected to be used by other major modules or by the customer are legal and in range. But they should not be used to validate user input. This is a super-critical assert. The more of these the better.
  
• Internal Interface (ASSERT_II): validates the parameters to methods that exist for good code structure and are intended for use only within the current module. Private methods would use these. They are for defensive programming, and reminding yourself what your assumptions were when you designed this method. They can provide a kind of documentation. These are less important than ASSERT_EI, but are great for debugging old code that you don't remember very well or that you didn't write. Again, the hope is that you can go faster. What if you took a short cut, and haven't finished a method for one use case. You can leave an assert such that if you accidentally use the method that way, you will obviously be reminded of the missing work, as opposed to having the method silently do nothing, or fail with some bizzare side effect.
• Internal Consistency (ASSERT_IC): validates that the state of a class remains consistent as it is manipulated. It is an invariant check. The design of your module makes assumptions about its data structures (e.g. an data item is in a list only once). Assert this periodically. I like to add a SanityCheck method to almost every class I build. It executes all the invariant checks I can think of (and yes, it can be pretty slow). It is especially useful to sprinkle around if you are currently tracking down a bug. It makes sense to verify your invariants going into and out of a method. Centralizing those invariants in a SanityCheck function can be pretty useful.
  
• External Consistency (ASSERT_EC): I don't use this very much, since nicely modular systems should not have tight interdependencies. For example, your module may be dependent on the configuration file being parsed before it is initialized. An ASSERT_EC can check (and document) that assumption.

I've seen game programmers take a couple of positions against asserts:

• They slow down the execution of debug builds so much that the app becomes unusable. OK. It really is too slow. There should be easy ways to disable the asserts especially in heavily executed bits of code. In fact, one should think twice about putting asserts inside tight loops. Also, your assert implementation should be able to runtime skip the predicate based on runtime configuration files, and do it fairly efficiently (e.g. check a global boolean). Disabling per module would be a good start. Providing a level-of-detail argument to the asserts should be possible.
  
• I keep having to skip some assert in someone else's code that I don't understand, and that interferes with my workflow. Everyone should be careful not to use asserts to remind us of work that needs doing. Some other mechanism should be used. Or wrap those checks in a per-developer ifdef. On the other hand, if a developer is hitting asserts they don't understand, maybe they are breaking code they don't understand. Using either comments or change-control software, a developer should find the auther of the assert, and learn about that bit of the system, or get them to change the assert if it is now obviated.
  
• I changed one little thing and all these asserts starting going off. This one is pretty funny. Given that the asserts are there for a reason, there is a pretty good chance that the one little change had much further reaching implications than expected. For example: someone now wants to handle a member being NULL. But ASSERT_IC's start going off that the member shouldn't be NULL. The thing is, if the rest of the class was built assuming that member can never be NULL, it could easily derefernce the pointer without checking. An argument that "it should have checked for NULL" doesn't fly. The assumption was built in.

Adopting these "extreme" uses of asserts might even take the place of unit tests for that class.

In Game "Transactions"

There are times when two players (or even other kinds of Entities) need to trade an object or perform some other action that is critical to occur transactionally. Generally, this is meant to mean that no matter what kind of error occurs, the transaction occurred or did not occur. E.g. I paid you 10K, and got a gold bar.

Support for transactions needs to work across server hosts. It is a very disruptive experience to be able to interact in one spot, but not 2 feet to the left. You have to assume that the players can purposely crash one or the other host at the worst possible point in the interaction (like Byzantine Generals). Assuming you can trust you database, the idea is simply to get both sides of the interaction saved to the DB simultaneously (i.e. in one DB transaction).

What if the two Entities are on different hosts? You have to simultaneously change remote variables and get the persistence request from two places to the DB, blah, blah, distributed handshake, Byzantine...brain fry. They do this in Cobal for banking systems. How hard can it be? Well it is too hard to be worth it (if you include failure/backout/retry, etc), even if you think it would be a fun challenge.

So here is a fantastic consequence of the non-geometric load balancing mechanism we've been talking about. Each simulator is single threaded (if you use multiple threads, you have multiple simulators). An Entity Behavior will execute without preemption. So straight-line code will run to completion, a DB save request can occur, and all is good. All you need to do is get both Entities onto the same simulator, and run that straightline code and co-persist the two local Entities (i.e. send the db save request with both entity's states). Boom. Done. Either the transaction makes it to disk or it doesn't. Not just half. This scenario is the origin of a lot of dupe bugs you've heard about.

The fact that migration policy and mechanism are separate means that adding a new policy is easy. E.g. migrate the guy I'm about to interact with over here (or me over there). Once it finishes, the transactional behavior can be scheduled. If things are a little crazy, it may take a while, but it won't fail and start giving away money. And it won't tell the user the transaction succeeded when it didn't.

Clearly, this is not something you want to do all the time. It would be too slow. Just for the stuff that *really* matters to the users.

If you don't like the thought of your Entities migrating around, build an Escrow Entity. Place one side of the transaction into it and copersist. Migrate to the other side, place the other half in and copersist. Move out the half, persist, migrate, move out the other half, persist, done. If there is a failure at any point, the Escrow object is known about by the DB and it can continue, or return the goods. Just like a Lawyer, but not as expensive.

Either of these approaches can support multi-Entity Transactions.

Networking Resource

Here's an article with lots of links to classic networking techniques:
http://gafferongames.com/2009/01/25/game-networking-resources/

Here are some research papers leaning toward large scale issues:
http://maggotranch.com/biblio.html

Entity Migration Mechanism

From earlier posts, we see that to achieve scalability, we need:

• large numbers of simulators
• an ability to load balance based on load (not just geography)
• an authoritative simulator to avoid DB bottlenecks
• a single-write paradigm to avoid overly complex synchronization

And since our world scales with the number of Entities, not the number of functions in the game, then load balancing, and thus, scalability is realized using Entity migration.

Setting aside the policy and impetus for initiating an Entity migration, lets talk about the mechanics. By separating policy and mechanism, we can experiment or customize the policy to use application-specific information, resulting in a closer to optimal solution. And we won't have to reimplement the mechanism each time.

We know we can run an Entity on any host by using interest management as discussed earlier to feed an Entity everything it needs to operate correctly. So all we really need to realize a migration is:

• getting the Entity state onto the new host
• getting the data flowing to that host that is needed by that Entity
• doing this quickly enough that there are no hiccups visible to the players
• avoid all ordering and race conditions so there is no game logic difference compared to not migrating (no side effects)
  
• survive crashes of any component at the worst possible moment (i.e. preserve important transactionality) without significant impact to the players

First, we use a data-driven means to identify which state variables need to be transferred to the new host. There is no reason to transfer truly temporary variables, but there are reasons to transmit variables that are not needed in the persistent database. E.g. current target. There are many mechanisms to serialize an entity and reconstitute it. One challenging aspect is whether to transfer the execution context (e.g. the stack and program counter) if your simulator uses coroutines to support blocking and waiting in a Behavior script. For example, Stackless Python is famous for pickling coroutines and reconstituting them.

There is a handshake needed to get this state across:

• suspend further execution of the entity so things don't change during the migration
• transmit the state
• recreate the entity on the target host
• resume execution of the entity.
  

Seems simple, but consider that update messages to players from the original and destination host might get out of order, the DB request queue might get backed up on the source (after all you are migrating away from a busy simulator) and save requests to the DB might get out of order, replicated state on the source and target might be at different versions (the entity may see a neighbor jump backward or forward in time).

So we need to add some steps:

• Get the target subscriptions set up and acknowledged before the transfer so when the Entity arrives, all data is available there that it had in its original location
• Have the original simulator "flush" its DB queue so the DB never sees out of order persistence requests, and then stop persisting that entity until after the migration.
  
• increment an "epoch" counter to allow us to discard any replication messages or requests from the past
• Given the increase in time and complexity, it may be worth optimizing the process by pre-loading the target host without actually pausing the original entity. Then once everything is set up, resend states that may have changed during the preload. Of course, you might also make use of any state that was previously replicated to the target.
  

There a quite a few trick available and needed to get this to come out right and be efficient. But distributed transactions like this happen reliably in a lot of "critical" systems in other industries so it is quite solvable. You can see how the need for migration and the requirement to do it quickly without player-visible hitches requires us to adopt many of the design principles already accepted: authoritative simulator, interest management, data-driven persistence and replication traits describing entity state variables, ... All of these key features are intertwined, so if your systems goes off track somewhere there, you may be buying a lot trouble elsewhere.

One of the coolest features of interest management is that you can choose to not migrate and the game still runs the same (but may use more datacenter-only networking). So if you can't migrate an entity until it finishes a behavior (because you can't migrate your stack), no problem, just wait. Program that into your policy. If you find that hitches are visible but only when a player is in a heavy combat situation, your policy can delay initiating the migration until the participants have been quiescent for a while.

Debugging leaked references

Everyone likes using smart pointers and reference counting to manage the lifetime of objects that are passed through modular interfaces. They can avoid a lot of copying and callers don't have to read a lot of documentation to figure out if they are responsible for deleting the object.

One big problem with using ref counted objects is when they "leak". It is extremely difficult to debug what code has taken an extra reference to an object that you think should have a single remaining reference. Why didn't this object destroy itself when I cleared this "last" smart pointer? When an object is passed through many layers and stored in various containers, there can be quite a few increment/decrement references occurring, so putting in breakpoints is not very useful. I have found this to be one of the most difficult and tedious problems to fix in a large application like a game.

Regular memory leak detectors are not too useful, since they just say "it leaked", not why. What you really want to know is the location of every outstanding reference to a block that you think should have already been deleted. You can ask this question at the end of a run on the unexpectedly outstanding blocks, or in the middle of a run when you have found something strange and want to backtrack.

It is "easy" but not much use getting the memory address of every smart pointer that points at the problem object. Make multi-map keyed on object addresses. Each time you assign or clear a smart pointer (increment or decrement a reference on an object), modify that map to include or exclude the address of that smart pointer. Done.

Making this "useful" is a matter of recording information about each smart pointer for later logging. Ideally, you would record a partial stack trace so you can see where the smart pointer was affected and what caused that. This requires another chunk of data beyond the smart pointer's memory location.

If you are only concerned about extra references, you could probably get away with recording the stack trace only on addRef. Note that for each smart pointer, there is only a single outstanding reference, so you only need the one stack trace per smart pointer.

If you have a situation where you have too many decRefs, you may need to record the stack trace of each addRef and decRef for the broken object. Garbage collecting that data is going to be interesting, because you can never be sure when an extra decRef might happen.

Putting this together, you can use regular memory leak detection to identying unexpectedly outstanding ref counted objects. Then ask this ref count debugging system for the stack trace(s) of the where the smart pointers where initialized that are still holding a reference to that object.

What is a memory leak and why do we care?

I am a big fan of Purify. It is a tool that helps programmers deal with the challenging memory systems of C and C++ . In those languages, we can "leak" memory.

We try to get rid of all the leaks (usually a few days before we ship). I've seen this take quite a lot of effort. Superficially, it seems like wasted effort since modern operating systems keep track of your memory and recover it when your processes exits. So, really, we could just exit and kill the process. The app would shut down a whole lot faster.

Why does that sound like such a bad idea? Why do we even care about leaks?

• We don't want to have our process use more resources than it needs. It could crash or make other apps unhappy.
• It makes for higher quality software. We are strictly disciplined about who owns what.
• Managing the scope/lifetime of an object is occasionally very important. For example, we may be holding some I/O that needs to be flushed.
  

There are two competing definitions of leak. Obviously I like the Purify definition better. I'm going to argue that the other (more common) definition is an oversimplification and a compromise:

• Precise: a leak is an allocated block of memory that you don't have a pointer to anymore. So you can't ever delete it. A potential leak is one where you only have a pointer to an address somewhere in the middle of the block. This might happen if you do some funky pointer arithmetic, and intend to undo it to later delete the block. Anything else is referred to as an in-use allocation.
• Traditional: a leak is a block that is still allocated (outstanding) when the application shuts down.

Most custom memory allocators use the traditional definition, because developers have no good way of providing the more precise definition. They require the application writer to build good quality code that carefully deletes all the memory it allocates such that none is left outstanding at the end of execution. Certainly that definition subsumes the Precise definition. The traditional definition is saying there are no leaks, potential leaks, nor outstanding allocations. Nothing. Period. How can you argue with that?

The tools used are simple. They keep track of outstanding allocations, but don't and can't subtract precise leaks. They have neat ways of showing where the memory was allocated, and so on. The app writer finds all those outstanding allocations and carefully clears them as the application shuts down.

But you don't super-need-to clear the in-use memory. It is not hurting anything. You could delete it any time, if you really wanted to (sounds like an addict). OK. There is one way it can hurt something. You could accidentally have lists or free-lists that bloat up and it will look like you really are using that memory. However, since it is in-use, you should be able to instrument your lists as watch them bloat up.

You do super-need-to clear precise leaks. They are caused by overwriting or clearing your pointers without doing the deallocate first. If you don't plug those leaks, you are going to sink, or crash, or lose oil pressure or air pressure, or some other analogy.

How could Purify possibly differentiate between precise leaks and in-use? Believe it or not, it watches every pointer assignment. And sees when the last reference to a block is lost. It does this with something called Object Code Instrumentation, so it doesn't care what compiler you are using. It inserts assembly code into your executable (e.g. around assignments), fixes up jumps and symbol addresses it changes when making room for the inserted code. It consequently knows what you have done or accidentally done to every pointer (including nasty things with pointer math).

As a result it can focus the coders attention on blocks that are unreferencable. It can even (theoretically) throw a breakpoint at the instruction that overwrites the pointer. I know it can break at the instruction where you read an uninitialized variable. At any point during debugging, you can make a call and have it dump unreferencable blocks of memory and where they were allocated. Of course you can also dump all in-use blocks by calling a function when paused in the debugger. I believe you can make a checkpoint and then later dump all blocks that are in-use that were allocated since the checkpoint.

If you insert some code in your custom allocator, the Purify SDK can even use your allocator to do its magic. You could make calls to it at run time to dump metrics or react to issues.

As you can see, unreferencable blocks are the real leaks. We only have to clear out all in-use blocks because we don't use tools like Purify, and have overreact and compromise. I don't like the busy work of clearing every last legitimate in-use block. I don't think I should have-to-have-to. (As long as I'm careful about my "other" resources like I/O buffers.) It makes for better code if I do, but if I want to trade time for quality or one feature for another, I still have to clear the real leaks, and like the option of ignoring the other blocks swept up by the tradition definition.

It has a bunch of other cool stuff too. Like knowing when you access memory that is uninitialized, or already deallocated. It knows when you run off the end of an array. It can instrument third party object code even if you don't have source, and it doesn't use your allocator.

Of course there is a runtime performance hit, but it isn't super bad. And you can control which modules are instrumented, so you might exclude your rendering for example.

It has a UI that integrates to Visual Studio and gives you a nice report of these various kinds of memory errors at the end of your run, or whenever you ask. It will even take you to the offending line of code.

Don't balk at the price either. Just remember the amount of time the poor guy spent that was stuck with clear every last in-use block. It more than pays for itself very quickly.

The Manifesto of Multithreading (for High Performance)

This document is a statement of principles that Emergent software developers adhere to concerning issues of concurrency, parallelism, multiprocessing and multithreading.
Related Docs:

• http://twiki.emergent.net/bin/view/ServerDev/ServerProcessModel
• http://cache-www.intel.com/cd/00/00/05/15/51534_developing_multithreaded_applications.pdf (Great comments on Granularity in section 3.2. Add comments on dynamic agglomeration.)
• Communicating Sequential Processes, C. A. R. Hoare. http://www.usingcsp.com/
• http://en.wikipedia.org/wiki/Von_Neumann_architecture

Principles:

• Multi-threading on a single processor is beneficial only in rare circumstances such as when we expect a program to block repeatedly, such as doing I/O.
• When concerned about performance, this is unlikely to be the case, so we should see only one or two threads created per core.
  
• Operating system context switching between threads can be very expensive. It involves saving and loading processor state, tends to result in complete cache invalidation, and most expensively entails updating of OS process management data structures. For systems that provide virtual memory, reprogramming the MMU and swapping out kernel resources such as file pointers can make switching even more expensive. Some system calls can force a scheduling quantum to end.
• Avoid context switching by keeping the number of threads low. Avoid system calls.
• Decompose the problem into large segments to minimize the number of context switches and total overhead. This is most easily done by decomposing into as many pieces as possible, then using a policy to agglomerate them back into large sequential computations.
• Reducing the number of threads will make the job of an SMP OS scheduler trivial and inexpensive. Ideally it could map a thread to a processor and leave it there indefinitely. Any load balancing needed can be accomplished by the application using app-specific knowledge without affecting the number of threads and their scheduling.
• The measure of efficiency of using available multiprocessors is determined by how much processing time is wasted or spent idle.
• For ease of measurement and tuning, an application should avoid consuming as much processing as possible, but should try to consume as little as possible, then idle, making inefficiencies much more visible.
• Never use a spin lock.
• Idle time of this sort can be filled by work scheduled to be done on processors that are already fully utilized or overloaded. This is the reason for load balancing and is one component of thread scheduling.
• Processors interfere with each other’s efficiency when accessing shared data. This happens directly if the other processor hits a lock that is already acquired. If the blocked thread suspends, another thread on that processor may be able to take over. But that adds a context switch on top of the lock check. Mutual exclusion (mutex) mechanisms and other atomic instructions cause cache flushes on remote processors, or lock the entire memory bus. These costs are hidden when doing performance analysis since they don’t affect the requestor, and are not attributable to any single instruction on the remote processor (other than as apparently “spontaneous” cache misses). Even storage barriers used in out of order memory access modes can add overhead from cache effects.
• Avoid the need for shared data. Either partition the data so it is exclusively used by one processor, or hand off entire blocks of data to a processor so the data has a single-writer at any one time.
• Minimize the number of interactions with shared objects, as each interaction bears an overhead. This relates to the (TBD) agglomeration policy mechanism discussed above.
• Even computations that only read data owned/written to by another thread concurrently must be guarded.
• In some cases managing a replica of the data for remote readers will simplify programming (removing the need for the guards), and have other benefits similar to double buffering such as removing a serial sequencing.
• Guarding disjoint blocks of code with a critical section mutex mechanism is error prone because the coordination code is not collocated. Overly conservative exclusion will impact performance. Surprising interactions (side-effects or reading shared objects) can lead to errors/races.
• Avoid code-based mutual exclusion (critical sections) for commonly/widely accessed systems. If it is the “only” approach, consider centralizing it (e.g. single reader and writer), as opposed to requiring almost every method of an object to grab the mutex.
• Consider whether the object being guarded must be a singleton or can be replicated per thread (in which case, no exclusion is required).
• Don’t confuse thread exclusion with reentrancy.
• Locks on data or code blocks that require more than one resource to be locked can lead to deadlocks, or priority inversion or self-blocking. If the deadlock is of low probability, it may not be observed in testing. Even though some consider it easy to detect and fix a deadlock, they are very risky since it is so hard to guarantee they don’t exist.
• If you find yourself resolving conflicts from multiple locks, it is time to redesign the system.
• Lock contention tends to not gracefully degrade in terms of performance and fairness/starvation. More sophisticated locking is required such as a ticket mutex for fairness. Simpler locks consume even more resources, mask their caller’s logical idleness, and cause memory performance side effects as threads busily contend for the lock.
• Avoid high contention resources. Duplicate them, or rethink whether they are as shared as you think.
• In the spirit of CSP (Communicating Sequential Processes), assign the ownership of the resource to a single thread and use message communication to access it.
• Before devising a more sophisticated and special purpose mechanism or data structure to address the high contention, reconsider the larger problem. Often a more coarse approach using CSP will fit better with the rest of the system. The task to be parallelized may not turn out to significantly contribute to overall performance. Optimize globally.
• Scheduling preemption should not be relied on to provide performance. Each forced context switch is an unwanted overhead. Near 100% of the CPU can be used by a single thread that has enough load assigned to it. Preemption should only be used for rarely invoked latency sensitive functions like I/O or for long running low priority background processing where the preemption rate can be very low.

Guidance:
Hoare’s Communicating Sequential Processes (CSP) can be used to solve any concurrency problem (any concurrent computation can be realized/reimplemented as CSP) and has a very easily understood mental model. A logical process (LP) contains its own state variables and performs computation concurrently to other LPs. LPs interact only via messages whose content and ownership is atomically transferred as it is sent.

By leaving the computation sequential, and avoiding all concurrency within each sequential process, algorithm development returns to the familiar Von Neumann Architecture. This approach is better for our customers as we do not require them to be concurrency experts when coding. It is better for Emergent since not all the developers need to be aware of the concurrency consequences in various systems they are less familiar with. Performance analysis becomes trivial, since algorithms are sequential, and message queuing can be analyzed to inspect workload. Critical paths and idealized parallelism analysis of the communication graph can be used to determine if a better load balance is possible, or if the problem itself needs to be further decomposed to realize a performance gain, or if more processors would improve performance.

• A thread is treated as a CSP logic process. While it may share a single address space with other threads, by policy it does not share any writeable (and ideally, any readable) data.
• The only point of concurrency is the message queue. A message with its content belongs to one logical process xor another.
• A large amount of data that needs to be “shared” among threads is handed off in a message. Copying can be avoided by using a pointer in the message to the transferring data and adopting the policy that the data “belongs” to the message once it is attached, and belongs to the target logical process once it arrives. This effectively uses SMP shared memory as a communication medium.
• The principles of CSP apply equally well in a multi-threaded shared-memory environment as in a multi-process SMP, in a NUMA or in a distributed processing environment. This future-proofs our software and allows reconfiguration and performance tuning by changing policies without rewriting code. This addresses application design and load changes as it evolves.
• Minimizing the number of LPs reduces context switch overhead but requires better load balancing algorithms. A good static balance based on the expected application behavior can extract quite a lot of CPU capability, especially when the workload does not fluctuate very much over time. This should be a design goal even without considering concurrency to avoid frame rate jitter. Dynamic load balancing can use recent history to predict a better near term balance. However, to do this there is work-migration overhead. This takes the form of per-task “global” scheduling onto available processors (less desirable as this is a continuing cost), or periodic analysis, extracting and transferring workload between LPs. Note that in most cases it is not worth the effort of eking out the last amount of performance with sophisticated load balancing techniques.
• Mapping similar work to an LP increases the likelihood of instruction cache hits. So when agglomerating small tasks, create large lists of similar tasks as opposed to doling them out round-robin.
• Always optimize at the end. Getting perfect parallelism out of a system that is only 10% of the application computation is probably a waste of effort.

Other Concerns
Note that strict CSP suffers from communication overhead. For systems which are extremely fine-grained and latency sensitive, a custom approach might be considered if the extra work and risk are justified. But it should be sufficiently encapsulated to avoid having its tradeoffs unknowingly cause performance side effects elsewhere.

Concurrency for utility reasons like background loading can also benefit from techniques used for high performance concurrency, but being less performance sensitive, the benefit is primarily in reuse of common facilities and ease of development.

The CSP focused approach and infrastructure can be reused trivially to implement most kinds of parallelism: functional parallelism, data parallelism, master/worker thread parallelism, pipelined parallelism, etc. It is not appropriate for very fine grained parallelism such as parallel loops, or SIMD computation but that should be rarely needed when considering the application as a whole.