Scheduled Maintenance: We are aware of an issue with Google, AOL, and Yahoo services as email providers which are blocking new registrations. We are trying to fix the issue and we have several internal and external support tickets in process to resolve the issue. Please see: viewtopic.php?t=158230

 

 

 

Do I need to align my short ints?

Programming languages, Coding, Executables, Package Creation, and Scripting.
Post Reply
Message
Author
Caitlin
Posts: 329
Joined: 2012-05-24 07:32
Has thanked: 3 times
Been thanked: 2 times

Do I need to align my short ints?

#1 Post by Caitlin »

I have some structures that have short ints in them. These short ints are "aligned" meaning a multiple of sizeof(short int) from the beginning of the structure. But to save storage, I want to malloc() a "hunk" of storage and chop it up with as few slack bytes in between as possible. There is no free function, so there is no need to keep track of each area and their length. Example:

Code: Select all

+----------+------------------------------------------------------------------+
|  area 1  |                       free area                                  |
+----------+------------------------------------------------------------------+

+-----------+----------+------------------------------------------------------+
|  area 1   |  area 2  |                  free area                           |
+-----------+----------+------------------------------------------------------+

+-----------+----------+----------+-------------------------------------------+
|  area 1   |  area 2  |  area 3  |            free area                      |
+-----------+----------+----------+-------------------------------------------+
However, if an area does NOT end at an address that is a multiple of sizeof(short int), the following area will not be aligned, and a short int that the compiler thinks is aligned won't be.

My questions:
Should I skip a few bytes between areas so the NEXT area is aligned? How should I align it; to a multiple of 2 bytes or 4 bytes or what? I want these structures to be accessed efficiently over a wide range of processors to keep it portable. How about pointers? Should they be aligned to (sizeof)whatever*? Or perhaps (sizeof)whatever* / 2 ?

Background information:
As my program initializes, it needs to allocate a large number of areas. They are never freed until none of them are needed any more, at which point they are ALL freed in mass. I've been using malloc() for each individual area up to now, but malloc() leaves big holes in the allocated storage and adds extra bytes for storage accounting (for use by free) but if I don't need that flexibility, I just want to jam the areas right up next to each other. I am aware that various processors handle unaligned variables differently, but as I said, I want it to run efficiently with a wide assortment of processors.

Caitlin

reinob
Posts: 1189
Joined: 2014-06-30 11:42
Has thanked: 97 times
Been thanked: 47 times

Re: Do I need to align my short ints?

#2 Post by reinob »

I'm afraid that if you want to really ensure portability your only option would be to use a struct/union containing the short int, and, at compile time, use that as your "chunk size" each time you allocate a chunk in your data structure.

Something like:

Code: Select all

/* here you include every possible type of element you want in your array */
union atom_t {
	short int a;
	void *p;
}

typedef struct array_element {
	union atom_t e;
}
such that sizeof(array_element) will be 2, 4, 8, or whatever, i.e. the (possibly padded) size you'd need to allocate for each element, regardless of the type (within those included in the union "atom_t" structure).

If you really force the size to the actual content (like 1 byte for char, 2 for short int, or whatever) you risk having misaligned access, which can cause slowdown, MMU exceptions (old ARM chips), and generally unpredictable behaviour (like the processor rounding the address for you, so you get different data than what you intended..)

Caitlin
Posts: 329
Joined: 2012-05-24 07:32
Has thanked: 3 times
Been thanked: 2 times

Re: Do I need to align my short ints?

#3 Post by Caitlin »

Dear reinob,

Perhaps an example is in order. The most common structure is:

Code: Select all

struct ELEMENT                                                              /* 328 */
   {struct ELEMENT* chain1;               /* chain of all tasks (excluding bogus)  */
    struct ELEMENT* chain2;               /* tasks that are part of this project   */
    struct ELEMENT* chain3;               /* tasks with due dates in order by same */
    struct WHEN due;                                          /* due date and time */
    char status;                       /* per the status table just before alttask */
    char priority[2];                                /* 1 (highest) to 99 (lowest) */
    char tasktype;                                    /* A through Z; user-defined */
    char tasknum[4];                    /* four-digit task number assigned by MTMS */
    char stepnum;           /* blank or a step number ('a' through 'i' in the tqe) */
    char descript[2];};     /* 2 to 501 bytes (null-terminated description string) */
(WHEN consists of two unsigned short ints.)

Not only are the different structs different in length, the last field shown above -- descript -- is from 2 to 501 bytes -- making it inadvisable to allocate each one based on the maximum possible size. I can allocate exactly as much storage as I need, then skip over a few bytes if necessary until I get to an address that is a multiple of (the size of a pointer, long int, or short int, whichever is greatest) bytes for the next area. I think this is what I will do.

You can see that the fields that might need alignment are those in the front of the structure; there's no way for a field to be misaligned if the struct begins aligned, with the possible exception if a long int is bigger than a pointer (but I don't think there is any environment where this is so).

Thank you.

Caitlin

LE_746F6D617A7A69
Posts: 932
Joined: 2020-05-03 14:16
Has thanked: 7 times
Been thanked: 65 times

Re: Do I need to align my short ints?

#4 Post by LE_746F6D617A7A69 »

Caitlin wrote: 2022-10-10 05:26 These short ints are "aligned" meaning a multiple of sizeof(short int) from the beginning of the structure.
First of all, good code shouldn't use types like int, short int, long int, long long and even very long int ;)
I know that even today, various documents are recommending this naming convention, but this is totally wrong and harmful.
The famous crash of Arianne5 has been caused exactly because some idiot used int in the program.
"int" type is non-portable because it has undefined size (it can be from 1 to 8 bytes)
Reliable code have to be explicit about type sizes, i.e. by using types like int16_t, int32_t etc.

Alignment of data structures is a very complex topic, but the most important thing is whether You're going to use "packed" structures, which are manually aligned and thus fully controlled by the programmer OR You want to let the compiler to align the data fields. Both approaches have pros and cons, mainly it's a trade of speed vs memory consumption.
Caitlin wrote: 2022-10-10 05:26 Should I skip a few bytes between areas so the NEXT area is aligned? How should I align it; to a multiple of 2 bytes or 4 bytes or what?
None of the above, most/all the architectures today are optimized for 8 or 16 bytes alignment (data cache line sizes, dual-channel memory controllers)
Caitlin wrote: 2022-10-10 05:26 As my program initializes, it needs to allocate a large number of areas. They are never freed until none of them are needed any more, at which point they are ALL freed in mass.
In such case You should consider using the stack for storing data structures - such solution allows to bypass all the "limitations" imposed by malloc(), and it is much, much faster.

Regards
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed

Caitlin
Posts: 329
Joined: 2012-05-24 07:32
Has thanked: 3 times
Been thanked: 2 times

Re: Do I need to align my short ints?

#5 Post by Caitlin »

Dear tomazzi,

I like the idea of "_t" data types -- I was never really comfortable with the "native to the system you're running on" idea.

c38189a3938995

LE_746F6D617A7A69
Posts: 932
Joined: 2020-05-03 14:16
Has thanked: 7 times
Been thanked: 65 times

Re: Do I need to align my short ints?

#6 Post by LE_746F6D617A7A69 »

Caitlin wrote: 2022-10-11 07:31 c38189a3938995
Nice ;)
Obviously, it's not ASCII, UTF8 or CP1250 - what encoding You're using?
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed

Caitlin
Posts: 329
Joined: 2012-05-24 07:32
Has thanked: 3 times
Been thanked: 2 times

Re: Do I need to align my short ints?

#7 Post by Caitlin »

Ready for this -- it's EBCDIC!!

Caitlin

schmuessla
Posts: 3
Joined: 2022-10-11 17:23
Has thanked: 1 time
Been thanked: 1 time

Re: Do I need to align my short ints?

#8 Post by schmuessla »

LE_746F6D617A7A69 wrote: 2022-10-10 20:43 None of the above, most/all the architectures today are optimized for 8 or 16 bytes alignment (data cache line sizes, dual-channel memory controllers)
Well for that particular use case (doing allocation manually to use memory as efficient as possible) the answer is:
'to the result of alignof/_Alignof operator'.
At least If you have a C11 compliant compiler.

There can be types which have stricter alignment requirements (e.g. types used for SIMD instructions or special hardware buffers like DMA), but alignof returns the value the compiler would pick.

LE_746F6D617A7A69
Posts: 932
Joined: 2020-05-03 14:16
Has thanked: 7 times
Been thanked: 65 times

Re: Do I need to align my short ints?

#9 Post by LE_746F6D617A7A69 »

Caitlin wrote: 2022-10-12 13:42 Ready for this -- it's EBCDIC!!

Code: Select all

c3 81 89 a3 93 89 95
C  a  i  t  l  i  n
;)
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed

reinob
Posts: 1189
Joined: 2014-06-30 11:42
Has thanked: 97 times
Been thanked: 47 times

Re: Do I need to align my short ints?

#10 Post by reinob »

Caitlin wrote: 2022-10-10 17:30 Dear reinob,

Perhaps an example is in order. The most common structure is:

Code: Select all

struct ELEMENT                                                              /* 328 */
   {struct ELEMENT* chain1;               /* chain of all tasks (excluding bogus)  */
    struct ELEMENT* chain2;               /* tasks that are part of this project   */
    struct ELEMENT* chain3;               /* tasks with due dates in order by same */
    struct WHEN due;                                          /* due date and time */
    char status;                       /* per the status table just before alttask */
    char priority[2];                                /* 1 (highest) to 99 (lowest) */
    char tasktype;                                    /* A through Z; user-defined */
    char tasknum[4];                    /* four-digit task number assigned by MTMS */
    char stepnum;           /* blank or a step number ('a' through 'i' in the tqe) */
    char descript[2];};     /* 2 to 501 bytes (null-terminated description string) */
(WHEN consists of two unsigned short ints.)

Not only are the different structs different in length, the last field shown above -- descript -- is from 2 to 501 bytes -- making it inadvisable to allocate each one based on the maximum possible size. I can allocate exactly as much storage as I need, then skip over a few bytes if necessary until I get to an address that is a multiple of (the size of a pointer, long int, or short int, whichever is greatest) bytes for the next area. I think this is what I will do.

You can see that the fields that might need alignment are those in the front of the structure; there's no way for a field to be misaligned if the struct begins aligned, with the possible exception if a long int is bigger than a pointer (but I don't think there is any environment where this is so).

Thank you.

Caitlin
In your case I'd do the same, i.e. once you have decided the size you actually need, just pad it to the next size divisible by 4 (or 8, or even 16).

In general I dislike variable-length fields (like your descript) within a struct. I find it slightly inelegant :), so in your case I would make descript a pointer to a string (char []) allocated specifically for that. It does add a level of indirection (and you have to be careful when free()'ing, etc.), but it would make your main struct fixed size (i.e. containing only atomic types or fixed-size struct's).

Good luck.

LE_746F6D617A7A69
Posts: 932
Joined: 2020-05-03 14:16
Has thanked: 7 times
Been thanked: 65 times

Re: Do I need to align my short ints?

#11 Post by LE_746F6D617A7A69 »

reinob wrote: 2022-10-14 20:12 once you have decided the size you actually need, just pad it to the next size divisible by 4 (or 8, or even 16)
It's not that simple - actually, a good data structure needs to be constructed with "access cost" in mind - that is, the most frequently accessed data fields should be optimized for "fast access" (that is, properly aligned and close to each other - (data locality)), while other data fields may be "packed" to save the memory.

Regards
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed

reinob
Posts: 1189
Joined: 2014-06-30 11:42
Has thanked: 97 times
Been thanked: 47 times

Re: Do I need to align my short ints?

#12 Post by reinob »

LE_746F6D617A7A69 wrote: 2022-10-15 20:17
reinob wrote: 2022-10-14 20:12 once you have decided the size you actually need, just pad it to the next size divisible by 4 (or 8, or even 16)
It's not that simple - actually, a good data structure needs to be constructed with "access cost" in mind - that is, the most frequently accessed data fields should be optimized for "fast access" (that is, properly aligned and close to each other - (data locality)), while other data fields may be "packed" to save the memory.
Yes. But the first issue is to make the thing work (portably) at all, and for that you'd need some sort of alignment that works with all/most processors.

For efficiency/locality/etc. it all depends on what exactly the OP is doing, such as how big the structures are, etc. Maybe it makes more sense to pack subsets (with the constant-sized stuff) of the struct's together and put the variable-length parts somewhere else, etc.

Caitlin
Posts: 329
Joined: 2012-05-24 07:32
Has thanked: 3 times
Been thanked: 2 times

Re: Do I need to align my short ints?

#13 Post by Caitlin »

reinob wrote: 2022-10-14 20:12
Caitlin wrote: 2022-10-10 17:30 Dear reinob,

Perhaps an example is in order. The most common structure is:

Code: Select all

struct ELEMENT                                                              /* 328 */
   {struct ELEMENT* chain1;               /* chain of all tasks (excluding bogus)  */
    struct ELEMENT* chain2;               /* tasks that are part of this project   */
    struct ELEMENT* chain3;               /* tasks with due dates in order by same */
    struct WHEN due;                                          /* due date and time */
    char status;                       /* per the status table just before alttask */
    char priority[2];                                /* 1 (highest) to 99 (lowest) */
    char tasktype;                                    /* A through Z; user-defined */
    char tasknum[4];                    /* four-digit task number assigned by MTMS */
    char stepnum;           /* blank or a step number ('a' through 'i' in the tqe) */
    char descript[2];};     /* 2 to 501 bytes (null-terminated description string) */
(WHEN consists of two unsigned short ints.)

Not only are the different structs different in length, the last field shown above -- descript -- is from 2 to 501 bytes -- making it inadvisable to allocate each one based on the maximum possible size. I can allocate exactly as much storage as I need, then skip over a few bytes if necessary until I get to an address that is a multiple of (the size of a pointer, long int, or short int, whichever is greatest) bytes for the next area. I think this is what I will do.

You can see that the fields that might need alignment are those in the front of the structure; there's no way for a field to be misaligned if the struct begins aligned, with the possible exception if a long int is bigger than a pointer (but I don't think there is any environment where this is so).

Thank you.

Caitlin
In your case I'd do the same, i.e. once you have decided the size you actually need, just pad it to the next size divisible by 4 (or 8, or even 16).

In general I dislike variable-length fields (like your descript) within a struct. I find it slightly inelegant :), so in your case I would make descript a pointer to a string (char []) allocated specifically for that. It does add a level of indirection (and you have to be careful when free()'ing, etc.), but it would make your main struct fixed size (i.e. containing only atomic types or fixed-size struct's).

Good luck.
I've decided to make each structure begin at a multiple of max(sizeof(void*), sizeof(long int)).

Thank you.

Caitlin

Post Reply