What would be the best way of dynamically 'change' instances regarding dynamic memory?

Question

Since I'm very used to object oriented programming, I would like to use this into my design. My application will have 4 led strips and each led strip will have a 'pattern' running on it. For this I like to create a base class and for each pattern a derived class. So this means I have 4 instances to a pattern. However, the pattern can change dynamically (based on music MIDI input). Each pattern has between 10-16 parameters.

I know dynamic memory allocation is mostly not a good idea in an Arduino. I'm using a Mega which has 8 KB. I found several 'solutions' but neither one I'm sure about. The first is not the solution but the way I should do it when I have 'plenty' of SRAM available (and simplified):

class Pattern
{
   public:
      virtual void Process();
}

class PatternA: Pattern
{
   public:
      void Process();

      // In example I only use 2 out of 10-16 parameters
      uint8_t SetColor(uint8_t colorIndex);
      uint8_t SetSpeed(uint8_t speed);

   private:
      uint8_t _colorIndex;
      uint8_t _speed;
}

// In this example I only use 2 out of 24 patterns
class PatternB: Pattern
(like PatternA but with its own implementation)

class LedStrip
{
   public:
       void SetPattern(Pattern* pattern);

   private:
       Pattern* _pattern;
}

Other derived classes may have other (named) parameters.

When changing instances, I would get something like this:

LedStrip::SetPattern(Pattern* pattern)
{
    delete _pattern;
    _pattern = pattern;
}

pattern* pattern = new PatternA(...);
ledStrip1.SetPattern(pattern);

However, since the new pattern may use more memory then the deleted pattern, there will be a memory gap. So this is not suitable for the Arduino to be used I assume.

Solutions:

1. Create all possible patterns beforehand.

Assume I would implement 24 patterns, and create any possible combination, I would have 4 (led strips) * 24 (patterns) * 13.5 (average number of parameters) = 1,296 bytes. This seems a bit much as only 4 are 'active'.

class LedStrip
{
   public: 
      enum EPattern {A, B}

      void SetPattern(EPattern pattern);

   private:
      PatternA* _patternA;
      PatternB* _patternB;

      Pattern* _pattern;
}

To change pattern:

void LedStrip::SetPattern(EPatternpattern)
{
case EPatternA: _pattern = _patternA; break;
case EPatternB: _pattern = _patternB; break;
}


ledStrip1.SetPattern(EPattern::A);

Of course I could also pass a pattern where the patterns are created globally but this is does not matter for this example. The idea is to create 4 (led strips) * 24 (patterns) instances beforehand and never use delete. This means out of the 4 * 24 patterns, only 4 are used, 1 per led strip.

Of course this causes a lot of unused memory.

2. New/Delete

I create the 4 correct derived instances and when one pattern (instance) change, I delete the instance and create the new. When I put no (instance) variables in the derived class, this could work, but I have some specific questions regarding this solution:

I make sure all the max. parameters are in the base class and I 'cast' 4 instances of the base class to a derived class. This seems a bit of 'tricky' solution.

class Pattern
{
   public:
      SetParameter(uint8_t parameter, uint8_t parameterValue);
      uint8_t parameter GetParameter(uint8_t parameter);

   private:
      uint8_t _parameters[16];
}

class PatternA: Pattern
... (does not have any variables)

To change pattern:

delete ledStrip1.pattern;
ledStrip1.pattern = new PatternA();

Question: can I assume the deleted memory of the old pattern will be replaced by the new pattern as the memory usage is equal?

The downside of this way is that each pattern will have the worst-case amount of parameters in each instance, but this is not a problem (I only have 4 led strips).

Answer 1

I don't know what you'll make of this, but:

If you can set aside a properly aligned and sufficiently large memory block you can use the placement form of the new operator.

Placement new is essentially new without the the part that behaves like (and typically is) malloc. Or put differently, it lets you construct an object inside of already allocated memory. By "already allocated" I don't mean already allocated on the heap; the memory can come from whereever you want. This more or less lets you make your own custom allocator with predictable behaviour that you don't get from generic heap allocator like malloc.

So you can set aside memory however you want. It can be an array of unsigned char in static storage duration (global, static local, static member). And placement new can put an object into it, or importantly, into part of it. Basically you're making your own arena for your allocator.

It's up to you to align the memory correctly. There are compiler keywords that can help with that. You can also resort to an older technique oversizing the block just large enough so that a properly aligned sub-block exists and can be found within it. However, on an 8-bit microcontroller like the AVR, there are no alignment requirements to speak of.

When it comes to using delete, well, you don't. You just call the destructor on the object directly. There are ways you could try to clean that up also.

If I become awake enough to completely understand your specific usage, I may try to make an example. But that is the basic technique I'd consider.

---

Regarding avoiding new/malloc: the case against them it is often slightly overstated. For example, doing a set of malloc / new at the beginning, and only the beginning, of your program and not thereafter is normally fairly stable and predictable. For example, you can read a configuration out of eeprom in setup() and use that information to allocate say three "dynamic" "arrays" with malloc, that you know they won't total more than some testable maximum. Maybe a slightly more accurate warning for them is something like: you will get into trouble if you don't have a reasonable understanding of your maximum heap usage and if your usage pattern requires that you free/delete/remalloc.

I mention this in part also because it's not completely unreasonable to malloc/new once, early in your execution, to acquire an arena to use with placement new calls.

Answer 2

Pattern classes are code and variables for the current set of parameters. The code doesn't take SRAM it is executed from flash. I would instance all 24 patterns for all 4 LED strips using global two dimensional array.

Advanced version could be a pool of pattern instances allocated with 'new' but never deleted, only reused. You would only create a new pattern class instance of requested type, if there is no free pattern instance of that type in the pool.

The parameters sets could be stored in PROGMEM or in EEPROM and loaded as needed into the variables of the corresponding pattern class instance.

Answer 3

When I need dynamically allocate memory, I generally pre-allocate a pool of memory blocks, each sufficiently large for the maximum size request I'll handle. Then, Whether the app requests 1 byte or MAXSIZE bytes, it gets a pointer to the first available one of those MAXSIZE blocks in the pool. free()ing such a block works just as you'd expect. Since all allocations are the same size, and no more memory is ever taken from the real heap, the pool doesn't have to (and can't, in my implementation) grow.

If this is the only dynamically allocated memory for your application, you can re-write new() and delete() to use your pool-allocator, or, if new() and delete() are implemented as wrappers around malloc() and free(), just replace those more primitive ones with the pool-based malloc() and free().

Answer 4

Since you only need four objects at any given time, it would be wasteful to statically allocate 4×24 objects, as you only really need four times the size of the largest object. You can still use static allocation by using an array of unions: each cell of the array will then be large enough to store the largest possible pattern.

There may be more elegant solutions, but the simple approach is to use a tagged union, i.e. a struct holding both a union and an extra variable telling you what data type the union is actually holding. Beware that there are limitations on what type of objects you can put in an union. You should be safe if the actual classes have trivial do-nothing constructors.

Below is a simplified example with two classes that each hold only a number, either an uint8_t or a uint16_t:

class Pattern
{
public:
    virtual void process();
};

class Pattern8 : public Pattern
{
public:
    void process() { Serial.println(8000 + param); }
    void set_param(uint8_t param8) { param = param8; }
private:
    uint8_t param;
};

class Pattern16 : public Pattern
{
public:
    void process() { Serial.println(16000 + param); }
    void set_param(uint8_t param16) { param = param16; }
private:
    uint16_t param;
};

// This is the tagged union.
struct AnyPattern : public Pattern
{
    AnyPattern() {}  // must be explicitly defined
    void process() {
        switch (type) {
            case TYPE8: pattern8.process(); break;
            case TYPE16: pattern16.process(); break;
        }
    }
    enum { TYPE8, TYPE16 } type;
    union {
        Pattern8 pattern8;
        Pattern16 pattern16;
    };
};

void setup() {
    AnyPattern patterns[2];
    patterns[0].type = AnyPattern::TYPE8;
    patterns[0].pattern8.set_param(21);
    patterns[1].type = AnyPattern::TYPE16;
    patterns[1].pattern16.set_param(42);
    Serial.begin(9600);
    patterns[0].process();
    patterns[1].process();
}

void loop(){}