size_t

[assaarpa]

This might be stupid thing to ask, but is the sizeof(size_t) supposed to be
same size as sizeof(void*) ? I need to store representation of pointer into
integer variable so that I can do arithmetics on it (bitwise xor), if not,
what you gurus would recommend?

 

[Rob Williscroft]

assaarpa wrote in in
comp.lang.c++:

This might be stupid thing to ask, but is the sizeof(size_t) supposed
to be same size as sizeof(void*) ?

No, it might be, but it isn't gauranteed.

I need to store representation of
pointer into integer variable so that I can do arithmetics on it
(bitwise xor), if not, what you gurus would recommend?

#include <cstring>
#include <cassert>

struct xorptr
{
char data[ sizeof( void * ) ];
xorptr() {}
xorptr( void *p ) { std::memcpy( data, &p, sizeof( data ) ); }
operator void * () const
{
void *p;
std::memcpy( &p, data, sizeof( p ) );
return p;
}
};

xorptr operator ^ ( xorptr const &lhs, xorptr const &rhs )
{
xorptr r;
for ( int i = 0; i < sizeof( r.data ); ++i )
{
r.data[ i ] = lhs.data[ i ] ^ rhs.data[ i ];
}
return r;
}

int i = 3, j = 4;

int main()
{
xorptr a( &i ), b( &j );

xorptr c = a ^ b;

xorptr d = c ^ a;

assert( d == &j );
}

HTH.

Rob.

 

[Jack Klein]

This might be stupid thing to ask, but is the sizeof(size_t) supposed to be
same size as sizeof(void*) ? I need to store representation of pointer into
integer variable so that I can do arithmetics on it (bitwise xor), if not,
what you gurus would recommend?

I would recommend not trying to do bitwise arithmetic on the bits of a
pointer because if you ever try to use it as a pointer again, the
behavior is undefined. Of course if you don't try to assign the
result to a pointer again, there's no problem.

But there is no guarantee that a size_t can hold a pointer, and in
fact there is no guarantee at all that there is any integer type that
can hold a pointer. On a platform with 64-bit pointers, a C++
implementation might not have such an integer type, because at this
time C++ has not yet standardized a required integer type with at
least 64 bits, like C has.

Why do you think that you need to do bitwise operations on the bits of
a pointer? What problem are you really trying to solve?

 

[Ivan Vecerina]

This might be stupid thing to ask, but is the sizeof(size_t) supposed to
be
same size as sizeof(void*) ? I need to store representation of pointer
into
integer variable so that I can do arithmetics on it (bitwise xor), if not,
what you gurus would recommend?

The C99 standard introduced intptr_t and uintptr_t in header <stdint.h>,
which can store the representation of a pointer. Your C++ platform
*might* have that header.
If not, I would suggest creating your own typedef, with a compile-time
assert as a sanity check. (see boost's macros, or something like:
typedef int compile_test[-1+2*(sizeof(intptr_t)>=sizeof(void*))];
// will trigger a compile error if the test is false

Note, however, that there is no guarantee that a platform even has
an integer type that can store the representation of a pointer
(intptr_t is optional in C99). But you may not need to worry
about it...


hth- Ivan

 

[Ioannis Vranos]

This might be stupid thing to ask, but is the sizeof(size_t) supposed to be
same size as sizeof(void*) ? I need to store representation of pointer into
integer variable so that I can do arithmetics on it (bitwise xor), if not,
what you gurus would recommend?

My suggestion is, place a check whether
sizeof(your_pointer_type)<=sizeof(unsigned long)

(which will always be true in C++98 but probably not in C++0x),and then
use std::bitset.


Regarding size_t, yes always sizeof(void *) will fit in size_t since the
result of sizeof is size_t.

 

[Ioannis Vranos]

What I said are completely wrong! (__Not adequate caffeine error__).


Fixed:


My suggestion is, place a check whether

sizeof(your_pointer_type)<=numeric_limits<unsigned long>::max()

(which will always be true in C++98 but probably not in C++0x), and then
use std::bitset to do bit manipulation.

 

[Peter Koch Larsen]

This might be stupid thing to ask, but is the sizeof(size_t) supposed to be
same size as sizeof(void*) ? I need to store representation of pointer into
integer variable so that I can do arithmetics on it (bitwise xor), if not,
what you gurus would recommend?

You almost never need to do bitwise operations on a pointer. I would think
twice about my design if that idea came up (are you trying to save space in
a doubly linked list? Forget about that!).

If you do need to look at pointers as integers for some reason (i do so in
rare situations when i need to search for a specific adress using hashing),
you could use an integer that is large enough for your void*. As pointed
out, such an integer might not exist, giving some nonportability to your
program.

/Peter

 

[assaarpa]

I would recommend not trying to do bitwise arithmetic on the bits of a

pointer because if you ever try to use it as a pointer again, the
behavior is undefined. Of course if you don't try to assign the
result to a pointer again, there's no problem.

I am doing this:

v = prev ^ next;

When iterating, and I know the node I am coming from, the next or prev is:

current ^= v;

I believe Knuth invented this, this use is in double-linked list with both
next and prev "pointer" encoded as xor of the both. Why? Just for fun.

 

[assaarpa]

You almost never need to do bitwise operations on a pointer. I would think

twice about my design if that idea came up (are you trying to save space in
a doubly linked list? Forget about that!).

Unfortunately I didn't, I had to try it out. The speed came out about 100%
faster than the std::list implementations that come with Visual C++ .NET
2003 and g++ 3.4.2 for some of the things I profiled against. I wrote the
interface to be same as std::list so could easily compare the code (since it
was identical just different namespace).

I resolve the "intp" typedef currently with a template and specialize it for
common integer types like char, short, int .. and also support long long and
__int64 where supported (compiler specific details), recently I read that
the idea for size_t was to provide support for various architechtures in a
way that 64 bit "pointers" in a, say, std::vector can be supported with
integer type as offset to the array on platforms where, say, int would be 32
bit but pointers 64 bit. I could be wrong but then that article was wrong
unfortunately I cannot bring it to top of my head which one and where it was
so I figured asking here would clarify the issue, afterall I am not too keen
on re-inventing the wheel if such nice typedef would exist already.

Just curious don't really have further agenda with this. The std::list<>
alternative implementation was just mental exercise nothing more, I do the
most stupid things sometimes because it's fun.

If the "100% faster" argument is annoying claim (we see that kind of claims
pop up periodically here don't we, anyone remember the FastString from few
years back?) so I just say that is results I profiled and that's that, I
will NOT post the code because my goal is not to brag about world
revolutionizing std::list implementation just wanted to know what the scoop
was regarding size_t, that's it.

If you do need to look at pointers as integers for some reason (i do so in
rare situations when i need to search for a specific adress using hashing),
you could use an integer that is large enough for your void*. As pointed
out, such an integer might not exist, giving some nonportability to your
program.

That is not a real concern, I write a lot of code that isn't "portable",
such as I assume that the platforms I going to work on are either BIG or
LITTLE endian, no BCP (or whatever the extreme endianess was that is not
been found in production systems for 20 years neither I think it is
critical that code doesn't work on one's complement architechtures and so
on. Mainly write code for mainstream systems like MIPS, ARM, X86 and
suchlike which are widely used and common. This is because I am a toolwriter
and can pick and choose platforms better than someone writing embedded code
for some archaic system for some bizarre reason. YMMV, naturally but basicly
100% portability is not a goal for me as that would be prohibitively
expensive in terms of development turnaround time. Doesn't mean I am sloppy,
but I acknowledge that I *do* design choises like that which from purist
point of view are serious errors.

Now consider the other thread I messed up around lately, the one about some
competition being stacked against c++ programmers and Standard Library,
notice obvious conflict of interest -- that is because of bias for issues
that are relevant to the mainstream platforms so in this light I am
consistent (since I am telling the truth it is easy to be consistent).

OK, I see that the general consensus is that size_t doesn't do what it
*might* have, which is useful information for me so BIG THANKS to everyone
who answered! Glad that I asked even though made myself look like a fool
(arrogant one at that).

 

[Ioannis Vranos]

But there is no guarantee that a size_t can hold a pointer, and in
fact there is no guarantee at all that there is any integer type that
can hold a pointer. On a platform with 64-bit pointers, a C++
implementation might not have such an integer type, because at this
time C++ has not yet standardized a required integer type with at
least 64 bits, like C has.

From the C90 draft that I have:


"Conversions that involve pointers (other than as permitted by the
constraints of $3.3.16.1) shall be specified by means of an explicit
cast; they have implementation-defined aspects: A pointer may be
converted to an integral type. The size of integer required and the
result are implementation-defined. If the space provided is not long
enough, the behavior is undefined. An arbitrary integer may be
converted to a pointer. The result is implementation-defined./37/ A
pointer to an object or incomplete type may be converted to a pointer
to a different object type or a different incomplete type. The
resulting pointer might not be valid if it is improperly aligned for
the type pointed to. It is guaranteed, however, that a pointer to an
object of a given alignment may be converted to a pointer to an object
of the same alignment or a less strict alignment and back again; the
result shall compare equal to the original pointer. (An object that
has character type has the least strict alignment.) A pointer to a
function of one type may be converted to a pointer to a function of
another type and back again; the result shall compare equal to the
original pointer. If a converted pointer is used to call a function
that has a type that is not compatible with the type of the called
function, the behavior is undefined."


I assume this means that we can store a pointer to unsigned long safely,
since unsigned long is the largest unsigned integral type in C++98:


"A pointer may be converted to an integral type. The size of integer
required and the result are implementation-defined. If the space
provided is not long enough, the behavior is undefined. An arbitrary
integer may be converted to a pointer. The result is
implementation-defined."

 

[Alf P. Steinbach]

* Ioannis Vranos:

I assume this means that we can store a pointer to unsigned long safely,
since unsigned long is the largest unsigned integral type in C++98:


From the C90 draft that I have:

"A pointer may be converted to an integral type. The size of integer
required and the result are implementation-defined. If the space
provided is not long enough, the behavior is undefined. An arbitrary
integer may be converted to a pointer. The result is
implementation-defined."

The crucial bit here is "implementation defined", which means that the integer
type may be an implementation-defined one, e.g. like Visual C++ __int64 which
is larger than 'unsigned long'.

In addition there may be a caveat in the word "may"; I'm not sure whether it
has special meaning in the C standard, or the folks who wrote that passage
simply didn't manage to express themselves clearly and unambigiously.

In short, the quoted material does not mean that you can safely store a
pointer in a an 'unsigned long', in the sense of preserving the address
information: whether you can do so or not depends on the implementation.

 

[assaarpa]

The crucial bit here is "implementation defined", which means that the
integer

type may be an implementation-defined one, e.g. like Visual C++ __int64 which
is larger than 'unsigned long'.

Yup, and the fact that for x86-64 / amd64 for instance long is 32 bits,
while pointers in 64-bit mode are 64-bit long so it would be fair to assume
that using just "unsigned long" is not the way to go, I stick with the
specialization and typedef akin the lines of:

template <int sizefoo>
class blah
{
// ...
};

template <>
class blah<sizeof(unsigned int)>
{
// ...
};

// do same for unsigned char, short, long, and depending on the compiler
"long long" and "__int64".. then Grande Finale:

typedef blah<sizeof(void*)> intp;

If we acknowledge the pedantic facts: this is not bomb-sure either, but for
practical use when constraints are acceptable, this is O.K. ? (I was merely
hoping that size_t would have better definition of what it represents,
always pleasure to see the replies here since so a BIG thank you to
everyone!)

p.s. I knew the caveat of this approach, that's why I asked for possibly
better alternative in the first place!

 

[Jack Klein]

I am doing this:

v = prev ^ next;

When iterating, and I know the node I am coming from, the next or prev is:

current ^= v;

I believe Knuth invented this, this use is in double-linked list with both
next and prev "pointer" encoded as xor of the both. Why? Just for fun.

Use two pointers. Some tricks are unreliable and/or unportable.

 

[Jack Klein]

From the C90 draft that I have:


"Conversions that involve pointers (other than as permitted by the
constraints of $3.3.16.1) shall be specified by means of an explicit
cast; they have implementation-defined aspects: A pointer may be
converted to an integral type. The size of integer required and the
result are implementation-defined. If the space provided is not long
enough, the behavior is undefined. An arbitrary integer may be
converted to a pointer. The result is implementation-defined./37/ A
pointer to an object or incomplete type may be converted to a pointer
to a different object type or a different incomplete type. The
resulting pointer might not be valid if it is improperly aligned for
the type pointed to. It is guaranteed, however, that a pointer to an
object of a given alignment may be converted to a pointer to an object
of the same alignment or a less strict alignment and back again; the
result shall compare equal to the original pointer. (An object that
has character type has the least strict alignment.) A pointer to a
function of one type may be converted to a pointer to a function of
another type and back again; the result shall compare equal to the
original pointer. If a converted pointer is used to call a function
that has a type that is not compatible with the type of the called
function, the behavior is undefined."


I assume this means that we can store a pointer to unsigned long safely,
since unsigned long is the largest unsigned integral type in C++98:


"A pointer may be converted to an integral type. The size of integer
required and the result are implementation-defined. If the space
provided is not long enough, the behavior is undefined. An arbitrary
integer may be converted to a pointer. The result is
implementation-defined."

You assume incorrectly. Neither C nor C++ require that an
implementation provide any type long enough to hold a pointer type.
So there is no guarantee that unsigned long can hold a pointer
successfully, and an unsuccessful attempt invokes undefined behavior.

This is in fact quite likely to be the case on some 64-bit platforms,
where pointers have 64 bits and (un)signed long has 32 bits. C++ does
not require an integer type with 64 bits.

 

[Jack Klein]

My suggestion is, place a check whether
sizeof(your_pointer_type)<=sizeof(unsigned long)

(which will always be true in C++98 but probably not in C++0x),and then
use std::bitset.

The statement above is 100% wrong. There is no prohibition in the C++
standard preventing a pointer from having more bits than can fit in an
unsigned long. If you believe to the contrary, kindly cite the
reference to that prohibition in the standard.

Regarding size_t, yes always sizeof(void *) will fit in size_t since the
result of sizeof is size_t.

This answer is true, but has nothing to do with the question the OP
asked.

He wanted to know if:

sizeof(void *) == sizeof(size_t)

....and the answer is that there is no such requirement or guarantee.

 

[Jack Klein]

What I said are completely wrong! (__Not adequate caffeine error__).


Fixed:


My suggestion is, place a check whether

sizeof(your_pointer_type)<=numeric_limits<unsigned long>::max()

(which will always be true in C++98 but probably not in C++0x), and then
use std::bitset to do bit manipulation.

Still confused...

 

[assaarpa]

Use two pointers. Some tricks are unreliable and/or unportable.

That wouldn't be fun now would it?

 

[assaarpa]

Use two pointers. Some tricks are unreliable and/or unportable.

On the technical side, most contemporary hardware achitechtures that are in
any ways relevant to my work DO support integer encoding of pointers and the
distinction is only how the hardware registers are USED, sematical
difference. The Standard does make this distinction and does not give
guarantees for the simple reason that this guarantee would be impossible in
practise to keep due to unorthodox hardware platforms that DO exist (rare or
obsolete for practical consideration for most).

When the platforms are known, unreliable? No.

When the platforms are well defined, unportable? Sure, but rarely an issue
configuration header wouldn't fix. When the target is a modern desktop
system or mobile platform such consideration is simply not an issue. In
these environements that the real, commercial programming community actually
works in, these so-called portability issues can crop up regardless of if
you use the standard library "right" or "wrong", platform specific details
creep in which the standard has NO control over simple as that. Consider the
recent heap/std discussion, the std cannot guarantee that code which
conforms to the specification will actually function predictably.

You can write "portable" code as much as you like and it WON'T function
correctly on all platforms anyway, and that is without taking implementation
specific bugs into account at all! What the standard seems to be trying is
to find and expose functionality that is universal, so that any
implementation can confrom to the specification. This is why the
specification is on purpose very loose and vague on some issues, so that any
implementation can be efficient there is very little point of being
conformant to strict specification if the implementation is substandard.

This creates the opinion on my mind that the C++ and C++ standard are just
tools, and when you know your platform limitations and implementation
specific details it is perfectly legal to use the tool on those platform in
specific manner. On x86/ia32, mips, arm, 68x00, power, ia64, sparc, just to
name a few, storing pointer as unsigned integer (if the type is known) does
work, the whole idea of the implementation of c++ compiler on these
platforms is to allow to write machine dependent code in machine independent
format-- that is the purpose of close-to-metal intermediate language like c
and c++, these langauges were engineered to do a task and they do it just
fine. If we wanted a higher level language we wouldn't be using c or c++ now
would we?

I'm not against portable code, on the contrary, a great fan of such thing,
but sometimes when want to get the job done we have to "limit" the scope to
practical boundaries (such as the list of architechtures above). For what I
am doing as example (for obvious reasons) this "limit" is in quotation
marks, because it is not a limit at all since that is the subset of hardware
architechtures I would work on anyway. When it is practical, I choose the
highly portable approach anyday of the week, and that is 99.999% of the
time.

But then once in a while, I want to try an idea and write a little
prototype, just for fun. You never do that anymore? I am lucky that I still
feel passion and love for programming (even with c++). After I got a little
prototype written, the next thing you find yourself wanting is to try a full
std compatible implementation, while you don't do it, it nags you and drives
you nuts. Then you one evening write it and it works better than intended,
few design problems are solved and all pieces just click into their places.
Then you have done it and move onto new interests, but one question lingers
in your mind: would there have been a portable typedef for what you call
"intp" in your test project's namespace?

You ask, and get interesting and informative responses. For your comment to
use two pointers, I think I won't and I know you will patronize me for that
attitude along the lines of "suit yourself", which does indeed as I *know*
what I am doing and generally know how things work. Blame it on my assembly
background, but that is still the mindset I have even when writing higher
level code, I cannot help knowing how the platforms and architechtures I am
writing code for, work, and how the compilers I use, work. It's a curse, I
know.

In short: I wasn't really looking for advice but for information, sorry to
be so ingrateful, the advice is appreciated but is not going to be followed.
I would give the same advice myself, but as the old saying goes: do as I
tell you to do, not what I actually do.. or something like that..

 

[Peter Koch Larsen]

Unfortunately I didn't, I had to try it out. The speed came out about 100%
faster than the std::list implementations that come with Visual C++ .NET
2003 and g++ 3.4.2 for some of the things I profiled against. I wrote the
interface to be same as std::list so could easily compare the code (since it
was identical just different namespace).

[snip]

I find it a little bit weird that you should get a 100% speed improvement.
Traversing the xorpointer should be slower in my view. How did you test it
ans what did you test? (e.g. did you test splice?)

/Peter

If you do need to look at pointers as integers for some reason (i do so in
rare situations when i need to search for a specific adress using hashing),
you could use an integer that is large enough for your void*. As pointed
out, such an integer might not exist, giving some nonportability to your
program.

[snip]
OK, I see that the general consensus is that size_t doesn't do what it
*might* have, which is useful information for me so BIG THANKS to everyone
who answered! Glad that I asked even though made myself look like a fool
(arrogant one at that).

No fool on your side ;-)

 

[assaarpa]

I find it a little bit weird that you should get a 100% speed improvement.

Traversing the xorpointer should be slower in my view. How did you test it
ans what did you test? (e.g. did you test splice?)

I had the same sentiments, the test is pretty trivial and indeed didn't try
splice neither I implemented splice the feature that were introduced in
C++2003 (could be wrong, all the same these methods are not implemented
are commented out as "TODO" section in the header.

Here's a snip what was tested and how, mostly insertion time and iteration
rate.

// snip snip some includes removed

// ---------------------------------------------------------
// profile
// ---------------------------------------------------------

template <typename container>
void profile(core::timer* xtimer, const char* name, const int size)
{

typedef typename container::iterator iterator;

std::cout << std::endl;
std::cout << name << std::endl;

float time0 = xtimer->time<float>();

container v;
iterator x;
iterator y;

for ( int i=0; i<size; ++i )
v.push_back(i + 1);

float time1 = xtimer->time<float>();

int sum = 0;

x = v.begin();
y = v.end();
for ( ; x != y; ++x )
sum += *x;

float time2 = xtimer->time<float>();

std::cout << " push_back() " << (time1 - time0) * 1000 << " ms, sum: " <<
sum << std::endl;
std::cout << " iteration " << (time2 - time1) * 1000 << " ms, sum: " <<
sum << std::endl;

}

// ---------------------------------------------------------
// main()
// ---------------------------------------------------------

int main()
{
// create timer object
core::timer* xtimer = core::timer::create();

// profile count
enum { size = 200000 };

profile< std::list<int> >( xtimer,"std::list", size );
profile< core::list<int> >( xtimer,"core::list", size );
profile< std::vector<int> >( xtimer,"std::vector", size );
profile< core::vector<int> >( xtimer,"core::vector",size );

// release timer object
xtimer->release();
}

Here's output from Windows XP Professional SP1 / Athlon64 3000+ / Visual C++
..NET 2003:

std::list
push_back() 32.2217 ms, sum: -1474736480
iteration 2.33968 ms, sum: -1474736480

core::list
push_back() 4.67015 ms, sum: -1474736480
iteration 0.99426 ms, sum: -1474736480

std::vector
push_back() 3.93877 ms, sum: -1474736480
iteration 0.507886 ms, sum: -1474736480

core::vector
push_back() 3.09313 ms, sum: -1474736480
iteration 0.527721 ms, sum: -1474736480

SuSE Linux 9.1 IA32 / Pentium4 1.7Ghz / g++ 3.4.2:

std::list
push_back() 33.382 ms, sum: -1474736480
iteration 2.744 ms, sum: -1474736480

core::list
push_back() 10.964 ms, sum: -1474736480
iteration 2.316 ms, sum: -1474736480

std::vector
push_back() 5.322 ms, sum: -1474736480
iteration 0.71 ms, sum: -1474736480

core::vector
push_back() 4.963 ms, sum: -1474736480
iteration 0.741 ms, sum: -1474736480

The "sum" is just value I compute and cout so that the computation is
forced, also checked the generated assembly code to verify that the code to
do the work was actually ran specified number of times and the result wasn't
computed at compilation time but runtime. Just mention this so that it's
clear what was being measured.

I had fun with this and the experiment is over, actually I did this over a
year ago but recently I read that one article that prompted me to ask the
question so this went back to old code for a moment. ;-)