Storing data efficiently in an array

Question

The problem is the following:

I am storing error codes with IDs (e.g. 23,53,12,64...) in an array with a predefined length (e.g. 10).

Now I would like to store some additional bytes to these codes (e.g. **23** (data: 102, 340), **53** (data: 10), **12** (data: 46, 23, 64, 12), **64** (data: 1,2,3)).

The data length is different for almost each error codes.

What is the best way of storing these additional bytes regarding the memory consumption?

My idea is to calculate the maximum memory I need for storing these additional bytes.

If I have 30 error codes and I would like to make it possible to store 10 of them (if they occur), then the maximum memory for storing the additional bytes can be calculated by summing up the number of the additional bytes of those error codes which require the most additional bytes. So when the 10 errors occur, which require the most additional bytes, the array for storing the additional bytes is just enough.

One error code only present once in a time.

When an error occurs, I save the additional bytes into this array and store a "pointer" (which is just an index of this array) to the error code, where the additional bytes start.

But this causes fragmentation if errors occur and I delete errors.

Defragmenting this array would be an overhead for the CPU.

Any ideas? I need to avoid dynamic memory allocating.

You need to allocate enough memory to handle the worst-case scenario and that's it. Allocating less memory than that "sometimes" doesn't make sense. Either your program can handle the worst-case scenario or it can't. — Lundin
30 is a very small number. Don't bother with "memory wasting" unless you really have very little memory on your device. — Jabberwocky
Enough bytes for worst case without wasting memory... sounds like a cat byting its own tail. Please, consider that it is common to distinguish average and worst case. If you must be prepared for worst case then doubts about wasting memory are... a bit useless. You may consider an optimal use of bits. 64 distinct error codes can be stored in 6 bits instead of 8. Using lossless data compression might be more effective but without knowing the exact characteristics of possible data it's impossible to predict the exact/worst compression ratio. — Scheff's Cat
I get into discussions like this a lot with rookie embedded programmers. The bottom line is always that they never actually know what they are "saving" for. A rainy day or some such. "Those bytes might be good to have" isn't common sense. Good for what? — Lundin

kkrambo kkrambo · Accepted Answer · 2018-06-21T17:11:35

It sounds like you have one array to store the error IDs and another array to store the additional bytes for all errors. (And do you have yet another array to store the pointers to the additional bytes for each error?) And your concern is with managing the additional_bytes array and the pointers. Is that right?

Instead of using separate arrays with pointers, store everything in a single array of structs.

First declare a struct that contains all of the information related to an error.

typedef struct ErrorInfo
{
    unsigned int error_id;
    uint8_t additional_data[MAX_ADDITIONAL_BYTES_PER_ERROR];
} ErrorInfo;

Then allocate a single array to store multiple errors.

ErrorInfo errors_array[MAX_NUMBER_OF_ERRORS];

Set an error like this:

errors_array[0].error_id = 23;
errors_array[0].additional_data[0] = 102;
errors_array[0].additional_data[1] = 340;  <--- Note that 340 will overflow a byte!

This should use less memory than your design because you no longer need to record pointers to the additional bytes for each error. This also removes your defragmentation issue because each error's additional bytes have a reserved place in the struct array and you no longer need to manage their location in a separate addition_bytes array.

If you must store all the additional bytes for all errors in a separate array then just use a fixed (permanent) offset for each error. The offset to the additional bytes for error number n is equal to (n - 1) * MAX_ADDITIONAL_BYTES_PER_ERROR. This will leave some empty bytes in the array between errors but it will remove the need to store pointers and manage fragmentation.

Storing data efficiently in an array

2 Answers