Optimization and C

Starting this next game in C, I've known there will be places where C isn't fast enough, and I'd have to drop to assembly to optimize things.  Particularly because the 6502 processor really isn't a suitable target for C.  There's just too large a gap between how C structures things and how the 6502 needs things to be done.

Well, this week I decided to see how long my background updating routine takes.  The easiest way to see how long a long-running routine takes on the NES is to play with the color/bw register.  You can set a frame to render in B&W, and when the routine finishes, change the register to color.  The screen will switch partway through the frame, and you can see by where the color starts how much of your frame's computation time you've used.

In this example picture, you can see that the routine being checked runs from the beginning of rendering, to somewhere around 10% of the screen height.  So it's taking up somewhere in the general order of 10% of the total processing time available.

Well, my background updating routine (which renders a new slice of background just offscreen to prepare for scrolling) was taking somewhere around 40% of my total time.  It was horrible.  After playing around, it turns out that this loop was the culprit:

    while (temp > 0) {  //temp is just a counter of how many times to do this
        cj = *tempPtr2;  //get the current metatile into cj
        slicePtr = (u8*) metatile_ptr[ci]; //figure out which slice array to use
        vram_NEXT_BYTE(slicePtr[cj]);
        ci += 4;
        if (ci == 16) {    //if we've finished a tile, go to the next one down
            ci = 0;
            tempPtr2 += yIncrement;
        }
        --temp;
    }

It's not important to get into the details of exactly what this loop is doing, but a few things ended up being problematic:

1.  I look up slicePtr each time through the loop, although if you pay attention, it turns out there are only 4 different values it can be.  Pulling those out of the loop gained me about 5%.  

2. More importantly, and this is where C starts to fall apart, getting a value by index into an array can be super-slow if the array isn't contant. (ie if it's a non-constant pointer pointing at an array of data).  This is because the 6502 only allows indirect indexed addressing from zero page.  And what exactly does that nonsense mean?  The 6502 has a single special page of memory, the "zero page" that's, well, special.  To do a pointer-based lookup, you first have to copy the pointer to the zero page, then do an index from that.  So for a single slicePtr[cj] lookup, it's something like:

     

lda slicePtr

sta tempPtr

lda slicePtr+1

sta tempPtr+1

ldy cj       

lda (slicePtr),y

That's 21 clock cycles, if I haven't forgotten all my instruction timings in the months since making an Atari game.

So to improve this, I allocated space on the zero page for 4 pointers, and not only pulled them out of the loop (like I was talking about in step 1), but dropped to inline assembly, and saved them on the zero page once, so I wouldn't have to jump through those hoops every time.   This ended up being a huge savings in time.

3. By this point, I figured I had optimized it that far, I might as well go further, and unroll the loop a little, and do most of the computation in inline assembly:

    tempPtrA = (u8*)metatile_ptr[ci];
    ci += 4;
    tempPtrB = (u8*)metatile_ptr[ci];
    ci += 4;
    tempPtrC = (u8*)metatile_ptr[ci];
    ci += 4;
    tempPtrD = (u8*)metatile_ptr[ci];

    while (temp >= 4) {  //temp is just a counter of how many times to do this
        cj = *tempPtr2;  //get the current metatile into cj
        __asm__("ldx %v", vram_buffer_current);
        __asm__("ldy %v", cj);
        __asm__("lda (%v),y", tempPtrA);
        __asm__("sta %v,x", vram_buffer);
        __asm__("inx");

        __asm__("ldy %v", cj);
        __asm__("lda (%v),y", tempPtrB);
        __asm__("sta %v,x", vram_buffer);
        __asm__("inx");

        __asm__("ldy %v", cj);
        __asm__("lda (%v),y", tempPtrC);
        __asm__("sta %v,x", vram_buffer);
        __asm__("inx");

        __asm__("ldy %v", cj);
        __asm__("lda (%v),y", tempPtrD);
        __asm__("sta %v,x", vram_buffer);
        __asm__("inx");

        __asm__("stx %v", vram_buffer_current);

        tempPtr2 += yIncrement;
        temp = temp - 4;
    }

It's certainly a bit uglier, but it went from the whole routine being somewhere around 40% of my frame time, to about 10%.   I'll take that optimization.

Edit: And if you're wondering why my variable names are so awful, that's once again an artifact of the 6502 way of doing things.  C's method of allocating local variables on the stack isn't a particularly good fit for the 6502, so it's much faster to allocate a handful of generic global variables on the zero page that can be reused all over the place.  So most of these oddly named variables are common globals that are used for all sorts of things. (ie ci and cj are common index variable that I use in all sorts of loops)

Level loading and scrolling engine

Well, after a bit of work here, a bit there, between baby feedings and lack of sleep, I've managed to get the first bits of my level-loading and scrolling engine done.

First, I needed to figure out a level format. The NES native background tiles are 8x8.  But levels stored at that resolution end up being huge in ROM space, so most people use something else. Sometimes some sort of compression (gzip? run length encoding?) but that works best with games that either only scroll one direction, or that have a big ram buffer on the cartridge to decompress the data into.  The cheap cartridge mapper/board I'm planning to use, GT-ROM (which has some awesome features) doesn't have extra ram.  So that's out.  Instead, I'm going to try doing 32x32 pixel metatiles.  Where each "tile" of my level data represents 4x4 hardware tiles.  The convenient thing about this is that the NES tracks palette data for backgrounds in 32x32 chunks, so this will simplify that calculation.

So first, I had to build the system for defining and accessing metatiles.  And figure out tooling for having a UI to work with them.  Luckily a guy on the nesdev forums made a cool editor that does just that.  I don't particularly like the level editor piece of that tool, but it's perfect for a metatile editor, and it can spit out the definition in JSON format, which made it really easy to write a python script that gets run as part of my build process to transform the JSON format into the necessary source code data format.

Then, for actual level editing, I decided to stick with Tiled, which I used with Robo-Ninja, and is super flexible.  It can save levels in a nice textual format, so again, I wrote a python script to be run as part of the build process to convert these levels into the format the game needs.

Next up was drawing a level to the screen, and then scrolling.  It's late and the baby finally fell asleep, so I'll talk about that later.  Until then, here's an ugly picture of my test level data.  Frankengraphics gave me some beautiful background tiles to work with, and I turned them into a horrible ugly mess for now. But at least it's starting to look something like a game....

As an addendum:  Python drives me crazy. I know the kids say it's great, but the significant whitespace, the duck-typing, the ugly-formatted documentation - it all drives me nuts.