Tilemaps are cool things, but as implied by the topic, you run into problems when you have many possible sprites that could be displayed. Just for fun, I was toying with a spritesheet with a full size of 384x176, or about 8 separate 128x64 xLIBC tilemap AppVars. Because xLIBC can only "cache" a maximum of two tilemap spritesheets at a time, having locality becomes extremely important. This locality can be exploited in one of several ways:
1) Pack together sprites that will be most likely to be displayed together on the same spritesheets, and pair spritesheets as needed so that the two can be frequently loaded at the same time.
2) Make multiple passes over the tilemap, displaying only tiles using sprites from the two currently-cached spritesheets in the current pass.
3) Allow new spritesheets to be swapped in, but be intelligent about which one you trash.

For this experiment, I chose to simply use LRU caching, and not bother with any temporal locality tricks:
Code:
As you can see, L1 is used to track which of six tilemap AppVars are loaded into buffers 0 and 1, and wipe out whichever was used less recently based on what the O variable was in the last iteration. I did see a significant reduction in rendering time compared with caching a new spritesheet on every single sprite draw, but the screenshots below still take about 20-30 seconds each to render.

Comments or questions? Suggestions about how I could do this better?

Can someone direct me to a thread where the principle and use of an AppVar is explained fully?

AppVars in general are just another variable type on the calculator, nearly indistinguishable from programs. Like programs, they have names from 1-8 characters, and the OS doesn't impose any structure on the contents of the variables. They were originally intended as non-volatile storage for Apps. In this case, I'm referring to the fact that xLIBC uses AppVars to store sets of sprites, with the contents representing a 128x64-pixel area, one byte per pixel.