C on the Spectrum (z88dk)

[ZxSpence]

It's worth pointing out that a two dimensional array is just a one dimensional array. You just index the row by X columns. However as connect 4 pieces only ever go down it's better to flip the model 90 degrees so that the columns are modelled but the rows are not. As the calculation should occur for 4 in a row once all gravity effects have been applied the checks for proximity are best modelled as you would with chess move checks, to whit recursive allowing an early exit.

[dfzx]

When I tried to change the structs, that just hold two-dimensional arrays to, well, global two-dimensional arrays, the program still worked, but was rather slow. Are structs stored in different memory areas than global arrays?

No, C is much simpler than BASIC or any other high level language. There's no concept of faster or slower memory areas (other than the Spectrum's concept of contended memory as imposed by hardware, irrelevant in this example because you're only using 0x8000 upwards which is outside the contended range).

In C when your code stores a byte in memory the compiler arranges the Z80 instructions to put that value into a memory location; when your code reads it back again the compiler arranges the Z80 instructions to do so. This is done very efficiently so there's only likely to be 2 or 3 such Z80 instructions per memory access in the compiled program. It won't be quite a efficient as a hand crafted assembly language program where the programmer can think about the exact best approach, but it'll be close.

If you change the data structures in the C you can guide the compiler to producing better code, at least to some extent. Likewise, if you don't yet understand exactly how the compiler works, you can also end up "guiding" the compiler to produce less efficient code. One of the fun things about C on the Z80 is that the compiler's Z80 output is quite readable, so you can have a look at what it's doing, spot the bottlenecks it might be introducing and learn how to guide it to improve things. All a bit down the road for you yet though.

Mind you, I'd be surprised if you managed to change your little game's source code to influence the compiler such that it made it noticeably slower. What did you do? If you can reproduce it try adding:

Code: Select all

-SO3 --max-allocs-per-node200000

into your compile line. Those flags turn on the optimiser, which is slow but quite efficient. See if that makes a difference.

[dfzx]

It's worth pointing out that a two dimensional array is just a one dimensional array. You just index the row by X columns. However as connect 4 pieces only ever go down it's better to flip the model 90 degrees so that the columns are modelled but the rows are not. As the calculation should occur for 4 in a row once all gravity effects have been applied the checks for proximity are best modelled as you would with chess move checks, to whit recursive allowing an early exit.

I think there might be a bit of room for optimisation in his implementation. The code isn't easy to read but as far as I can see he's pre-populating an array with the 69 winning patterns then doing a comparison of the current board against that data set each move. So, perhaps not as advanced as what's in your head, but a decent exercise for a C beginner.

[ZxSpence]

Fair enough. Any chance the memory for globals ends up in a contended bank?

[AndyC]

I can't speak to z88dk specifically, but as a general rule of thumb it's harder for compilers to optimize global objects as it requires reasoning over a much larger block of code to ensure the output remains valid.

[dfzx]

Fair enough. Any chance the memory for globals ends up in a contended bank?

No. His compile line ORGs the program at 0x8000, so the program starts there, then the DATA section goes directly above it, then the BSS section goes directly above that. Nothing will go in the lower contended bank. C doesn't know anything about switched bank memory on the 128K machines, and although there's library support for it you very much need to work to make it happen. It can't happen by chance.

[dfzx]

I can't speak to z88dk specifically, but as a general rule of thumb it's harder for compilers to optimize global objects as it requires reasoning over a much larger block of code to ensure the output remains valid.

Yes indeed.

z88dk allows you to choose between 2 C compilers. The more modern one is a modified SDCC, and that has relatively sophisticated static analysis. It works hard to allocate registers and static locations efficiently over large code blocks. Even so, the most efficient approach is to keep code blocks tight so they only use as many variables as the compiler can arrange in the Z80's registers.

[Alcoholics Anonymous]

I can't speak to z88dk specifically, but as a general rule of thumb it's harder for compilers to optimize global objects as it requires reasoning over a much larger block of code to ensure the output remains valid.

The z80 is a special case though - it so happens that it is often faster to load and store from absolute memory addresses instead of loading and storing to local variables on the stack. Using the stack for local vars only saves time if the compiler is able to hold those values in registers as long as possible and then have the option not to write to memory if not needed. For reasoning about static variables, zsdcc does distinguish between volatile and non-volatile memory but I'm not sure how well that is obeyed.

zsdcc will also try to allocate to registers to avoid writing values to memory if it can. It's not terrible at it but it can be befuddled by sub-optimal C code and results can vary with C coding style.

Fair enough. Any chance the memory for globals ends up in a contended bank?

C doesn't know anything about switched bank memory on the 128K machines, and although there's library support for it you very much need to work to make it happen. It can't happen by chance.

The humans programming do though

The compiler gives you (the C or asm programmer) total control over where things are placed in memory. The toolchain is a modern one and it works by defining a memory map composed of sections into which the linker distributes code and data that the programmer has placed into specific sections.

For the 128k spectrum, the toolchain is fully aware of banked memory and all you have to do to put stuff into banks is assign your c code or asm code into a bank. You can also define your own sections with their own org and put stuff into those. The appmake generator in z88dk understands these sections and can generate an SNA automatically using them or you can go to things like raw binaries for the banks. As a byproduct of adding the zx next support, the zx type can also generate dot commands for divmmc interfaces which has a separate memory space in divmmc memory.

The default memory map for the spectrum target collects everything not placed into a BANK section into the "main binary" which is assumed to be destined for the usual start-up spectrum memory map, that is banks 5,2,0. The main binary is composed of the CODE,DATA,BSS sections ORGed at the user defined CODE origin (32768 by default).

[Alcoholics Anonymous]

It's worth pointing out that a two dimensional array is just a one dimensional array. You just index the row by X columns. However as connect 4 pieces only ever go down it's better to flip the model 90 degrees so that the columns are modelled but the rows are not. As the calculation should occur for 4 in a row once all gravity effects have been applied the checks for proximity are best modelled as you would with chess move checks, to whit recursive allowing an early exit.

As a 2d array the program must still perform a multiplication and addition to index to the chosen entry. If the numbers are nice, the multiplication may be turned into a bunch of shifts and adds so the penalty is not too bad. A manual 2d array where the programmer indexes into a 1d array with an actual multiply explicit in the code may not be optimized as often; I think the fact the compiler knows it's a 2d array means it will look for a nice shift-add solution for the entire index operation.

But another faster 2d array type is the jagged array which is an array of arrays. The main 1d array is an array of pointers so arr[ i ] returns another array. Then the second index is a 1d offset so arr[ i ][j] turns into a fast operation since arr[ i ] is reading a 16-bit value from an array of 16-bit values which means the offset is i*2 which is fast.

[ZxSpence]

You don't need to multiply.