passing ref to ptr again as ref to ptr....

[osama178]

Let's say I have this code

--------------------
class GenericQueue
{
public:
bool Pop(void*& refToPtr); // //--------------------(1)

};

class SpecialQueue: private GenericQueue
{
public:
bool Pop(T*& refToPtr)
{
return
GenericQueue:op(refToPtr); //--------------------(2)
}

};


Why doesn't the statement in -------(2) compile?

 

[osama178]

Let's say I have this code

--------------------
class GenericQueue
{
public:
bool Pop(void*& refToPtr); // //--------------------(1)

};

class SpecialQueue: private GenericQueue
{
public:
bool Pop(T*& refToPtr)
{
return
GenericQueue:op(refToPtr); //--------------------(2)
}

};

Why doesn't the statement in -------(2) compile?

And I did have the

template<class T> in front of SpecialClass. Sorry!. I just posted a
snippet here.

 

[Kai-Uwe Bux]

Because T*& and void*& are different types with no automatic conversions
between them.

And I did have the

template<class T> in front of SpecialClass. Sorry!. I just posted a
snippet here.

Why do you run your own code for queue? It seems as though std::queue<T*>
might be what you are looking for.


Best

Kai-Uwe Bux

 

[osama178]

Because T*& and void*& are different types with no automatic conversions
between them.



Why do you run your own code for queue? It seems as though std::queue<T*>
might be what you are looking for.

Best

Kai-Uwe Bux

I am implementing a lockless queue, which I don't think the
std::queue<T*> provides. To avoid template-induced code bloat, I am
implementing a generic the queue using void* pointers. But to gain
type-safety, I am implementing a templated interface-class.

Now what is confusing me is that this function works


SpecialQueue:ush(T* ptr) { GenericQueue:ush(ptr); }

and it converts T* to void* no problem.

But when I do

SpecialQueue:op(T*& refPtr) { GenericQueue:op(refPtr); }

Now let's say I instantiate an object

SpecialQueue<int> spQ();
int a = 10;
int p = &a;
spQ.Pop(p);

It gives me this error:

"cannot convert parameter 1 from 'int *' to 'void *&'"

 

[osama178]

Because T*& and void*& are different types with no automatic conversions
between them.

Sorry. Why don't we need automatic type conversion from T* to void*
but need it from T*& to void*&.
I am still learning C++, so please excuse my ignorance.

 

[Bo Persson]

I am implementing a lockless queue, which I don't think the
std::queue<T*> provides. To avoid template-induced code bloat, I am
implementing a generic the queue using void* pointers.

And you believe you can outsmart the compiler?

I wouldn't bet on that. ;-)


Bo Persson

 

[osama178]

And you believe you can outsmart the compiler?

I wouldn't bet on that. ;-)

Bo Persson

Why not?

If you instantiate GenericQueue a dozen times, you'll have a dozen
copies of its code. But if you use GenericQueue for storing void*
pointers instead, make its ctor, copy ctor, and assig operator
private, you'll prevent clients from making instances of it AND you'll
have only one version of the code. And the templated interface class
will implement its functionality in-terms-of GenericQueue
functionality and provide for type safety. The code in the interface
class is substantially less than that of the GenericQueue and will not
result in as much code bloat. No?

Of course I'll have to account for the fact that a pointer to an
object might have been pushed onto multiple stacks.

 

[osama178]

Why not?

If you instantiate GenericQueue a dozen times, you'll have a dozen
copies of its code. But if you use GenericQueue for storing void*
pointers instead, make its ctor, copy ctor, and assig operator
private, you'll prevent clients from making instances of it AND you'll
have only one version of the code. And the templated interface class
will implement its functionality in-terms-of GenericQueue
functionality and provide for type safety. The code in the interface
class is substantially less than that of the GenericQueue and will not
result in as much code bloat. No?

Of course I'll have to account for the fact that a pointer to an
object might have been pushed onto multiple stacks.

The idea is from Scott Myer's "Effective C++", Item 42 - Use Private
Inheritance Judiciously.

 

[Ivan Vecerina]

: I am implementing a lockless queue, which I don't think the
: std::queue<T*> provides. To avoid template-induced code bloat, I am
: implementing a generic the queue using void* pointers. But to gain
: type-safety, I am implementing a templated interface-class.

This is a common optimization technique indeed (used back in early
C++ times). But keep in mind that, nowadays, some compilers/linkers
are able to automatically eliminate redundant copies of the same
code, such as those resulting from multiple template instantiations.

: Now what is confusing me is that this function works
:
:
: SpecialQueue:ush(T* ptr) { GenericQueue:ush(ptr); }
:
: and it converts T* to void* no problem.

Indeed: the compiler passes a *copy* of ptr to the generic function.
During this copy, it can make an implicit conversion from T* to void*.

: But when I do
:
: SpecialQueue:op(T*& refPtr) { GenericQueue:op(refPtr); }
....
: It gives me this error:
:
: "cannot convert parameter 1 from 'int *' to 'void *&'"

Mind the fact that the int* and void* may have different
in-memory representations (even though this is not the case
on the common processor architectures that you and I use).
You can force the behavior you are looking for by using an
explicit cast:
SpecialQueue:op(T*& refPtr)
{ GenericQueue:op(reinterpret_cast<void*&>(refPtr)); }
However, this will result in undefined behavior, even though
problems will only happen in "exotic" platforms. It will work
perfectly fine on most architectures, but is not portable.

In proper and portable C++, you would need to write:
bool SpecialQueue:op(T*& refPtr)
{
void * ptr; // I assume this is an output-only parameter
bool const result = GenericQueue:op(&ptr);
refPtr = static_cast<T*>(ptr); // ok, works if the
// previously pushed pointer was indeed a T* or NULL
// ( any T* can be converted to void* and then back )
return result;
}


As you see, C++ only allows the implicit conversions that are safe.
(except for those (many) that were inherited from C...)

Cheers -Ivan

 

[Bo Persson]

Why not?

If you instantiate GenericQueue a dozen times, you'll have a dozen
copies of its code.

No, you will probably not.

On the compiler I use, templates will most often share code for
objects of the same size, as the linker will merge identical code
blocks. For example,

struct two
{
short x;
short y;
};

std::vector<int> v1;
std::vector<long> v2;
std::vector<two> v3;

will only generate one set of code in the resulting .exe file.

But if you use GenericQueue for storing void*
pointers instead, make its ctor, copy ctor, and assig operator
private, you'll prevent clients from making instances of it AND
you'll have only one version of the code. And the templated
interface class will implement its functionality in-terms-of
GenericQueue functionality and provide for type safety. The code in
the interface class is substantially less than that of the
GenericQueue and will not result in as much code bloat. No?

Or it will possibly add to the code size by adding another layer. At
least it will add to the complexity of the code.


Bo Persson

 

[osama178]

Thanks Ivan and Bo.

I did not know that some compilers/linkers do in fact eliminate
redundant code. It still does not make sense to me that void* and int*
might have different size/memory representation. Aren't all pointers
indexing entries in the machine's address space? Which means a
pointer's size has to be the same regardless of what it points to
(int, void, double, ...etc.)

 

[Bo Persson]

Thanks Ivan and Bo.

I did not know that some compilers/linkers do in fact eliminate
redundant code. It still does not make sense to me that void* and
int* might have different size/memory representation. Aren't all
pointers indexing entries in the machine's address space? Which
means a pointer's size has to be the same regardless of what it
points to (int, void, double, ...etc.)

Yes, and no.

The address space can be different than the one we see on an average
PC. If you go to some old mainframes, or some embedded processors, the
native address can be an index to a word. If you want to access
smaller parts, like characters, that may require additional info. In
that case, a char* might be quite different from an int*. This affects
the options for void*.


Bo Persson

 

[James Kanze]

(e-mail address removed) wrote:

[...]
You'd have to see the documentation for your implementation, but
by default, std::queue is lockless, since there are no locks (or
threads) in the standard. Most of the implementations I'm
familiar with do not use locks even in multithreaded
environments.

If you mean that you intent to implement a queue which can be
used without locks in a multithreaded environment, be aware that
you'll need some implementation dependent code; it can't be done
in standard C++.

No, you will probably not.

If the types are different, and the compiler is conform, he
probably will.

On the compiler I use, templates will most often share code for
objects of the same size, as the linker will merge identical code
blocks.

I certainly hope not. That wouldn't be conform. (I presume, of
course, that the compiler will only do so if the objects are
PODs as well. Otherwise, the code won't be identical.)

For example,

struct two
{
short x;
short y;
};

std::vector<int> v1;
std::vector<long> v2;
std::vector<two> v3;

will only generate one set of code in the resulting .exe file.

Despite the fact that the member functions of v1, v2 and v3 are
guaranteed to have different addresses?

None of the compilers I use do this (at least not to my
knowledge).

Or it will possibly add to the code size by adding another
layer. At least it will add to the complexity of the code.

It was a more or less standard technique back when templates
first appeared, and memory was a bit scarcer. Even today, it
might be used to reduce coupling; all of the complicated parts
of the implementation are non-template, and so don't have to be
in the header. (I use it in a couple of my classes, but more
for historical reasons than anything else---the original
implementation dates back to a time when memory was scarcer. In
fact, the original implementation often dates back to
<generic.h>, when you definitely moved as much as possible out
of the "template", since the "template" was in fact an
impossible to debug macro.)

 

[James Kanze]

I did not know that some compilers/linkers do in fact
eliminate redundant code.

Very few do, and it's difficult to do it and still be standard
conform.

It still does not make sense to me that void* and int* might
have different size/memory representation.

Why not? I've worked on machines where they did, and I think
some of them are still being sold today. A void* must be able
to hold any pointer type, including a char*.

Aren't all pointers indexing entries in the machine's address
space?

I'm not sure what that means. Pointers aren't necessarily
indexes, and when they are, they don't necessarily "index"
bytes. Some common architectures, even today, have segmented
architectures, and word addressed machines still exist.

 

[peter koch]

(e-mail address removed) wrote:

    [...]

You'd have to see the documentation for your implementation, but
by default, std::queue is lockless, since there are no locks (or
threads) in the standard.  Most of the implementations I'm
familiar with do not use locks even in multithreaded
environments.

And it probably is the wrong level anyway.

[snip]

If the types are different, and the compiler is conform, he
probably will.


I certainly hope not.  That wouldn't be conform.  (I presume, of
course, that the compiler will only do so if the objects are
PODs as well.  Otherwise, the code won't be identical.)

I believe you are wrong.

Despite the fact that the member functions of v1, v2 and v3 are
guaranteed to have different addresses?

None of the compilers I use do this (at least not to my
knowledge).

That must be because you do not use VC 8.0 (or 9.0). And I really do
not see any reason to disallow std::vector<int>ush_back to have an
adress that equals e.g. std::vector<unsigned>ush_back. How are you
going to detect that in the first place?

[snip]

/Peter

 

[peter koch]

Very few do, and it's difficult to do it and still be standard
conform.


Why not?  I've worked on machines where they did, and I think
some of them are still being sold today.  A void* must be able
to hold any pointer type, including a char*.


I'm not sure what that means.  Pointers aren't necessarily
indexes, and when they are, they don't necessarily "index"
bytes.  Some common architectures, even today, have segmented
architectures, and word addressed machines still exist.

And that includes the CPU most of us use to read this newsgroup with.
Intels processors have used a segmented architecture since the 286,
and are capable of adressing more than 4GB of memory. If you program
under Windows you are even able to exploit this adress space, but as I
never tried to do so, I am not aware if this is done by reintroducing
the segmented adresses space.

/Peter

 

[Bo Persson]

(e-mail address removed) wrote:
[...]

I am implementing a lockless queue, which I don't think
the std::queue<T*> provides.

You'd have to see the documentation for your implementation, but
by default, std::queue is lockless, since there are no locks (or
threads) in the standard. Most of the implementations I'm
familiar with do not use locks even in multithreaded
environments.

And it probably is the wrong level anyway.

[snip]

If the types are different, and the compiler is conform, he
probably will.


I certainly hope not. That wouldn't be conform. (I presume, of
course, that the compiler will only do so if the objects are
PODs as well. Otherwise, the code won't be identical.)

I believe you are wrong.

Despite the fact that the member functions of v1, v2 and v3 are
guaranteed to have different addresses?

None of the compilers I use do this (at least not to my
knowledge).

That must be because you do not use VC 8.0 (or 9.0). And I really do
not see any reason to disallow std::vector<int>ush_back to have an
adress that equals e.g. std::vector<unsigned>ush_back. How are you
going to detect that in the first place?

Like James says, he can take the address of the functions and compare.
Different objects must have different addresses, including functions.

The merging of the code is really designed to solve the problem of
having vector<int>:ush_back instantiated in several different
translation units. The linker tries to fix this by only keeping one
copy of each identical code block. That this also merges code blocks
for different types of equal size, is by accident.


There are other conformance problems that bother me a lot more than
this.



Bo Persson

 

[peter koch]

(e-mail address removed) wrote:
[...]
I am implementing a lockless queue, which I don't think
the std::queue<T*> provides.
You'd have to see the documentation for your implementation, but
by default, std::queue is lockless, since there are no locks (or
threads) in the standard. Most of the implementations I'm
familiar with do not use locks even in multithreaded
environments.

And it probably is the wrong level anyway.

[snip]

If the types are different, and the compiler is conform, he
probably will.
On the compiler I use, templates will most often share code for
objects of the same size, as the linker will merge identical code
blocks.
I certainly hope not. That wouldn't be conform. (I presume, of
course, that the compiler will only do so if the objects are
PODs as well. Otherwise, the code won't be identical.)

I believe you are wrong.

That must be because you do not use VC 8.0 (or 9.0). And I really do
not see any reason to disallow std::vector<int>ush_back to have an
adress that equals e.g. std::vector<unsigned>ush_back. How are you
going to detect that in the first place?

Like James says, he can take the address of the functions and compare.
Different objects must have different addresses, including functions.

But you compare two different types. I do know that for two objects of
the same type, if their adress compares equal, the adresses must refer
to the same object. But thus is not the same situation: you can't
directly compare a void f(int) and a void f(long). Without really
knowing (and bothering!) the standard in this respect, I am quite
confident that to compare you do need some quite heavy casting.

The merging of the code is really designed to solve the problem of
having vector<int>:ush_back instantiated in several different
translation units. The linker tries to fix this by only keeping one
copy of each identical code block. That this also merges code blocks
for different types of equal size, is by accident.

I believe you are wrong. This certainly is not by accident as there
are different mechanisms involved. To remove different occurences of
the same function, you typically mark the function as discardable:
when during linking, the second definition of the function shows up,
you discard the new function instead of giving an error-message.
For removing different functions that generate the same code, you
probably calculate the hash-value of the code. When you find two
functions with the same hash-value, you compare the individual
opcodes: if they are similar, one function is - as above discarded.
Notice that a true duplication of code (define a non-inline function
in a header and include that header in more then one compilation unit)
still gives linker-errors.

/Peter

 

[James Kanze]

(e-mail address removed) wrote:
[...]
I certainly hope not. That wouldn't be conform. (I presume, of
course, that the compiler will only do so if the objects are
PODs as well. Otherwise, the code won't be identical.)
I believe you are wrong.

I'm sure I'm not. The issue has been discussed before.

But you compare two different types. I do know that for two
objects of the same type, if their adress compares equal, the
adresses must refer to the same object.

This is true for objects of different types as well, as long as
they are complete objects (e.g. not base classes or members of a
class or union). Except, of course, objects with different
complete types must be different objects.

But thus is not the same situation: you can't directly compare
a void f(int) and a void f(long). Without really knowing (and
bothering!) the standard in this respect, I am quite confident
that to compare you do need some quite heavy casting.

You need some casting, yes. In the case of objects, you don't,
because pointers to objects convert implicitly to void*. In the
case of pointers to function and all pointers to members, you
need some casting. But the guarantees still hold.

About the only case this might be useful in practice, I think,
is in some very advanced forms of template metaprogramming,
where you don't know the types to begin with (except that they
are e.g. pointers to a member function). And even then, I'm not
sure that it would be that useful. But the standard explicitly
guarantees it.

I believe you are wrong. This certainly is not by accident as
there are different mechanisms involved.

You're right about that. The first depends on "weak
references"; the linker ignores any weak references if the
extern has already been resolved. Even if the functions aren't
identical. (That could be a result of undefined behavior, but
it could also be because you compiled some of the instances with
optimization, and others without.)

To remove different occurences of the same function, you
typically mark the function as discardable: when during
linking, the second definition of the function shows up, you
discard the new function instead of giving an error-message.
For removing different functions that generate the same code,
you probably calculate the hash-value of the code. When you
find two functions with the same hash-value, you compare the
individual opcodes: if they are similar, one function is - as
above discarded. Notice that a true duplication of code
(define a non-inline function in a header and include that
header in more then one compilation unit) still gives
linker-errors.

Yes. It's also possible to arrange things so that the addresses
are different (e.g. by inserting more or less no-ops before the
function). But I've never seen a compiler which did this, and
given the size of memory today, I doubt that it's an
optimization with a particularly high priority. (It also has
the problem that it involves the linker, which means that there
can be political problems involved in implementing it.)

In the end, of course, the reason you factor out the common
behavior today is generally because you don't want complex code
to be generic (more difficult to debug and maintain), and you
definitely don't want it in a header (and most compilers still
don't implement export).

 

[gpderetta]

[...]
Yes. It's also possible to arrange things so that the addresses
are different (e.g. by inserting more or less no-ops before the
function). But I've never seen a compiler which did this, and
given the size of memory today, I doubt that it's an
optimization with a particularly high priority. (It also has
the problem that it involves the linker, which means that there
can be political problems involved in implementing it.)

GCC 4.3 has -frtl-abstract-sequences, but I think that currently
it doesn't work across translation units (i.e. it is a pure
compiler thing).

OTOH, in theory it does more than collapse common functions:
it can collapse any sequence of common instructions (a subset
of a function or more than one function).