7

I have to track a large amount of data (for an Arduino) in a program while taking care of a fair amount of other business.

I started with a struct like this:

struct MyStruct
{
   // note: these names might as well be foo bar baz
   uint8_t color; 
   boolean state; 
   uint8_t area;
   uint8_t number;
   uint8_t len;
};

I have an array of 800 of these. At 5 bytes each, that's 4Kb, or half the ram on the Arduino Mega.

I changed to a struct like this:

struct MyStruct
{
   uint8_t color : 3; // max value 7
   // uint8_t state : 1; *** moved, thanks Ignacio ***
   uint8_t area : 5; // m.v. 31
   uint8_t number;
   uint8_t len : 5; // m.v. 31
   uint8_t state : 1; // m.v. 1
};

I understand this reduces the size of each instance to 3 bytes, for a total of 2.4Kb in my array.

I have read that in some implementations / chipsets using bit fields in structs can lead to less efficient execution. Obviously this is a more efficient use of memory, but my question is:

How does the Arduino handle bit fields? Will it be better, worse, or negligibly different in terms or speed when iterating through an array of bit field structs? Is there a good way to test this?

6
  • 3
    That order will use 4 bytes. Get that 1-bit field out from between the other 8. Oct 1 '14 at 0:33
  • 1
    @Ignacio Amazing... you just shaved another 9% off my total memory usage.
    – anthropomo
    Oct 1 '14 at 0:43
  • The reason bit fields in structs can lead to less efficient execution is because of word alignment restrictions. E.g. if they cross the natural 32/64 alignment, causing multiple accesses. This should not be a problem for the ATmega
    – Milliways
    Oct 1 '14 at 7:39
  • 1
    The question you need to ask yourself is if you are most worried about running out of RAM, program memory, or CPU cycles - this is a situation where you can optimize quite a bit for one at cost of another and some impact on the third. At a certain point you should also ask if an ATmega-based Arduino is really the right platform. Oct 1 '14 at 14:35
  • I was able to restructure the program to use the array index where I was using the 8 bit number, so down to 2 bytes per struct, another 9% shaved. It looks like I can spare the cycles. I iterate through the 800 structs every 50 milliseconds while also handling intermittent http requests. No problems. I've been pushing the ATmega limits with this one, but I seem to be coming in well under.
    – anthropomo
    Oct 1 '14 at 15:28
8

What you are facing is the classic time-memory tradeoff. The bit fields will be smaller in memory, but will take more time to operate on. You can count that no matter what processor, the bit fields will be slower.

You use the word efficient, but that word has no certain meaning without a metric for what is good or bad. When you only have 8 k of RAM, using memory is bad, time may be cheap. If you have real time constraints, then using time is bad and memory may be cheap. In general, you can only buy your way out of this tradeoff. In other words, when you find both time and memory bad, spend cash and use a bigger chip. There is no single answer for what is good or bad. This is part of why there are so many choices for microcontrollers, people fit the chip to the application and application to the chip.

Populating the bits of a bit field will be slower than filling of complete bytes. Take for example

x = 5;
...
asimplestruct.len = x;
// vs
abitfield.len = x;

The first simple case will just:

  • load value of x to a register
  • store it to the byte for len

The second does something like:

  • loads the current value of abitfield
  • loads a mask
  • clears the bits for len
  • loads current value of x
  • loads a mask
  • clears off unused bits of x
  • shifts the bits of x
  • or's x with the abitfield
  • stores the current value back to memory

If all your operations are packing data into the bit field, or unpacking out of the bitfield, you should expect slower execution. Bit fields are a type of compression - they cost ticks.

But moving around bit fields will be faster because there are less bytes to load and store. If you where sorting this array, the smaller byte count could be an advantage. If you where transferring them over a serial port, the compressed size of the bitfield might be a winner.

So with respect to your question:

Is there a good way to test this?

The only good way to test this is to write test cases for both approaches using a pattern that closely matches your application. It really matters what mix of operations you perform to decide whether the difference is negligible or significant.

When doing this sort of optimization experiment, definitely use source control on your project. You can create a local GIT or Mercurial repository with just a few clicks. Keeping a chain of checkpoints allows you to tear up your code exploring the effects of different implementations. If you take a wrong turn, the repository allows you to simply go back to the last good point and try another path.

(Side note: This time memory tradeoff exists in the opposite direction also. If you look through the compiler options for desktop class processors, you will find something called structure packing. This option allow you to add blank bytes between single byte fields such that they stay aligned at word or double word boundaries. This may seem crazy to throw away RAM on purpose, but on processors with 16 or 32 bit wide registers and buses, so called word or dword aligned memory operations can be faster than byte wise operations.)

3

A discussion of bit-fields wouldn't be complete without mentioning that:

Structures with bit-fields may be used as a portable way of attempting to reduce the storage required for a structure (with the probable cost of increasing the instruction space, and time, needed to access the fields), or as a non-portable way to describe a storage layout known at the bit level.

[Kernighan & Ritchie, The C Programming Language, Second Edition, Appendix A-8.3]

Other posters, including yourself, have addressed the space/time tradeoff. But what is sometimes missed (possibly not relevant to your application - ?) is the complete implementation-dependence of the storage layout. This matters when applications share this data with another process: Reading or writing hardware, whose register bit-assignments are necessarily fixed; communicating the data to another system (via network or storage device doesn't matter); or to another application on the same system, that may have been compiled with a different compiler or version of the compiler.

1

A little tip - I see that the struct is not a 1B aligned for 8bit CPU. At the end of your struct you can add padding 2bit length or rethink increase of the size of state.

struct MyStruct
{
   uint8_t color : 3; // max value 7
   // uint8_t state : 1; *** moved, thanks Ignacio ***
   uint8_t area : 5; // m.v. 31
   uint8_t number;
   uint8_t len : 5; // m.v. 31
   uint8_t state : 1; // m.v. 1
   uint8_t padding : 2;
};
2
  • Adding the padding does not change the dynamic memory at compile time. Forgive my ignorance here, but it seems like the compiler takes care of the padding. Or is something happening at runtime to compensate if I don't include the padding?
    – anthropomo
    Oct 1 '14 at 13:01
  • That's true. In this case is more like a good practice.
    – soerium
    Oct 1 '14 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.