The Workbench

NaCl & best practices for fileIO

2012-01-30T11:06:00.000-06:00

FileIO continues to be a pain point for most Native Client developers. I've talked about this before, but I think it's time for a refreshing post; Note that this is a huge brain dump, so sit back and get ready to read.

For hosted applications
Native Client is a web technology that runs INSIDE of webpage. More specifically, Native Client data is HOSTED on a server, and served to the client when they browse to the website. NaCl modules are defined in a web-page using the EMBED tag that points to the .NEXE files for your architecture. As such, the web browser treats your .nexe files as though they were any other web content (images, videos etc) and saves a copy of your Nexe to the cache when processing the elements of the webpage.

Note that the EMBED tag, and the corresponding Manifest file ONLY lists the NEXE data, any binary data that you may have uploaded into the same directory as your NEXE on the server is not brought down to the client when the page loads.

As such, in order to access your files, you must first retrieve them from the server and pull them down manually. This can be done inside of NaCl by issuing an geturl (XHttpRequest) to the specific URI of the content; the asynchronous call will return the result to you as a binary stream of the content once it has been fetched properly. Once you have the data, you can operate on it as you normally would, no problems. On your behalf, Chrome will cache any geturl request results, so that future requests can be re-used. The downside is that the cache can be evicted any time, without your app's consent.

Pulling down the content manually can be a cumbersome, and bandwidth hogging process if it has to occur every time the user loads your game. To help alleviate this, NaCl provides the Filesystem API, allowing developers to read and write files and folders to a sandboxed area of the user's native filesystem. The files are obfuscated and not easily navigated to by typical users. The API offers a storage location that allows random read & write access to binary data your application stores. The data is persistent between launches of Chrome, and most importantly, the data will not be evicted unless your application deletes it, or the user manually deletes it. When using PERSISTENTT storage, there is no storage cap for the amount of data you can store.
Once assets are fetched from your web server, the Filesystem API can be used to aggressively cache that data locally to disk. With future requests for the same file, first check the local filesystem before issuing the request for the file from the server.

The intended flow of this, is that when you would like to load a file, first check the FileSystem APIs in NaCl to see if the file exists locally. If it does, load it, and be happy that you've accomplished something. If the file doesn't exist locally, then you issue a geturl request to your content server to grab the file; when the results are ready, immediately open up a FileSystem API call to write that file to disk.

For packaged applications
One of the downsides of hosted applications, is that the developer has to pay for hosting cost, and for highly popular content, this can be a large financial burden.
At the time of this writing, Native Client applications can only be distributed from the Chrome Web Store. One of the more alluring features of using CWS is that you can create a packaged application that CWS will host for you and distribute to users free of charge. You can read more about how to properly distribute your NaCl application from the CWS using this documentation from gonacl.

When a user clicks the 'install' button from CWS your Nexe and binary content that has been packaged into a .CRX file will be downloaded to the users' machine in one large blob, and unpacked there on your behalf. These files are downloaded to a directory that’s seperate from the cache and sand boxed filestore; It’s a SEPARATE directory that contains only CWS downloaded and installed apps.

As such, this means that your NaCl app will still have to use the geturl call to fetch assets. The trick here, however, is that you need to use a relative path to geturl to properly fetch the files.

Since these files are already local to the users' machine, you will NOT need to cache them into the obfuscated filestore unless you need some sort of advanced read/write/seek access to the file that geturl does not offer.

There's a whole separate discussion to be had about how to modify your existing content API to match the Pepper API. So I'll leave that for another time ;)

Implementing your own two-step authentication

2012-01-24T13:00:00.000-06:00

I'm a huge fan of two-step authentication for my Google accounts. It is cumbersome at times (like when I'm trying to pull up a receipt e-mail while standing in line for something) but the security blanket it provides is well worth it.

Many times I had thought to myself "I wish I could use this for other websites too."

Imagine my joy when I discovered that implementing two-step authentication on a website isn't that difficult to do; in-fact, it's open source.

Using 2 step authentication is very straight forward. The user enters their username / password like normal, and when that authentication is validated, they are presented with a text field, and asked to enter a number.
From there, the user loads Google Authenticator on their smartphone, and receives a custom random number to input into the provided text field.

Once that number is confirmed correct, the user can log in as normal.

I was going to write my own tutorial on how to get started using all this, but realized that there was a great running example that implements this TOTP process in javascript. So, I'll direct you there instead ;)

Important bits from the above example, to help you along:
You can create custom QR codes pretty easily; The following QR image was created with this:
https://chart.googleapis.com/chart?chs=150x150&cht=qr&chl=hellomynameismainroach

And google provides a great doucment on how to embed the TOTP keys in the QR code here.

So go forth! Add this ability to your service! There's no reason to hold back!

NaCl And Pepper Thread communication.

2012-01-18T10:01:00.000-06:00

Chrome provides a plugin API called Pepper (PPAPI) that NaCl uses to communicate with the underlying platform. As documented before, all pepper calls must come from the main thread (referred to after this as the ‘pepper’ thread). This includes FileIO, Audio, Rendering, and Input. It's also worth pointing out that these calls are all non-blocking which means that you call them, and some time in the future, the results are received. More specifically, Pepper APIs and message pumps run on the Pepper thread, along with your webpage script, and V8 / Javascript processing. Which means that blocking the main thread will result in your page processing hanging, causing your tab to stall.

Audio and Rendering are fire-and-forget style systems, and as such don’t require much modification to your game/app; You can call these on the main thread, and continue on withing having to worry about blocking. Input is poll-based, and can be quiried at any time. The real problem is FileIO, where most developers have expectations that the fileIO is blocking.

All of the FileSystemAPIs are non-blocking. As you make the call, your pepper thread will not halt and wait for the function to finish. Your results will be available the next frame cycle. POSIX style blocking functions are on the road-map, but their ETA is yet to occur.

One of the more common solutions to this, is to Spawn a new thread to act as your main thread. This thread will own your update/render loop. You can overload fopen / fread to kick off commands to the pepper thread, and spin-loop to wait for their result.
One of the key results in this is that you need some sort of nifty code that allows you to kick off calls to the main thread from your workers, and block until the results are finished.

Mad Props to NaCl PM Christian Stefansen who threw this snippet together.

Christian wrote a generic "do stuff on the main thread and block" class:

class GenericJob : public MainThreadJob {
void (*function_)();
public:
~GenericJob() {}
GenericJob(void (*function)()) : function_(function) {}
void Run(MainThreadRunner::JobEntry* e) {
(*function_)();
MainThreadRunner::ResultCompletion(e, 0);
}
};

To run "func" on the main thread and block, you'd do something like

GenericJob* job = new GenericJob(func);
runner_->RunJob(job);

where runner_ is a pointer to a pre-initialized MainThreadRunner object.

With this, you should be able to overload fread/fwrite when called from worker threads to kick off read calls to the pepper thread to be serviced.

NaCl & CORS pt. 2

2011-12-12T12:42:00.000-06:00

Since my last post, I've been getting a slew of "your CORS solution doesn't work for me" e-mails. After some digging, most of these were not related to Native Client, and the fixes did work.

So, before you flame-on, follow these steps to find the problem :

Can you access the request when running a javascript function in a page hosted on the domain? (ie www.google.com/corstest.html)

If YES, Can you access the request running a javascript function on a page NOT on the domain? (ie www.colt.com/corstest.html)

YES? then please test these steps listed to configure NACL for CORS requests.
if NO, Have you configured your server to accept CORS requests?

If NO, please check your syntax and web service accordingly.

NaCl & fetching content across domains

2011-12-02T09:44:00.001-06:00

I've been working with a handful of developers lately, that have all been hitting a brick wall with trying to fetch resources from their web-server using GetURL, and having the requests fail.
The problem is that the internet generally doesn't allow you to fetch data across domains for Get/Set requests. Which is great for security, but harsh for NaCl developers who need to fetch binary assets from a cloud service, like Google App Engine.

Thankfully Bill Budge (yes, that Bill Budge), who works on Native Client here @ Google, was on hand to point out how to fix this problem, using CORS.

HTML5Rocks has a great article that discusses this issue, and how to fix it in javascript. This doesn't help you when doing the calls from C++ though, so let's talk about how to attack that.

The setup
The Native Client SDK contains a great example on how to to GET/POST requets to load a page. I've mentioned before that this is a required process for fetching files off of a server.

You can compile that app from the SDK, and see how it's used to fetch file data. If you just load the webpage, press the "Get URL" button, and see that it fetches the contents of the desired file. Note, that the HTTPD.py file that's distributed with the SDK creates a webserver to host the NaCl content from. As such, the results of the GetUrlHandler function is actually communicating with a 'webserver' (but it's local).

Once you try to access a file outside that webserver though, you'll get a denial. For instance, in geturl/geturl.html, change line 60 to read:

geturlModule.postMessage('getUrl:http://www.sameas.org');

When you load the page, you can press the "Get URL" button, and receive this response:

FULLY QUALIFIED URL: http://www.sameas.org
RESULT: pp::URLLoader::Open() failed

This is beacuse you are attempting to fetch data from outside of your apps' origin, and thus are getting denied.

How to fix it
In geturl/geturl_handler.cc, add the following code @ line 34:

url_request_.SetProperty(PP_URLREQUESTPROPERTY_ALLOWCROSSORIGINREQUESTS, pp::Var(true));

Compile the code, and run the web-page again. When you load the page, and click "Get URL" button you'll receive the stream of HTML data from the sameas.org homepage.

With this flag, you'll be able to fetch your binary assets across domains properly!

One final note
For CORS to work on your server, you'll need to make a modification to the server accesses to allow CORS requests. This differs by server type, so please refer to your server documentation on how to properly enable this.

~Main

NaCl & Detecting user setup problems

2011-11-08T08:22:00.001-06:00

I would apologize about the lack of updates, but it's due to a ton of activity in Native Client land, which I'm sure is just as important as my blog ramblings ;)

With the recient press about Native Client, I've started getting flooded with e-mails about developing on NaCl. One of the interesting set that I saw was about common issues with troubleshooting the first line of NaCl restrictions; This includes:

Does the user have the proper version of chrome?
Has the user installed the NaCl app from the Chrome Web Store?
Does the user have the required hardware to run the NaCl module?

Oddly enough, most of the solutions to these problems have nothing to do with NaCl dev itself, and are more related to Web development. In any case, let me try to address them here.

Firstly, I'm assuming you've read our gonacl.com page on how to distribute to the Chrome Web Store (CWS), and are aware that there's a difference between Hosted and Packaged applications.

Does the user have the proper version of chrome?
This one is pretty important. NaCl shipped live in Chrome 14, and shipped 3D support in chrome 15. So if you have a user who hasn't upgraded, this could be an issue. The simplest way to do this is a javascript check for the browser vendor and version. The NaCl SDK has a great example that wraps up how to do a great load of these tests called load_progress.

To note, Chrome releases every 6 weeks or so, so it's common to get new versions frequently and require the user to update. Detecting the proper version shouldn't be a point of stress however, just make sure you target that the user HAS chrome and has at-least the earliest version with your feature support.

Has the user installed the NaCl app from the Chrome Web Store?
Let's be clear about why this is an issue : If you don't have the app installed in CWS, then you won't be able to run the NaCl module.

This is a common problem! Let's say that personA installs your Hosted app from the CWS, so that when they launch it, they get re-directed to your page where your module is running. They bookmark THAT page, and copy the URL to send to a friend. FriendB clicks the link, and the NaCl module doesn't load, generating lots of bug reports for you.

The proper fix here is using a small snippet of javascript to tell if the user has installed the application from the CWS. This page has the details. ("How do i detect if my app is running as an installed app...").

Does the user have the required hardware to run the NaCl module?
This is a frequent problem for our NaCl modules with 3D support, specifically that the user installs the app, and doesn't have the required hardware to run the graphics. The exact problem is that Chrome has a list of Blacklisted Drivers which are known to cause stability / security issues.

The detection for this is that you won't get a valid glContext when you attempt to create one for the first time. This needs to be detected inside of NaCl and reported back to the javascript layer to alert the user of the problem.

For the user, the general fix is to simply upgrade their graphics drivers. To be specific, Chrome blacklists the driver not the gpu hardware.

NOTE the REAL fix here is that we should be able to detect these hardware issues in the CWS and display the issue to the user. FWIW our CWS team is working hard on this feature, until then, please make sure you have proper fallbacks in your application.

~Main

NaCl And compiler flag groups

2011-10-24T09:21:00.000-05:00

The Native Client SDK provides a modified version of the GCC compiler that produces safe, portable executable code.

And for some developers, GCC is dark magic voodoo. (Proved by my previous post getting a bit of 'wtf? where's my IDE plugin' responses).

GCC is a command line compiler that can generate your applications from C/C++ code. The SDK attempts to obfuscate you from the dirty bits of command line generation by using SCONS, but sadly, this still requires a bit of hand tweaking to get right.

Getting proper performance is key; and if you've been used to an IDE handling most of the command line options for you, then you've got no idea what flags actually need to be set.

Here's an extensive list of compiler flags, some of the more important ones are listed below, depending on your build configuration.

DEBUG: -g -O0
PROFILE: [-g] -O{2|3} -msse -mfpmath=sse -ffast-math -fomit-frame-pointer
DEPLOY: -s -O{2|3} -msse -mfpmath=sse -ffast-math -fomit-frame-pointer

Note The -Os flag (to optimize for size without loss of speed) has not been thoroughly tested. I suggest you strip the symbols from your nexe using the nacl-strip app provided in the sdk.

Also the main difference between -O2 and -O3 is whether optimizations that involve a space-speed tradeoff are performed. It could be the case that these are not desirable due to download size, as such, you'll need to make your own performance measurements to detrmine if this is right for you.

~Main

NaCl And browsing detection

2011-10-24T09:06:00.001-05:00

Loading NaCl modules can get tricky; Currently, you can only access Native Client apps through the Chrome Web Store; so if someone browses to a hosted NaCl app w/o first accessing the CWS, the module will fail, as the proper flags have not been set for access.

Krasin has a nice page which can detect this; Simply browse to it, and it will check your browser version, flags, and even do a sample load of a nacl module to determine if it succeeded. (you can see the important javascript here.)

EDIT: One of my friends pointed out that the best way to do this is to actually browse the list of installed plugins in javascript. In my tests, this proved to give the right answer 100% of the time.

~Main

NaCl : PSA for your current setup.

2011-10-08T17:31:00.002-05:00

This is a Public Service Announcement on how your current build setup should be working when developing on Native Client

REMOVE -fno-builtin from your compile options. - This flag turns on the slow path for math emulation, which will slow down your game considerably.
ADD the following flags to your compiler options:
- -mfpmath=sse
- -ffast-math
- -fomit-frame-pointer
Make sure you're on the latest SDK for chrome 15
- This moves the 3D APIs out of dev APIs
- A number of speed improvements for the rendering RPC buffers
- Fixes for ANGLE speeds.
Make sure you're running builds of Chrome Canary, so that you get our fixes as they get pushed out. NOTE, as of right now, Canary is up to date with Chrome 16.

Also, the memory allocations in Native Client is not as fast as it should be right now.
The NewLib library that Native Client is using for its' C++ runtime is not as performant as it needs to be; the GLIBC that's available in the beta SDK is better, but the hassle of switching over may not be worth the effort (the process is not automated, you still have to do some manual work).
Until this is fixed, please consider the following :

Reduce dynamic memory allocations, per-frame, as much as possible (use free-lists, etc)
Use a static heap algorithm with either dlmalloc, tlsf, or tcMalloc

FPS Counter in Chrome

2011-10-08T17:21:00.000-05:00

Little known fact: you can turn on an FPS counter in chrome.

Type about:flags into your address bar
Turn on the FPS Counter flag.
Turn on the Focus existing tab on open flag.
Turn on the GPU compositing on all pages flag.

Give the browser a restart, just to be sure.
The next time you load up a page with some action, you'll see the FPS graph in the upper corner!

~Main

NaCl : Don't call glDisable(GL_TEXTURE_2D)

2011-09-29T08:27:00.000-05:00

This information is valid as of 9.29.2011, with chrome build 101943

OpenGlES 2.0 does not support fixed function rendering. Sadly, for some engines porting over to NaCl that do support fixed function, they will eventaully call glDisable(GL_TEXTUE_2D). Which works for the older 1.1 FF calls, but in 2.0, this isn't supported.

do not call this function in your shipping product

According to the spec, this generates an error. And in NaCl this error gets logged in our about:gpu tab, and grows endlessly.

So, if you're calling this about 1-3 times a frame, you can expect a memory-filling logging overhead of about 3mb /sec.

We're working to fix this behavior on our side, but until then, please don't call this function!

~Main

NaCl : Fetching files

2011-09-26T11:11:00.001-05:00

In Native Client FileIO doesn’t work the same way as it would in a standard desktop running application. For security reasons, NaCl doesn’t let you just run off into the woods and randomly read / write to things. Instead it provides an obfuscated, restricted area on disk that you can read / write safely to.

because of this, there's some nuances we need to talk about wrt How to get to your files.

Firstly, your EXE file is being hosted on a WEB PAGE; Which means that the EXE isn’t running directly on a desktop, and doesn’t have access to the file system. So, in order to load files in your session, you need to you can use geturl_handler to directly access files that appear to be 'on the server' where the .nexe file is hosted. The result will fetch the asset and return to you a binary stream that you can do with as you see fit.
Since GetURL is a web-call, Chrome will actively cache your asset for you; which means suibsiquent calls should not have to go out to the internet, but rather, pull it from the local cache.
The upside of this, is that Chrome is doing this on your behalf. The downside, is that you’re victim to the whims of the cache, and have no guarantee of residency.

A solution to that, is to use the Pepper FileAPIs. They will give you access to the local disk to write the data to and manage caching yourself. For writing you’ll get access to a local sandbox data store that you can read/write too freely. More specificly this works well for games that can download their binary assets into the local file manager store, and stream the data from disk into the product so that you can control caching yourself.

The latest SDK comes with an example that shows off how to use the File System APIs, and you can see that here.

~Main

NaCl apps in the wild!

2011-09-22T10:37:00.000-05:00

Turns out NaCl apps have been starting to pop up in the wild!

First is SodaSynth a sound synth tool built in Native Client.

Next is OGRE which currently only works with Chrome 15 out of the Dev channel.

More includes 60 second shooter. (see the HOW TO in order to get the flags right)

And NaClBox just got Descent working!

And don't forget the classics : QUAKE and DOOM.

~Main

NaCl : The super quick start

2011-09-13T09:25:00.001-05:00

Looking to get up and running with Native Client quickly?

Firstly, let me point you to the SDK site; I suggest running through the 'getting started' tutorial first, just to make sure everything is set up.
Secondly, take a look at How to get experimental 3D up and running. (If you're into that sort of thing.)
Thirdly, hop over to some details on how to get various forms of debugging working.

Once you've got those set up, there's some known pain-points that we're working on:

#1 - There's currently no native support for TCP/UDP. You can get around using TCP by sending calls through Pepper to Javascript, and using a websocket from there. (This is primarily a security issue. Imagine if a webpage could sniff your ports and watch your network traffic!)

#2 - File IO - While Pepper has a full Filesystem API; most developers find it easier to request their binary bundles using geturl_handler.cc from the SDK (check out the life example) Once they grab the bundle, they can either cache it locally using FileIO, or just skip through it in memory

#3 - Sound - If the Pepper sound API isn't good enough for you; FMOD has support for native client.

#4 - Build Systems - The SDK comes with SCONS. Most people find SCONS to be confusing the first few times (especially if you develop on windows primary); SCONS is a 3rd party library with lots of documentation to find, please seek that out first.

#5 - Help - If the SDK and Chromium pages don't answer your questions, there's two resources available to you:
1. For New Developers, or common issues, head over to Stack overflow.

2. For NaCl bug reports, SDK Problems, stop by the Native Client Discussion group.

~Main

NaCl & 3D: Alpha Blending Bug FEATURE!

2011-09-12T08:48:00.000-05:00

In NaCl, there are two primary ways to do alpha blending.
1) Drawing a transparent object with alpha blending ENABLED.
2) Drawing a transparent object with alpha blending DISABLED.

The first way acts as you would expect, blending with the frame buffer as any other API;
The 2nd one though.. that's where the magic happens.
If you render an object with modified alpha, with alpha blending disabled, then the system assumes that you are taking into account premultiplied alpha, and rather than blending with the frame buffer, blends with the last modified alpha. Namely being the webpage, not the frame buffer.

To Be Clear: If you disable blending, and render an object with a non 1.0 alpha value in the pixel shader, then that object will blend with the background webpage, not the background frame buffer

The unfortuinate part of this, is that it's not the exact result you expect when coming from other rendering APIs. There's a couple ways to fix this.

#1 : in C++ Force-Clear the backbuffer alpha at the end of the frame
Add the following at the end of your render loop, before the glPresent():

glColorMask(false,false,false,true);
glClearColor(0,0,0,1);
glClear(GL_COLOR_BUFFER_BIT);
glColorMask(true,true,true,true);

#2 : in HTML, add a DIV under your EMBED tag.
This is less fun, but isolates the issue on the HTML side of things, rather than the C++. One thing to note here is that you need to be VERY sensitive to page re-size events to make sure that the NaCl, EMBED, and DIVs all have the same pixel size.

#3 : When the API gives you lemons, find a cool background image.
Alternatively, there's some interesting things you can do with blending your game to your page background color. For instance, you could create a custom shape for your rendering window. Or even better, incorporate this into your product, and do some really nifty Pepper / NaCl magic to modify your render window shape over time.

Or, play a YouTube video of a Boxing Cat behind your app. It'll drive the internet wild.

~Main

NaCl & 3D: Rendering from a sandbox

2011-09-07T17:37:00.002-05:00

We've had NaCl 3D support in Beta channgel for a bit now. You can go here if you're interested in playing with it.

To understand that, let's take a look at how 3D is implimented in NaCl & Chrome.

Firstly Chrome is a mutli-process browser; each tab is a seperate process, that has its' own memory, cycles, and containment. Because processes don't directly share memory spaces, communication between tabs/processes is done through a method called RPC, or Remote Procedure Calls. RPC commucation acts like a packatized networking stream, where small blocks of data are batched up in a buffer, and flushed across the RPC pipe to another process at a later time.

BTW, these RPC flushes come in two flavors:
A flush - simply do an asyncrhounus flush of the buffer
A sync flush - flush the data, and wait until the buffer is consumed.

For 3D in NaCl, it's the 2nd kind that you need to be worried about.

For security purposes, all your 3D calls occur in a seperate process. This is not the same process as your current tab, but yet another process that focuses solely on communicating with the graphics API. As such, all your OpenGLES calls occuring inside of your NaCl process do nothing more than push command data into an RPC buffer.

The upside of this, is that your NaCl process doesn't lose any processing due to graphics API calls. This has been a bane of PC graphics computing for some time now, and its' nice to know that you don't have to split processing between rendering and sim work on your main thread.

The downside though, is that it's unclear when an RPC flush call can occur, and weather it is going to be a simple flush or a sync flush. Since each GL call pushes a new command onto the buffer, your flush can occur inside your gl call on your NaCl process. Which means if you're doing processing, it could look like a random GL call spikes up to 98ms for no reason. This type of debugging data would lead you to believe that there's something wrong with the Native Client GL implimentation, but alas, it's all about the RPC flushing.

So, how do you work around this to keep your 3D performance high in your application?

Firstly, visit this page and walk through some testing to determine if you're GPU or CPU bound. Note, if you're GPU bound, there's nothing NaCl specific about your problem; NaCl uses the same driver and GPU as your desktop rendering apps. If you're CPU bound, and your seeing spikes in your openGL ES calls then try this:

First, turn on these environment variables to profile when flushes occur:
Note, the following data is valid as of 9.07.2011
For more output:

set PPAPI_BROWSER_DEBUG=1
set NACL_PLUGIN_DEBUG=1
set NACL_PPAPI_PROXY_DEBUG=1
set NACL_SRPC_DEBUG=1 # pick higher number for increased verbosity
set NACLVERBOSITY=2

Redirect the stdout/stderr (needs --no-sandbox as a command line flag):

set NACL_EXE_STDOUT=c:\work\nacl.log
set NACL_EXE_STDERR=c:\work\nacl.log

With these turned on, you should be able to see when your flushes occur in nacl.log.

Secondly, try to force flushes before heavy processing that doesn't have an RPC function call. For instance, right before you kick off your multithreaded particle work, call a flush so that the RPC pipe will be clear by the time you're going to start doing GL calls again.
You can do this directly with two GL function calls :

glFlush - which will force a flush
glFinish - which will force a flush with a sync.

I find doing flushes around every 500 or so draws nets me a huge win in NaCl. So make sure your profile your workload and use case, and find an appropriate heuristic in which to issue flush calls.

~Main

Back in Black; But highly salted.

2011-09-01T11:49:00.000-05:00

I'm back! This site had to go down for a while due to unforeseen circumstances. But now that I've gotten all the Tribbles out of the warp nacels, we should be good to go.

I'm now over at Google as a Developer Advocate focusing on gaming for Native Client. The short of which, is my focus to bring genre-busting gaming experiences to Native Client and the Chrome Web Store .

For those who haven't heard, Native Client (or NaCl) is an open source technology that allows you to run native code in web browsers. More specifically, it allows you to run C++ code in web browsers.

We're seeing a massive segmentation in the games industry right now. Every platform seeks to create a silo of content, community and developers, and as such, usually has a barrier to entry for developers to move to that platform. This is exceptionally difficult for C++ game developers who ship on consoles/PC to adopt to. Until now, if you wanted to get your XBLA game into the web, you had to re-write everything from C# to HTML5.

And that's a lot of risk for game developers, who are usually doing everything they can to stay in the black. So tossing all their code out the window to move to a new platform isn't an option to them. But what if they could use that same code, and move to the web, so you get digital distribution, AND access to all 6 billion humans on the planet?

With Native Client, you can do that.

Basically, you send your C/C++ code through a modified GCC compiler, and in return, get a 'web safe' application that can be ran inside of a web browser, on any platform.

But we'll get into that more later.

In fact, we're just getting started.

~Main

If you're interested in Native Client, hop on over to the SDK and get started.

Abstracting

2008-04-15T13:36:00.001-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

BTW, I'm published

2008-02-27T13:34:00.001-06:00

Game Programming Gems 7 just hit the shelves, and with an unbound amount of luck, my article, "Efficient cache replacement using the Age and Cost metrics" is sitting front and center in the book.

As already reported on the web, I've got another article coming up in AI Programming Wisdom 4, co-authored with a good friend James Stewert.

I've got about 4 more articles sitting around, waiting for someone to publish them (well.. waiting for me to have time to finish them first...) so I'm glad I'm not dry on ideas ;)

To be honest, I like publishing articles and sharing my knowledge. I'm usually bound by the 'Don't talk about anything that's too super cool' due to my job, but in general, there's enough I do in a given day to shake up 1-2 publications every few months. That's one reason I started (and still am) teaching at Guildhall; I'm a self taught games programmer, my undergrad was useless to me for programming purposes (although I did learn the valuable art of the keg stand..) and I recall so many times wishing for information that wasn't available. In some respects publishing and teaching is my way of giving back to others, what I didn't have when I was a struggling programmer.

See, now I can add "Humanitarian" to my resume...

~Main

What does it take?

2008-02-03T13:33:00.002-06:00

The first exposure many of you had to my current project was when this news came out. (Wow.. 2006.. has it been that long?) As we've mentioned before, the project was in development for some time before that date for prototyping. In truth, development on this project has been brewing since as early as 2004 with prototype teams and proof of concept that we could pull off a great RTS on the console. But as many of you know, what's required in this industry are results; Shipping your game. I think our relative release date has been mentioned, although for sake of CYA, I won't mention it here, but rather suggest that you will be able to purchase this product sometime this year. So on the verge of realizing a 4 year vision, I've been looking really hard lately about what it takes to actually get your product out the door.

I'll be blunt : Video game development is psychotic. And anyone who's involved with it needs to be a tad bit screwed up in the brain to make it through at a professional level.

I've mentioned before that this industry may not be stocked with the most technical people, yet at the core, we're developing a product in a super technical environment. This causes large swings in impact of decisions over the lifetime of the project. Technical and tool chain decisions made at the very beginning of the project often butt heads with fast-and-hard crunch and final push development at the end of the project. So in reality, our job as programmers is almost to act as oracles into the future of the life cycle of the project. In truth, we can't trust our users, ( which is a concept that I naively ignored when starting this project and has come full circle to bite me in the lower parts of my ass.) so we really can't rely on what they are telling us they 'want' out of the future of their development environment.

I can personally vouch for the fact that too much freedom with content developers is asking for death and confusion in your product. Which, if you listen to them, is the only thing that they dream about at night or when they are alone in the shower. Actions show, however, that more freedom requires more technical understanding of the authoring process, which requires more frontal-lobe-power-per-minute in order to complete their jobs, and that's not always available , or the best idea. I've been impressed before by low-tech solutions to engine systems that have amazing art results and visual, and have come to the conclusion that the reason for visual success in these realms, is not due to feature availability, but LACK of features that force content creators to explore the entire expanse of potential within their constraints.

So when your final 15-month crunch starts before ship, the ability to finish the project relies on the fact that your tool chain is simple enough that low-frontal-lobe-horsepower people can make art, and not screw things up / break the entire pipeline.

That being said, I believe there's some confusion at a great deal of companies about what it takes to get that last 100meters out of the game. Recent GDC talks from Blizzard suggest that they have an 'All hands' approach to a shipping title, in that when the cowbell rings, everyone gets behind the shipping cow, and pushes it over the line, as though it were incapable of doing so on it's own like some 50 ton Banana slug. Within 15 mintues of that news hitting, e-mail threads started like wildfire supporting this idea. "Woah" I replied, "If we can't finish the final 10% this product without the entirety of the rest studio helping us, why wait until the final RTM crunch? Why not bring everyone on board NOW so that we release a MUCH more polished product, rather than something with 'less bugs' ?"

Crickets.

Which goes to prove my next point: It takes heart to ship a game.

To elaborate, it takes the attachment to stay focused and productive when you're not crunching for a beta, or a milestone, or RTM. It takes dedication to keep making progress even when the game isn't sexy (yet), and be committed to it long before the it-just-hit-the-fan crunch.

Game studios that adopt to the 'all hands before ship' approach to things are in my opinion, just patching up problems from the entire dev cycle, and fooling themselves into thinking that adding 200 chefs into the already packed kitchen will really make a massive difference in the short term. More importantly, they are fooling themselves by putting people on the project, during the most crutial time of the project, whom don't have the heart for it. These people are usually working on other projects, their projects, and getting sucked into your project is, at even an unconcous level, pretty annoying.

If you're going to need the help at the end, just bring them on earlier. Let them get attached to the product, let them take vestment in the decisions. Let them give a damn about what's rolling out the door.

Because we're all aware, nothing hurts your heart for your project than A never ending crunch.

Which, unfortunitally, is what most people think is what it REALLY takes to ship a game......

~Main

New year in 'threads'

2008-01-07T13:31:00.001-06:00

I bit the bullet reciently and upgraded my 4 year old single core PC to a snazzy new Intel Q6600 Quad core machine. The price was pretty good, for around $500 I walked out with the processor, Motherboard, and 2gb of ram. What spurred this, was mainly the interest and research I've been doing lately in the real time ray tracing realm.

And let's get one thing straight with that. About a year ago, when I told people that software graphics would be the future, I had my fair share of arguments and skeptics. A year later, a software project is already putting out an open source real time ray tracer, which doesn't do any black magic. Really, it does what you'd expect it to, Use multi core, and SIMD. WOW. Amazing! Nothing fancy with RT hardware, or any cutting edge BVH.. just using what is available to us.

Plus, these other people agree with me. So, it's safe to say I'm not that crazy.
Arauna real time ray tracer
Intel Blogs
Beyond 3D response

~Main

Random Access Compressed Containers

2007-09-01T09:50:00.004-05:00

One situation I've been having to work with a great deal lately is the problem of not having enough memory for data that is highly, repetitively, and randomly accessed in my applications.

The data is accessed too much to warrant an out-of-core solution, I suppose that I could free up memory from other systems to make room, but instead, I've embarked on a series of containers that are just really cool.

Standard regular grids (such as textures) save a bit of memory because they don't store spatial locality data. Rather, it's implied that through neighborhood association, your location can be derived. Even with idiotically large data sets, you can still access a regular grid pretty randomly, and almost quite immediately. You never need extra traversals besides a single offset value into the memory stream.

But, with idiotically large data, you run into the problem that you either don't have enough memory to hold it all. The problem then, is how do you store your large regular grid data set in memory, while still keeping all the properties to allow random access?

That's where these containers come in. Standard compression algorithms, like JPG2k, vector and wavelets operate on iterative compression systems, such that to get the value of any single data element, we must evaluate a much larger portion of our data.

For clairity, let's define a Random Access Compressed Container (RACC) as having the following properties:
a) The in-memory, working data set is a compressed representation of a larger dataset.
b) Any element of data within the set can be randomly accessed with minimal decompression of non-relevant data. ( this gets a little 'fuzzy' as 'minimal' changes depending on your platform and target performance.)

Optionally, you can modify the RACC to be a Working RACC (WRACC) by adding another property:
c) As data is added to the compressed representation, non-relivant data is re-compressed based upon its corrolation to the input data.

What this basicly means, is that a WRACC is a runtime container that data is added to over time. As the data is added, depending on the compression method, other data may need to be re-compressed to take into account the incoming data. For example, if you and a WRACC that implimented an RLE compression scheme, and you added a piece of data to the set that broke one of the RLE runs internally, then that run would be split into two runs, each strattling the newly inserted data.

Now, each one has their place. I love the ease of use of WRACCs, although you can never get as much compression as you can with a standard RACC.

Some examples:

RACCs

Perfect Spatial Hashing
Hugues Hoppe came up with this one. Basically, he removes sparse data in a set by moving the defined data to a separate data structure which still keeps some implicitly defined regular organization. ( you can read the actual paper for a much better explanation)

The pro's of this are that you can compress your sparse data set in to it's MINIMAL needed representation, and still have random access to it that doesn't requrie any traversals or extra decompression. (note, this works much like the jagged container, in that we must define what data value is considered 'empty' and only move non-empty values into the extra data sets)

The cons are that the data must be static. Which kills us for direct editor usage, but it's still nice to take in some of the philosophies.

WRACCs

Jagged Array
Andrew Foster came up with a great solution for the Halo Wars editor (and where this all started). Basically, we were struggling with exceptionally sparse data sets, but needed the ability for the sparse data set to a) be compressed, and b) still emulate a regular grid to the outside world.

The Jagged array container works by creating pointers to the start of each scanline of your 2D data (IE, one per row). When data is placed into the array, we first determine if that row exists. If it doesn't, then we allocate the entire row, and set the pointer appropriately. When we access the container, we usually pass in a 2D coordinate; If the specified row value exists, then we traverse the row to the column coordinate, and return the proper value. If the row has not been allocated however, then we simply return a pre-specified 'empty' value.

The container works exceptionally well. The row index acts as a pseudo hash key into a table of data (which still maintains regular connectivity). While the x coord is the internal value. We can still keep random access with this process, and we save memory by not allocating 'empty' data.

This does however, degenerate, as we add progressivly more data, the container itself degenerates back to a regular grid. Also, this conainer allocates a great deal more memory than needed most of the time; for instance, if we enter every element in a single column, the JA would allocate every row, and immediatly degenerate into a 2d grid

Random Access RLE (or JaggedRLE)
An extension to this process that I developed is an extra step to help reduce the memory footprint was to RLE any row of data that the jagged array points to. This way, if we have any sort of homogeneous data, we get a mild perf win. This also addresses sparse raster data, such that if there is minimal data elements in a single row, then we do not store the entire row in memory.

Per row, I label RLE compressed blocks with their start and value, and to safe time, I flag unique blocks with the same process. The row index still acts as a hash key, but now the X value requires some searching to occur. To find our X value, I have to find what block the X Value resides in. This requires walking each block in the stripe and adding the traversed pixels to our running count for the line until we find a block that spans X. If the block is compressed, we simply return the repeated value. If it's not compressed, then we return the element that exists where X should be pointing (derived by subtracting the start of the block from X, and adding that to the start of the block as a local index..)

Although it's trickier, you can still submit data into the container @ runtime, and allow it to RLE the row as it changes.

One problem with this however, is that it falls to the standard problems of RLE, in that the more random the data, the less efficient it is to store it as such.

One side observation though, is that it may be wiser to store pointers to blocks, instead of stripes. Usually images are not really raster in nature, and rather block based, such that RLEing a block may yield better results than a scanline.

Well, those are just a few ideas. You can see that these are powerful notions. The ability to edit data that is compressed on the fly, as well as randomly access it with minimal performance hit, all while expressing a minimal memory footprint!

That's good shit.

~Main

Game Dev & Crunch

2007-08-30T09:48:00.006-05:00

Everyone crunches. If a managers says they don’t, or that ‘it’s not that bad’ they are lying. And you should kick them in the face for that. (I’m kidding… not really..). Crunch is essential to our industry. But, it’s not just us. Every industry has the overtime, and the late hours. We’re no different, we just have a cooler catch prhase to describe why we can’t have a social life for the next month.

Crunch is a direct result of management. Let me explain.

If your milestone goals are too large for your team, you crunch.
If personnel hasn’t been allocated correctly, and nothing is done, you crunch.
If you have another demo in a month, you crunch.
If you don’t have enough talent to do the job, you crunch.

All of the above reasons are directly controlled, and a result of management. They control the goals for the milestone, personel allocation, demo schedules and focus, and whom is hired, and how.

Note the lack of “if X happens, MANAGEMENT crunches”

To be honest, we are talented individuals (well… most of us…) that can get our jobs done, and ensure things work on time. Most of the time though, this isn’t the case, and the management calls CRUNCH!

Overly long crunches are a sign of a bad company. I would say anything longer than a month is just un-necessary. And in reality, shows that management really doesn’t care much about its’ personnel.

Tips to survive crunch:

Showstoppers take top billing. Not all bugs are created equal. If there’s anything that’s keeping any other member of the team from doing there job, then that should be handled first. Trust me, the worst thing to hear is ‘well, I couldn’t work because I was waiting on you.” Also in this category is any fatal bugs that make the game un-playable.
Polish is essential. If you’re in a demo crunch (not just a standard, “no one will see this but us” crunch) then you’ve got to know that there’s about to be people looking at your game, tearing every piece of it apart. Take the attention needed to address polish points before moving on to anything else. Trust me, no one will notice that your exportation code runs 20 seconds faster, but they will notice that slight, 0.5sec jitter between animations on your infantry..
Work the hours everyone else does. If you’re like me, you work the hours you choose, because they fit your schedule and life style. But, this doesn’t fly during crunch. You work what everyone else works, or you can be in a world of hurt. If you leave for the day, and something breaks, everyone WILL notice you’re gone. Even if it’s not your fault! Make sure management sees you pounding away at your work. Stop for food breaks (hopefully provided by the company) and take a point to talk to the producer & manager about how the crunch is going. It’s sometimes tempting to finish your work for the day and head out; be warned, as soon as you do this, something will break, and it’s your fault.
Expect the freakout. It always happens. Some high-strung individual is over-stressed about the milestone, and decides that you’re the person whom is responsible. Try to remember that people in crunch, are not normal people. They are some form of mutant zombie, fueled by caffeine and compiler errors. Try not to get sucked into a trivial yelling argument, or debating stupid items. Keep your eyes on the milestone. After all, at the end of the day, dealing with these problems only detracts you from getting your job done.
New features aren’t that important – If you have a 12 day crunch, and it will take you 4 days to get a new feature done, it’ll take 5 days before anyone else notices or uses it. On top of this, expect a lot of ‘new’ features to show up during crunch. For some reason, people like to brainstorm with your time when they are under the gun. To this extent, find out what is REALLY needed for the milestone, and try to concentrate on the big features. If it’s worth the risk of introducing new bugs, breaking the pipeline, and generally screwing everything up, then go for it. Otherwise, you might want to take a rain check until after the crunch is over.
If you have time, try to do a pre-crunch. The entire development process takes a beating during crunch. So much so, that it will flesh out bugs you never though possible. And trust me, there’s nothing more stressful than having a show stopper that completely makes the game un-playable, or keeps the editor from working. If you can, try to handle some of these high-priority issues the week before crunch begins. Tackling things like memory issues, general performance, and overall stability ahead of time will run miles during the crunch, as it will improve the performance and output of everyone on the team. Not to mention keep your plate a little lighter.
Let your family know you love them. This is for all you married guys out there.. I try to buy my wife flowers before crunch, and after crunch. To be honest, we are willing to work for an unhuman amount of hours because we love what we do. Most spouses don’t agree with that amount of work though. The pressure of crunch is always magnified when you throw home problems into the pot as well. It’s hard to concentrate on the task at hand when you’re mad at your spouse because they didn’t clean out the dish washer last night..

~Main

Algorithmic Dynamic Range

2007-08-26T09:47:00.000-05:00

Making a game is about compromise, and specalization.

Let me expand:

You often can't use the algorithm you'd like to use, because you have some constraint specified by some external force that you have no controll over. (memory, perf, boss, wife....) This is where compromise comes in. How much of the algorithm can you sacrifice in order to make it work within the constraints, and still achieve its goal? This is not an easy question. Often, you have the answer, and end up haveing to change the answer 3 months down the line due to a change in constraints.
Compromise is a good thing however, as it lets you REALLY determine what your algorithm is doing, and what it needs to survive. This sort of system can be developed to expand later on, to add bells and whistles to do other things, when you have the headroom to do so.

This is where specalization comes in.

When I say 'dynamic range' i'm not talking about your standard HDR talk. I'm talking about a moving range of algorithms that all accomplish the same thing, but handle specific data sets to accomplish it.

For example, lets say you have a program that sorts a list of numbers. The numbers can be given to you in any fashion, and continue to be added later on.
What sort algorithm would you use? I think we all know by now that no ONE sort works for everything. But rather different sorts for different tasks.
So, to begin this process, you may write one sort to rule them all, then start specalizing sorts based upon input (ie RADIX sort works great for floats, but it's not as good as quicksort for huge data sets w/ ints) This is what i mean when i say 'dynamic range'

You'd be suprised how often these special case situations come up in video game development.
Almost always dealing with your data sets, you're constantly fighting the battle of specalization of processing of your data to save memory and increase perf. Why create 3 channels of color when only 1 is used for meshes X,Z,Y,Q? Now, 3 channels are used for ABCD, so you need it there. The rendering of these two differences is important as well, you can create a fast path that renderes the 1 channel texture faster than the 3 channel. So already, you've got a dynamic range system, that, based upon the input will load, sort, operate, and render differently than it's neighbor.

This is a good thing

Why?

Well, because with a large amount of dynamic range, it makes it easy to look at what 'average' is, and makes it even easier to define what 'worse' and 'best' is.
Best case scenario, Every object in the world has 1 channel textures
Worst case, every object has 3 channel textures
Well, we don't have enough memory for everything to have 3 channel, but we can make a compromise that will allow 50% 3 channel, and 50% 1 channel. And shit, while wer'e at it, the artsits are asking for specific 2 channel textures to use on a few special places.
And, if we can find some time in the scedule, we can write a compressor that will make our 3 channel textures take up as much memory as our 1 channel textures, and allow us to have more of them

Now it's a ballgame folks.

This idea should be kept in the forefront of your mind while you're programming a system. One algorithm hardly ever works. Instead, break your algorithm down into discrete components that you can understand, and swap between easily. When you do this, you not only give yourself a greater range to drop your perf metrics in, but you also make it easier to enhance perf in any specific branch of the algorithm. (If there's 4 channels, i can make an optomization that it'll run 20% faster than a 3 channel etc..)

Getting back to it, "Know thine data"
and "understand thine algorithms."

~Main

Look under the hood

2007-08-24T09:45:00.002-05:00

I find sometimes that it's pretty interesting to view the disassembly output from my compiler.

I usually find this interesting especially when i've found that a particular section of code is taking up 500% of my alloted perf.

So what do i usually find?

I did a nice little test today that mirrored a class I had written some time ago to access bits in a stream of __int64s. This class does a great deal of methods. I can set single bits, or spans of bits, as well as any sort of standard list queary that you'd expect (findFirstOfType, findLastOfType, giveTypeRatio, etc etc). My test created the same class, but instead of using__int64s with bitwise operations and logic, i instead, made a bitfield struct, w/ 64 members, all 1 bit long.

struct int64Bitfield
{
bool _00:1; bool _01:1; ......bool _63:1
};

I then modified the class to do the same operations, but access this class like i would any other structure. There's some things that cause difficulty, like trying to do a bitwise operation on a bitfield (it gets tricky!). What i was testing for, was compiler output. I actually wanted to see what the compiler was generating, to see how far off my custom solution was.

I was shocked, and appauled. (and a little turned on...)

What i found, was that simple probing of the bitfield churned out LESS instructions on the whole, vs my powerPC intrinsic heavy-bitwise function using version.

Dramatically less.

What did I do? Well, i tabled it for now. I didn't have time to do a full perf analysis on the running functions, and it's always hard to look into how many cycles that chip-specific intrinsics are actually taking up without a profiler.

What i learned from this though, is an important lesson that i've been hearing from a great deal of PS3 developers : Write your own compiler.

What???!!! How could you even suggest this? Well, there was a couple reasons that the bitfield specific version of the class produced less number of instructions than my intrinsic version.

1) Bitfields have built in explicit knowledge of how they need to work. For instance, accessing the 0th bit in a bitfield of 4, the compiler knows that it only needs to do a andi r3, r1, 128. Now, you'd think that by generating the same sort of code in C++ that you'd get the same results. But, you'd be wrong!

#define cHighBit 128 //0x80 h
bool k = charVal & cHighBit

You'd think that cHighBit would be constantly loaded in, and replaced everywhere by the value 128. BUT in some instances, this isn't the case! Rather, in some instances, the value 128 has to be loaded into a register, then used from there! This requires a lbz r1, d(rA) before being able to do the andi r4, r2, r3. although this is a really small example, imagine what's occcuring during a great number of temporary variables. Lesson : You may be generating more instructions than you think.

2) There's a problem with c++. Mainly that it's abstracted from the code that actually runs the goddamn box. You can code away in c++ land, making all these nifty functions and systems, all the while, blissfully ignoring the fact you're killing the cache, and overloading the memory stack.
You don't really know you're doing it until you see perf drop to it's knees as much as your mom did in college. There's no feedback as to HOW bad your code really is, or even WHAT is making it so bad! Now, go down into assembly land, and wow! Look at how much information you're getting! You can visually see that you're thrashing your registers loading in all those temporaries, or that you're causing cache misses all over the place. Basicly, you can see the pulse of the actual system.

So what i've been hearing going on, is that some developers are either writing all their PS3 code in straight C, or they are writing their own compilers to generate code that's friendly to how the PS3 works. I like the idea of writing your own compiler honestly. Yea, it's a great deal of work, but you can harness so much more from the hardware! Imagine actually being able to define blocks of code that automatically get thrown into a threadpool behind your back, and async. comm back to the main thread w/ the proper information, all in assembly! You, of course, would just have to define start/stop tags for the whole thing, but you get the point.

Basicly, when you're in perf-critical land, abstraction is your fucking arch-nemisis. This is why platforms like .NET are considered a joke to the video game community. Yea, you can write a graphics engine in C#, and it'll look the same, run at 80% of the regular perf, and you can use all theri nifty frameworks, but you loose two of the MOST important concepts in writing fast code: Know what your memory is doing, and know what your assembly is doing.

Abstracting your language up multiple levels does great things for the human understanding of programming. But that's not always how the machine thinks. Writing a custom compiler is a great idea, because you can taylor make your output machine code to match what the hardware would expect to do. Along with tons of safety nets that other PC compilers would completly glaze over about. (For instance, how about an automatic pre-cache update when the compiler recognizes that a long block of memory is about to be linearly accessed? That'd help your perf wouldn't it?)

Am I saying that you should program in fortran? No. And infact, you'd be a fucking idiot if you did. C++ is a great language, that offers you an exceptional amount of power. BUT you have to be willing to explore, and understand, all the innerworkings of what it's doing, in order to truly harness that power to do your bidding. Code highlevel, think lowlevel is a great motto here.

We should all understand WHAT our assembly is doing, and even more important, what the HARDWARE is doing too. Really, if you think about it, programming on a console without knowing what your code is doing to the hardware is pretty stupid. (Like fucking some random chick without a war-helment.) You can really parallel it to blindly shooting at a target, hoping to understand how to hit the bulls eye. "Well, i can't see, but i THINK i was a little to the left of the target that last shot.."

When you're blindly wading through code like that, it's time you look under the hood, and come face to face with how you're raping your console.

~Main

Types of books

2007-08-22T09:44:00.000-05:00

As far as i'm concerned, there's 2 types of programming books:

1) The kind that make me crazy
These books are usually great lexicons of useful algorithms and collections of great know-how. These things are the ones that you constantly go back to for info. Why do they make me crazy? Because once you read through one of these books, your brain starts to scour for how you can actually USE all of the information that you've just absorbed. I'm always saying 'well, someone else is going to use it.. i should too.' Most of the time that's just paranoia, other times, it's legit. All in all, these books contain a great deal of information that i can't hold in my brain at one time, and have to keep going back to.

2) The kind that make me sane
These books are written by the vetrans of the industry. That is, people whom have been around the block a few times wrt programming, and have some generally good insights on how all the information from book type 1 can be, and should be used. These books generally give me the vision of understanding of what the hell i'm really doing on a daily basis. I can see the forest, and the trees.

There's really 2 other types of books that I classify, but aren't as important.
3) The books that interest me, but i don't get around to reading because they are of a subject matter that i'm not in a place to master just yet.
4) Books that bore the shit out of me, and i generally have no desire to look at. These books are also considered 'copiers' That is, how many 'C++ tricks!' books can you really read before they all start to sound the same? One of these books is nice, but 5? oh come on!

~Main

Walking Lists

2007-08-21T09:43:00.001-05:00

Walking a list is a common practice for every programming task. Even the most boring, trivial tasks requrie you traverse some sort of grouping of data in order to find data.

Now, contrary to what your CS1 teacher taught you, this is not as simplistic as creating a FOR loop and throwing in some IF statements. Lets take, for example:

You're creating software for a building with 1 million rooms. Each room has 1 light swtich in it. You need to create software that holds the states of every lightswitch in the building : ON, or OFF.
Lets say that at any time, you ned to traverse the list, and find the first ON swtich. What's the most memory efficent, and performance efficent manner to do this?

cs 101 : for(i=0;i< 1 million;i++) if(lightSwitches[i]==on) return i;
what works : Uhh, it works...
what doesn't : What if there's no ON element? we'll walk 1mm objects. That sucks.

Better idea?
cs 102 : Keep a structure of your data that allows you to traverse it in some sort of faster, more efficient manner.
what works : reduces time to find an object greatly (depending on the algorithm)
what doesnt : usually requires more memory to keep all the information for relationships. Also, takes more time to process the data in recursive systems. (this is usually offset by the speedup of faster traversal)

Better idea?
cs 103 : Keep a 2ndary listing of data that will allow you to immedialy identify the first of a node you're looking for. Think of it as a FIFO structure for your data.
what works : finding the first of a node, REALLY FAST.
what doesnt : more memory again

We can keep going on like this forever. Read any ALGORITHMS book by Knuth, and you'll see what i mean.

There are some things though, that programmers need to be aware of before just writing a simplistic walking algorithm.

1) Cache efficiency
Most PC programmers don't have to be aware of this, but console programmers do. Processing chips come with a temporary area of memory called a 'cache' that data is stored into upon access, and kept there until it's time to free it again. What the cache is for, is to improve seek and read times over long amounts of data access by frontloading all that time at first. Any subsiquent accesses check the cache first, before going back to main memory. When your controller goes to the cache to find a piece of data, and it's in the cache, this is called a 'cache hit' This is a good thing! reading memory from the cache is super fast! When you go to the cache for data, and it's not there, this is called a 'cache miss' THIS BAD! GROG HATE THIS! Why? Wellll, because of the time to access data from main memory is usually pretty slow, and that data has to be loaded into the cache. If your cache is full, you also incur the overhead of determining what cacheline to free, and can overwrite something that another function will need in a few milliseconds, thus incurring a cache hit there. (see my previous post about LRU/MRU efficiency for more on this) Planning for this occurance is actually not too difficult, you just need to be aware of your memory access patterns, and ensure that you're doing prefecting correctly.

Firstly, ensure that the data you're accessing can fit into a cacheline. On the 360, a cache line is 128 bytes. This means that you can load that data into the cache, and access all of it before incurring a cache miss again. So, if you have a structure that's 64bytes, you can only fit 2 of those in a cacheline before you get a miss. This degenerates REALLY quick when walking structures of these types. Just like the inibitions of your sister when she's out with that guy who has a fast car and 'nice hair.' slut....

There's some things that make sense about this, that can help.
1) Ensure your structures are aligned properly. Any sort of padding inserted into your structure will add un-needed bytes into the structure class. This takes up precious space in your cache, and can cause a great deal of problems. (I won't go into all the details on how to ensure alignment and padding, you can google that)
2) Try to keep your structures as small as possible. Infact, if needed, break down your structures into smaller data types. Think about 'HOT' and 'COLD' sets. That is, a HOT set is a group of data in your class that's accessed frequently. Say the state, or number of elements it contains. These things are constantly looked up in list walks. the COLD set is things that are only looked at every now and again. If you have a 64byte class, but 40bytes of it can be considered COLD, then it would help you to instead, place all the HOT data into your list, with linkage back to the main data container class. This way, you only have 24bytes per struct of data to queary as you walk the list, and can fit more of these data classes into memory.
3) Try to create 'Structures-of-Arrays' instead of 'Arrays-of-structures' This is just the next stage of (2) above. If your'e not accessing all the data in your HOT set at the same time (ie you'll only ever check the state, OR the number of containments, but rarely both at the same time) it would be smarter to make a list made entirely of STATE, and a seperate list entirely of NUMCONTAINERS. That way, you can fit even MORE information into a cacheline, and you're not wasting cycles moving your memory pointer around for data you don't want.

Of course these optomizations come with some engineering cost, and maybe a bit of overhead in memory for linkage or explicit defintion of workings of the function, but in general, these are the things that can GREATLY improve your coding speed.

2) Memory fragmentation.
True, this is more like a memory management issue, but it is important to know, none the less.
By now, everyone should know that dynamic runtime allocations are the DEVIL. Why? Well, every time you call 'new' the memory allocation function trots off into memory, finds a free spot, and gives you memory back that you asked for. Over time, this can cause lots of spaces to be freed, or used, giving the physical apperance of a cratered surface of the moon. What starts to occur, is that when you've got lots of little pieces of memory free everywhere, and you go to allocate a large block, well, the memory has to defragment in order to accomidate your request.

Not only that, but lets think about jumping around in memory. We already know that when you access spot X in memory, you can get X + 128 in the cache. Well, what if the next data element you're looking for isn't within the next 128 bytes? What if its 2 mb away in memory somewhere? Well, then you have to jump all the way there, cause a cache hit, and load the data. Memory seek times usually aren't that bad, but it can add up the more you start bouncing around. Lets say you've got a linked list, that will dynamically allocate over a number of frames. Well, you've got no insurance that those nodes are conguious in memory. And as you walk that list, you'll find yourself jumping around everywhere, causing cache misses, and incurring perf burden all over the place. This really comes to light in places like file IO, where you have to incurr seek time costs for every read you do off the disk. Especially if you're reading from slow-as-shit optical disks!

What's better? Known thine data! It is much better to allocate large blocks of memory up front, and manage them yourself over time, rather than constantly rely on dynamic allocations and potentials for memory fragmentation. There's some hueristics that go along with this, namely 'how much do i need to allocate before i run out of room, and how do i handle that?' But those are topics for a different post. What you need to know now, is that handling your own memory by hand is tricky, but can cause massive perf and mental wins over time.
Especially for console development, or large project settings. It gets a great deal easier when you know that your AI system will ONLY ever use memory between addresses 0x61227372 and 0x81227372. So, you know if for some reason your XML system is trying to read memory at location 0x71111111, you've got a problem (unless you're talking to the AI). Not only this, but it maks cleanup a great deal easier. Linked lists are the worst for this, because it takes a great deal longer to free tons of tiny blocks, than it does one big one.

3) PRECACHE
if you know your memory is conguious, and you know that you're potetially going to have to walk to the next 128byte block, go ahead and issue a precache command on the block to get all the pipes churning so the data will be loaded in there by the time you get there. The reason cache misses hurt so bad, is that the thread your on WAITS until the cache data gets loaded, then returns the data requested. If you precache, then the cache can start loading while your thread is doing it's dirty business. This is good shit.

4) PRECALCULATE
If, for some ungodly reason, you need to sample a calculated variable while you walk a list (say you need to find the smallest value of a grouping, that requires some math to be done every time its sampled) it's better to NOT do that every time you touch that array element. Instead, precaclulate that stuff as much as you can, even if it's only for this one frame. Remember, list walking is seldom ever a 1 time thing. Most of the time, you'll have to search the same list, a number of times, for different criteria, for different results. Having to caclulate that data every frame, wow, that can suck dick.

So, all in all, make sure that you keep some of these things in mind when designing youre classes and your list searching structures. Look around your code and you'll be suprised how many violations of these patterns you're doing. And as always, don't be afraid to profile your code. it's always good to know how fast an algorithm is in relation to how fast it could be with the proper attention.

~Main

The importance of visualizing

2007-08-18T13:41:00.003-05:00

Debugging is a really crummy process. It's inherit to what we do of programmers. We, as flawed organisim, generate flawed logic and processes that rear their heads into your code, causing us nothing but premature balding, and grief.

As thinking creatures, we construct mental models in our mind, which we visualize as a series of logical steps and outcomes.

This is why visualization is so important. Ensuring that you're generating proper information from your systems to actually create a visual representation of what's occcuring can help millions of steps faster than just running the algorithm.

Infact, imagine NOT having a debugger. Image not having even a visualization of basic steps for your code paths. How hard would it be to debug anything in your code?

Now, there's not 100% definition about how much visualization you need, or when you should spend time implimenting it. IE you should spend the first 70% of your time, putting an algorithm together, and only until you need to start profiling, or a nasty bug comes up, do you need to visualize everything. BUT the main point here, is that stopping a debugging process to put in tools to help w/ the debugging process, is actually pretty valuable. Mainly because the same tools that you put in for the process can help you to do profiling characteristics.

So, make sure that next time you find yourself going "what the hell is this thing doing?" answer with " I don't know, let me look."

~Main

Virtual Memory Management

2007-08-18T13:41:00.001-05:00

Like the average programmer gives a hoot. But virtual memory handling is a pretty big deal.

Especially w/ video games.

So let's talk about low memory systems. You've got a budget of X texture memory required to render the visible scene. (we're not talking about the full memory required to load that scene into memory, or bus throughput) But, we've only got X/3 space available for this scene. Believe it or not this is actually a really important problem, even on PCs!

Why is this important?

Next gen video games will rely heavily on multithreaded systems. For rendering, file IO, network communication, AI.... you name it. It makes sence then, that systems that take full advantage of Asyc communications between these threads will be of more benifit and flexibility than those that do not. Infact, it'll start progressing to the point that if you DON'T enable your systems to be aware of threading and streaming,then you're actually handycapping your entire engine.

So, that being said, back to our goal here : Working with a cache.
OS programmers have been dealing with this problem for years, and much to my chagrin, know a great deal more about it than I do. They call it 'Virtual Memory Management' and for the sake of confusion, I'll keep to their terminology. How i'll be using it though, is the way that game programmers have been using it for a number of years now : Active texture slots.
Let's say you're working in an pre-vertex shader system. You've got 8 texture slots available to you, and all of your objects on the screen are single textured, referencing some pool of textures on disk. So, in a typical FPS view, lets say you have 20 objects, with about 12 textures used for these objects. In a neive way to render, you would loop through all the objects, set the active texture, render the object, and repeat. This leads to bad perf wrt the API, mainly due to the heavy lifting of all the state changes. A smarter approach would be to sort the objects by texture, so that you minimize the number of state changes that occur over time. This works qutie well for the given example. So, lets try something a bit more challenging.

Lets say you have 20 objects, and 20 different textures.. Oh shit! Now what? Even with the accelerated view above, you'll cause worst case perf. The answer to this, that many people figured out quite some time ago, was that it's smarter to fill the active texture slots of the GPU with textures that are going to be used, and allow the objects to reference the different slots, instead of just slot 0 all the damn time. This is known as texture cache managment.
So, you would take the first 8 objects. load all 8 textures, then render the 8 objects. Reload 8 textures from 8 new objects, then render those 8 objects. Rinse, recycle, repeat. This of course is worst case scenario, where we have unique textures everywhere, and nothing can be reused. Although, we can save a great deal of perf from this, in the form of preservation. That is, a coherience between frame N and frame N+1. If we can organize our textures in the cache, so that at the end of this frame, we keep around textures that are going to be used next frame, then we decrease the amount of swapping that must occur next frame, and lower the overall perf hit for our system.

The question is, well, how do we do that? That is, how do we accuratly determine what textures to keep in the cache over time, and what ones we should just dump by the curb? IE how do we pick proper metrics to choose a 'victim' page of memory, when the cache is full. Believe it or not, this is a much harder problem then it sounds. Factor into account the fact that each 'thrash' (replacement of a victim page w/ a new page) has a specific cost associated with it. And there's another cost that the victim texture you choose, might be needed again next frame, which will cause another thrash in the future.

This is where all those stupid, crazy ass virtual memory algorithms you learned in your OS class in college come in to play. Believe it or not, there's some really good engineering algorithms in there. Let's talk about a few, how they help our texture cache system, and some ideas.

OPT: this ofcourse, is the best algorithm ever. Your mom boned this algorithm, and created your brother, who now bangs supermodels and gets free money. OPT is theoretical. OPT has the ability to know what texture is going to be used the FARTHEST AWAY in the future, and chooses that texture as the victim when a thrash occurs. This is what we're hoping to move closer too.

MRU: Most Reciently Used. MRU replaces the page that hasn't been used for the longest amount of time. So when a texture is loaded into a cache page, you set a frame counter to it. When a thrash occurs, you walk the current textures in the cache, and find the one with the oldest frame count. Then you slit the guy's throat and replace him. MRU does some cool things, but is prone to MASSIVE texture thrashing. That is, you'll always have an oldest texture in the cache, which means that unless you're careful, you can actually clear the entire cache every frame. Not exactially good shit.

LRU: Least Reciently Used. LRU replaces the page that was just replaced. That is, the youngest texture in the frame. LRU has the same problems of MRU (potential to replace the entire cache) but one thing it does have as an advantage, is that it creates a scratch pad. Say for instance you only need to thrash 1 texture spot between 2 textures for the next 10 frames. Well, MRU would thrash every texture in the cache over those 10 frames. (becauase as it inserts, it becomes the youngest) LRU though, would look at the latest replacement, and victimize that. In essencine, this keeps you from thrashing ALL pages, to just thrashing one page. Which, as far as memory cache is concerned, is a good thing.

There's been some good descriptions about how a MRU/LRU hybrid is a good approach. Basicly, it works in the form that you use MRU most of the time, until you reach the point that your'e needing to thrash every frame (or the youngest texture in your cache, was created last frame) At this point, you switch to LRU to keep from re-creating the entire cache over the next X frames.

COST : An addition to these algorithms is a cost based metric. That is, you determine how much this texture will COST you to reload it into the cache. So basicly, what this turns into, is that you're more worried about performance cost of a thrash, as opposed to coherience between frames. When a thrash occurs, you find the cheapest texture in the cache, and get rid of it. This has the metric that it COULD create a scratchpad system (if you're constantly bringing in low cost textures) or it could thrash the whole damn thing (if your'e brining in high cost textures.) The good news is that this EVENS OUT over time. That is, that over time, you keep those textures which cost the most to thrash, in memory, and not thrashing. This is a good thing. Now, you can put this on top of LRU/ MRU if you desire. That is, find me the oldest texture, and use that as a multiplier as to the cost of the thrash.

AGE: One algorithm I really like is a log system. That is, we use the history of this texture to predict the future. When a texture gets placed into the cache, we mark (for a certain number of frames) how many times this texture is used. When we go looking for cost, we evaluate the number of frames it's been used, over the number of frames in our analysis window. This gives us an 'Age percent cost' which allows us to evaluate how imporant this texture is to our scene.
IE if you have a texture that's been visible 70% of the last 100 frames. It's got a high chance that it's going to be visible next frame too. On the other hand, if you have a texture with a 10% APC, then chances are it just became visible, or is on the edge of your view frustum.

What I like about AGE is that it gives a number of implict benifits, that i don't have to code myself.
1) It biases Old textures. That is, forces textures to PROVE that they are needed for the scene. And once they have, they keep them around. Once an APC gets above 50%, it gets really hard to release it from the cache. This is a good thing!
2) It creates scratchpad. That is, new textures whom haven't proved they are valuble yet, get turned into scratchpads. This is a good thing, as new textures are often results of frustum intersections, and have a high probability to vanish next frame for no goddamn reason at all.
3) It is an NRU scheme. That is, Not Reciently Used. Texutres that might have been visible a high percentage for a short time, could easly shoot up to 50% APC, but then drop out, and slowly work their APC back down over a number of frames. Well, AGE allows you to anaylize this, so that even if the APC > 60%, if the texture hasn't been used in X frames, kill it.

So, these are just some POV's about this stuff. It's really important to understand this, because more-often-than-not, you're going to run into a sitution when the words 'well, we just don't have enough memory for that' come to play. If you do your homework, your response should be 'well, true, we don't have enough memory to hold it all in memory at the SAME TIME. But if we only have what's NEEDED in memory at one time, then we've got plenty of memory for this!"

Your boss will love you.

~Main