Arduino Dynamic Array

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.

image

3 Likes

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.

@Agent6

To give an example of what @Dreamer3 suggested:

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

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

const uint8_t * const frames[] PROGMEM =
{
	sprite0frames,
	sprite1frames,
};

class AnimationData
{
private:
	uint8_t frameCount;
	const uint8_t * frames;

public:
	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:
http://gameprogrammingpatterns.com/contents.html

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.)

True.
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:

loop:
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
{
private:
	Example * self;

public:
	Example(void)
	{
		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.

At some point you have to decide how abstract you need things. I imagined the important part is allocating a FEW objects of various sizes and juggling/resizing them. The pointers themselves don’t really need to be dynamic.

unsigned char *dynamic_ptr[10];

Etc… And you could use some macros to get prettier code vs dynamic_ptr[5] everywhere.

I still have very little idea what you’re thinking.

  • How does the defragger know which heap objects it can and can’t relocate?
  • How does the defragger know where the pointers referencing the heap objects are located?
  • How does the system handle pointers to pointers?

When I was thinking of having pointers to pointers,
I was thinking of the typical implementation of a shared pointer:

Shared Pointer Implementation
template< typename T >
class SharedPointerSentry
{
private:
	using Counter = unsigned int;

private:
	T * pointer;
	Counter useCount;

public:
	SharedPointerSentry(T * pointer, int useCount)
		: pointer(pointer), useCount(useCount)
	{
	}
	
	T * getPointer(void) const
	{
		return this->pointer;
	}
	
	bool isAlive(void) const
	{
		return (this->useCount > 0);
	}
	
	void addReference(void)
	{
		++this->useCount;
	}
	
	void removeReference(void)
	{
		// Error condition
		if(useCount == 0)
			return;
		
		--this->useCount;
		if(useCount == 0)
		{
			delete pointer;
			pointer = nullptr;
		}
	}
};

template< typename T >
class SharedPointer
{
private:
	using Senty = SharedPointerSentry<T>;
	
private:
	Sentry * sentry;
	
public:
	SharedPointer(void) = default;

	SharedPointer(T * pointer)
		: sentry((pointer != nullptr) ? new Sentry(pointer, 1) : nullptr)
	{
	}
	
	SharedPointer(const SharedPointer & other)
		: sentry(other.sentry)
	{
		if(sentry != nullptr)
			sentry->addReference();
	}
	
	~SharedPointer(void)
	{
		if(sentry != nullptr)
		{
			this->sentry->removeReference();
			if(this->sentry->isAlive())
				delete this->sentry;
			this->sentry = nullptr;
		}
	}
	
	T * operator ->(void)
	{
		return (this->sentry != nullptr) ? this->sentry->getPointer() : nullptr;
	}
	
	const T * operator ->(void) const
	{
		return (this->sentry != nullptr) ? this->sentry->getPointer() : nullptr;
	}
	
	T & operator *(void)
	{
		if(this->sentry != nullptr)
			return *(this->sentry->getPointer());
		else
		{
			// Error case
			T * t = nullptr;
			return *t;
		}
	}
	
	const T & operator *(void) const
	{
		if(this->sentry != nullptr)
			return *(this->sentry->getPointer());
		else
		{
			// Error case
			T * t = nullptr;
			return *t;
		}
	}
};
  1. IMHO there wouldn’t be much point (on a small chip) if you didn’t allow EVERY heap object to be moved.
  2. I suggested an array of pointers that could be moved: unsigned char *dynamic_ptr[10];. Though perhaps it’d be void type and you’d recast them as needed.
  3. It wouldn’t. And it wouldn’t need to. In any pointer chain only the FINAL pointer should point to dynamically allocated memory. Anything else is kind of crazy IMHO.

You could have a class like shared pointer keep build on top of an array of dynamic pointers and abstract it further if you wanted. So you could create up to x SharedPointers and it would “just work”.

Oh, in C++ you can override ->, HA, that’s amazing. Didn’t know that.