Here's an idea [LWN.net]

Here's an idea

Posted Dec 10, 2007 7:25 UTC (Mon) by jzbiciak (✭ supporter ✭, #5246)
In reply to: Here's an idea by pr1268
Parent article: Memory access and alignment

Yes. On an architecture with alignment constraints, the "packed[3]" field isn't necessary. The compiler will insert padding. You can check this out with the offsetof() macro.

For example, if I compile the following program on my 64-bit Opteron, you can see the pointers all get aligned to 8 byte boundaries like they're supposed to. If I compile it on a 32 bit machine, they get aligned to 4 byte boundaries. This is regardless of whether that filler field is there.

#include <stdio.h>
#include <stddef.h>

typedef unsigned int uint32_t;

typedef struct obj_1
{
    uint32_t   a, b;
    char       c;
    char       filler[3];
    uint32_t*  p1;
    char**     p2;
    char**     p3;
} obj_1;

typedef struct obj_2
{
    uint32_t   a, b;
    char       c;
    uint32_t*  p1;
    char**     p2;
    char**     p3;
} obj_2;

int main()
{
    printf("offset of obj_1.a:       %5d bytes\n", offsetof(obj_1, a));
    printf("offset of obj_1.b:       %5d bytes\n", offsetof(obj_1, b));
    printf("offset of obj_1.c:       %5d bytes\n", offsetof(obj_1, c));
    printf("offset of obj_1.filler:  %5d bytes\n", offsetof(obj_1, filler));
    printf("offset of obj_1.p1:      %5d bytes\n", offsetof(obj_1, p1));
    printf("offset of obj_1.p2:      %5d bytes\n", offsetof(obj_1, p2));
    printf("offset of obj_1.p3:      %5d bytes\n", offsetof(obj_1, p3));
    putchar('\n');
    printf("offset of obj_2.a:       %5d bytes\n", offsetof(obj_2, a));
    printf("offset of obj_2.b:       %5d bytes\n", offsetof(obj_2, b));
    printf("offset of obj_2.c:       %5d bytes\n", offsetof(obj_2, c));
    printf("offset of obj_2.p1:      %5d bytes\n", offsetof(obj_2, p1));
    printf("offset of obj_2.p2:      %5d bytes\n", offsetof(obj_2, p2));
    printf("offset of obj_2.p3:      %5d bytes\n", offsetof(obj_2, p3));
    putchar('\n');
    printf("sizeof(int)   = %d bytes\n", sizeof(int));
    printf("sizeof(long)  = %d bytes\n", sizeof(long));
    printf("sizeof(void*) = %d bytes\n", sizeof(void*));

    return 0;
}

Output on a 32-bit machine:

offset of obj_1.a:           0 bytes
offset of obj_1.b:           4 bytes
offset of obj_1.c:           8 bytes
offset of obj_1.filler:      9 bytes
offset of obj_1.p1:         12 bytes
offset of obj_1.p2:         16 bytes
offset of obj_1.p3:         20 bytes

offset of obj_2.a:           0 bytes
offset of obj_2.b:           4 bytes
offset of obj_2.c:           8 bytes
offset of obj_2.p1:         12 bytes
offset of obj_2.p2:         16 bytes
offset of obj_2.p3:         20 bytes

sizeof(int)   = 4 bytes
sizeof(long)  = 4 bytes
sizeof(void*) = 4 bytes

Output on a 64-bit machine:

offset of obj_1.a:           0 bytes
offset of obj_1.b:           4 bytes
offset of obj_1.c:           8 bytes
offset of obj_1.filler:      9 bytes
offset of obj_1.p1:         16 bytes
offset of obj_1.p2:         24 bytes
offset of obj_1.p3:         32 bytes

offset of obj_2.a:           0 bytes
offset of obj_2.b:           4 bytes
offset of obj_2.c:           8 bytes
offset of obj_2.p1:         16 bytes
offset of obj_2.p2:         24 bytes
offset of obj_2.p3:         32 bytes

sizeof(int)   = 4 bytes
sizeof(long)  = 8 bytes
sizeof(void*) = 8 bytes

(Log in to post comments)

Here's an idea

Posted Dec 10, 2007 7:40 UTC (Mon) by jzbiciak (✭ supporter ✭, #5246) [Link]

Oh, and bit-fields (that is, fields of somewhat arbitrary bit widths) tend to be based around the size of "int" on a given machine. That is, they tend to be word oriented. The fields pack together to form words, and a field doesn't straddle two words.

Note that I say "tend to." Bit field layout and struct layout are actually ABI issues (ABI == Application Binary Interface). For example, here's the SVR4 i386 ABI. Take a look starting at page 27. In the case of the SVR4 ABI, it appears bitfields are actually packed in terms of their base type. I believe the latest C standard only wants you to use signed int, unsigned int and _Bool, though.

Bitfields in C++

Posted Dec 10, 2007 21:31 UTC (Mon) by pr1268 (subscriber, #24648) [Link]

Bjarne Stroustrup discusses a C++ Standard Template Library (STL) vector of bools (The C++ Programming Language, Special Edition, p. 458) - this is designed to overcome the wasted space of a 1-bit data structure taking up 16, 32, or 64 bits of memory.

Bitfields in C++

Posted Dec 11, 2007 14:24 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246) [Link]

Keep in mind that a bitvector (sometimes called a bitmap) is something rather different than a bitfield member of a struct or class. Bitvectors have array-like semantics and are quite typically used to represent things such as set membership. (eg. a 1 indicates membership, a 0 indicates lack of membership.) Bitfield members, on the other hand, are scalar quantities. There is no indexing associated with them, and their range is often much more than 0 to 1.

Bitfield members are often useful for storing values with limited range in a compact manner. For example, consider dates and times. The month number only goes from 1-12 and the day number only goes from 1-31. You can store those in 4 and 5 bits respectively. If you store year-1900 instead of the full 4 digit number, you can get by with 7 or 8 bits there. Hours fit in 5 bits, minutes and seconds in 6 bits each. That leads to something like this:

struct packed_time_and_date
{
    unsigned int year   : 7;  /* 7 bits for year - 1900      */
    unsigned int month  : 4;  /* 4 bits for month  (1 - 12)  */
    unsigned int day    : 5;  /* 5 bits for day    (1 - 31)  */
    unsigned int hour   : 5;  /* 5 bits for hour   (0 - 23)  */
    unsigned int minute : 6;  /* 6 bits for minute (0 - 59)  */
    unsigned int second : 6;  /* 6 bits for second (0 - 59)  */
};

Now, if I did my math right, that adds up to 33 bits. Under the x86 UNIX ABI, the compiler will allocate 2 32-bit words for this. The first 5 fields will pack into the first 32-bit word, and the 6th field will be in the lower 6 bits of the second word. That is, sizeof(struct packed_time_and_date) will be 8. If you can manage to squeeze a bit out of the year (say, limit yourself to a smaller range of years), this fits into 32 bits, and sizeof(struct packed_time_and_date) will be 4. In either case, the compiler will update these fields-packed-within-words with an appropriate sequence of loads, shifts, masks, and stores. No C++ or STL necessary.

(If you want to see a more in-depth (ab)use of this facility, check out this source file. It constructs a union of structs, each struct modeling a different opcode space in an instruction set.)

Anyhow, this is what I was referring to as "bit-fields" in the comment you replied to. As you can see, it's rather different than bitvectors. :-)

Bitvectors in C++ and STL have their own problems. I've been reading up on C++ and STL, and vectors of bits apparently have a checkered history in STL. There was one implementation (I believe at SGI) of bitvector (separate of vector<bool>) that didn't make it into the standard, and yet another (apparently a specialization of vector<> especially for bool) that many feel doesn't actually provide proper iterators. I wish I could provide references or details.

All I know is that it's enough for me to avoid STL on bitvectors, and just resort to coding these manually. It's served me well so far. And I don't see a need to invoke generics like sort on them. Something tells me most generic algorithms aren't as interesting on bitvectors. ;-)