Harnessing >64kB with SDCC

[duncan_bayne]

Hi,

I'm still working on my Amstrad game in my (very limited) spare time, and I've run into an issue accessing more than 64kB RAM with C programs (compiled with SDCC).

E.g. this code:

Code Select Expand


void _test_malloc()
{
  long idx = 0;
  while (1)
    {
      if (malloc(5))
    {
      printf("%ld\r\n", ++idx);
    }
      else
    {
      printf("done");
      break;
    }
  }
}


... running from a ROM on a 64kB system consistently taps out at 92 malloc()s on my emulator (WinCPC, run through Wine on Linux).  I make that 460 bytes, which leads me to a couple of questions:

   
• What is malloc() doing on this system?  I was sort of hoping for an order of magnitude more storage even on a 64kB system
• The behaviour is consistent on 64kB systems and 128kB systems; do I have to perform some sort of magic to access the additional memory, like manual bank switching?

The (redundant) background: I'm trying to implement a very simple Scheme-like Lisp in which to code AI routines for my game.  If the best I can get is 92 cons cells, I can see myself having to abandon C and break out the assembler ...

[arnoldemu]

My answer:

No idea what it's doing with malloc.

For the extra ram:

I'm guessing it doesn't support it, and you would have to do the banking yourself to access it.

[TFM]

Time to learn Z80 assembler and enjoy the full power!

[duncan_bayne]

Time to learn Z80 assembler and enjoy the full power!

I actually know Z80 assembler tolerably well - I submitted the (Amstrad) Z80 assembler entry on the '99 bottles of beer' website.

Which is why I wanted to use C

[ralferoo]

... running from a ROM on a 64kB system consistently taps out at 92 malloc()s on my emulator (WinCPC, run through Wine on Linux).  I make that 460 bytes, which leads me to a couple of questions:

   
• What is malloc() doing on this system?  I was sort of hoping for an order of magnitude more storage even on a 64kB system
• The behaviour is consistent on 64kB systems and 128kB systems; do I have to perform some sort of magic to access the additional memory, like manual bank switching?

malloc also needs to store information so it knows the size of each block and whether it's free or empty. It might also have some alignment rules e.g. only allocating memory on 16 byte boundaries, etc.

Your best bet (and this is true on most platforms too) for fixed-sized structures is to pool them yourself. e.g. you might have an array of 256 structures and a bitfield to say which are free. This will generally be quicker than malloc, lead to less memory fragmentation (which is when you free a block between two others and then it's hard to re-allocate that block, or you allocate something smaller in the middle and then waste the rest), only has a single bit overhead for free or used, no need to maintain a list of blocks and their sizes, etc.

Following on from this, on systems with smaller memories, you're often better doing "structures of arrays" (SOA) rather than "arrays of structures" (AOS) as this avoids the risk of wasting memory at the end of a structure, but obviously complicates access and pushes you towards global variables.

The thing to remember is that malloc is designed to be suitable for all types of allocations, and so it's designed to be usable in all situations, but it's obviously designed around a typical case of few allocations of variable sized blocks. For a fixed-size allocator, you can almost do better than malloc yourself as you have more knowledge about the application.

[duncan_bayne]

It turns out that SDCCs heap size is hard-coded to 1kB on the Z80.  Maarten Brock explained this for me on the sdcc-user list:

Hello Duncan,

You have to create the heap yourself if the standard 1kB is not enough.
Copy heap.s into your project dir and modify it to create your preferred
size. Then assemble it and link with your project.

Unlike the mcs51 heap which is defined in _heap.c this is not documented
for Z80 in the manual. Feel free to request a documentation update or
merge of _heap.c and heap.s in the tracker system.

Maarten

So I think the best option is a hybrid.  Specifically:

   
• follow Maarten's advice, and increase the heap size manually (for things like buffer strings etc. in the REPL)
• don't allocate cons cells using malloc(), instead, manage their space manually as suggested by ralferoo

I think this could give me the best of both worlds: access to all the RAM on the system, and the use of C instead of raw assembler.

[duncan_bayne]

Further to this (thanks to Philipp Klaus Krause for the advice), SDCC supports a subset of the standard for named address spaces:

3.5.2

CHAPTER 3. USING SDCC

Named address spaces

SDCC supports named address spaces. See the Embedded C standard for more information on them.
So far SDCC only supports them for bank-switching. You need to have a function that switches to the
desired memory bank and declare a corresponding named address space:

Code Select Expand


void setb0(void);            // The function that sets the currently active memory bank to b0
void setb1(void);            // The function that sets the currently active memory bank to b1
__addressmod setb0 spaceb0;  // Declare a named address space called spaceb0 that uses setb0
__addressmod setb1 spaceb1;  // Declare a named address space called spaceb1 that uses setb1

spaceb0 int x;          // An int in address space spaceb0
spaceb1 int ∗y;         // A pointer to an int in address space spaceb1
spaceb0 int ∗spaceb1 z; // A pointer in address space spaceb1 that points to an int in address space spaceb0

So it looks like creating an array of cons cells per bank, and then managing allocation / reallocation myself, will be the way to go.  And I shouldn't have to write more than a line or two of assembler

[duncan_bayne]

Having had a bit of a play, I'm going to take the malloc() approach first, with the heap as large as I can make it.  Then, when things are running properly, roll my own memory management using named address spaces.