Store information in pointers

Discussion in 'C Programming' started by Francis Moreau, Apr 28, 2010.

  1. Hello,

    For optimisation purposes, I'd like to use some unused bits of a
    pointer. This assumes a certain bits layout for pointer encoding hence
    making the code not portable.

    These pointers are pointers to a structure 'A':

    struct A {
    unsigned long a;
    };

    so I assume that their alignment requirement should be the same as the
    first member whose type is 'unsigned long'.

    Now I don't know from the C specification what is the alignment
    requirement for 'unsigned long' type (I assume it's unspecified, but
    not sure). From my experience, I always find them to align to either 4
    bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    the pointer which I'd like to use.

    For example, I'd like to use one of these bit when condition 'C1' is
    true:

    struct A *p;
    /* setup 'p' */
    if (C1)
    *p = (struct A *)((uintptr_t)p | 1);

    (In this example I used 'uintptr_t' type which is 'optional', so this
    probably means that using this type implies non portable code.)

    So the question is: even the code above is not portable, it seems to
    me that it should work on most systems (I'm aware), is this correct ?

    Thanks
    Francis Moreau, Apr 28, 2010
    #1
    1. Advertising

  2. Francis Moreau

    Eric Sosman Guest

    On 4/28/2010 7:53 AM, Francis Moreau wrote:
    > Hello,
    >
    > For optimisation purposes, I'd like to use some unused bits of a
    > pointer. This assumes a certain bits layout for pointer encoding hence
    > making the code not portable.
    >
    > These pointers are pointers to a structure 'A':
    >
    > struct A {
    > unsigned long a;
    > };
    >
    > so I assume that their alignment requirement should be the same as the
    > first member whose type is 'unsigned long'.
    >
    > Now I don't know from the C specification what is the alignment
    > requirement for 'unsigned long' type (I assume it's unspecified, but
    > not sure). From my experience, I always find them to align to either 4
    > bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    > the pointer which I'd like to use.
    >
    > For example, I'd like to use one of these bit when condition 'C1' is
    > true:
    >
    > struct A *p;
    > /* setup 'p' */
    > if (C1)
    > *p = (struct A *)((uintptr_t)p | 1);
    >
    > (In this example I used 'uintptr_t' type which is 'optional', so this
    > probably means that using this type implies non portable code.)


    Let me get this straight: You're diddling the bits of your
    pointers, and you're worried that the use of `uintptr_t' might
    make the code non-portable?

    Years ago, Tom Lehrer wrote a song about a girl who murdered
    her entire family. When asked what had happened to them, she
    confessed -- because she knew lying was a sin.

    > So the question is: even the code above is not portable, it seems to
    > me that it should work on most systems (I'm aware), is this correct ?


    You're correct, but there's a whiff of tautology about your
    correctness: If it works on most systems you're aware of, then it's
    true that it works on most systems you're aware of ...

    Yes, it's likely to work. On the other hand, I hope there's
    a special place in Hell reserved for a person I once knew who did
    this with function pointers, "knowing" that machine instructions
    always had four-byte alignment. I was the lucky fellow who had
    to get his code running on a VAX, whose instructions came in all
    manner of lengths and had no alignment at all ...

    So: Yes, go right ahead, do as you please, it will work on
    most systems you're aware of. Be forewarned, though, that
    somebody someday may curse your name.

    --
    Eric Sosman
    lid
    Eric Sosman, Apr 28, 2010
    #2
    1. Advertising

  3. Francis Moreau

    Richard Bos Guest

    Francis Moreau <> wrote:

    > For example, I'd like to use one of these bit when condition 'C1' is
    > true:
    >
    > struct A *p;
    > /* setup 'p' */
    > if (C1)
    > *p = (struct A *)((uintptr_t)p | 1);
    >
    > (In this example I used 'uintptr_t' type which is 'optional', so this
    > probably means that using this type implies non portable code.)
    >
    > So the question is: even the code above is not portable, it seems to
    > me that it should work on most systems (I'm aware), is this correct ?


    Nope. It is perfectly legal for a pointer which does not contain a
    correctly aligned value to be a trap value. It is also perfectly legal
    for the reassignment to a struct pointer to reconvert the value to
    proper struct alignment, thus losing your extra information.

    Richard
    Richard Bos, Apr 28, 2010
    #3
  4. Francis Moreau

    Noob Guest

    Francis Moreau wrote:

    > For optimization purposes, I'd like to use some unused bits of a
    > pointer. This assumes a certain bits layout for pointer encoding
    > hence making the code not portable.


    On a related note, AMD64 requires virtual addresses expressed in
    canonical form, explicitly to prevent this type of "optimization".

    http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details
    Noob, Apr 28, 2010
    #4
  5. Francis Moreau

    cr88192 Guest

    "Noob" <root@127.0.0.1> wrote in message
    news:hr9c5r$gcj$...
    > Francis Moreau wrote:
    >
    >> For optimization purposes, I'd like to use some unused bits of a
    >> pointer. This assumes a certain bits layout for pointer encoding
    >> hence making the code not portable.

    >
    > On a related note, AMD64 requires virtual addresses expressed in
    > canonical form, explicitly to prevent this type of "optimization".
    >
    > http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details


    yep, but this only requires that one not try to address memory via such a
    pointer...

    if one makes sure to re-fill the upper bits to their expected values, then
    there is not as much of a problem with shoving stuff into the high-order
    bits.


    as for fiddling with the low order bits:
    yeah, it typically works, and there are a number of programs that actually
    do this kind of thing floating around;
    yes, it is also not very portable...

    it also makes a bit of a problem if one might consider having something,
    like a "char *" pointer, since this pointer will typically point to
    individual byte addresses.


    my solution was to do something different:
    using a part of the address space (otherwise unusable) to encode special
    values.

    on x86 and Win32, it grabs the address range 0xC0000000..0xFFFFFFFF.
    on x86-64, it grabs 0x71000000'00000000..0x71FFFFFF'FFFFFFFF.

    granted, in this scheme, pointers in these ranges generally don't point to
    any actually usable memory objects (instead they are used for integers and
    floating-point numbers and similar...).


    as a cost though, one could argue that a range check is possibly a little
    slower than tagging the low-order bits, but for my uses it works well enough
    (even if type-checking could use to be a little faster).

    if I can still type-check an integer in 16ns, I don't have too much of a
    problem (given my implementation, it is a little more for heap objects,
    often around 70ns in my tests on a fairly recent computer, and around 200ns
    typically for a lookup failure, IOW, trying to type-check a pointer which is
    not on the GC'ed heap).

    a little faster is possible but would require partly reworking my GC's
    internals.
    at present the lookup cost is a linear-time factor WRT the heap size (for
    small objects), as well as is the GC time (larger objects use a different
    strategy and should have a lower per-space overhead).

    or such...
    cr88192, Apr 28, 2010
    #5
  6. Noob <root@127.0.0.1> writes:

    > Francis Moreau wrote:
    >
    >> For optimization purposes, I'd like to use some unused bits of a
    >> pointer. This assumes a certain bits layout for pointer encoding
    >> hence making the code not portable.

    >
    > On a related note, AMD64 requires virtual addresses expressed in
    > canonical form, explicitly to prevent this type of "optimization".
    >
    > http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details


    Canonical form prevents the use of the top bits. I think the OP is
    planning to use the bottom bits.

    To the OP:
    As the old maps used to say "here be monsters". You might get away with
    it but I've used systems where some pointer casts shift the pointer's
    bits left or right. It's possible that the code will stay within one
    platform for the whole of its lifetime, but code does tend to outlive
    hardware.

    Consider packing the bits you want to associate with the pointers
    somewhere else. By placing them together you can reduce the space usage
    but exactly if (and how) this might work will depend on the memory
    allocation you are using. For example, if these bits are flags in a
    tree node and you use a pool allocator for the nodes, the bits can be
    put into and array associated with the pool.

    --
    Ben.
    Ben Bacarisse, Apr 28, 2010
    #6
  7. On 2010-04-28, William Ahern <william@wilbur.25thandClement.com> wrote:
    > Eric Sosman <> wrote:
    ><snip>
    >> So: Yes, go right ahead, do as you please, it will work on
    >> most systems you're aware of. Be forewarned, though, that
    >> somebody someday may curse your name.

    >
    > djb uses the lsb of pointers. IIRC it provides significant
    > perforance gains:
    >
    > http://cr.yp.to/critbit.html
    >
    > i don't think it's mentioned on that page, but IIRC he exlains it in the
    > source code.
    >


    The OHCI specification uses the bottom two bits of some
    pointers as well. See section 4 of:

    ftp://ftp.compaq.com/pub/supportinformation/papers/hcir1_0a.pdf

    (Plus, it uses physical addresses, which cause no end of grief
    when your driver is running in virtual memory space.)

    --
    Andrew Poelstra
    http://www.wpsoftware.net/andrew
    Andrew Poelstra, Apr 28, 2010
    #7
  8. On 28 avr, 14:34, Eric Sosman <> wrote:
    > On 4/28/2010 7:53 AM, Francis Moreau wrote:
    >
    >
    >
    >
    >
    > > Hello,

    >
    > > For optimisation purposes, I'd like to use some unused bits of a
    > > pointer. This assumes a certain bits layout for pointer encoding hence
    > > making the code not portable.

    >
    > > These pointers are pointers to a structure 'A':

    >
    > >    struct A {
    > >            unsigned long a;
    > >    };

    >
    > > so I assume that their alignment requirement should be the same as the
    > > first member whose type is 'unsigned long'.

    >
    > > Now I don't know from the C specification what is the alignment
    > > requirement for 'unsigned long' type (I assume it's unspecified, but
    > > not sure). From my experience, I always find them to align to either 4
    > > bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    > > the pointer which I'd like to use.

    >
    > > For example, I'd like to use one of these bit when condition 'C1' is
    > > true:

    >
    > >    struct A *p;
    > >    /* setup 'p' */
    > >    if (C1)
    > >            *p = (struct A *)((uintptr_t)p | 1);

    >
    > > (In this example I used 'uintptr_t' type which is 'optional', so this
    > > probably means that using this type implies non portable code.)

    >
    >      Let me get this straight: You're diddling the bits of your
    > pointers, and you're worried that the use of `uintptr_t' might
    > make the code non-portable?


    Not at all, I was just wondering the point to introduce a type which
    is 'optional' since using it means not portable code...
    Francis Moreau, Apr 28, 2010
    #8
  9. On 28 avr, 14:44, (Richard Bos) wrote:
    > Francis Moreau <> wrote:
    > > For example, I'd like to use one of these bit when condition 'C1' is
    > > true:

    >
    > >   struct A *p;
    > >   /* setup 'p' */
    > >   if (C1)
    > >           *p = (struct A *)((uintptr_t)p | 1);

    >
    > > (In this example I used 'uintptr_t' type which is 'optional', so this
    > > probably means that using this type implies non portable code.)

    >
    > > So the question is: even the code above is not portable, it seems to
    > > me that it should work on most systems (I'm aware), is this correct ?

    >
    > Nope. It is perfectly legal for a pointer which does not contain a
    > correctly aligned value to be a trap value. It is also perfectly legal
    > for the reassignment to a struct pointer to reconvert the value to
    > proper struct alignment, thus losing your extra information.


    Ah that's interesting. Could you point out the revelant section in the
    C spec ?

    I searched in the "Conversions" but failed to find it.

    Thanks
    Francis Moreau, Apr 28, 2010
    #9
  10. On 28 avr, 16:29, Ben Bacarisse <> wrote:
    > Noob <r...@127.0.0.1> writes:
    > > Francis Moreau wrote:

    >
    > >> For optimization purposes, I'd like to use some unused bits of a
    > >> pointer. This assumes a certain bits layout for pointer encoding
    > >> hence making the code not portable.

    >
    > > On a related note, AMD64 requires virtual addresses expressed in
    > > canonical form, explicitly to prevent this type of "optimization".

    >
    > >http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details

    >
    > Canonical form prevents the use of the top bits.  I think the OP is
    > planning to use the bottom bits.
    >
    > To the OP:
    > As the old maps used to say "here be monsters".  You might get away with
    > it but I've used systems where some pointer casts shift the pointer's
    > bits left or right.  It's possible that the code will stay within one
    > platform for the whole of its lifetime, but code does tend to outlive
    > hardware.
    >
    > Consider packing the bits you want to associate with the pointers
    > somewhere else.  By placing them together you can reduce the space usage
    > but exactly if (and how) this might work will depend on the memory
    > allocation you are using.


    This is the part where I'm not sure, please correct me if I'm wrong:
    alignment requirement of 'unsigned long' type (for example) is
    implementation defined. All implementations I met uses 4 or 8 bytes
    boundaries but nothing prevents an implementation to use 1 byte
    boundaries.

    > For example, if these bits are flags in a
    > tree node and you use a pool allocator for the nodes, the bits can be
    > put into and array associated with the pool.
    >


    But you still use more memory. And another drawback of this solution
    is that the bits are located in a different place than the node data,
    meaning you probably have more cache misses when dealing with the node
    data.
    Francis Moreau, Apr 28, 2010
    #10
  11. Francis Moreau

    Eric Sosman Guest

    On 4/28/2010 3:04 PM, Francis Moreau wrote:
    > On 28 avr, 14:34, Eric Sosman<> wrote:
    >> On 4/28/2010 7:53 AM, Francis Moreau wrote:
    >> [...]
    >>> For example, I'd like to use one of these bit when condition 'C1' is
    >>> true:

    >>
    >>> struct A *p;
    >>> /* setup 'p' */
    >>> if (C1)
    >>> *p = (struct A *)((uintptr_t)p | 1);

    >>
    >>> (In this example I used 'uintptr_t' type which is 'optional', so this
    >>> probably means that using this type implies non portable code.)

    >>
    >> Let me get this straight: You're diddling the bits of your
    >> pointers, and you're worried that the use of `uintptr_t' might
    >> make the code non-portable?

    >
    > Not at all, I was just wondering the point to introduce a type which
    > is 'optional' since using it means not portable code...


    ... and I was just pointing out that diddling the pointers
    is already non-portable, and more seriously so. I suggest that
    any platform whose pointers are so odd that they can't be
    converted to integers is also a platform that may well choke on
    diddled pointers.

    An old acquaintance used to describe this concentration on the
    minor issue instead of the major as "Cleaning the bottle caps off
    the beach so the sand will look nice around the whale carcasses."

    --
    Eric Sosman
    lid
    Eric Sosman, Apr 28, 2010
    #11
  12. Francis Moreau <> writes:
    > On 28 avr, 14:44, (Richard Bos) wrote:
    >> Francis Moreau <> wrote:
    >> > For example, I'd like to use one of these bit when condition 'C1' is
    >> > true:

    >>
    >> >   struct A *p;
    >> >   /* setup 'p' */
    >> >   if (C1)
    >> >           *p = (struct A *)((uintptr_t)p | 1);

    >>
    >> > (In this example I used 'uintptr_t' type which is 'optional', so this
    >> > probably means that using this type implies non portable code.)

    >>
    >> > So the question is: even the code above is not portable, it seems to
    >> > me that it should work on most systems (I'm aware), is this correct ?

    >>
    >> Nope. It is perfectly legal for a pointer which does not contain a
    >> correctly aligned value to be a trap value. It is also perfectly legal
    >> for the reassignment to a struct pointer to reconvert the value to
    >> proper struct alignment, thus losing your extra information.

    >
    > Ah that's interesting. Could you point out the revelant section in the
    > C spec ?
    >
    > I searched in the "Conversions" but failed to find it.


    I don't think there's any particular section that permits it. But the
    behavior of any code that produces a misaligned pointer is undefined,
    which of course means that anything can happen.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Apr 28, 2010
    #12
  13. Francis Moreau <> writes:

    > On 28 avr, 16:29, Ben Bacarisse <> wrote:

    <snip>
    >> > Francis Moreau wrote:

    >>
    >> >> For optimization purposes, I'd like to use some unused bits of a
    >> >> pointer. This assumes a certain bits layout for pointer encoding
    >> >> hence making the code not portable.

    <snip>
    >> Consider packing the bits you want to associate with the pointers
    >> somewhere else.  By placing them together you can reduce the space usage
    >> but exactly if (and how) this might work will depend on the memory
    >> allocation you are using.

    >
    > This is the part where I'm not sure, please correct me if I'm wrong:
    > alignment requirement of 'unsigned long' type (for example) is
    > implementation defined. All implementations I met uses 4 or 8 bytes
    > boundaries but nothing prevents an implementation to use 1 byte
    > boundaries.


    Sure, 1-byte alignment is possible. That's just another reason why you
    might have trouble.

    >> For example, if these bits are flags in a
    >> tree node and you use a pool allocator for the nodes, the bits can be
    >> put into and array associated with the pool.

    >
    > But you still use more memory. And another drawback of this solution
    > is that the bits are located in a different place than the node data,
    > meaning you probably have more cache misses when dealing with the node
    > data.


    Because the solution uses more memory there will be an increased chance
    that something useful gets kicked out of the cache, but I don't think
    the cache cares much about where the data is (though I must hold my hand
    up here and admit that the last machine whose insides I really knew was
    probably something by Data General).

    BTW, you can avoid the problems of traps and misaligned pointers by
    storing the "pointer" as an integer and only converting it to a real
    pointer at the point of use: once it has been tided up and the converted
    pointer is known to be safe.

    Also, have you considered using indexes rather than pointers? An index
    into a memory pool can be much shorter than a pointer and you can either
    use the space saved to store the extra bits or, at worst, you can encode
    the extra bits in the integer far more safely.

    --
    Ben.
    Ben Bacarisse, Apr 28, 2010
    #13
  14. Francis Moreau

    Guest

    On Apr 28, 2:24 pm, Francis Moreau <> wrote:
    > On 28 avr, 16:29, Ben Bacarisse <> wrote:
    >
    >
    >
    >
    >
    > > Noob <r...@127.0.0.1> writes:
    > > > Francis Moreau wrote:

    >
    > > >> For optimization purposes, I'd like to use some unused bits of a
    > > >> pointer. This assumes a certain bits layout for pointer encoding
    > > >> hence making the code not portable.

    >
    > > > On a related note, AMD64 requires virtual addresses expressed in
    > > > canonical form, explicitly to prevent this type of "optimization".

    >
    > > >http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details

    >
    > > Canonical form prevents the use of the top bits.  I think the OP is
    > > planning to use the bottom bits.

    >
    > > To the OP:
    > > As the old maps used to say "here be monsters".  You might get away with
    > > it but I've used systems where some pointer casts shift the pointer's
    > > bits left or right.  It's possible that the code will stay within one
    > > platform for the whole of its lifetime, but code does tend to outlive
    > > hardware.

    >
    > > Consider packing the bits you want to associate with the pointers
    > > somewhere else.  By placing them together you can reduce the space usage
    > > but exactly if (and how) this might work will depend on the memory
    > > allocation you are using.

    >
    > This is the part where I'm not sure, please correct me if I'm wrong:
    > alignment requirement of 'unsigned long' type (for example) is
    > implementation defined. All implementations I met uses 4 or 8 bytes
    > boundaries but nothing prevents an implementation to use 1 byte
    > boundaries.



    On many compilers for x86 (for example – particularly since x86
    handles unaligned accesses without complaint), you can turn structure
    packing on (or set it to some lesser level of alignment), either on a
    per-structure basis, or for the whole program. For example, on MSVC,
    compiling with "/Zp1" will cause alignments within a structure to be
    on a one byte boundary.
    , Apr 28, 2010
    #14
  15. Francis Moreau

    Gene Guest

    On Apr 28, 11:12 am, William Ahern <will...@wilbur.25thandClement.com>
    wrote:
    > Eric Sosman <> wrote:
    >
    > <snip>
    >
    > >      So: Yes, go right ahead, do as you please, it will work on
    > > most systems you're aware of.  Be forewarned, though, that
    > > somebody someday may curse your name.

    >
    > djb uses the lsb of pointers. IIRC it provides significant
    > perforance gains:
    >
    >        http://cr.yp.to/critbit.html
    >
    > i don't think it's mentioned on that page, but IIRC he exlains it in the
    > source code.


    I have read about dyamically typed languages that differentiate
    unboxed fixnums (normally 4- or 8-byte ints) from pointers by setting
    the low order bit in the fixnums and storing the signed quantity in
    the upper 31 or 63. In this manner, a type test requires only a
    single "or" with 1, and recovering the value of a fixnum needs only an
    arithmetic shift right. Both are a single instructions on most
    processors. Pretty slick. Of course C implementing this idea is
    entirely non-portable.
    Gene, Apr 29, 2010
    #15
  16. On Apr 28, 8:53 am, Francis Moreau <> wrote:
    > Hello,
    >
    > For optimisation purposes, I'd like to use some unused bits of a
    > pointer.



    Alarm bells are ringing loudly. Storing flags in unused bits
    of a pointer may speed things up, or it may not.
    It may well slow things down.
    (Of course the optimization may be for space not speed.)
    A simple change is to make all your pointers structure
    members with flags stored in the structure. Write
    a few macros (set_c1,get_c1, get_pointer, declare_pointer ...)
    and you can easily change back and forth.
    This would at least give you some
    idea if the "optimization" was worth anything.
    What's more, you will have portable code to fall
    back on if you need it.

    - William Hughes
    William Hughes, Apr 29, 2010
    #16
  17. Francis Moreau

    Stargazer Guest

    On Apr 28, 2:53 pm, Francis Moreau <> wrote:
    > Hello,
    >
    > For optimisation purposes, I'd like to use some unused bits of a
    > pointer. This assumes a certain bits layout for pointer encoding hence
    > making the code not portable.
    >
    > These pointers are pointers to a structure 'A':
    >
    >   struct A {
    >           unsigned long a;
    >   };
    >
    > so I assume that their alignment requirement should be the same as the
    > first member whose type is 'unsigned long'.
    >
    > Now I don't know from the C specification what is the alignment
    > requirement for 'unsigned long' type (I assume it's unspecified, but
    > not sure). From my experience, I always find them to align to either 4
    > bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    > the pointer which I'd like to use.
    >
    > For example, I'd like to use one of these bit when condition 'C1' is
    > true:
    >
    >   struct A *p;
    >   /* setup 'p' */
    >   if (C1)
    >           *p = (struct A *)((uintptr_t)p | 1);


    I think this won't compile on any system, assignment of "struct A *"
    to "struct A".
    If you really must do this (no idea why not union), it's somehow
    better to make "p" of type "uintptr_t" and only cast it to pointer
    when you need to use it as pointer. This will remove issues specific
    to double casting and also protect against using pointer when you are
    not intending to use it as such.

    > (In this example I used 'uintptr_t' type which is 'optional', so this
    > probably means that using this type implies non portable code.)
    >
    > So the question is: even the code above is not portable, it seems to
    > me that it should work on most systems (I'm aware), is this correct ?


    In a sense, yes, it may work on all It may be

    >
    > Thanks
    Stargazer, Apr 29, 2010
    #17
  18. Francis Moreau

    Stargazer Guest

    Sorry, it slipped away.

    On Apr 29, 10:44 am, Stargazer <> wrote:
    > On Apr 28, 2:53 pm, Francis Moreau <> wrote:
    >
    >
    >
    > > Hello,

    >
    > > For optimisation purposes, I'd like to use some unused bits of a
    > > pointer. This assumes a certain bits layout for pointer encoding hence
    > > making the code not portable.

    >
    > > These pointers are pointers to a structure 'A':

    >
    > >   struct A {
    > >           unsigned long a;
    > >   };

    >
    > > so I assume that their alignment requirement should be the same as the
    > > first member whose type is 'unsigned long'.

    >
    > > Now I don't know from the C specification what is the alignment
    > > requirement for 'unsigned long' type (I assume it's unspecified, but
    > > not sure). From my experience, I always find them to align to either 4
    > > bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    > > the pointer which I'd like to use.

    >
    > > For example, I'd like to use one of these bit when condition 'C1' is
    > > true:

    >
    > >   struct A *p;
    > >   /* setup 'p' */
    > >   if (C1)
    > >           *p = (struct A *)((uintptr_t)p | 1);

    >
    > I think this won't compile on any system, assignment of "struct A *"
    > to "struct A".
    > If you really must do this (no idea why not union), it's somehow
    > better to make "p" of type "uintptr_t" and only cast it to pointer
    > when you need to use it as pointer. This will remove issues specific
    > to double casting and also protect against using pointer when you are
    > not intending to use it as such.
    >
    > > (In this example I used 'uintptr_t' type which is 'optional', so this
    > > probably means that using this type implies non portable code.)

    >
    > > So the question is: even the code above is not portable, it seems to
    > > me that it should work on most systems (I'm aware), is this correct ?

    >
    > In a sense, yes, it may work on all It may be


    In a sense, yes, it may work on all systems on which you explicitly
    make it work. If you consider "system" as compiler with specific
    switches + run-time + architecture. It may be less portable than you
    think though, as many compilers have switches to alter default
    alignment rules regardless of architecture per source file, its part
    or per structure.
    Stargazer, Apr 29, 2010
    #18
  19. On Apr 29, 9:44 am, Stargazer <> wrote:
    > On Apr 28, 2:53 pm, Francis Moreau <> wrote:
    >
    >
    >
    >
    >
    > > Hello,

    >
    > > For optimisation purposes, I'd like to use some unused bits of a
    > > pointer. This assumes a certain bits layout for pointer encoding hence
    > > making the code not portable.

    >
    > > These pointers are pointers to a structure 'A':

    >
    > >   struct A {
    > >           unsigned long a;
    > >   };

    >
    > > so I assume that their alignment requirement should be the same as the
    > > first member whose type is 'unsigned long'.

    >
    > > Now I don't know from the C specification what is the alignment
    > > requirement for 'unsigned long' type (I assume it's unspecified, but
    > > not sure). From my experience, I always find them to align to either 4
    > > bytes or 8 bytes boundaries. So this leaves a couple of unused bits in
    > > the pointer which I'd like to use.

    >
    > > For example, I'd like to use one of these bit when condition 'C1' is
    > > true:

    >
    > >   struct A *p;
    > >   /* setup 'p' */
    > >   if (C1)
    > >           *p = (struct A *)((uintptr_t)p | 1);

    >
    > I think this won't compile on any system, assignment of "struct A *"
    > to "struct A".


    you're right, the last statement is wrong and should be:

    p = (struct A *)((uintptr_t)p | 1);

    > If you really must do this (no idea why not union), it's somehow
    > better to make "p" of type "uintptr_t" and only cast it to pointer
    > when you need to use it as pointer. This will remove issues specific
    > to double casting and also protect against using pointer when you are
    > not intending to use it as such.


    Yes I agree.

    But the sad thing is that uintptr_t has been made optional, and I miss
    the point to have done so.
    Francis Moreau, Apr 29, 2010
    #19
  20. On Apr 28, 11:53 pm, Ben Bacarisse <> wrote:
    > Francis Moreau <> writes:
    > > On 28 avr, 16:29, Ben Bacarisse <> wrote:

    > <snip>
    > >> > Francis Moreau wrote:

    >
    > >> >> For optimization purposes, I'd like to use some unused bits of a
    > >> >> pointer. This assumes a certain bits layout for pointer encoding
    > >> >> hence making the code not portable.

    > <snip>
    > >> Consider packing the bits you want to associate with the pointers
    > >> somewhere else.  By placing them together you can reduce the space usage
    > >> but exactly if (and how) this might work will depend on the memory
    > >> allocation you are using.

    >
    > > This is the part where I'm not sure, please correct me if I'm wrong:
    > > alignment requirement of 'unsigned long' type (for example) is
    > > implementation defined. All implementations I met uses 4 or 8 bytes
    > > boundaries but nothing prevents an implementation to use 1 byte
    > > boundaries.

    >
    > Sure, 1-byte alignment is possible.  That's just another reason why you
    > might have trouble.
    >
    > >> For example, if these bits are flags in a
    > >> tree node and you use a pool allocator for the nodes, the bits can be
    > >> put into and array associated with the pool.

    >
    > > But you still use more memory. And another drawback of this solution
    > > is that the bits are located in a different place than the node data,
    > > meaning you probably have more cache misses when dealing with the node
    > > data.

    >
    > Because the solution uses more memory there will be an increased chance
    > that something useful gets kicked out of the cache, but I don't think
    > the cache cares much about where the data is


    Well if the structure's data is accessed and fits into one cache line,
    then all information about the structure can be accessed with at most
    one cache miss. But if the extra bit is not stored in the structure
    you need to do an extra memory access to retrieve the information thus
    one more chance to get a cache miss.

    Even worse if the structure data and the extra bit share the same
    cache line (this can happen depending on the cache configuration).

    >
    > BTW, you can avoid the problems of traps and misaligned pointers by
    > storing the "pointer" as an integer and only converting it to a real
    > pointer at the point of use: once it has been tided up and the converted
    > pointer is known to be safe.


    That's true. But 'uintptr_t' type is optional and I'm still wondering
    the point to make it _optional_ since it makes it almost useless.
    Francis Moreau, Apr 29, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?UnVkeQ==?=

    to store or not to store an image

    =?Utf-8?B?UnVkeQ==?=, Mar 29, 2005, in forum: ASP .Net
    Replies:
    6
    Views:
    620
    =?Utf-8?B?UnVkeQ==?=
    Mar 30, 2005
  2. Cheok Yan Cheng
    Replies:
    1
    Views:
    1,827
    Chris Smith
    Apr 15, 2004
  3. Nathan Sokalski
    Replies:
    1
    Views:
    455
    sloan
    Jul 18, 2008
  4. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    656
  5. saurabh
    Replies:
    2
    Views:
    109
    Bullschmidt
    Oct 25, 2005
Loading...

Share This Page