Monday, July 24, 2017

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)

6 comments:

sverx said...

the top part of the screen (approx 10%) is gray, which means you're using 10% of your frame time ONLY IF you're doing your work starting at scanline zero... are you sure you're starting there?
I mean, most of times the work starts at vBlank, which is just after the screen visible lines are drawn...

Nathan Tolbert said...

Good point -- you're right in that I'm absolutely oversimplifying things. Where is the work starting? It's not actually at scanline zero. But it's actually not THAT far off.

I'm spending most of vblank pushing last frame's updates to the PPU, and doing a bit of between-frame bookkeeping. So I'm not sure exactly what scanline I'm starting on my update code, but it's somewhere "around the end of vblank", which is close enough for a quick sanity check of "is my code terrible and slow?"

Edit: just checked, this code starts 3 scanlines before zero. So, close enough :)

sverx said...

Sure! :)
BTW I was wondering how you could spend 10% of your CPU time just to update a column of tiles (IF I got it correctly) - frankly it seems to me it's a lot of time, but I admit I'm not very knowledgeable here, as I know NES very little.
What if you store your 2x2 metatiles as two separate array 'columns' so that you'll be only reading two tiles sequentially either when updating an odd or an even screen column? You'd save one address calculation every two...

Nathan Tolbert said...

Good question :)

First, I'm pretty sure I'm NOT doing things very efficiently. My tentative plan with this is to write everything in not-very-optimized C, then go back and optimize things as needed. There's still a lot of written-for-readability C in my background updating routine. And add that to being my first NES game, I have no confidence in what I'm doing.

That said, I'm actually doing 8x8 tile metatiles, AND this game will support 8-way scrolling. So a lot of the nicer solutions (storing things as columns) don't necessarily help, as that will only help with the horizontal scrolling. (If it comes down to it, and I need to optimize further, I guess I could double-store my metatiles, both in column stripes and row stripes. That might be a nice tradeoff of time vs space)

There's a lot of things like that that I've found, where if it was content to limit it to horizontal OR vertical scrolling, I could tighten up the code a lot. Just figuring out where in the nametables to start drawing is more complicated, because I can't assume it starts at the top and draws to the bottom, but instead, it may start partway through one nametable, carry on into another, then end partway through that one. Ugh.

That said, suggestions (like your separate columns of metatiles) are always helpful. Like I said, I'm new to this platform, and not above hearing good advice :)

Marketing 92 said...

Marketing92 is the IT Company in Lahore, Pakistan. The Service of Facebook Marketing in Lahore and SEO Services in Lahore, Pakistan, will increase the numbers of customers on Your Business and increase the traffic of your website.

HostOne Pakistan said...

HostOnePk is the best service provider in all across the country providingweb development in Lahore. Now you can develop the best web sites in a very cheap prices. HostOne services includesreseller hosting in Pakistan. Which is the best and cheapest web hosting service in Pakistan.

Metatile Designer

For the NES game, I'm building my levels out of 32x32 pixel metatiles.  What is a metatile?  The NES background tiles are 8x8 pixels, bu...