nesdev.org

Posted: **Sun May 12, 2019 7:07 pm**

Unfortunately, in the situation you proposed, the answer is the same, since the list has over 256 elements and each one is 2 bytes. The 6502 is an 8-bit CPU after all, so it's not surprising that it's not particularly swift when dealing with more than 256 of anything.

What we do in assembly is we often try to avoid these problematic situations. You may have over 1000 screens, but since you don't need random access to all of them at any given time, you can resort to some sort of "banking", and change which set of 256 elements or less is visible at any given time as you go (totally not worth the trouble for something that only happens once every several seconds, but you get the point). It's true that by breaking up large amounts of data into smaller chunks you increase the path needed to reach it (there's more indirection), but as long as you don't need full random access, you don't need to reconstruct the entire path on each access, just the final step, which's ideally comprised of 8-bit operations. Whenever a big change happens (new screen, new level, etc.), you might need to recalculate the earlier sections of these paths, but that will happen way less frequently.

And even if you need total random access to a large data set, you can still optimize the most common cases, maybe by placing the 128 most commonly accessed elements first, and only doing the slower type of look-up when the index is larger than 127.

Also, when dealing with 16-bit data, in assembly it's common for the data to be split into two arrays of 8-bit values, one with the low bytes and one with the high bytes, so that you don't lose any range (an 8-bit index can still still access 256 elements) or time doubling the index.

The thing is that in assembly, we usually have more control over how we store or stuff, so we try to pick the most suitable schemes for each type of data, as opposed to always using linear arrays for everything. I don't know if the same approach is feasible in C, or if a C programmer would even want to spend time on that kind of optimization...

Posted: **Sun May 12, 2019 8:49 pm**

Well anyway, the generic problem of 16-bit base address and 16-bit word offset looks like this:

Double the offset (because the data type inside is 16-bit and not 8-bit)
Add to base address
Load a 16-bit word

In 6502, it's something like this:

Code: Select all

lda indexLow
asl A
sta tempLow
lda indexHigh
rol A
sta tempHigh
clc
lda tempLow
adc #baseLow
sta tempLow
lda tempHigh
adc #baseHigh
sta tempHigh
;now tempLow/tempHigh contains the address of the pointer to load.
ldy #0
lda (tempLow),y
sta pointerLow
iny
lda (tempLow),y
sta pointerHigh

If you are able to double the number ahead of time, you can do this instead:

Code: Select all

clc
lda indexLow
adc #baseLow
sta tempLow
lda indexHigh
adc #baseHigh
sta tempHigh
ldy #0
lda (tempLow),y
sta pointerLow
iny
lda (tempLow),y
sta pointerHigh

Posted: **Mon May 13, 2019 12:35 am**

Yeah, maybe splitting it into two or more arrays would be better. However, indeed, stuff like this is never time-critical since I only have two of these arrays anyway: Screens and dialogs. Every other item in the game (for example character types, palette data etc.) should come in units of less than 128.

But nevertheless, it's still a good thing to optimize whatever the compiler produces here.

@Dwedit: Thanks for the code. I'll have a look at it later.

Posted: **Mon May 13, 2019 1:40 am**

The compiler's code for this particular case is not bad. It can only be optimized by the things you listed, the redundant Y load and using your own pointer directly.

Posted: **Mon May 13, 2019 8:56 am**

If CurrentDataIndex cannot exceed 127:

Code: Select all

  lda _CurrentDataIndex
  asl a
  tax
  lda _AllData+0,x
  sta _CurrentData+0
  lda _AllData+1,x
  sta _CurrentData+1

Otherwise, this is how I'd write it:

Code: Select all

  ; cc65 makes 18 bytes of ZP variables available for callees' use:
  ; ptr1-ptr4 (2 bytes each), tmp1-tmp4 (1 byte each),
  ; regsave (4 bytes), and sreg (2 bytes)
  ; https://github.com/cc65/wiki/wiki/Using-runtime-zeropage-locations-in-assembly-language
  .importzp ptr1

  ; Multiply map position (20*Y+X) by
  ; sizeof(const byte *) which equals 2
  lda _CurrentDataIndex+0
  asl a
  tay         ; low byte goes to Y
  lda _CurrentDataIndex+1
  rol a
  sta ptr1+1  ; high byte goes here

  ; Add the base address of world map array
  lda #<AllData 
  sta ptr1+0
  clc
  lda ptr1+1
  adc #>AllData
  sta ptr1+1

  ; Read the pointer from the world map
  lda (ptr1),y
  sta _CurrentData+0
  iny
  lda (ptr1),y
  sta _CurrentData+1

Posted: **Mon May 13, 2019 9:33 am**

Yeah, you can save a little bit of time by putting the low byte of the doubled offset in Y and letting the CPU's indexing do the addition for you, instead of calculating the compete pointer and loading Y with 0, but that's probably as far as you can go when optimizing the generic case.

You can probably get rid of that CLC too, since the index can only go up to 32767, so the carry would always be clear after shifting that left. Unless you're using that bit for something else, of course.

Posted: **Mon May 20, 2019 1:21 pm**

Thanks for the generic function and the optimization.

It turns out that cc65 produces even smaller code than the handwritten Assembly version due to using some internal subroutines (ldaxi, aslax).
Since speed is not an issue (I only use this kind of pointer array access with interger index during the screen buildup) and therefore, I can swallow two additional JSR/RTS, I will simply keep the C version for less ROM space usage after all.

But it was still very informative. (For example, I now know how to double an unsigned integer variable in Assembly.)

nesdev.org

Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502

Re: Accessing an array of pointers in 6502