Fio:Caching

From Fio

Revision as of 14:25, 17 September 2006

"The world is changing , right before your eyes." - The Eagles

Image Caching

Now Fio's renderer is implemented using DirectX(8.1). To render fast in DX images should be first loaded into back surface then blt onto the primary surface(what you see on the screen). For the video memory which hold the surfaces is limited - it isn't big enough to hold an entire level, we need an image cache to manage the back surface:

• load only images need to show up on the screen into back surface;
• and unload those ones out of screen (when the map scrolls, critter steps outof viewport, dialog sinks etc.);
• tell the renderer where to find the cached image on the back surface;
• avoid duplicated images load into back surface.

How It Works

The cache is basically a big rect(represent the back surface) and will be fraged by tokens(represent the dimension of an image) when caching in/out happens. These tokens will be arranged line by line from top to bottom of the cache. When renderer need to draw an image, it'll ask the cache to find out where the image is located then use the returned rect to blt the image from back surface onto primary surface. Let's check the details:

Token and Lines

A token is a rect representing an image's location and dimension in back surface. It is marked as busy or free.

When busy, it means an image is loaded into back surface at the rect defined by this token.

A free token can be:

• • occupied to be busy;
  • merged with it's neighbor(s) which is also free into a wider token;
  • fraged into 2 narrower tokens - one is busy, the other is free.

A line is a list of tokens. Its height is the max height of all its tokens(plus a tolerance value).

Cache In

When the game starts, all images of the first screen in the view port will be loaded into back surface. Firstly we'll sort all images into a list based on the height to pack them into cache more compactly. Now the cache is empty. It's time to find a place(rect) for the first image in the list.

We cut a new token at the left top of the cache (token1 : top = 0, left = 0, bottom = top + image1.height, right = image1.width) for the first image in the list and creat a new line to hold that token. The token for the second image in the list just follows the first one (token2 : top = 0, left = token1.right, bottom = image2.height, right = left + image2.width). Then the third one, and so on ... When we reach the right bound of the cache, we've finished one line of tokens. The height of the line is set to the max height of these tokens. To cache the left images we'll create a new line just below the first line, and pack the tokens from left to right, top to bottom - this approach is called tiling. After tiling, the cache is not virgin any more.

When a single image need to cache in, we'll try find a line high enough to hold that image. Then try to find a free token in that line. If there is a free token wide enough, we'll occupy it or frag it. If we can't find a token wide enough in that line, just step to next line. If all existing lines can't hold the token, we'll have to cut a new line below the lowest line in the cache.

A typical back surface snapshot when game loaded(red crossed tokens are cached out) looks like:

For we don't erase the old image - just draw the new one over the old one in back surface when caching in, it looks a little messy - but the renderer doesn't care.

Finally if there's not enough space left in cache, bad luck for that image. see When The Cache Overflow

When an image is cached in, we'll do a dual-mapping between the token and the image(using hash table now) to allow quick find from image to token or reverse.(is a dual map needed? i'm in doubt)

Cache Out

When an image needs to be swapped out from back surface, we'll find and free the token the image maps in the cache. A free token should be merged with adjacent free tokens. There're 4 kinds of neighbor-patterns to consider(BUSY one is the token to be freed):

1. free-BUSY-free
2. free-BUSY-busy
3. busy-BUSY-free
4. busy-BUSY-busy

(line head/tail is taken as busy)

Only the last one doesn't involve merge. The BUSY token in other 3 patterns need to merge with free token on it's left or right side into a new wider token in the line. Later it might be reused when image caching in.

Caching Operation

Cache manages how the back surface is used/occupied by images. But cache itself doesn't care how images are loaded or unloaded. We abstract the cache in/out operation into an interface named CacheOp. Cache should be configured with a CacheOp object when ctoring. And when allocating/freeing a token in cache, we'll invoke cacheIn/cacheOut operation on that CacheOp object - who'll finally do the labor of load/unload image into/outof back surface.

By separating the back surface/image loading details from caching strategy, we make the cache testable - just need to define a subclass of CacheOp who doesn't even know DX/graphics and it will play well with cache. Launch the unit test suite, we can test the cache in a console application.

When The Cache Overflow

After the game running for a while, a lot of caching may happen with the critters step here and there, dialogs pop and sink, screens switch back and forth. New lines of tokens may reach the bottom of cache rect. Now when a caching in happens, cache might not find a token with proper size - though there might be a lot of holes left there in cache, the cache is just too fraged. We name this condition Cache Overflow.

When a cache overflow happens we need to resort all tokens in cache and do a tiling again. After a tiling the cache is much compact than before - all holes are squeezed out as free space down to the bottom of the cache. A fresh new start.

Mapping to Image/Frame

Image and token are associated to each other thru a dual mapping using hash table.

There's another mapping from image to reference-count. This map is to avoid duplicate loading of the same image into cache. When another component(say a button) want to cache in an image that is already in cache, we just increase the reference-count here. And when caching out, we only really cache out an image when the reference-count is decrease to 0.(keep the reference in token might also works and cleaner)

Isolate Cache from Component

We've use CacheOp to isolate surface/image operation from cache. In Fio all drawable things are Component(buttons, lists, critters, doors, etc.). Should a component know caching? (e.g. When a list item is scrolled out of the bottom of a list, should the list call cache out to unload that list item's image from cache?)

If each component do its caching in/out immediately when it's torched, there might be:

• many lock/unlock of back surface in CacheOp(the lock/unlock takes time!);
• an image cached out by this component might be cached in by another component(kind of jitter as real cache).

We design a Marker class as a static member of Component(so it can be shared by all components instance). When a component needs to cache in/out an image, it just mark that image in the marker - the marker will record which image need to be cache in/out and keep a reference count. When the time comes for rendering the world in the game loop, the marker will do a cache out for all images marked-as-out and then do a cache in for those marked-as-in - this totally-swap-out-then-swap-in approach is more efficient too.

Marker is also an interface; the implementation is in CacheMarker.

Strategy: Active or Inactive

When the cache overflows we takes a lazy approach - if cache doesn't fail we don't care about how messy there in the cache. We'd considered a heuristic approach to measure the messiness of the cache, it's easy to measure by the free/busy token proportion, token counts of lines etc. When it's messy enough, we'll do a sort and tiling.

But we give up this approach - for the lazy approach is

• simpler;
• fast enough.

Sanity Check

As the game running, many images come in and then leave the cache. If an image is deleted(dialog sinks, critter dies, etc.) and we forget(a bug) to mark that image out thru the Marker, the token of that image will be left in cache as garbage - it may lead to some rendering error or just eat up the back surface. For all these happens on the back surface - we can't see it. And when we notice the render error or cache crashing, we've been far away from where the error orginal happens.

To make sure the cache is healthy, we'll do a sanity check for tokens in the cache in each game loop. In debug mode when an image is deleted, crt will fill some flag data into the dealloced memory. Sanity check is to check if the image maped by each token is a valid one - left, top, width, height are all positive and in a proper range. When a sanity check fails, we can locate the bug in the caching of the last game loop and find out which component failed to mark out it's image there.