I need advice on how to store sequencer events in memory

I am making yet another step sequencer. I ran into the wall of dynamic memory size of arduino uno.
The simplest and best way to define an array to store the sequencer; if it was a 16 step sequencer, would be:

byte sequence [16][3];

being the first dimension time, and the second would be for the three parts of a standard midi message.
but such a sequencer would only allow one event per step. there would be no place for poliphony or composition along many channels, or cc events. Therefore, we need a polyphony dimension.

byte sequence [4][16][3];

and 16 steps is not a decent amount of steps. We will often want longer sequences, and more precise timing than just, say, four steps per beat. so…

byte sequence [4][64][3];

that is already 960 bytes in size, and it gets really hard to fit any other interesting code for interface, etc. But also this approach is not the most efficient: while it’s true that access is very straightforward, most of the time, the greeater majority of these allocated memory slots will be empty.

following that, I tried an array that stacks events with a time stamp. When an event is recorded, it goes into next available array slot, with the beat where it should play.
example:

sequence[0]={/*on step*/3,/*play this midi event*/,0x92,0xCC,0xFA}

Problem with this is that it takes too long to iterate through. Iterating only 16 slots, each 64 repetitions of the loop, take enough time to break the interaction experience. It would be nice for instance, that the program knew a range within which to iterate, but I don’t know how to do that in simple terms, because the events programming order is not guaranteed to be in the same order as they should be played in the sequencer. There would be some kind of defragmentation process involved.

So now I feel out of ideas, and I need the help of more experienced programmers on better ways to do this. Hopefully it doesn’t involve hardware changes.

*edited

Did you consider to use PROGMEM?

https://www.arduino.cc/en/Reference/PROGMEM

Joaquin: following that, I tried an array that stacks events with a time stamp. When an event is recorded, it goes into next available array slot, with the beat where it should play. example:

sequence[0]={/*on step*/3,/*play this midi event*/,0x92,0xCC,0xFA}

Insert new events in play order. It's fairly quick and easy to move the later events down an index to make room for a new event. To delete and event, move the subsequent events back an index.

johnwasser: Insert new events in play order. It's fairly quick and easy to move the later events down an index to make room for a new event. To delete and event, move the subsequent events back an index.

Thanks for that idea; Johnwasser worth trying indeed. Is the way to move events one an index, one by one iteration, or is there a better way I an unaware of?

omersiar: Did you consider to use PROGMEM?

https://www.arduino.cc/en/Reference/PROGMEM

Thanks for the pointer, Omersiar. I used progmem to eliminate a lot of overhead in other areas of my firmware. The problem of using PROGMEM for the sequence events, is that I need to modify them at runtime, while PROGMEM is used for variables that will remain static. You may correct me if I am wrong.

Joaquin: Thanks for that idea; Johnwasser worth trying indeed. Is the way to move events one an index, one by one iteration, or is there a better way I an unaware of?

There is a way to move everything as a block of memory with memmove() if you do the math right. http://www.cplusplus.com/reference/cstring/memmove/

// Insert 'value' into index 'i' of array:
    if (entries > i) {
         memmove(&array[i], &array[i+1], (entries-i)*sizeof array[0]); // Move subsequent entries down
    }
    memcpy(&value, &array[i], sizeof array[0]);
    entries++;

johnwasser: There is a way to move everything as a block of memory with memmove() if you do the math right. http://www.cplusplus.com/reference/cstring/memmove/

// Insert 'value' into index 'i' of array:
    if (entries > i) {
         memmove(&array[i], &array[i+1], (entries-i)*sizeof array[0]); // Move subsequent entries down
    }
    memcpy(&value, &array[i], sizeof array[0]);
    entries++;

That sounds nice and dangerous. I will try it out :) Thanks, Johnwasser