Store information in pointers

[Francis Moreau]

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

 

[Eric Sosman]

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.

 

[Richard Bos]

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

 

[Noob]

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

 

[cr88192]

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...

 

[Ben Bacarisse]

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.

 

[Andrew Poelstra]

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.)

 

[Francis Moreau]

     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]

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]

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.

 

[Eric Sosman]

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."

 

[Keith Thompson]

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.

 

[Ben Bacarisse]

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.[/QUOTE]

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

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.

 

[robertwessel2]

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.

 

[Gene]

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.

 

[William Hughes]

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

 

[Stargazer]

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

 

[Stargazer]

Sorry, it slipped away.

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 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.

 

[Francis Moreau]

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]

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



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.