Arduino Dynamic Array

Context? Why does it need to be dynamic? Best option is to make it the max size and then keep track of what size it in somewhere else.

1 Like

I want to loop through the array to animate a sprite… When a Sprite is in one state it might have a 3 frames, and the other state may have 6…

My work in progress…

Then have multiple arrays and keep a pointer to the active state… but you’ll still have to track the length of the arrays.


Why not a multi-dimensional array … one dimension is state, the others are frames.

1 Like

Waste of space – all sprites would have to have allocated the same amount of space as the one with the longest animation. Although if space isn’t an issue, you could do it, but I’d implement it rather as a struct:

#define MAX_FRAMES 4 // <--- change to whatever

struct SpriteAnimation
  unsigned char frames[MAX_FRAMES]; // <--- list of frame numbers
  unsigned char numberOfFrames; // <--- length of the above list

Otherwise I’d recommend what @Dreamer3 says.

Dynamic memory allocation in general is not a good idea on these light system.

For what you want to achieve i would suggest you to look into the sprites class which can handle a good portion of animating for you.
All you would need to store in progmem would be the the frame indices in an fixed array.



As I understand it, dynamic allocation is bad as it fragments the heap. You can run out of memory in unexpected ways. Sometimes the game seems to work fine, others it crashes, just depends on what order you grab chunks of the heap and how badly it ended up fragmented.

Static allocation means the memory space stays stable the whole time.

1 Like

Really the problem is with the “dynamic” part of the allocation. It’s easy to allocate different size chunks of memory (on heap or stack), but you can’t just release/retain them randomly and of all different sizes - or then you’ll end up with fragments as mentioned above. If you only need a little dynamic you might be ok, if you need a LOT then watch out.


To give an example of what @Dreamer3 suggested:

const uint8_t sprite0frames[] PROGMEM =
	// Number of frames
	// Frames
	0, 7, 14, 21, 17, 1, 2,

const uint8_t sprite1frames[] PROGMEM =
	// Number of frames
	// Frames
	0, 1, 2, 1, 2, 3,

const uint8_t * const frames[] PROGMEM =

class AnimationData
	uint8_t frameCount;
	const uint8_t * frames;

	AnimationData(uint8_t frameCount, const uint8_t frames)
		: frameCount(frameCount), frames(frames)
	uint8_t getFrameCount(void) const
		return this->frameCount;
	uint8_t getFrameIndex(uint8_t index) const
		return pgm_read_byte(&frames[index]);

inline AnimationData getAnimationData(uint8_t spriteNumber)
	const uint8_t * frames = reinterpret_cast<const uint8_t *>(pgm_read_ptr(&frames[spriteNumber]))
	uint8_t frameCount = pgm_read_byte(&frames[0]);

	return AnimationData(frameCount, &frames[1]);

Hopefully you understand what’s going on, but if not don’t be afraid to ask.

Note that there are other ways to do this,
but this approach should give you a nice interface to work with and a bit of flexibility.

This is the crux of the issue.

Previously I’ve used dynamic allocation and been safe because I deallocated everything in the reverse order to how I allocated it (like a stack), but I still eventually switched to static allocation because scrapping the internal call to malloc (new calls malloc) saved me progmem.

The problem comes from the release of memory.
If you can release the memory in a deterministic way then you can avoid fragmentation.
But if you release things at random intervals, that’s when you end up with the fragmentation.

Although even deterministic deallocation can’t protect you from simply not having enough RAM.
And on Arduboy, the heap grows towards the stack, so eventually the two will crash into each other without warning.
I’ve never tested, but one of two things will happen:

  • If we’re are lucky, the Arduboy will reset like it does when the stack overflows
  • If we’re unlucky, the Arduboy won’t notice and part of the heap will be overwritten with ‘nonsense’ (from its point of view) from the stack, leading to strange bugs that could potentially lead to ‘dangerous’ behaviour (like overwriting the bootloader if the protection fuses aren’t set properly).

Most programming languages like to hide the realities of memory allocation from the programmer behind a ‘garbage collector’.
On an embedded system, there’s no such luxury.

1 Like

If you carefully tracked your dynamic pointers you could write a memory defragmenter… I always thought that would be a fun little project.

awesome drawing!

Another problem with dynamic memory is it has more overhead. If you ask for 10 bytes, then ask for 12 bytes, someone has to remember the first 10 bytes are taken in order to not give them out twice. The compiler builds this book keeping into your sketch for you, but it takes a little space and memory. With static memory, the compiler can just line things up one after the other and not have to do much book keeping.

1 Like

That’s pretty much what a GC (‘garbage collector’) does at a basic level.
(There’s more to them than just that though, e.g. they often have several different ‘generations’ of objects.)

It could be done if you used smart pointers instead of raw pointers, but the main issue is timing:
when to move the pointers and how long you should spend trying to move them.

A GC usually operates on another thread and will usually pause the main thread to intervene for a small timeslice before resuming.

It is, but sadly it’s not mine :P

It’s from the “Object Pool” section of Bob Nystrom’s Game Programming Patterns:

It’s free online, but I recommend buying the book to support him because it’s one of the best resources out there.

(I do draw though. I wouldn’t call it ‘art’, but I draw.)

Though how much memory depends on the implementation.

Technically it’s not actually the compiler that does the book keeping, it’s the implementation of the malloc and free functions (and their siblings) that handles it.

There’s lots of different possible implementations of malloc.
I happen to know that the code backing the Arduboy uses a kind of free list.

I was referring to static memory. As I understand it, statically initialized objects go to the .data section. The linker can determine the addresses at link time and embed them into the program. Then .data is essentially “memcpy”'d into RAM at boot.

Well in a non-interruptible type program (like most sketches) you can just do this wherever in the loop you felt like it. And even with interrupts you could always disable them briefly just for the actual pointer rotation/memcpy.

I meant to grab the “The compiler builds this book keeping into your sketch for you, but it takes a little space and memory.” part.

There’s certainly less overhead with static allocation than with dynamic allocation.

Partly, but there’s three caveats.

Firstly if the statically allocated objects are zero-initialised then they can go in the .bss section instead,
which is zeroed out at start-up.

Secondly, function-local static variables are initialised on the first execution of the function, not at program startup.

And thirdly the memcpy analogy/approach doesn’t work for objects that have complex behaviour (or specifically are ‘non-trivial’). For example, an object that calls malloc in its constructor.
Side effects from constructors still have to occur, so this can’t be accounted for with a simple memcpy.
I’m not sure how exactly they get handled, and I can’t find anything to say either way, but I would assume that non-trivial constructors must be called manually at start up before main begins.

You could indeed just call it whenever you felt like it, but you’d still have to chose when to do it very carefully, and keep an eye on how long you’re doing it for.

Another alternative that might work is to implement the system in the equivalent of new,
and to only try to move things when you actually hit fragmentation issues,
and to only attempt to perform a move that would be provably capable of fixing the fragmentation issue.

Memory is pretty fast and there isn’t that much of it. Look at how fast we can send 50% of our memory out over very SLOW SPI. For a platform like AVR “defragmenting” the heap memory just means shifting each allocation downwards to fill in any gaps that have been created. So worse case you’ve moving 1,xxx bytes of RAM or so with memcpy. You could probably do it every frame with no real consequences.

I’ve never measured the speed of RAM copying, so it might not be too bad,
but don’t forget everything else that goes on in an update loop,
it could still be enough to cause noticable lag.

I still think it would be better to try to move the minimum number of objects required to fit the new object in rather than trying to move everything at once.

In which case the remaining issue is how the ‘smart pointer’ would actually cope with the unerlying raw pointer being moved.

It’s plenty fast, just do the math on the back of your hand in clock cycles if you really want an idea.

You could have pointers to pointers, or you could just keep very specific track of a FEW things you allocate in the heap and make sure you pass those pointers to the defrag code.

If defined as:

LD r1, X+ ; 2c
ST Y+, r1 ; 2c
CP X, r2 ; 1c
BRLO loop ; 2c (jump) or 1c (no jump)

Then (7 * sizeof(object)) - 1, so about 699 cycles for a 100 byte object, or 7167 cycles for a full KB

But, that’s just the speed of the copy,
that’s not accounting for the overhead of any additional calculations.

And of course, I’m completely guessing how the copy would actually be implemented, there might be additional overhead for various reasons.

You can’t, because then you need to allocate the pointers to pointers, which then makes them a target for relocation.

You could do it if you could mark them as ‘pinned’ so they can’t be moved,
but then you’d defeat the point because you could end up with fragmentation between the pinned pointers.

I’m not sure what this means.

Now I think about it, there are other cases that would break too.

For example, this would break if an instance of Example were relocated:

class Example
	Example * self;

		this->self = this;

So you’d have to be careful not to allocate anything that uses raw pointers.

So far the only possible implementation I can think of is to have a kind of translation table that translates integer handles (stored in the ‘smart pointers’) to actual pointers to heap memory blocks.

But then you run into the problem of where to store that table and how to resize it.

No, only pointers to DYNAMIC allocations need to be moved.

Either manually have a list of a few variables or have an array of pointers… and only those can be defragged, etc.