Any way to “factor out” common fields to save space?

  • A+
Category:Languages

I have a large array (> millions) of Items, where each Item has the form:

struct Item { void *a; size_t b; }; 

There are a handful of distinct a fields—meaning there are many items with the same a field.

I would like to "factor" this information out to save about 50% memory usage.

However, the trouble is that these Items have a significant ordering, and that may change over time. Therefore, I can't just go ahead make a separate Item[] for each distinct a, because that will lose the relative ordering of the items with respect to each other.

On the other hand, if I store the orderings of all the items in a size_t index; field, then I lose any memory savings from the removal of the void *a; field.

So is there a way for me to actually save memory here, or no?

(Note: I can already think of e.g. using an unsigned char for a to index into a small array, but I'm wondering if there's a better way. That one will require me to either use unaligned memory or to split every Item[] into two, which isn't great for memory locality, so I'd prefer something else.)


(Note: I can already think of e.g. using an unsigned char for a to index into a small array, but I'm wondering if there's a better way.)

This thinking is on the right track, but it's not that simple, since you will run into some nasty alignment/padding issues that will negate your memory gains.

At that point, when you start trying to scratch the last few bytes of a structure like this, you will probably want to use bit fields.

#define A_INDEX_BITS 3 struct Item {    size_t a_index : A_INDEX_BITS;    size_t b       : (sizeof(size_t) * CHAR_BIT) - A_INDEX_BITS;  }; 

Note that this will limit how many bits are available for b, but on modern platforms, where sizeof(size_t) is 8, stripping 3-4 bits from it is rarely an issue.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: