The Workbench

BigO notation needs to retire.

2009-10-01T11:43:00.004-05:00

I've been having discussions lately about algorithms, iteration, and timing, and something has been bugging me about every conversation that I've had:

Big O notation is horrible when comparing algorithms.

I realize this is going against 30+ years of established programming rules, but the fact is that I've never found BigO notation to be that useful because of the amount of data it doesn't describe.

Why? BigO only works when we assume that the running time per element is constant across all data structures. In addition, it assumes that data structures / algorithms don't incur 'unknown' performance burdens. In REAL programming, both of these concepts are incorrect; Sparse traversal data structures, which may be faster due to lookup times etc, can incur additional hardware burdens (such as cache misses, branch mis-prediction, and pointer chasing) that aren't listed in your general O(n log n) evaluation.

In addition, BigO notation doesn't give any suggestion towards the millions of other issues around selecting a given algorithm, like memory consumption, or setup time (which the ps3 devs really care about!) .

What do I use then? Personally, I came up with something else :

The more I program, the more I realize that every algorithm is a trade-off. You are always pushing/pulling/compromising and trying to fight the caveats at the same time.
I find that the Triangle makes a much better discussion measure, as you can easily bounce things around and evaluate what REALLY matters.

In addition to that, any given algorithm is usually a sum of it's parts, meaning that you may need to create sub sections that lean more one way than the other in order to get the entire algorithm skewed towards one point on the pyramid.

For instance, computing all floating point values at run time between [0,1] can be done, but you'll loose performance for it. Where as moving towards a LUT increases memory footprint, decreases quality, but massively increases performance.

Another great example is mip-mapping. In order to increase performance, we decrease texture quality by introducing more mip values. Effectively, we've moved the point in our triangle from the quality side, closer to the middle, where performance increases, and so does memory consumption.

Finding an algorithm that pins right into the middle of this pyramid is usually pretty difficult, and more importantly UNDESIRABLE to find. Specifically, putting an algorithm right in the middle is something you don't want to do, because every algorithm always has a trade off. You need to know where you can squeeze out 10% more performance, or memory. Which is another reason I prefer the triangle; It allows you to see where you COULD go, and more importantly, what SPACE your algorithm can improve in during periods where you need to increase in any given dimension.

As a graphics programmer, I'm always worried about these three factors when writing an algorithm, especially if you're about to ship on a console, or other embedded memory system, in which case the trade offs between performance, memory, and quality are MUCH worse.

Think it's crazy? Give it a try, and I'm confident you'll find that as a programmer, it's much more natural to think in terms of a triangle than an O.

That's what she said.

~Main

People like ray-tracing..

2009-08-13T10:44:00.003-05:00

A siggraph demo showed off a new 'fast' raytracing app. Entirely written in CUDA; which seems odd that they consider this a ‘breakthrough idea’ … using a multithreaded teraflop SIMD processor for millions of rays *GASP!*

IMHO, Arauna seems much more impressive for CPU side RTRT , (with free source code) ! simply because I consider CUDA / OPENCL a mild fad when compared with more general computing promise of many-core / LRB setups.. (but that’s just me…)

Although not real time, it’s worth looking at is SmallPT, it’s an entire path tracer in 99 lines of code. That has a higher-performance CUDA version written by another developer .

And if this sort of thing interests you, you really want to download TinyRT , a grouping of raytracing template containers. I think some of their containers are TOO generic, and thus loses some performance quality. But I always side on the concept that hand-optimized code for a specific platform will out-perform most containers.

Which all of this is funny to see a siggraph style conference devoted to ray tracing, even though it's been around for 30+ years now. : http://www.sci.utah.edu/rt08/

Viva la history.

~Main

Perpetural Motion Squad

2009-06-22T20:13:00.004-05:00

After the closure of Ensemble Studios I was cast back into the pond of job hunting.

After taking a bit of time off and enjoying my new daughter, I started into job hunting sometime in mid-April, and after 4 full weeks of phone calls, tech interviews, and 24 hour plane flights, I have accepted a position at Blizzard Entertainment Where I'll be working on something that I can't tell you about yet, but I can tell you that I think it's going to be much, much bigger than my previous project.

Interviewing is always a difficult process. As the interviewee, you've got such a small window of time to prove your mental metal, and a massive deck of problems already stacked against you. On top of that, a significant portion of the companies I interviewed with still used the arcane concept of "white board interviewing."

First, I will admit, I am quite horrible at white board questions. My skillets focused in standing in front of a group of people, and coding on a large dry-erase board have never been developed. Especially when the peanut gallery likes to talk, distract, and try to correct you mid-thought process. I understand the "logic" behind white boarding, generally that someone who's good at answering those types of questions will be good at any skill set;(which in itself is a good deduction to make) but the problem arises when you docking your interviewee for things that they would normally rely on a compiler to check for them. (Semicolons, spelling, etc). At some point you have to ask the question "what are we really testing this person for?"

Through it all, I came out with one horror story I'll share:
After passing the phonescreen and written test, I flew out and interviewed at one company that had a standard "casual interview" format, where you'd meet the team in a semi-formal setting, and they would ask questions and have talks face to face. This is pretty common from what I've seen, (although a couple companies didn't even have me meet the rest of the team, I only spoke with the leads..) Before all that though, they started off the day with the white boarding session. I entered the room with all the interviewers waiting for me already. two out of the five said hello, while the other three continued on with a conversation about their cool new iPhone features event, and avoided eye contact.

After standing there for a good 2-3 minutes, waiting for the group to finish side conversations, one of the more senior gentlemen started the process. "We'll ask you some questions, answer as best you can, try to show your work and talk through the process. We want to know what you're thinking, just as much as what you're doing. If you get stuck, we'll try to help out to get you on the right path."

Boilerplate statement. I nodded in agreement, as the first question was tossed out to me.

I started off outlining the problem and running through a few examples to attempt to derive a general algorithm for. (standard fodder if you've ever read this book.) Every now and again I would look over my shoulder, or turn around to point out a specific comment or design choice I had made. And what I noticed during the process was quite alarming; The entire time, the interviewers were texting, carrying on side conversations, and surfing the web. In fact, I would stop every now and again during their conversations and ask if I had missed something, or if they had a comment on what I was working on. (This was met with angry looks and rolling eyes each time I did it.)

I know it's a common stage to try to put too much pressure on your interviewee. Some companies pride themselves on it. It's a weird balance between YOUR ego, and trying to interview the candidate. But half way through the 2nd question, I was just pissed off. If my bald ass has to stand up and put on a dog-and-pony show, the least you can do is act like you haven't seen the goddamn problem 50 times before.

After the hour was up, I left the room with a horrible taste in my mouth. Not because of my answers to the problems, but more so because of the realization that if these jack offs didn't show enough respect for me to give-a-damn during my interview, I'd never get that respect if I'd accepted an offer there. The last thing I want in a company is MORE ego to deal with. [[EDITED]]

Remember kids, Interviewing is a 2 way street. Yes, one side holds the gate keys, which grants them specific powers of Asshole-ness, but be warned that you're not the only show in town.

Anyhow, onto a different topic.

After my previous GDC talk, I drummed up a few bits of research that never made it fully into production, and have caught on to another talk at Austin GDC.

So what's next then? Who knows. Right now I'm just trying to find a decent priced home in the Irvine CA area, and trying to sell a home in BEDFORD TEXAS.

Which, oddly enough, has nothing to do with programming...

~Main

Gets me all tingly..

2009-05-28T00:05:00.003-05:00

Most of your programmer time during a project is spent researching, making decisions and then scrapping all those decisions for some good reason or another. For every project i've worked on, i've usually kept some sort of daily linear journal in electronic form that describes issues / concepts / decisions about a given research / problem and describes the results. These types of logs are massively important for a number of reasons, the most dominant being the ability to correlate information so that I can walk back through niche ideas that may have been discarded for prior constraints, but may now be applicable. I also can store information for specific decisions (ie "we chose 256 as a texture size due to disk read speed on an XBOX360, here's the stats:" ).

Prior forms of this used GoogleDocs but as the amount of information grew, it became massively difficult to actually manage the dataset over time, especially if you wanted to find everything related to "terrain."

I've been doing consulting for a company that goes somewhat overboard with their online wiki process to describe code changes. Effectively any change must be discussed, validated, added to the wiki, discussed again, and then done. Now, in particular, that's overkill, but it did spark a light in my head about how a custom wiki would help me keep track of my daily journals much better than google docs.

So I set off in search of a way to get access to a free wiki to install on my webserver. Unfortintally, most of the wikis require Apache, or Ruby etc etc, which my webserver doesn't do for me at the current cost per month.

And then i stumbled across one of the coolest things I'd seen: TiddlyWiki. The entire wiki itself is contained in a single .html file, so it's easy to keep track of, move, or carry around with you on a USB stick. Apparently I'm a little late to the party, as it was voted one of the "best tools of 2007."

In addition to that, it seems that quite a few number of people have decided to script / modify the system with some rather cool results:
TiddlyWiki FTRUS : A simply wiki skin designed for ease of use
TiddlyThemes: a massive site divoted to custom skins of tiddlys
TiddlyDesktop: Control content via movable windows in your browser.
LATEX: Add mathmatical symbols to your wiki entries
Wiki On A Stick : A much more slimmed down, notes based version of things. By far the most bare-bones version of this type of thing.
TiddlyBackpack : is a nicely slimmed down and cleaner version of things.

If you like keeping these types of data logs, or you think it might be up your alley, then i highly suggest looking at this tool.

~Main

A different scalable threaded architecture?

2009-05-04T09:25:00.005-05:00

DISCLAIMER : This is a wandering brain dump of thoughts. If it doesn't lead anywhere, you can't be disseminated.. you've been warned..

A lot of C++ style API's are out there now to deal with things revolving around task-based decomposition (IE mass-threaded processing of small job packets) :

Intel Threaded Building Blocks

Job Swarm

OpenMP

Click++

All of these models handle the batch-job processing system the same way; the thread manager owns a number of threads, in which each thread will (quickly) run through the cycle of poll-acquire-work-release job tasks.

Although task-based decomposition is really the only way to ensure scalability across increasing cores, in the games industry, we still need the ability to work on Functional-based decomposition (ie the "sim" gets thread 0, the "renderer" gets thread 1) as well as task-based. Specifically when dealing with non-thread safe Graphics APIS, you need a linear execution of graphics actions to occur in sequence. Especially in your main render loop, which might look something like this:

compute shadow maps

sort visible geometry

skin animated characters

render opaque geometry

render transparent geometry

render HUD

Or whatever. The main point here is that this is a very linear process that NEEDS to be linear in order to interact with the depth rendering process of the GPU. As such, it makes sense that for atleast the inner most render loop, you'll need some sort of functional based decomposition of things. And since most of the APIs require the device access to be single-threaded, means that you either need to have a single, long "job" that has a thread affinity to a single thread, or you need to just lock down that thread as the "render thread"

With that concept, it's easy to see how most current generation titles hobble together their threading systems : 1 sim thread, 1 render thread, +N Thread Job Pool.
In practice, this seems to scale pretty well at this point, as you can at least ensure the capability of 2 threads on hyperthreaded machines. The downfall though, is that the Job-Pool threads are effectively just slaves of swarm computing. For instance, if you want your networking systems to receive information on a separate thread, with the above model, you'd have to spawn a job to listen / poll for that work into the pool, which could be difficult with timing (ie are you ALWAYS sure that the next network poll will be 16ms from now?) Additionally, this type of setup only allows you to communicate to the functional-threads through message passing. IE you can't really have a system that 'belongs' on a specific thread, since you only have 2 explicit threads, and N job-pool threads, meaning you can't send a message to a system on a specific thread, without thread affinity and advanced knowledge of the number of threads on the system. The main point here, is that the job-pool threads will never be anything BUT job-pool threads; Slaves tasked to adorn their shackles of mindless job computing.

In HALO WARS, we had a similar functionally threaded system, except that our JOB POOL didn't OWN the threads. Instead, we allowed ANY THREAD to query / wait on the job pool to acquire work. So there really was no 'manager' to the threads; Anyone could fire up a thread and control it's own processing loop, and when it wanted, grab work to do from the thread pool.

The excellent part about this, was it allowed us to bridge that gap between functional and task based decomposition. IE you could easily spawn a thread that now becomes the 'physics thread' and allow it to query the job pool whenever it wants. (Additionally you could perform waitForSingle/MultipleObject calls on the pool, and as you were waiting for your event, you'd grab work and process it..). In addition, it also allowed us some interesting concepts, like cloud processing, where a given thread could have a TCP/IP connection to another machine, grab a packet of work (and the marked memory) and send it off to "the cloud" to be computed. The Job-Pool didn't care about this; It just has jobs, and hopes someone will service them.

The down side of this, was that each thread was effectively bottle-necked by the speed and memory of how fast they could grab work from the job pool. In addition, there wasn't a way to load-balance the number of jobs against available workers; Effectively the thread issuing the jobs was responsible for determining proper job-size, which gets problematic when you consider that it forces the logic for thread-count and job-size determination to the caller, rather than the manager. (Which is not good if you have a team that really doesn't "get" multithreading..)

I've been pushing thoughts around for some time on a decent bridge between these two concepts. I don't really think the linear-dependency-in-job-pools issue has been solved in a 'right' way that doesn't make your brain bleed when you consider thousands of jobs being interdependent. I think things like the D langauage, and "Atomic Function Programming" are better ideas to solve the problem, but asking the current generation of game programmers to develop applications in either would be suicide. Which forces me to keep considering that a mix of hybrid and functional based decomposition is still the best thing out there.

The depressing thing about that, is that it stalls us from actually moving forward with adapting more design-specific elements into threading, as opposed to experience-specific elements. I suppose the bigger problem is how do you make a 'design concept' still play the same on a box with 2 cores, and a box with 20 cores. The first step to fixing this problem, I think, is already on the table in terms of DX11 /360 style multithreading. The DCB / PCB generation process effectively lets you 'render' across multiple threads in parallel, and then submit them to the GPU linearly. I can only see this type of model currently working for GPUs though, where the 'setup' and 'state' setting for a given draw call can be even more of a burden than actually drawing a given object. In my experience, this doesn't translate over to sim related tasks, where usually the operation (not the setup) is the more expensive part.

So it seems that as we continue on this path towards parallel graphics / hetrogenious computing, that the client side tasks (graphics, physics etc) will become more and more parallel and scale better with new hardware, but the sim side tasks (limiting number of units in the world depending on minimum expected experience) will seemingly always stay linear, and a function of single threaded execution. Meaning that we'll atleast always need a few functionally designated threads.

Damn.

~Main

Perspective

2009-02-20T09:29:00.001-06:00

HALO WARS reviews are pouring onto the net like wildfire, and it's an amazing thing to watch.

I realized a long time ago that HALO WARS was going to be a success. To what level I was still unsure, but I knew that people were going to remember it. It really puts things into perspective when you start thinking about the average career time of a video game developer. Most of us burn out within 8-10 years and leave the industry for something that's much nicer to our family lives.

And in that 10 years, think about how many titles you'll ACTUALLY get to ship. Maybe 2? 3? 27? (if you work for EA...) and how many of those titles will be million copy sellers? Or have a million dollar marketing budget? Or action figures? or 7-11 tie ins?

For almost 90% of the industry, the answer to those questions are "None of them."

It's quite humbling to think about luck-of-the-draw when it comes to signing on with a company that ends up producing a product that has this scale and industry response. I mean, every video game company thinks THEY are working on the next big thing, but in reality, how many of them really are?

HALO WARS is big. Really big. If you haven't read the reviews, I suggest you stop by and do so. When I stopped by WAL-MART the other day, and saw 4 separate HALO WARS posters throughout the store, I realized that I should very much appreciate the opportunity I've had to work on such a large scale game. Because who knows if I'll ever have that chance again?

Well, maybe I have an idea about how long it will be...... but more on that later..

~Main

So hopefully I won't be the only one there..

2009-02-17T16:01:00.005-06:00

The February 2009 issue of GAME DEVELOPER magazine just hit my desk, and behold on page 10 is a bump from Editor-At-Large Chris Remo picking my GDC talk "Halo Wars : The terrain of Next Gen".

Apparently it was bumped on GAMASUTRA a after it was suggested as a highlighted pick by the advisory board.

On top of that, massive thanks to Mark Cerny (from Cerny Games inc.) a member of the GDC Advisory board that also picked my talk as a suggested title.

All in All, the talk itself is coming along nicely. I've done 3-4 mock presentations so far, and I'm finding my pacing is working out and can start adding in extra videos and demonstrations of our tool chain.
Below is a slightly censored quickly-grabbed screenshot of our editor. Although the colors don't look all high-tech and funky, the system is very powerful. Hopefully I'll be able to talk about some of the great masking systems and hydraulic erosion technology we put in; Or at least have enough time to show it off ;)

~Main

Play in the Mud!

2009-01-27T23:11:00.006-06:00

No, I'm not talking about the "if there's grass on the field" limerick..

Halo Wars has gone gold, officially sounding the impending closing of Ensemble Studios. And with the impending job hunt coming along I decided to sharpen my coding teeth and start putting together some various research topics that I've been waiting to find time to do; In the games industry, you get so little time to do REAL research and prototyping that's not aligned to a product time line.

Much to my chagrin however, I realized that in all my years in the industry, I did not have a code base that didn't legally belong to someone else. IE all the code I had been using and prototyping on has been the property of the companies I've worked for at the time. Hypothetically, i could continue to use snippets of code from these companies I've worked for, but legally, that's a bad idea; and on top of that, most useful code is so ingrained in common classes & libraries that extracting small portions of it is just a nightmare of pulling a spegetti noodle out of a plate. AND with MS's legal department eyeballing ES with the impending closure, I decided that it had been high time, and decided to throw together my own code base, that I owned the rights to, rather than some other corporate entity with lawyers who look at me like I'm going to steal the coffee maker...

Now, some of you may not find this interesting, or very rewarding, but for the few of us, this type of process can be very meditative. That is, creating and organizing code bases and categorizing ideas and program flow puts us in a very tranquil and zen state of programming when our tasks are usually quite chaotic. But none the less, I needed to start creating a library of code to use. Firstly, I laid down some ground rules about WHAT type of code i was putting together.

This IS a collection of code to be used for personal research and demos. I'm not going to use this to ship a game, or sell to companies.

This IS going to allow slop. I'll follow standard coding syntax & commenting, but why spend time doing useless things. If I did ever want to propagate some of this code into a mainline of a project I'm working on for a company, I will port the code to the new system and only take what's needed. Spending un-needed brainpower on specific nuances in interface design and consistency throughout name spaces is just something I don't want to burn up.

This is NOT an "engine". An "Engine" denotes some sort of pipeline for content processing and handling, and that is NOT what I'm building.

This is NOT optimized. Programmers can spend a ton of time writing the perfect implementation for SIMD systems and faster KDTrees, but that's not what i want to focus on here. You've always got plenty of time to optimize, but you don't always have time to research.

I like to call this library a "Mudbox" (Or "MudBase" like "CodeBase"), not a "Sandbox," specifically for the reasons listed above that this isn't meant to be production & main-line quality code, this is idea code; fast, dirty, and cheap. If I need it to be something more, then I'll re-write it in the context that's needed. (Your first writing of code is usually pretty crappy anyhow. It usually takes 2-3 revs of the 'concept' before it solidifies and actually results in a high quality product.)

At this point, I've got 100% of the code systems done that I originally planned for. Which includes enough functionality to port various demos and code systems that I had using other code bases to my own, and have them work to produce the originally desired results. Which is a very good thing, considering I started entirely from scratch!

To be honest, it's very liberating and free-feeling to be working in this type of code base. And I honestly encourage all of you to break free from your corporate code bases, and make your own mud-base to just hash out ideas and 'fun code' in. I think we as programmers get to focused on lots of minute details : "Well, as I write this file system, I need to take into account the fact that we may be using archives later, so that information needs to propagate into my design."
Yea, you're supposed to think that for a shipping product; After all, you're being paid to not need to re-write code. But for your personal code base, fuck it and just use fopen with no error checking. I mean who's watching, really? And is it really the point to write the most stable system, when you're just testing if the overall concept for your crazy brained idea is going to work at all?

Another great part about breaking free from corporate code bases, is that you can vulture some code from great resources on the internet. TBH I've most likely bought in a little TOO hard to the "Good programmers code, great programmers reuse" concept. I mean really, I can't recall how many times I've re-written a thread safe vector class, that I STILL don't own the rights too; That's quite a defeating feeling.. There's some great resources out there that you can directly look at when making your own mudbase, and quite frankly, you SHOULD be looking at other resource material!

Here's some great resources that you can use when looking for this type of code.

Intel Threaded Building Blocks

I suppose the moral of this story is: If the corporate owned code keeps grass from being on the field, then write your own code base and play in the mud.

Ok, so I did end up referencing the limerick...

~Main

Sparse Voxel Octrees

2009-01-08T21:05:00.003-06:00

#1 Happy New Year.

#2 My child has been born! I've now been defecated on by Bipeds as well as quadrupeds..

#3 Sparse Voxel Octrees:

I've been spending a great deal of time lately attempting to make heads / tails of the whole 'sparse voxel octree' technology that ID is touting as the 'next big thing'.
You can find a good writeup of similar technologies here at Anteru's blog and get the origional post from PC Perspective.

What piqued my interest in this topic was the latest Windows Graphics Summit, in which we discussed the concept briefly in terms of it's supposed 'silver bullet' to artist content generation.

I did a little digging on the whole 'point cloud' / 'voxel' rendering process, and drummed up some good links.

Jon Olick from ID gave a Siggraph talk on their tech, you can find a discussion on it over at OMPF; a website, IMHO that contains some pretty good resources in terms of raytracing and hardware black-magic. The link provided also contains many sub-links to other great papers on the same topic.

An excellent paper over at Pixar's vault : Point-Based Approximate Color Bleeding echo's a similar desire to work in a point-cloud space, rather than a parameterized mesh/texture space. Their voxel setup allows them to approximate various forms of lighting to be used for near / far geometry. Pixar also has a great chapter in the book Point Based Graphics, that, from what i can tell, was written entirly by the guys over at Pointshop3D (which is an interesting concept in it's own right). The chapter details their point cloud system for the RenderMan system that uses Brick maps and other fun things to access LOD in volume space for various rendering reasons.

Sylvain lefebvre (whom I will always give props to for his research into the texture synthesis relm) has a great derivation that appeared in GPU GEMS2 titled Octree Textures. It's a little different concept, but the same idea in the end;

After going through all this research, and implementing my own version of an SVO system, I came to a couple conclusions that I'd like to share.

After implementing my own version of the system, I've got some thoughts that I figure I can briefly share:

As far as ray tracing goes, when we discuss making it accessible to the hardware, standard poly/ray ray tracing is quite difficult to map to the hardware. And by this, i mean that it needs to be simple and easy enough to create dedicated hardware set aside to actually produce the system. Like putting LZW on a chip, or a Hardware tessellation unit. Voxel grids on the other hand, are much simpler to implement in the hardware relm for obvious reasons. I can't help but to think that if the future was to design graphics hardware for it, then yes, voxel ray tracing would be easily produced in hardware, and would likely give us a much better performance throughput as far as ray tracing is concerned.

Voxel data for an entire level takes up an epic crap ton of memory. You can consider that most geometry in videogames right now get away with a few memory tricks by re-using tiling textures, and instanced objects. But for a voxel representation, each one of those pixels (voxels) will be unique; ultimately forcing you to need an out-of-core management system in order to interact and use it properly. Now, IMHO that seems like a stretch to me; I know we're moving in the direction of multi-core systems, which enable out-of-core compression and streaming, but it seems like a step backwards to increase our memory footprint (to a MASSIVE scale) to achieve the same visuals and reduce our ability to handle dynamic environments. Now, you can do this with the proper setup, but I'm simply stating that maybe we could do something else with all that bandwidth; instead of dedicate it to streaming in the same scene representation that we can achieve now

If you ignore the memory / streaming footprint issue, Voxels make a great deal of sense from the performance perspective. In traditional rasterization, you have the difficulty with overdraw and tessellation problems that occur when dealing with ZBUFFER style rendering. On top of that, we have to implement a great deal of extra LOD systems for geometry and textures in order to effeciently balance the payload when we get sub-pixel tris/texels. Octree Voxel tracing fixes that; As your ray is being cast through the octree, if the children of the current node have a screen space area that's less than a pixel size, return the color of this node instead of moving lower in the tree. That's a pretty interesting concept if you think about it. Hypothetically, you could increase your detail indefinitely. It also removes the need for artists to be concerned with memory footprint / geometry detail, because it's all translated into something that the programmers manage, rather than the artists. Which from my experience is a huge win from the asset creation standpoint.

With the links I've provided, you can find a great deal of other smart people talking about the same idea. To be honest, after implementing the concept myself, I can't see this technology really taking hold of the industry when stacked next to Realtime raytracing in a multi-core universe.

Now, if hardware manufactures came back and started providing dedicated hardware for this type of task, then yea, I can see it catching up, but that's a huge amount of time down the line. I have a feeling this technology is a good idea, but will fall the way of the hype of 'mega texturing.' Great idea, but what about it makes the end user really want to pay the extra money to upgrade their box to buy it?

Just like attempting to implement realtime GI for games; Is the dev time and result enough to squeeze an extra 30k product sales for your title?

If not, move on to something more important; like trying to figure out how to change a dirty diaper in 30 seconds flat..

~Main

Come to GDC. See a Roach talk!

2008-12-13T09:27:00.003-06:00

I have to say that I'm both very excited, and massively honored to be selected as a speaker at GDC 2009. My talk HALO WARS : The Terrain Of Next Gen, will cover the long story that has been the development of the Halo Wars terrain system. As many remember from the prior 2005 Ensemble talk about the graphics of AGE3, terrain is a HUGE system in an RTS game, easily taking up 75% of the visual screen, and around 40% of the time to develop a given map. So stream lining that process for maximum visibility and creation process is a huge win.

I won't talk too much about the process, or the talk, but instead encourage you to come see the talk and try not to throw tomatoes at me.

I will, however, leave you with an unofficial screen shot of our terrain system!
This pic is showing off our ability to sculpt arbitrary overhangs in the terrain system and increased UV control to combat texel stretching on large vertex displacements. If you look closely, you can see some of the highlighted features of our terrain material system; particularly you can pick up on sub-surface scattering within the ice, and emissive channels inside the shadowed areas. Also, if you look towards the edges of the screen (the overhang spikes), you'll see a great use of our "Terrain Clip-Art" system, which allows content creators to copy areas of the terrain, store them to a library, and place them later like large pieces of clipart.

click for larger image:

And to clarify, that is NOT a mesh that was 'attached' to the terrain. Rather that screen shot was generated 100% inside our terrain tool using our editing features and systems.

Viva GDC!

~Main

Lets talk about assert

2008-12-01T09:38:00.005-06:00

Gather around children, uncle Roach has something to teach you all.

The assert code path should be defined in non-assert code
Can someone tell me what's WRONG with the following chunk of code?

int customVector::getValueAtIndex(int idx)
{
   assert(idx > 0 && idx < mNumElements);
   return mValues[idx];
}

"Why no uncle Roach, that sure looks fine to me!"

Well it's not; Can you tell me what happens when that assert gets compiled out in a final build, and the index value is out of range? That's right children; Problems happen.

Firstly, we need to understand that an assert is a great debugging tool, because of it's usage and ability to alert the programmer to specific boundary cases of our coding patterns. Checking that a value is null is a great example:

void deleteThis(object* obj)
{
   assert(obj != NULL);
   customDelete(obj);//** edited.. see comment below
}

The real question here though, is what SHOULD the code do in the case that the assert doesn't exist? If you take that into account, than this is not a safe snippet of code; and definitely not something you'd like to ship in your $20million dollar project.The issue is that the code path to be handled when the assert is compiled out is missing; which is crucial, as you'll get a random crash in final builds, that is damn difficult to rack down if you don't properly check for this condition. Below is the proper snippet :

void deleteThis(object* obj)
{
   assert(obj != NULL);
   if(obj == NULL) return;
   customDelete(obj); //**edited.. See comment below
}

The rule of thumb here is that you should properly define the accurate code path to occur when asserts are removed.

Don't use an assert when you meant to use fail
Assert != fail. Let me just get that out in the open. When you want an ASSERT, you're generally looking for information about a specific conditional that can allow your application to hault operation in order to present some information to the user, before deciding if it would like to stop execution (fatal assert), continue on, or ignore that assert in the future.

When you want a FAIL though, you are looking that the code is in a state that things are generally wonky and recovery will be an issue. You'd generally like all the logging information and what-not that an assert has, but a fail is generally more of a hard-termination.

"Well golly uncle Roach, a fail sounds like a fatal assert to me. Why can't I just use assert and stop execution?"

Excellent question Cleetus. The problem is that as a programmer, you should be using the proper syntax for the proper result. Throwing assert as a catchall seems like a good idea, but quite frankly, there's positions where you WANT a failure to occur, so that you can accurately catch it.

A great example is loading data from disk :

void loadAssetArchiveFromDisk(const char* archiveName)
{
   const retCode = loadArchive(archiveName);
   assert(retCode == LOAD_OK); //Dirty disk error?
   if(retCode == LOAD_OK)
      OpenAndProcessArchive(archiveName);
}

Let's say the above code fails to load the archive. The assert fires, and we have the option to continue forward. But is that really what we want to occur? Let's say that this is a critical archive that contains all the strings for the entire game. Would we really want to gracefully bail out like this with a simple assert?

void loadAssetArchiveFromDisk(const char* archiveName, bool failOnNotLoad)
{
   const retCode = loadArchive(archiveName);
   if( failOnNotLoad && retCode != LOAD_OK)
      Fail("retCode != LOAD_OK");// NON RECOVERABLE

      OpenAndProcessArchive(archiveName);
}

Now the code will properly fail if the archive doesn't load (and it's a core archive). This allows you to properly call dirtyDiskError on the console, or whatever other handling you want. But not ASSERT!

So what?
The point here is that assert is a good idea, but it's sometimes used as a catch-all drunk drawer by programmers when it should really be used in proper places at proper times. It is not a silver bullet of debugging, but most programmers use it like it is.

Be careful though, because silver bullets can still shoot you in the foot.

~Main

** changed Originally from "delete obj" to "customDelete(obj)" in order to continue to provide my point without everyone getting caught up with the fact that "delete NULL" is valid in C++. Thank you for your feedback.

I am Jacks' stress level

2008-10-23T22:27:00.003-05:00

The stress level around ENS right now is epic.

You'd be amazed about how fast you have to learn when thrown into something. Like a drunken father, tossing his son into the lake w/o a life vest, you learn to swim by instinct and adrenaline more than any conscience method. That describes the vibe right now perfectly: Caffeinated adrenaline on stress steroids.

We've passed content complete, and are chugging towards ZBR full steam ahead, and I just can't seem to get caught up with the clusterfuck of bugs that keep landing on my plate. And not your tiny, "whatever, we can ship with it" bugs; no, these are the kind that carry strap-ons and chant Gregorian hymms while walking down the street glaring at you.

Memory has been a big problem all-of-a sudden. With the push to content complete, we realized that about 4x assets went into the game in about a 48 hour period, and that none of our systems or budgets expected that load (and no one was policing them in the process). As an oddity, we've recently come under the question of 'Can we ask the OS for every block of allocated memory?' Basically, there's a problem when you try to override malloc/new/delete/HeapAlloc/XMemAlloc/XPhysicalAlloc etc. in that a 3rd party library can easily bypass one of those and go right to the hardware to allocate data. To my dismay, going back and forth with XboxDev support provided no insight into the potential to track down allocations that were coming from 3rd party libs that we didn't have tracked in our heaps. On windows, I've been able to do this sort of thing using an external hooking system. A strategy most noted for hackers and keyloggers, this allows me to hook into any app and intercept all calls to it in order to redirect them to my own app. But, XBOX doesn't play as nicely, and I couldn't get that same system up and running (I tried..)

At this point we have to throw our hands up on the lost memory. My estimate is that we've always been missing this large block, and until all the content went in, we never really started getting close to needing it. With more time, we may track it down, but with only a month left until ZBR, there's bigger fish to fry (like the list of 30 heisenbugs on my list right now...

With a 4th quarter QB sneak, I was able to shave us off about 20mb per scenario and give us that memory back across the board, which for now, puts every map in the green, and keeps us from (hopefully) having to make decisions about cutting larger features from the game. We should be able to do a per-asset analysis of textures to get all our maps above the budget needed.

Performance is next on our radar. It's no secret that we've written our rendering engine elements to be multi threaded as much as they can. Taking full advantage of the awesome 360 hardware we've got available. The sim though, limped along, and never made the transition. So now, we've got around a 100ms sim frame that can easily bounce above 120 if you drop a few extra groups of marines on the map.

The problem here, is how do you accurately fix performance without knocking over the house of cards that is the simulation? Multithreading it now seems like a lost cause, We'd introduce more bugs then we'd have time to fix. So we may just have to settle for multiple render frames per sim frame and ship it. I hate the fact we have to do this, but to be honest, I could see it coming.. no one really took the ball on making the sim work 'right' there was just a group of programmers who were constantly focused on making it 'work' at all. The render frame is still around 30ms though ;)

I'm finding out ungodly amounts of tidbits of information about our engine that I never knew.. small pieces of data that would crumple in the light if you brought them to the surface, so you can only behold them in the belly of the evil beast. But I suppose all the stress is forcing me to learn this stuff. Which can't be all that bad, I should have learned it from the beginning, but just didn't have time to play catchup with our tech-lead programmer; I had a full other list of things that had to get done in parallel.

If you haven't read it, I really suggest "Why don't zebra's get ulcers" I've found it an excellent reference to the human stress system, and the effects on the human body. It really makes you take note of how mental stress really does fuck your living world up, and why working 15 hour days for the next 4 months is not going to go well for my health.

But fuck it; it could be worse I suppose. At least I don't have to worry about getting killed by a Lion when I walk out the door in the morning.

*shrug*

~Main

I'm Chargin my Resume!

2008-09-14T08:00:00.002-05:00

About 3 years ago, I stood in front of one of my first classes @ SMU, and told them a very, very important piece of information. I explained to them the fickle, odd nature of the games industry, and described that they should get used to the fact that sooner or later, the company they are working for would close, and they would be cast out into the cold wilderness to handle things themselves. At the time, TKO had just closed, a company I had hardly worked at for more than 3 months, and to be honest, I expected the stability of Microsoft, coupled with the history of Ensemble to have less of a chance of that same problem.

I was wrong.

Which I suppose most everyone has heard the news : Upon the completion of Halo Wars, Microsoft is shutting down Ensemble studios, and Laying us all off.

I had a number of reactions when i first heard the news Tuesday morning :
My first thought was "HA Called it!" To be honest, the past 3 years haven't been a cakewalk @ Ensemble. The Halo Wars development has been increasingly difficult , ad we've had numerous prototypes all shut down by Microsoft. In short, there was a massive difference in vision between the Ensemble and Microsoft management, and that divide grew larger once we added a large amount of people to the company, and wasn't producing any new titles.

My second thought was "Oh shit, I'm out of a job!" This thought lasted about 30 seconds before my third thought : "Oh, wait.. I've got like 10 job offers in the last week..I should be ok."

Which brings us to the 4th thought, the one that still rings my head to this day (and until Jan 1st, when MS officially closes the doors.) "Wait.. My first child is due January 30th...."

Needless to say, this week has been difficult on my expecting wife..

I can't lie, the work-life balance at Ensemble has been getting pretty harsh in the past 8 months; where I found myself less and less interested in sticking around. Decisions made by management made less, and less sense, and multiple slips and lack of progress on Halo Wars was getting intolerable. I can't lie, I'd been debating leaving after the ship of halo wars for many months; At which time, I realized a crucial trend in my career : I'm dedicated to the project, not the company. In other words, I have no love for the management and decision makers behind the title of the company. I no loner feel that I owe them for signing my paycheck and handing out company perks. I've been sticking it through the ship of Halo Wars for two reasons, #1 to get a title that I started, and brewed the original code base into the wild. and #2 to stick with the other developers whom have shed blood over this project in the past 3 years. Much akin to a soldier in the trenches, dealing with flying bullets, feeling more loyalty to the others in the pit with them, than they do to the government that assigned them the standard issue boots they have to wear.

I think I'm more so hurt by the mental ramifications of this separation. In any relationship, it's usually better for it to be terminated on your terms; and I'd much rather move forward saying "I'm leaving Microsoft for reasons X,Y,Z" than "Microsoft laid my company off for X,Y,Z" I know that the company closing had nothing to do with me personally, but the sentences above have their own stigma associated with it. I expect every interview to ask those questions, to which I unfortunately must give the 'not as nice to my ego' response of the two.

So what's next for the Roach? Well, there's never a shortage of head hunters in this industry, and there's never a shortage of positions available for a balding graphics & systems programmer. So, if my wife and I are willing to relocate, we've got more options that we know what to do with. Staying local is difficult, as the DFW game development community is very, very small, and the probability of getting in at one of the local companies is even smaller.

Maybe I'll start my own shop.. Hmmm....

~Main

Yea, Screw You ATI.

2008-08-23T07:36:00.002-05:00

I'm sure you've seen the Starcraft 2 techincal papers:
Here, here, and here

The biggest take away from all this is the fact they've moved to deferred rendering for their RTS. I am a big proponent of deferred rendering, and originally pitched it back when we started HaloWars as our lighting solution. Unfortunitally, due to EDRAM sizes our lack of understanding with the hardware at the time, we couldn't' figure out how to pass around that much information in memory to store the frame buffers, and still be 4xAA compliant w/o taking tons of memory from our content creators. (We know better now..)

Those of who you've been around for a while, remember a nice little chat I had with some ATI people back in 2005. Below is the original post, with a few spelling corrections. What took me by such surprise back then was how quick they were to just toss the concept out the window. Obviously no one had tried to use it before for the RTS genere, but that doesn't mean it was simply 'going away.' I think at this day, most all games use some sort of 'deferred' system of either post screen effects, or final lighting / HDR passes, which we can effectively view as a bastardized attempt at raytracing on GPUs.

Thursday, July 28thth
So, I just got back from microsoft meltdown 2005. I have to say, pretty interesting stuff.

So, let me rant for a second... I had a chance to discuss 'Deferred Rendering' with some of the bigwigs over at ATI. I was quite surprised about how easy they were to dismiss the technique as invalid. To be fair, I did come into the situation pro-deferred, and although they brought up some valid points, nothing was REALLY said that would cause deferred rendering to not be a valid technique for generalized situations. (Besides, 'it doesn't scale well' which was actually brought up by some of the DirectX ninjas)

To preface, this was the first words out of the ATI tech mouths (note, plural, as I debated with about 2-3 of them for the better part of 3 hours.): Early Z will give you the same performance boost (in fact, better) than deferred rendering, and the amount of time that's going to be spent turning it into a viable technique, is longer than the lifetime of the technique itself. And to top it all off, forcing a single BRDF for the entire scene isn't a good plan for next gen systems. It's just not worth it. Ok, valid, Potentially graphics hardware will allow a large jump w/ the dx10 stuff where early z cull will be pretty nice. And YES, a single BRDF for the whole scene does tend to make artists a bit squirmy. BUT, that's not the reason I like it.

The example I proposed to them: Imagine you have a full RTS. You've got dynamic environment lights, texture splatting on the terrain (avg 25 splats per chunk, lets just say 4 chunks visible), 100+ (min) skinned units on the screen, about 100+ non-skinned prefabs. We've got 3 main directional lights (one main for shadows, the other two are just support), and then 35 local lights on the terrain, attached either to objects, or just placed by artists for 'cool' appeal (note, both point and spot lights for the locals). We're using Tom Forsythe's multi-frustum shadow map approach, oh, and we'll just throw in reflective water for the hell of it.

My argument was, that in this sort of situation, Deferred rendering is a BIG win. (And in my mind, 'the way') So first, lets talk about simple light management. I offered this suggestion 'So, with that many lights in the world, we have to search our hierarchy for local lights every render, decide which are the most important, bind those to our shader (assuming PS2.0 for current hardware), take the less important ones, and either throw them into an ambient cube, or some sort of SH mapping, and then bind those to the shader. Simple management heuristics at this point already tell us that deferred is a big win here. Having to manage the searching and binding of each of those lights every frame is pretty difficult. On top of that, we're using the multi-frustum shadow map approach, so potentially, each shadow casting light could have 2-3 shadow maps. (Which, in it's native implementation, requires each receiver to know what maps it's receiving.) So already, we're looking at a pretty messy management system for a single object on the screen: What lights do i get directly, what lights go into my ambient setup. What shadows do i receive (and am I capped?), and Do i have enough texture slots left in the shader for shadow maps (not taking into account albedo, normal, and a few control textures). I mean, at this point, you have to admit, from sheer management issues alone, the ability to separate the lighting passes from the objects is a pretty decent win here.

At which the ATI individuals responded: Well, that can be solved with an UBER shader derivation. Create a version of each shader for each potential combination of lights and shadows, and just assign that to the mesh before it's rendered.

Well, I countered, Isn't that limiting your artists to a single, predefined group of BRDF's? Just like deferred rendering?

Not really, you can have multiple materials. You just need a version for each shader for each combination of input lights and shadows.

Granted, this is the path that halflife 2 took, but, from what I recall, their shader directory ended up being some ungodly high number of MB in size. Fine, I'll accept that I allowed, so what about all the other effects that we wish to add globally to a scene, such as atmospheric scattering and what not. That would exponentially shoot up the number of shader combinations for each type of material to be affected by these global effects.

Just Multipass it then.

What about being batch bound at that point? Seems like tripling your calls on such a setup would be a bad thing?? X draws Per character * Y reflective surfaces + Z shadow maps??

*Shrug* Yea, you'd be draw bound at that point..

At this point, I was just dumbfounded.

I don't know if i was just talking to the wrong group of guys, but the whole conversation came across less as 'Hey, we've done the research, and here's some viable reasons why DR would cause some problems in your pipeline.' and more like 'Hey, fuck you.'

[...]

Anyhow, my thoughts on deferred rendering lie in the sole fact, that management of lights, and shadows becomes quite easy. Not only that, but keeping the headache of bazillions of shader combinations is a big win. Yea, the DX Ninja's are correct, It doesn't scale well to lower end systems (non FP Blending for example..), and, convincing your artists that a single defined set of control values through a single BRDF is useful, is quite difficult. I really think with the amount of Post processing we're moving towards, Pushing the graphics card itself (forcing a filtrate bind) with a fullscreen quad, is more efficient that resorting back to multipassing and batch limiting yourself (ESPECIALLY IN DENSE OBJECT ENVIRONMENTS!!!!)
Now, WRT earlyZ, Yes, I do agree that Earlyz will give you one hell of a performance boost. BUT, it still doesn't solve the light / shadow management situation, or the batch count submission problem. It's It just saves us on fillrate, which is entirely on the GPU side of things..

Fine, don't listen to me in 2005. You'll have to listen to Blizzard from now on.

Assholes.

~Main

OMFG!

2008-08-18T08:35:00.004-05:00

I've been absolutely swamped these past few months. We rolled right from E3 crunch to Code Complete, to Code Checked Complete, and just haven't had any time to sleep.

Halo wars is getting some great press from the e3 buzz. You can find some of it at the main site (halowars.com). We've also been nominated by the 'official' e3 board for 'best strategy game.'

The '08 E3 demo went a little smoother than the '07 one IMHO. We started about 2 weeks before the event in 07, which caused many, MANY late nights, including a few 24 hour pulls to get the whole thing done in time. The killer in this process was the amount of last minute "Ooohh, this would be nice.." on top of feature requests that the systems were FAR from being able to produce. At the end of it all, everything was realtime, and ran at a great frame rate, but I think we could have achieved the same results with much less headache if we would have scaled back a bit, and focused on major polish items.

This year, we had a similar problem occur. Our 2v2 map had some MAJOR performance problems, to the point that 24 hours before we cut our disk, the leads were considering not showing the map at all; which to us on the tech side of the fence, really didn't like the sound of. Needless to say, around 1-2AM, the magic happened, and the game jumped back up to 30fps on our 2v2 map.

Don't fuck with the tech team.

~Main

How to teach Parallel Programming

2008-06-23T08:28:00.006-05:00

Intel dev blogs just posted an interesting question about 'What 3 things students need to know about parallel programming'. I'm sure we're all aware that the answer is '3 things aren't enough..' But for shits & giggles (which i always found was an odd combination of words for an expression...) let's run with this question..

I moonlight as an adjunct professor at SMU GUILDHALL for game development. I've been teaching there since about 2004, and have taught various courses on Math, Phsyics, Advanced Rendering, and am now teaching a course on concurrent programming for video games. This is my first time teaching this course on threading, but since I got to make the curriculum myself, it came pretty easy to me ;) The class is 8 weeks, and I was lucky enough to have Rich Geldreich and Andrew Foster along to help lecture along the way. All in all, we've had a really good result in terms of getting the students to understand and use the data in a practical application.

Here's the basic breakdown of what the kids need to know:

Introduction to threading.
Introduction of basic threading concept at both hardware & software levels. Introduce low level threading primitives : Event, Mutex, Critical Section, Semaphore, Monitor. Introduce basic threading control (waitFor*Object(s)...)

Thread safe Memory; Thread safe Code
Introduce importance of memory models & ownership between threads. Discuss various memory models and how they relate to threading. Also discuss thread safe code, and how to make your code thread safe.

Thread safe Containers
Introduce synchronization concepts (fine grain / course grain synchronization). Introduce various thread safe containers (fifo, vector, etc).

High level threading control
Introduce message passing & memory transfer between threads. Introduce Producer / consumer architecture; Fork & Join; Thread Pool.

Task Synchronization
Discuss task generation & work distribution. Discuss task identification and data decomposition for threading. Introduce parallel_* concepts and how they fit into everything. Discuss higher level locks & task dependency

Lock Free & Wait Free algorithms
Introduce lock free containers & algorithms.

I have to say that the kids have been responding very, very well to the class work. Besides their brains melting w/ lock free algorithms, they have been picking up and running with threading and memory safety quite well.

Quite frankly, we need to start pushing parallel programming to our students. Hardware manufactures are quite obvious about the lack of desire to make single core chips any faster, and things like LARRABEE just prove that we should be jumping on the multi threaded bandwagon!

~Main

The Seeds of Wait-free Synchronization

2008-06-09T07:52:00.004-05:00

Is this code thread safe?

Class NB_FIFO
{ 
   volatile FIFONode* mHead;
   volatile FIFONode* mTail;
   void push(Object obj)
   {
      FIFONode* fn = new FIFONode(obj);
      while(true)
      {
         FIFONode* last = mTail;
         FIFONode* next = last.mNext;
         if(last == mTail)
         {
            if(next == NULL)
            {
               if(last.mNext.CompAndSet(next,fn))
               {
                  tail.compareAndSet(last, fn);
                  return;
               }
            }
            else
            {
               tail.compareAndSet(last,next);
            }
         }
      };
   }
}

At first glance, you would assume that this is very much in violation of a thread safe model. But, you're incorrect; Not only is the above code thread safe, it's completely wait-free. But it uses a concept that not many programmers are familiar with : Lazy synchronization. (Which, if you said "No, it's not" don't feel bad)

Wait-free algorithms are becoming more and more needed as multi-core boom starts to hit full stride. The above code combines a number of concepts to remove the need to do locking on a dataset in order to operate on it.

The ultimate goal for wait-free algorithms is the removal of locks and resource contention, and instead replacing it with :

Atomic Operations
Memory Barriers
Crazy ass new ways to look at the dataset.

The first two shouldn't be too 'off the wall' for most of us. Atomic operations are a great tool in the programmer tool set for parallel processing. But few have bridged the gap to understand that it can be used to remove locking! And memory barriers, (or the volatile keyword) are a must have for ensuring that our data is consistently valid across multiple thread reads.

Lazy Synchronization is just popping up lately as a means to remove blocking from thread safe containers. The basic idea behind the process is that instead of limiting threads from accessing resources in the data structure, we instead allow them to help out with the work we're doing. Effectively turning the biggest problem, into our biggest benefit. Lazy Synchronization allows accessing threads to encounter 'broken' or 'partial' states in the container traversals, and if such a state is found, the current thread fixes up the problem before moving on. This allows that if the modifying thread has only made partial changes to the structure, but has not yet finished, any other accessing threads won't get invalid data, but will fix the problems and move on. Effectively though, this breaks the ACID model of synchronous computing; specifically the 'don't leave your data in a weird state' one. But patches it up nicely by allowing other threads to fix it for you!

The great thing is, that it doesn't stop there. I've talked before about multi core blowing up, and there's even more proof of it as the days go by, and as that occurs, we'll start needing more wait-free algorithms to help along the process, and reduce resource contention and performance issues from our current hardware memory models. Cliff Click is proposing a nice elegant solution to one view of the problem (although he seems to ignore the 'out of core' versions of the same data containers..) And these guys like to talk about what's wrong with the current threading primitives.

Still don't get the point? Then here it is: Wait free algorithms are coming. They are already here. If you fancy yourself a systems programmer, then you need to learn the full in's and outs of these models. Come another 5 years, Course grain synchronization models will go the way of the dinosaur.

And I can't wait!

~Main

Optomization path

2008-05-28T07:39:00.002-05:00

The dark black art of optimization is a tricky little SOB. It doesn't come to you overnight, but rather over time, as you continuously understand your code base, and stub your shin on the pitfall-in-the-dark performance problems of games development. No one really 'talks' about optimization, rather it's just assumed that programmers will write the best code possible, as fast as possible, and we'll clean it up on the back end. More so, it seems most people don't know how to talk about the proper way to go about optimizing.

So here's my personal checklist of tasks when looking at slow code.

Anything that can be moved into the Async Phase, should be.

This is the smallest change footprint in terms of code flow, and yields the biggest perf gains. IMHO we should be taking a serious look at the sim for this purpose right now.

Can anything be ignored / non processed

Fastest processing is the one we don’t have to do. (You’d be surprised about how often this is a big factor…)

Can anything be batched / deferred

LHS and pointer chasing issues can sometimes be addressed by this process.

Inner loop fixes

Can things be bubbled up, out of the inner loop?

Is it faster to compute elements of the loop seperatly?

IE it may be faster to compute all the VMX operations in a loop before the data processing loop. Analysis shows that VMX hits a sweetspot at a large amount of instruction throughput, so computing one at a time inside the loop could actually be slower. Especially if you’re just removing the data from the VMX register to the float or int registers.

Address slow code inside the loop

LHS, L2 Cache miss, etc

Some have told me that I'm doing it backwards, that I should be looking to optimize the inner loop first. Truth be told, optimizing the inner loop won't get you the massive speed increases that you would think of. And often, you'll find that the slowness of inner-loop code just can't be fixed.

What then, smart ass?

In my experience, taking a look at multi threading as a first step allows you to get the best performance improvement w/o having to make the most code changes. For instance, if you've got a 6 thread thread pool, you should be expecting a 6x speedup of your processing immediately. Not bad for a day's work... Now, if you're code's not thread safe, or just can't be computed in parallel, then you need to start looking at serialized fixes. IE bubbling up slow code out of loops, and filtering operations that don't need computation. As another task, it seems that you'll rarely get that type of performance increase from simply filtering out un-needed work, but every bit helps, and once you cut-the-chaff, you can start looking at optimizing each path (or combining paths) to get even greater gains.

At the end of the list is the inner loop optimizations, which includes low-level performance issues. I wait until the end of the perf for this, mainly because it takes quite a bit longer to track down and address these issues when compared to the other items above.

~Main

Programmers don't read?

2008-05-27T08:51:00.002-05:00

I stumbled across this article a while back from coding horror (whom I've discussed before) discussing why programmers shouldn't read books anymore. I've personally discussed how books exist in my little mind, signaling that I do, in fact, read books. The problem with print media is that it moves at the pace of handicapped snails when compared to the day-to-day changes that the internet can offer. New algorithms and discussions can be presented, tested, and destroyed in the time it takes for one chapter to be proofread for a print book. In that same vein, however, the internet is cluttered with a great deal of crap, mis-knowledge, and lack of understanding. Things that proofreading, and controlling the 'big picture' all flesh out when creating a print book. All that aside, I think that there's just some great literature out there in book form that benefits from being in a cohesive world view that you can only get from a book. You know, the thing that doesn't contain pop ups and advertisements down the side of it?

I'm Published and more importantly, I enjoy publishing. I think it's because I enjoy reading publications too. I'm the guy sitting at the lunch table that will talk to you about anything technical, for any reason. I just like hearing new ideas and concepts that you can't find anywhere but inside someone else's head. I also enjoy reading good books about good topics.

I've told my students @ SMU many times, that if you're not reading publications, and potentially not considering writing them, then you're not that good of a programmer.

Why?

Simply put, programming is an ever-evolving blob of skill sets. We're always changing, probing, asking, challenging, categorizing, and debunking even our most solid dogma. If you're not out there reading the latest in this concept, then you're behind the curve. Quite frankly you can't learn it all from just programming. In fact, if that's all you do, program, and don't learn from other resources, then quite frankly, your code is going to be very short sighted, and is going to suck.

I still find that the best way for a programmer to learn is to have a mentor. I guess it's something about the mirror neurons in our brains that make information coming from another human so much more potent than information coming from a piece of paper.
I can personally say I've had a few mentors in my career. Each have progressed my programming abilities by leaps & bounds each time. But I find the things I learn from these other programmers are not low level coding gems, but rather, higher level concepts and programming patterns. You know, the type of shit that you HATED when you were in college; Reading a 400 page book about how important it is to use "//" vs "/*" doesn't stick when you've got 8 finals to cram for. I suppose that proves there's a time for everything.

I would say that mentor programming needs a solid place in the games industry. Game programming is STILL not like any other product programming on the planet. IMHO The application programming world was always under lock-and-key, and now the dangerous world of the web has seemed to develop a leash and collar. But games programming is still such a wild-west world. Each studio handles issues in a way that's completely different from other studios, containing separate vibes, skillets, and personnel. And because of that, you need to learn abilities that will carry you between these jobs, and still make you a valuable professional.

A great example of this comes from a time I worked at a smaller game company. The programming lead had pointed out another programmer, and mentioned that he used to be a big-shot at EA; Shipped a bunch of titles. I dutifully took note, and continued on my way. About half way through the project, we noticed that the game wouldn't load any more in final builds. The culprit? The EA pro had replaced all the error checking for model & asset loading to exist INSIDE Assert(..) macros, so that 50% of our loading code was compiled out in release builds.

Regardless of the fact this guy worked @ EA, and shipped games, he blatantly didn't bring over the basic skill sets to keep him from blowing such a rookie mistake.

So, if you're just starting in the industry, find a mentor, read some research papers, and spend some time talking to the guy at lunch about crazy ass programming ideas.

~Main

Death Of A Thousand Default Values

2008-05-22T07:02:00.003-05:00

I'm sure we've all seen this:

class MyVideo
{...
int loadVideo(string name, bool loop = false, bool fullscreen = false,
int ioBufferStart = 256, int width = 10, int height = 20, int xLoc = 10, int yLoc = 20);

};

But, it should really look like this:

class MyVideo
{...

class LoadParms
{
public:
   string mName;
   int mIOBufferStart;
   int mWidth;
   int mHeight;
   int mXLoc;
   int mYLoc;
   bool mLoop;
   bool mFullscreen;

   LoadParms():
    string name(""),
    loop(false),
    fullscreen(false),
    ioBufferStart(256),
    width(10),
    height(20),
    xLoc(10),
    yLoc(20)
   {};
};
   int loadVideo(LoadParms lp);

};

The reasoning lies in the fact that default values will, eventually, screw you. Period. If not you directly, it'll screw someone else, using your code. If it hasn't happened to you yet, it will. Having a class that contains all the loading information keeps the actual load function nice & tidy, as well as it allows you to generate default values w/o allowing other users to pass in wrong values to wrong items when they want to set just one variable.

You shouldn't be worried about creating a new structure for this data. Most of the load options would have copied the data to the local version anyway, so you're just temporarily moving some information onto the stack.

~Main

Low Level Performance : FCMP (2)

2008-05-10T18:10:00.003-05:00

First, this is an amazing day for you and I. This post breaks a 3 year streak of only posting 8 times! (Yes, look to the right to check for yourself.) You're welcome. Now bring me some pie..

Secondly, let me address a little "*" that should have been assigned in my last post. FCMP logic causes problems in Out-of-order architectures like the PowerPC inside the 360. As posted before, it's caused by the fact that the branching hardware occurs before the FPU logic on the power pc, so in order to get the result for execution, the pipeline must be flushed and the branch must be processed before everything can resume.

One other problem exists on PPC platforms that ALSO comes from incorrect use of FCMP, and that's Load-Hit-Stores. I'll make a separate post about them, and how to fix them later, but I just wanted to point out for now that the prior solutions work to remove any FCMP problems from your performance bottlenecks, but if done wrong, CAN introduce LHS penalties.

A LHS penalty can occur when switching between processing units. That is, the simple process of typecasting a Float, to an INT causes a LHS. Why? Well, short story is that the separate int/float/vmx processing units on the 360 don't have direct read/write access to each other, so they have to write the value to main memory before loading it into their registers.

So, here's the fine print in my last post. Those solutions only work (well) if the floating point value hasn't already been loaded into the floating point registers. IE the value still resides in memory.

If the float information is still in memory, the processor will just load it up as the compiler tells it, to the proper address space. As talked about before, we can reinterpret the bits of a float to an int, which effectivly loads the same memory space into the int registers for our work. IF the float had already been in the floating point register (ie, y=mx+b; if(FastFloatCompare(y,0))) then you would techincally remove the FCMP penalty, but have the full wrath of the LHS problems, which could be 2x as long.

I'll mention something about LHS, and my thoughts on a few industry happenings later.. Right now : BEER.

~Main

Low Level Performance : FCMP

2008-04-30T08:26:00.014-05:00

The 5th rule of performance optimization is "Know thy compiler." Specifically, know what your C++ code is generating at the machine level, and understand that there may be things going on further down that could cause performance concerns that do not seem apparent in your higher level language. This is a difficult concept for any novice programmer, as it usually means you have to give a 2nd look at your code for performance that occurs at the syntax level, which is the most difficult for programmers to address. (We tend to like program flow and how we decide things...)

So, I'd like to take a second and talk about one optomization for PowerPC platforms that causes a world of problems : FCMP

A floating-point compare instruction (fcmp) can introduce an execution delay of 30 CPU cycles, if it is immediately followed by a conditional branch instruction.

The execution penalty occurs because the fcmp takes more than one cycle to execute through the CPU pipeline. The CPU detects this and flushes the most recent instructions from the pipelines, and then reissues them while the conditional branch waits for the result. It may have to do this several times before the fcmp result is available. Once the pipeline is empty, execution slows as the pipeline is reloaded through the execution of subsequent instructions.

When FCMP needs to return a float : use FSEL instead
In many cases fcmp can be avoided by using fsel instead. For instance, the floating-point versions of fmin and fmax shown in the following code, are branchless, avoid pipeline flushes, and also give the compiler more scheduling flexibility:

#define fpmax(a,b) __fsel((a)-(b), a,b)
#define fpmin(a,b) __fsel((a)-(b), b,a)

So for a real world example, here's some code that will add a minimum distance to a bounding box when it can be potentially small:

Before :

if((maxCorner.x - minCorner.x) < cMinDelta) 
   x = minCorner.x+cMinDelta;
if((maxCorner.y - minCorner.y) < cMinDelta) 
   y = minCorner.y+cMinDelta;
if((maxCorner.z - minCorner.z) < cMinDelta) 
   z = minCorner.z+cMinDelta;

After :

const float maxY = minCorner.y+cMinDelta;
const float maxZ = minCorner.z+cMinDelta;

const float xTest = cMinDelta - _fabs(maxCorner.x - minCorner.x);
const float yTest = cMinDelta - _fabs(maxCorner.y - minCorner.y);
const float zTest = cMinDelta - _fabs(maxCorner.z - minCorner.z);

maxCorner.x = __fsel(xTest,maxX,maxCorner.x);
maxCorner.y = __fsel(yTest,maxY,maxCorner.y);
maxCorner.z = __fsel(zTest,maxZ,maxCorner.z);

In the above situation, it was much more efficient to compute the result of the float comparison, and instead use the fsel to decide between the original max value, and the adjusted max value.

The basic concept here is to turn the fcmp into a mathematical operation and then use fsel to decide between two paths.

When FCMP needs to return a bool : use bitmasking
The main problem with fsel is that it returns a floating point value. So it doesn't help you when you're attempting comparisons that return boolean results (assume a & b are floats):

Before:

if(a > 0) continue;

After:

const int pT0 = reinterpret_cast < const int* > (&a)[0];
if(pT0 & 0x80000000)continue; // check the sign bit

Before:

if(a == b) continue;

After:

const float test0 = a - b;
const int pT0 = reinterpret_cast < const int* > (&test0)[0];
if(pT0 == 0)continue; //will be null if a==b

Before:

if(a > b) continue;

After:

const float test0 = b - a;
const int pT0 = reinterpret_cast < const int* > (&test0)[0];
if(pT0 & 0x80000000)continue; //sign bit will be negative if a > b

The reinterpret_cast function allows us to view the binary representation of the float value w/o having to do a conversion to int. This helps us eliminate any potential load-hit-store penalties that could occur in the process.

~Main

Can you pull that out? Thanks...

2008-04-20T11:23:00.003-05:00

Abstracting code out to proper, generic, reusable containers is not something that the novice programmer excels at. Most often, code produced is highly specific, very static, and often, not to easy to modify and maintain over time. Early on, I devised a way to fix most of these issues, as I was writing the code. As time went on, I learned to identify the things that could be extracted out into generic containers early on, and avoided having to do multiple passes over my code to generate them.

"Where is this useful?" I've often found that data managers can, on the whole, be turned into generic functions. For example, a streaming terrain system could be abstracted to several generic containers : Generic Cache, LRU Cache, Streaming Class, Streamed Cache, Streamed Cache populator etc etc. These all could be rolled into one manager for the process, but then if you'd like to duplicate everything for streaming meshes, well, you'd almost have to re-write the entire damn thing!

In general, here's the process I hold to :

Write the code as it functions and works in your head. Make sure you're including all the bells and whistles you need. As a general rule here, you want to make the interfaces as slim and generic as possible. Not just because you're planning on genericising it, but because that's just good programming. Note, this also includes allowing massive initialization parameters to be bunched up into classes so that if your function is overridden, the parameters can also be overriden to be expanded by other implementing classes.
Do a quick check to see if any of the operating functionality of your class can be either replaced, or better represented with common generic containers. I'm not saying that your custom, slim, name-value hash paring isn't good, but if it can be replaced by an STL container, or another one that is used elsewhere in the code, you can bet it may be more reliable, and have more general functions. Yea, and as stupid as this sounds, you'd be amazed how many times you'll re-write basic functionality for a system that already exists in a generic form elsewhere. Don't laugh, you're guilty too!
Take a look at your data and how your using it. Could there be any part of your data that could be considered abstracted? Can how you're using it be abstracted? In some cases, can your data be replaced by generic dynamic containers? (Ie can a statically allocated array be replaced by a statically templated array?)
Create new containers that are 'above' your current class. Always approach your current class as the result of inheritance of several container classes; IE it's the leaf of the tree. Start with baby steps in this process. If you get hung up in an area that can't be genericied, then consider it as part of your leaf class, and not part of your generic container. Standard warnings apply about ensuring that your generic classes are memory safe, potentially thread safe, and well documented about it's differences and operations against other containers.
Repeat these steps until you can get at least one generic container out of your data manager. If you can get more, even better.

Yea, it's a bit slower than you'd like, but atleast you're getting some good, reusable stuff out of it. And really, when I do code reviews, this is one of the things I look at, just how generic is your code, son?

~Main

Wow.. That's fun...

2008-03-21T18:00:00.004-05:00

I'm a tech head. I'm the guy in the basement of the code base trying to pump out 6 extra frames before a beta. And as such, When I look at a game, I look at the technology of it more than the game play. It could have the greatest turn based combat ever... I really don't care... Unless they have a technical process that I don't understand, I really don't care about it.

But, sometimes, I have to stop and nod to the titles that make this industry go around.

Portal was a phenomenal game. Combining great brain puzzles, a good graphics engine (built on a successful franchise company and engine) and a half sadistic, dark and twisted plot, how could it not be a win? I loved portal. I laughed all the way through it. I did go back and play through it 2 times just to make sure I caught everything, and still had fun the 2nd time through! That makes it worth it.

I just finished Super Paper Mario for the Wii. I have to say that I haven't seen a game with as many new ideas, and fun ways to entertain the player. The 2D to 3D puzzles were a great addition. The fact that the game made fun of nerds, geeks, and cellphones is something You don't see in most mainstream games, and was quite refreshing to me.

Games like these make me stop and think about what it takes to make a fun game. Not a fun product, or a AAA product, but a fun game.

Sometimes it's good to get perspective on what you're really doing in this industry. Would I make casual games? Maybe. It would be nice to ship a game sooner than once than every 4 years. Things like Wii and XBLA open doors for tech heads like myself to innovate in our areas to make design decisions to make better games. I still don't think the money is there, although I think Portal can be considered a casual game, (in the sense that you can sit down, play for 5 minutes, get up, and walk away) which I hope opens up more doors to bring the money in. I think that will help convince companies that their side projects don't have to be AAA titles on the time. Have a team doing smaller games, pump them out sooner, have fun with it. Because I tell you, everyone focused on crunching to get a whale out the door doesn't help morale after a while.

Sometimes it's good to do something that reminds us to have fun at work. I mean shit, we do make games right?

Roach Reccomends :

2008-03-18T09:54:00.004-05:00

Intel Threading Building Blocks - BUY
Even though it's geared towards education of a particular product, you can't beat the information that this book hands out. While other books skimp on implementation details, ITBB has it in large amounts. Skip the first few chapters of the book if your familiar with concepts like parallel_for etc. Chapter 9 really starts the meat and potatoes of this book, describing how their scheduler system works. Which, try to find a decent description of a low-level task sceduler, and you'll easily see why the info they present here is great. I suggest you pick this book up as soon as you can, download the code, and embrace the multicore boom.

Java Threads - BUY
First, I have no idea what's pictured on the cover.. Whatever it is, it looks like it wants to attack my genitalia, which most of the time, is not something I call a 'good time'. Second, if you're looking for a good, entry level discussion of what threads are, and want to avoid too much worry about windows or hardware specifics, this book is for you. On top of that, it gives some good references to lower level issues and discusses standard threading pitfalls. It's not as good as ITBB, but it covers the issues for people whom aren't threading gurus.

Threading In C# - BUY (download for free..)
This is a free down loadable Ebook. Although the details don't get much more than surface level explanation of c# threading primitives, it's written for a programmer's mind. If you read code better than English, this is a great reference to have.

Modern Multi threading - AVOID LIKE THE PLAGUE
I've read my fair share of threading books, and this one is all talk, no balls. It's geared to be more of a textbook, which spends most of the time talking about philosophies behind how threading ideas work, but don't give you anything solid to walk away from. The writing isn't clear, understandable, or easy to follow. In reality, it succeeds in being a textbook item, appearing to be more for a PHD course than any field manual. I'd steer clear of this money loss if you're new to threading.

Got your own pros / cons? I'd like to hear them!

~Main