Service Update: Cached Shadowmaps

This is probably not news, and I don't often post links or summaries of conferences, as there are many people that do a better job than I would at that, but since I posted a bad sketch of an half-tested idea a while ago about caching cascaded shadowmaps I got some inquiries about it. So why didn't I wrote something decent? Let me digress :)

At that time our team at work was trying to optimize a game's GPU performance, and among the various things, shadows were a problem. We were already experimenting with some forms of caching of static objects, we had this idea (inspired by looking at Crysis 2 in action... if you look closely you can see this) of rendering our far cascaded every other frame (five in total, in a frame we would 

update the first one and two of the remaining four).

This worked only so-so due to dynamic casters being able to walk "into" their own shadows, so we tried to cache the static objects and render only the dynamic objects every frame (for the two cached cascades). This turned out not to be a win with the size of our shadowmaps, we were basically using half of the shadow generation time in bandwidth/resolve, so the caching didn't really bring anything.

This consideration, killed for us the incentive to go further implementing other caching schemes, and left me wondering if on this generation of consoles this scheme could really turn out to be faster.

Well, wonder no more! Luckily, decent ideas tend to eventually be discovered many times and recently Mike Day published an excellent work (presented by Mike Acton) on something that he implemented which is closely related to the bad idea sketch I posted on the blog. His work is very detailed and provides all the information on how to implement the technique, so go and read this paper if you haven't already.

He does the caching by reprojecting the old information both in UV and in depth before splatting in the dynamic occluders, as at the time I was already concerned about the bandwidth, I was speculating of using the stencil to tag the z-near and z-far used to render a given region (that though would have worked only on 360 and ps3 where with some trickery you can access the stencil information while sampling the depth shadowmap, not on dx9) and using other hacks which are probably not worth their complexity as they would still result in the same worst-case scenario.

P.S. You might have noticed the little "posted with Blogsy" logo at the bottom of this article, this is the first time I use my iPad for the blog and I have to say, I'm pleased. This little app lets you write the post with all the formatting features (which I don't use) and integrates a browser and image functionalities so you don't have to fight with the broken (absent) multitasking of iOS.

And here, let me go full hipster with a photo taken with HDR Camera on Android, then abused on Instagram and uploaded to the blog via its Picasa account... It will burn your eyes :)

Posted with Blogsy

Back from vacations, Parameter Databases poll results.

Back after Siggraph and some well-deserved vacations, I have many posts to prepare. For now, here there are the results from my last poll.

Coast near my hometown

The poll was: "Parameter Database systems should use..." and here are the final results. Didn't get too many votes this time (32), maybe people were in vacation as well, or maybe the subject was boring, anyhow:

• Reflection (53%)
• Code-Generation (28%)
• Handles/Dynamic Types (18%)
• Immutable Data (in-game) (18%)
• Data Inheritance (18%)
• Schema Inheritance (18%)
• Relational DB (15%)
• Live-editing via tool (78%)
• Live-editing in-game (40%)
• Serialization via tool (53%)
• Serialization in-game (34%)

Predictably I'd say, people prefer to keep editing and serialization in a tool instead of in-game, having the in-game client only to load/listen to the data changes.

As for the database type, relational systems do not seem to be favored, I guess most parameter systems are still key-values. Low scores are also assigned to dynamic typing, data and schema (class) inheritance.

What is maybe surprising that reflection wins over code-generation, even if in C++ there is no easy way to  implement the former.

I've noticed how often we, as engineers, have a perverse aesthetic sense for which a C++ disgusting macro based reflection system is considered "prettier" than mixing different languages or crafting languages and tools. 

To be fair, reflection could also be done more simply by parsing PDBs or using C++ parsers, but I doubt these are really widespread.

The good thing about reflection though is that code changes can "break" data, or require data changes, but the opposite is not true. With code-generation data changes can "break" code which is arguably worse.

Mine your Data!

Some simple ideas:

1. Add to your bug tracking two compulsory fields to be filled (choosing from a list) when closing a bug: where it was found (AI, Rendering, Loading etc...) and what caused it (Incorrect API usage, corner case not handled, memory stomp, wrong algorithm, variable not properly initialized, invariants not enforced and so on). Soon you'll see what parts require rewriting, what need unit testing, automated tests and so on.
2. Give testers a build connected to a sampling profiler. Sample. Diff the profiled function list with the list of functions in your symbols file. Voila', cheap coverage analysis. Now we know which code to delete!
3. Install automatic time tracking tools, like this one. Anonymously gather data about your project (be nice). At the end, you'll know how much time was spent in which area (much better than measuring the number of changes or check-ins or so). So we'll know which things are better to be moved into a scripting language, or into a dynamically loadable module!
4. It's also a good idea to keep track of the CPU time of some key processes, like your compiler, linker, the time your VCS spends in networking operations and so on. Unfortunately I don't know any program that does that on windows and I ended up writing a simple one a year ago to prove we were spending too much time waiting for linking.
5. Do you have a in-game telemetry? Are you not using it internally on testers machines to gather data (memory usage, FPS and so on). Shame on you!

What other data are you mining? Comment!

Hacking bools idea

Little idea. After reading this post about bools, chars and bitfields, I started thinking of an ugly c++ hack. 

What if we defined our own custom bool (chances are that you already have one around in your engine, if not it's probably not a good idea to add one) that it behaves like a bool (char sized or whatever) always, but it strictly stores only 0 or 1?

With such a thing we could make sure when returning a native bool out of it, that what we store is still either 0 or 1 and thus have a mean to identify some memory stomps in many classes that have boolean members, for free.

Of course this "idea" could be extended, via templates, to have ranged integers and so on, but that would start being really ugly...

Alternatives to object handles

I'm tired, so I'll write this as a "note to self" (even more than how I usually do here). 

Hot-swapping (and similar concepts) are often implemented with object handles and a "manager".  Refcounting is often used to manage object lifetime.

A possible implementation is to have all the resources stored in the manager, let's say in an array, and the handles could be the index into this array. Or the handle could be a pointer to a shared object that points to the resource on the heap (same as C++ TR1 shared_ptr, but sharing also the pointer, not only the refcount) and the manager can just have an array of pointers to the resources on the heap.

This works well, but it introduces an indirection that will cause cache misses every time we have to access to the actual resource, especially if the resource is small and could be stored directly in the structures that need it, for example shader constants that can be represented just with the GPU pointer that contains the data to be set in the ring buffer (i.e. NVidia OpenGL bindless API see http://developer.download.nvidia.com/opengl/tutorials/bindless_graphics.pdf).

Also, in general reference counting is not the best idea to manage object lifetime. It leaks memory if we have cyclic references, leaks that are not hard to detect with a debugging allocator but that can be complex to fix. It's also not too fast when destructing objects, as an object desctruction can trigger a chain of RC destructions or RC decrements that can cause more cache misses.

Ideas:

• Storing the objects to be "patched" in the manager. We avoid handles, but when a pointer to a resource is obtained, the location of the pointer is stored in the manager (via a multimap: resource pointer to list of locations that point to it).
• Pros:
• No extra indirection, nor extra space used in the objects that hold the resource (other than the resource itself)
• Still it can be wrapped in something having the interface of a shared_ptr, so the solution allows to go back to a more standard object handle implementation if wanted.
• Can move resources in memory easily! Sort them to have cache-coherent access (if possible)
• It's even an alternative to intrusive_ptr (Boost), that is a good (performance-wise) way of doing RC (without hot-swapping) that also does not incur in space penalty in the objects that point to resources but it can be used only to point to objects that implement a given interface. 
• Cons:
• It will have way worse performance every time you change one of the pointers to a resource!
  
• Requires a complex data structure, difficult to implement and balance.
• In general it will require more space.
• It will patch objects... not the most clean thing... nor the most robust, you can easily forget registering a temporary copy of an handle in the manager or you really have to be sure that no such temporaries exist when you swap things...
• It will have worse performance on object creation and most probably, destruction (handles and RC are not great in destruction too, it's hard to say because they can trigger a chain of RC destructions or decrements that results in cache misses).
• It will be harder and slower to make thread-safe, even assuming that the hotswapping happens while the application is single-threaded.
• "Hardcoded" Garbage Collection. Very similar to having an "update" function that triggers the caching of resource pointers to resource caches in the various classes, but without the need of having to waste space... Every class that holds references to GC objects implements a "walking" function that will mark them. Every GC object will need a flag to check if it was marked. We still need a manager with a list of all the GC objects.
• Pros:
• Safe even in presence of cycles.
• Not too much of an extra burden if you're writing methods in every class for things like reflection (actually, if you have any form of reflection of the fields in your objects, this will be "free") or serialization...
• At no extra cost you also will know which objects are holding references to your resources...
• Cons:
• Changing a resource is almost as expensive as a GC, we will need to walk through all the references!
• Different interface, can't change your mind easily.
• Error-prone, you can easily forget to update one of the tracking functions, and still you have to make sure you never create untracked copies of an handle, i.e. a temporary (or well, you have to be sure none of them are around by the time you execute the GC/hot swapping)
• You will need to be a genius to have the GC or the reference-updating process run in parallel or incrementally.
• List of references. Similar to the first idea, but instead of the multimap we just store a list of all the locations that contain resources. When we have to change them, we go through all the list and see which ones need patching
• Pros:
• No extra indirection, nor extra space used in the objects that hold the resource (other than the resource itself)
• Still it can be wrapped in something having the interface of a shared_ptr, so the solution allows to go back to a more standard object handle implementation if wanted.
• • Cons:
  • Changing a resource is still expensive, we will need to walk through all the references.
  • We probably still would need to maintain a separate list of resources, other than the list of patching locations, if we need to be able to enumerate and find them... In general it will require more space.
  • It will patch objects... not the most clean thing... see above...
  • Again, harder and slower to make thread-safe
• Permutation array. We add a second indirection level, to be able to sort resources to cause less cache misses. An handle in an index into an array of indices (permutation) of the array that stores the resources.
• Pros:
• Resources can be easily moved around in memory, and be sorted to be cache-friendly.
• • Cons:
  • Many times we don't have a coherent memory access order...
  • Many times the resources are actually small, so the array of indices won't cache-miss less than the actual array of resources!
  • yes, this one is not a great idea most of the times...

But maybe this is all wrong, as I said, I'm tired. I'll think about it more another day... Comments as always are welcome.

p.s. Hybrids are also possible I guess... Like dividing the locations roughly into buckets (i.e. depending on part of the msb of the pointed resource) thus trying to minimize the cost of mutating pointers in the first solution (list add and delete would be needed only if the pointer changes to a resource in a different bucket).

Surviving C++

WARNING: This post (as 99% of my posts regarding C++) contains suggestions but also scathing critiques to what it could be your beloved language. 
If you are offended by the former, please before rushing to post a comment, at least make sure you've read and understood the "Defective C++" section of this faq, that contains some of the most high-level remarks (i.e. without going down to many of the details, like bad defaults or awkward keywords) on what is bad about C++ design. 
I know it's hard to get out of our own comfort zone, and we all tend to get defensive about things we are used to, even if they really suck. If you want to argue and discuss on the merit, then I'm happy to chat either via comments or you can find an MSN widget somewhere on the right of this blog page. If you just want to write that I don't understand C++ or something like that, avoid, it's just a waste of time (and I would really love to check if you are a better C/C++ or any other language programmer than I am...)

Introduction

 

If you've been reading my blog for some time, you know what I think about C++. It's an horrible mess that managed to be successful exactly because it's lame. It was designed to be a glorified macro system on top of C in order to please the market of C programmers, not scare them with this new "OO" thing but just give them something they could relate to, that they could reason in terms of C. In retrospect, it was not even a good at achieving that (see D for example) but it was the first and in a few years most C programmers were "won" by C++ (not all) so now we have to live with it.

How do we survive it? How do we manage to create projects and sell software made with it? Well, the best answer so far has been to "subset" it. Basically every professional studio working in C++ (that is, in gaming, everyone) restricts C++ in a "somewhat safe" subset that is more manageable and less tricky to work with, to avoid at least the biggest pitfalls.

What does it take to be a C++ masters? Is it the knowledge of fancy design patterns (omg!) or expression templates? Of course not, these are things that all the kids talk about out! To be a C++ master is really about knowing C++ defects more than its features, as it's demonstrated by these three fundamental, cornerstone books: Effective C++, More Effective C++, C++ Coding Standards.

In fact, no one uses straight C++ to make anything, in real world everyone starts by sub-setting C++ into something "safer" and then adding back the fundamental missing features (i.e. memory management, serialization, reflection and so on) via libraries, macros or  other trickery (i.e. code to code transformers, code generators or parsers and so on), so really the C++ we use is not a standard, but a studio specific version of the language.

This "custom" C++ is then enforced either informally via code reviews and coding standards, or more strictly with the help of configurable "lint" software.

So one day I decided to stop using the blog only to blame C++ but actually try to help developers by seeing if people could agree on some "gaming/realtime rendering" C++ standards. With the help of a shared notepad, I seeded the guidelines with my personal considerations and waited for people to start adding their own.

http://typewith.me/aigp7OGWps

I think we got something interesting there, and I'll clean it up and post a snapshot on the blog of that work. But the more I got into this the more I grew dissatisfied with the guidelines, as it seems to me most of them are "aesthetic" in some sense that they are certainly needed to reduce the WTF/minute ratio when dealing with a C++, but they don't change fundamentally the experience of developing a project.

What is fundamental, really, when dealing with a big software project? What is the first thing we need in order to survive?

Everything else does not matter (much)

Apart from running and producing an output, what is the most important quality that a software project has to have, from a development perspective? If you think about it it's obvious. The most important quality that we want is the ability to change it.

That is what we do all day, all days, we edit code. We don't just add functionality. We don't design a perfect, immutable system that will withstand centuries (especially not if you're making a game!).

Code changes, code rots, hardware changes, design changes, ideas change, players change, the single most important quality of code is its ability to be changed without breaking, without effort.

Also, really, if we can change code easily, we have all that we need. A junior programmer made a mess in our camera system near the deadline of our game? No problem, for the next title we can rewrite it! We have a crash that we don't have any clue about? Well, maybe we can rip out some systems, one by one, and find out the culprit. Designers changed their mind on the control system? Well, we might write some prototypes with them at their desk.

The more our language and project is easy to change, the less time and less obstacles it poses to change, the more all the other problems fade in the background. It's not a coincidence that the more a language is dynamic, the less need there is for fancy debugging tools. Who needs a watch window indeed, if I can just add on the fly a widget on screen that graphs the value of a given variable?

Unfortunately though, when you look at our beloved (not!) C++, there is little to be happy about. C++ as a medium for our art looks more like statuary marble than modeling clay: it requires a team of muscular stone cutters under the guidance of a genius in order to produce some amazing sculptures. And once a given idea has been translated into the stone, you hardy can change it without re-sculpting most of it or having to work in the constraints that the shape it currently has impose on you.

C++ is not only static typed but also statically linked and its performance depends on that. You don't get any fancy JIT or runtime optimization, but not even a standard way of loading modules or functions (even if to be fair, 99% of the systems you work with will have some non-standard functionality to achieve some sort of dynamic linking). Not that I'm advocating dynamic typing here, that's another can of worms (and you might even argue that types are not really the best form of static checking, and C++ classes are surely not the best expression of user defined types, I digress...), but static linking surely give us less options.

So what we can do? Well, the art of sculpting in C++, the art of design, becomes really the art of subdividing our sculpture in pieces, the real design challenge is all about how to cut or work into pieces. Too many of them and the sculpture will be a fragile and ugly mess (translation: craptastically slow OOP shit). Too little and we loose flexibility. 

Also, we would of course love if each piece was connected to as few other pieces as possible, otherwise replacing it would be a pain, and that the connections themselves to be as simple as possible.

How do we achieve that? Well, it can be tricky because dependencies are in many ways evil, but they are also the most innocent looking features of any languages, devils in disguise. Structured programming is all about composition (even disregarding the excesses of OOP)!

If you see these... think twice.

I originally thought this as some "coding flashcards" for a course at my former workplace but project deadlines had priority and I didn't end up finishing it. So when I started the collaborative guidelines experiment I wrote them in a similar "visual" style: if you see this code, then your spider-coding-senses should tingle. 

Great, experienced coders develop an instinct, an aesthetic if you want, something really subconscious about good structure and good looking code that is often difficult to formalize, is some sort of gut feeling that comes from having read a lot of code and knowing the perils of some structures.

So here it is. This is the part that really matters of these visual coding guidelines: the global-disaster causing wall of shame.

You see: Foo.h (header file)

You think:

• Is everything in this header really meant to be seen outside?
• Can we make more things part of the implementation?
• I.E. Look for private functions that could be outside of the class.
• Is everything in this header really meant to be seen by every other module depending on this one?
• Can we more move things into a header that is seen by this module only (i.e. a good schema would be to have local includes in a module_name/source directory and the outside visible ones in a module_name/include/module_name one)
• Should we consider using PIMPL (Façade if you like changing names of existing techniques)? Or abstract interfaces?
• Are we exporting concrete types, or contracts and functions?
• If we are exporting concrete types, are they fundamental enough? If we are exporting interfaces, do we really need them or are we over-abstracting, over-generalizing?
• Remember: don't generalize something if you don't already have two/three different usages of a given thing. Don't abstract anything if you don't have two/three different dependencies on a given thing. Code should change to adapt to situations, not try to predict them.

You see: #include (especially in an header)

You think:

• Do we really need the include or we can use forward declaration?
• Can we include that file or are we introducing a dependency that we don’t want across two modules of our system? (even better, make sure that this can't happen by structuring your project in a way that to access a given module from another one, the project properties have to be changed, and make sure you have all these changes approved by a technical director)
• Is the dependency static (function linking / inline functions / templates / types) or dynamic (interface calls / function pointers)?
• Which one makes most sense here? Do we need performance or abstraction?
• You will usually want to statically depend on core system libraries (memory, math...) and dynamically from other modules.

You see: a_type* Foo(...) or a_type& Foo(...) (interface returning a pointer, or returning a structure containing pointers)
You think: 

• Who will own that memory? Who will destroy it? When?
• What if we want to hot-swap resources?
• Better use a handle? Reference counted?
• Should we be allowed to mutate it (non-const)?
• And who else will mutate it?
• Is the pointer type the least derived (if it's part of a type hierarchy) possible?

You see: class Foo : public Bar
You think: 

• Are we inheriting from an interface (pure abstract class)? Are we generalizing needlessly? Is the interface as small as possible? Then go ahead.
• Otherwise, the class has to have some data associated with it. Are we sure we want to link Foo both to the interface of Bar and to its in memory layout? 
• No, you are not. Don't do it, use composition instead. [More Effective C++, 33 Make non-leaf classes abstract]

You see: Class Foo{ void MyFunction(…) }
You think:

• Can it be implemented as an external function instead? 
• Especially if it's private, should it be visible to anyone that can see the header? Prefer implementation-only functions to private member functions.
• Should MyFunction be const?
• Has it really to be part of the class or should it be an external utility function?
• Is it needed to make the class complete and minimal?
• Should it be declared const?

You see: static
You think:

• Can we safely have multiple instances of this static (i.e. if we link this statically to multiple dynamically-linked modules), or it will be a problem with DLLs?
• Can we safely access this static from multiple threads, will that be needed?

Conclusion

This is it for now. Look at the typewithme pad above to see the full coding guidelines. I'm sure I forgot other things and I will probably edit this post over and over. If you want, comment as usual or better, join the discussion on the typewithme shared document!

p.s. There is of course quite some discussion in the comments and actually something persuaded me that I should clarify here. A point someone raised is basically: "you seem to hate C++ but still in the end you say things about decoupling that will apply to many other languages (to some degree - I would add). 

It is 100% true and right. That is what I felt and what I probably failed to clearly express. I started this "collaborative guidelines" experiment, I got some great input there and it was all nice and exciting. But then I started thinking that yes, these are the landmines we all know and have to avoid, there are books written on them and everyone really agrees. 

Yes, there might be people arguing on the details (Boost is good or evill? Design patterns? and so on), surely everyone comes up with their own implementation of the same extensions (reference counting, serialization and on and on) and that sucks but still the bottom line is, everyone knows that the default new/delete operators are useless, everyone knows that "friend" is bad and so on. 
There are things to avoid always, things to mostly avoid and things to remember because of bad defaults (i.e. "explicit" or "virtual ~Foo", redefining equality operators or hiding them and so on) and probably even many things that everyone forgets until they hit them, but at the end of the day... they don't matter much.

In all my years as a professional programmer I've learned that. You can work with the worst code and language and tools on earth, if the problems are "local", they are hidden behind well designed abstractions, then all the implementation behind them does not really matter. Or it matters, yes, but at a totally different order of magnitude.


So yes, I still hate C++. But we can work with it. If we pay attention to the only thing that really matters, the decoupling, then life will be fine. And slowly, we will even be able to move stuff over other languages, if it's all nicely decouple and the interfaces are sane. And believe it or not, it's already happening.


Now go, look at your project and try to do an experiment. Take a small piece that has defined inputs and outputs, with some coworkers we tried once with our camera library. Can you take it apart and put it in a DLL? Or rewrite it in another language? If yes, then sweet dreams, your project is nice. If not, then you should think, maybe you have a problem...