For support of a game map, I'm creating a struct which contains an array of objects, its size, and the capacity.

(This is just the code I'm using, if you need to see it.)

struct s_bound
{
   short left,right,top,bottom;
   short btile;
};


struct s_bound_array
{
   unsigned int size;     // Number of items actually used
   unsigned int capacity; // Number of (pre)allocated items
   s_bound* array;        // Array of s_bound objects itself
};

I'm going to add a new function to preallocate the memory. But my question is, should I allocate just the amount specified by the user (in this case, the map itself indicates the number of objects it needs to read in from a file), or should I bump up that amount to the next-power-of-two for data alignment?

Say that the map has stored 129 objects. Calling the add_bound_item() 129 times will need to reallocate the memory about 8 times, and result in a total capacity of 256. If I preallocate the memory at the beginning, though, I only allocate memory once.

Now, do I allocate 129 or 256 objects (the next-power-of-two)? I have to also consider that the game's script (Lua files) may add/remove any of these bounds as well: if I have capacity set to exactly 129, and add one more to it, the add_bound_item() function above states that the capacity should double, giving 258 (not 256). Not a power-of-two boundary.

Suggestions?

Are you worried about using too much memory or you're worried about performance side effects? (caching, paging etc.) I'd say allocate by multiples of 4096 and call it a day.

[EDIT]

That's if you allocated the start of the block on a 4096 byte boundary.

Alright, I would've thought most STL implementations would act a bit more intelligently, but I stand corrected. Principle stays the same, albeit implementation changes: look at Java's ArrayList.

What Oscar said.
If you are in a situation where you know exactly how many elements you are going to store, just allocate enough space to accommodate them, and nothing more.
For dynamic allocation, as provided by std::vector, the most efficient strategy is to double the size whenever the capacity is exceeded. You still don't have to use a power-of-two size, and in fact, a std::vector that is initialized to have a capacity of, say, 3 elements, will probably resize to 6, 12, 24, 48, and so on.

To take care of alignment, you (or the compiler) should make sure individual elements have a size that is a multiple of the platform's native register size, i.e. 4 bytes for 32-bit systems and 8 bytes for 64-bit ones. Chances are your compiler does this automatically for you, depending on compiler options and #pragma directives.

Allocating to the next power of two, or doubling the size, does save some time and new/realloc calls. But the actual size doesn't really matter.

It's generally best if you manually sort the largest items to smallest items in a struct. If you put the char stuff[3] first, then there'll be padding before the next member.

Well, I'll be damned, it used to make a difference! I'll try again once I sober up.

Arthur: Rearrange that a bit to see:

Result:

  Size of s_bound 1 is 20
  Size of s_bound 2 is 24

When I look at Wikipedia and do a test run on my Mac (32-bit, I believe), this is what I see:

#include <stdio.h>

struct s_bound
{
  short left, right, top, bottom;
  short btile;
} s_bound1;

int main(void)
{
  printf("Size of s_bound 1 is %d\n",sizeof(s_bound1));
  return 0;
}

Output:

  Size of s_bound 1 is 10

But will this be the case for 64-bit platforms, or even DIFFERENT 32-bit platforms?

EDIT: Did you rearrange that after you posted? I thought your original had identical structures..?

He did, I saw the structures identical and didn't understand what was Arthur's point.

Not really. Shorts are aligned to 2 byte boundaries, and chars to 1 byte boundaries (so not really alligned ).

So

struct s_bound
  {
    char align[5]; 
    short shorty;
    long longy;
    double dubble;
  }s_bound1;

is going to be alligned like this:

        1           2            3            4
00   align[0]  |  align[1]  |  align[2]  |  align[3]
04   align[4]  |  padding   |          shorty
08                        longy
12                        dubble
16                        dubble

(that's 20 bytes)

while

struct s_bound_two
 {
   short shorty;
   long longy;
   double dubble;
   char align[5]; 
 }s_bound2;

will be alligned this way:

        1           2            3            4
00          shorty         | ------ padding -------
04                       longy
08                       dubble
12                       dubble
16  align[0]  |  align[1]  |  align[2]  |  align[3]
20  align[4]  |  ------------ padding -------------

(that's 24 bytes)

This in a 32 bit system.

[edit]
Arthur : can you try this one:

struct s_bound
  {
    char align[5]; 
    short shorty;
    double dubble;
    long longy;
  }s_bound1;

Doubles may be 8 byte alligned, so in the first case you'd get 24 bytes instead of 20.

Maybe in an array. In structs things are generally aligned to the native "word" size. So two single chars would be aligned and padded to separate "words". x86 does work with unaligned accesses, but last I heard, it is slower than unaligned accesses, so you generally want it to align, even if it can waste 3 or 7 bytes per char.

Not the only problem. Accessing even a char unaligned may take some extra operations.

Thomas: what you don't want is having a variable spawning over several "lines" of memory, because that'd mean that for reading 1 variable you'd need 2 memory accesses.

This is what you don't want:

@    00   01   02   03   04   05   06   07
             |       looong      |

While accessing looong in the x86 is possible (other cpu's don't allow it), it requires 2 accesses (one for retrieving the first word, 00-03, and another to retrieve the second word, 04-07, and then joining the correct bytes). So there's a big performance hit, thus why the alignment.

If you have this:

@    00   01   02   03
      sshort | sshort  |

is ok, and nice since you can read both shorts with just one memory access (after loading you'll need to separate them in 2 different registers, but that's a very fast operation, compared to having 2 memory accesses if you aligned the shorts to word boundaries).

So, google a bit about this. You'll find it's as I said.