Sunday, April 17, 2016

Digest for comp.lang.c++@googlegroups.com - 18 updates in 2 topics

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 17 01:38AM +0200

On 17.04.2016 01:05, Jens Thoms Toerring wrote:
>> stack in the expected order to ensure that the dtors are invoked in
>> the correct order?
 
> Sorry, but you can't.
 
Right.
 
 
> The compiler can, more ore less, put any object whereever it likes.
 
C++ provides a guaranteed ordering for data members with the same access
level.
 
 
> Actually, neither the C nor C++ standard even mandate that there's a
> stack at all
 
Wrong (to the degree that nonsense can be said to be wrong, but it might
more correct to say that it's not even wrong).
 
Possibly you mean that they don't specify the stack implementation,
whether it's a linked list or an ordinary machine stack or what.
 
But both languages support recursive function calls with automatic local
variables: in the general case this is impossible without a stack.
 
 
> how could be there a requirement on how things have to be organized
> on the stack?
 
There is the general stack requirement, last-in-first-out, which is the
definition of a stack.
 
However. this applies, as a logical necessity, to allocations of
function call frames, not to allocations of individual local variables.
 
I suspect the OP mistakenly thought the stack behavior for allocation
was required for individual automatic storage local variables, since
their constructor and destructor calls are in LIFO order.
 
 
Cheers & hth.,
 
- Alf
Kalle Olavi Niemitalo <kon@iki.fi>: Apr 17 02:33AM +0300


> Any idea as to why it appears that the double ** variable is
> put on stack before the double * variable ?
 
If the variables are not part of the same object, then the
language doesn't specify where they are located in memory
relative to each other.
(IIRC, built-in pointer comparisons like &a < &b are undefined
in such cases, but std::less<void*>()(&a, &b) is fine.)
You can do the following though,
 
int main()
{
struct {
double myArray[10];
double * dblePtr;
double ** dblePtrToPtr;
} vars;
// then use vars.myArray, etc.
}
 
and the addresses will then stay in declaration order.
(If not all data members were public, then the order
might be different.)
Bob Langelaan <bobl0456@gmail.com>: Apr 16 05:36PM -0700

On Saturday, April 16, 2016 at 4:38:24 PM UTC-7, Alf P. Steinbach wrote:
> their constructor and destructor calls are in LIFO order.
 
> Cheers & hth.,
 
> - Alf
 
Thank you to all the people who have replied.
 
I would like to ask a question in regards to the last paragraph that Alf posted. If I interpret it correctly, that even though "constructor and destructor calls are in LIFO order", I should not assume that the automatic local variables are in fact stored on some form of a stack? If this is the case, it seems to me that any other form of data structure would be awkward to use/implement and still have the LIFO order maintained.
 
Thanks again :)
Ben Bacarisse <ben.usenet@bsb.me.uk>: Apr 17 02:33AM +0100


> On Saturday, April 16, 2016 at 4:38:24 PM UTC-7, Alf P. Steinbach wrote:
>> On 17.04.2016 01:05, Jens Thoms Toerring wrote:
<snip>
 
>> I suspect the OP mistakenly thought the stack behavior for allocation
>> was required for individual automatic storage local variables, since
>> their constructor and destructor calls are in LIFO order.
<snip>
 
> Alf posted. If I interpret it correctly, that even though "constructor
> and destructor calls are in LIFO order", I should not assume that the
> automatic local variables are in fact stored on some form of a stack?
 
There's a lot of confusion here. Alf is not saying that. In fact he's
saying that automatic local variables will be on a stack. His point is
that just because this might be the case, it is not the mechanism by
with constructor and destructor calls are maintained. Within a function
the local object can be positioned as the compiler likes, provided the
constructors and destructors are called correctly.
 
But (and this is an aside) there is no guarantee that anything will be
stored in a stack-like structure. In the general case you do need a
LIFO structure for function calls, but if the functions are not
(mutually) recursive, only the return addresses need to be stored in a
stack like structure -- function locals could be in statically allocated
storage. And if, like in your example, there is only one function, you
don't need even that small stack-like structure.
 
Now, from a practical point of view, there is no reason for a compiler
to abandon what it must do in the general case (fully mutually recursive
function calls) and do something special when it detects that it could,
so stack allocation is to be expected, but it's not guaranteed by the
language.
 
> If this is the case, it seems to me that any other form of data
> structure would be awkward to use/implement and still have the LIFO
> order maintained.
 
When the compiler inlines a function call, one of the things it is doing
is optimising away a stack frame, but any automatic objects in the
function body must still behave correctly with the constructors and
destructors called in the right order. This is not very different to
what happens when entering a block with declared objects.
 
Remember that construction is really initialisation. The compiler will
often allocate one area for an object and then call the constructor many
times to simulate objects coming and going:
 
void f()
{
...
while (...) {
A a(42);
B b(43);
...
}
...
}
 
might compile to
 
void f()
{
space big enough for b;
space big enough for a;
...
while (...) {
call A's constructor(&a, 42);
call B's constructor(&b, 43);
...
call B's destructor;
call A's destructor;
}
...
}
 
Here the constructor/destructor order is maintained with no relation to
stack pushing and popping or relative addresses.
 
--
Ben.
Bob Langelaan <bobl0456@gmail.com>: Apr 16 08:13PM -0700

On Saturday, April 16, 2016 at 6:36:11 PM UTC-7, Ben Bacarisse wrote:
> stack pushing and popping or relative addresses.
 
> --
> Ben.
 
Thanks Ben. Very clear. You could/should be an instructor :)
 
Bob
Kalle Olavi Niemitalo <kon@iki.fi>: Apr 17 09:55AM +0300


> Now, from a practical point of view, there is no reason for a compiler
> to abandon what it must do in the general case (fully mutually recursive
> function calls) and do something special when it detects that it could,
 
That depends on the target CPU. The venerable Intel MCS-51
microcontrollers do not support a register+constant addressing
mode, so if the compiler places variables on the stack, it has to
emit additional instructions to compute the address of each
variable. The generated code becomes larger and slower.
 
I remember using a version of Keil C51 that did not support
reentrant functions and always placed local variables in
statically allocated storage. To minimize the amount of memory
needed, the linker computed a call graph and chose overlapping
locations where possible. Calls via function pointers had to be
pointed out to the linker. That compiler was for C rather than
C++ but I except a C++ compiler would have done the same thing,
and calls via virtual function tables might even be easier to
analyze than calls via program-defined function pointers.
 
Later versions of Keil C51 support reentrant functions too, but
the documentation advises that those are inefficient and should
be used sparingly.
 
http://www.keil.com/support/man/docs/c51/c51_le_reentrantfuncs.htm
http://www.keil.com/support/man/docs/lx51/lx51_in_overlaying.htm
 
One version I used had a surprising bug with C++-style // comments.
When I did
 
#define SOME_MACRO 0x28 // Decriptive comment.
int i = SOME_MACRO + 1;
 
the "+ 1;" part got commented out.
Those were the times.
David Brown <david.brown@hesbynett.no>: Apr 17 01:00PM +0200

On 17/04/16 01:38, Alf P. Steinbach wrote:
 
>> The compiler can, more ore less, put any object whereever it likes.
 
> C++ provides a guaranteed ordering for data members with the same access
> level.
 
This is trumped by the "as is" rule. C++ can re-order as much as it
likes, as long as it /appears/ to the code that the objects follow that
ordering. If you have objects that the standard says must be in a
certain order, but the code never takes the address of these objects,
then the compiler can put them wherever it likes (including holding them
in registers, or eliminating them altogether - as long as the program
logic is unchanged).
 
>> stack at all
 
> Wrong (to the degree that nonsense can be said to be wrong, but it might
> more correct to say that it's not even wrong).
 
No, he is correct - there is no requirement for a stack. C is used on
small microcontrollers that don't have any sensible support for a stack,
though it is rare to see C++ on such systems. There are odd processor
architectures with no stack, or with multiple stacks, that have at least
C compilers - and there is no fundamental reason for them not to have
C++ compilers.
 
Having a stack is typically the easiest way to implement the
requirements of C and C++ - but it is not the only way.
 
> whether it's a linked list or an ordinary machine stack or what.
 
> But both languages support recursive function calls with automatic local
> variables: in the general case this is impossible without a stack.
 
It is perfectly possible to implement recursive functions without a
stack - a linked list, as you mentioned above, is /not/ a stack. It is
perfectly legal for a compiler to analyse the source code, see that the
recursive functions in use have a maximum depth of 3, and allocate 3
sets of fixed statically allocated data space for their variables. In
the general case, a stack is far and away the easiest and most efficient
way to handle recursive functions (and many other features of C and
C++), but it is not required.
 
For example, on an 8051, a C compiler will usually not generate any data
stack for most programs.
 
 
> I suspect the OP mistakenly thought the stack behavior for allocation
> was required for individual automatic storage local variables, since
> their constructor and destructor calls are in LIFO order.
 
Yes - position on the stack (assuming you have one) has no influence on
the logical allocation order of data, which is the important ordering
for constructor and destructor ordering.
 
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 17 09:24PM +0200

On 17.04.2016 13:00, David Brown wrote:
> a linked list, as you mentioned above, is /not/ a stack.
 
It seems there's an outbreak of nonsense today. This is the third, if
not fourth, nonsense statement I've seen today. Presumably the above
(plus the rest, but I chose this little part) seemed to make perfect
sense to you when you wrote it, and perhaps still!, so I'll spell it out
for you: you're arguing that one can't implement a stack with a linked
list, and I'm very sorry, but that's complete idiocy.
 
 
Cheers & hth.,
 
- Alf
David Brown <david.brown@hesbynett.no>: Apr 17 10:09PM +0200

On 17/04/16 21:24, Alf P. Steinbach wrote:
> sense to you when you wrote it, and perhaps still!, so I'll spell it out
> for you: you're arguing that one can't implement a stack with a linked
> list, and I'm very sorry, but that's complete idiocy.
 
You can use a linked list to implement a stack, yes. You can even do so
using a singly linked list, though it will be very inefficient.
 
But in the context of the low-level aspects of compiler code generation,
or of basic cpu features, "stack" has a particular meaning other than
simply "something that implements the API of a LIFO". The key features
of a stack, in this context, are a contiguous block of memory and a
"stack pointer" that indicates the current depth of the stack.
Additional features may include limit markers, access protection, etc.
Granted, this is a particular way of implementing a more general stack -
but it is this single particular implementation that is meant here.
Vir Campestris <vir.campestris@invalid.invalid>: Apr 17 09:19PM +0100

On 16/04/2016 22:15, Bob Langelaan wrote:
 
> Address of dblePtrToPtr is: 0033FE0C
 
> Size of dblePtr: 4
> Press any key to continue . . .
 
Having read right the way up to 2109 today...
 
AIUI (and there are people here who are able to correct me if I am
wrong) the compiler's quite entitled to stick some/all of those
variables in registers - in which case they don't really have an
address, and certainly aren't on a stack. So by asking for an address
you're actually constraining the compiler's optimisation.
 
Andy
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 17 10:54PM +0200

On 17.04.2016 22:09, David Brown wrote:
>> for you: you're arguing that one can't implement a stack with a linked
>> list, and I'm very sorry, but that's complete idiocy.
 
> You can use a linked list to implement a stack, yes.
 
Right.
 
 
> You can even do so
> using a singly linked list, though it will be very inefficient.
 
I'm sorry, that's more nonsense.
 
There is an [1]inefficiency of dynamic allocation of different size
chunks, forced by different size stack frames.
 
But that has nothing to do with [2]singly linked versus double or
multiply linked.
 
 
> But in the context of the low-level aspects of compiler code generation,
> or of basic cpu features, "stack" has a particular meaning other than
> simply "something that implements the API of a LIFO".
 
Generally right, but
 
• in the context of Norwegian, which is also irrelevant, "stakk" is an
old word that means a skirt;
 
• in the context of restaurant kitchens, …
 
 
Cheers & hth.,
 
- Alf
 
Notes:
 
[1] That is, inefficiency compared to an array implementation where an
array implementation is applicable. Which currently is most common. An
example where an array implementation of the C/C++ stack probably won't
do, is a (sufficiently) large number of co-routines or threads where at
least some of them use general recursion. Then a linked implementation
can conceivably and probably be more efficient.
 
[2] Indeed, contrary to your statement, since double linking requires
twice the number of link updates, and M times the overhead for M links
per node, the singly linked list is /slightly more efficient/. However,
even though that fact has rhetorical value, the link maintenance
overhead is peanuts compared to the dynamic allocation overhead. The
mention of singly linked is simply not meaningful.
Jerry Stuckle <jstucklex@attglobal.net>: Apr 17 05:27PM -0400

On 4/17/2016 4:09 PM, David Brown wrote:
> Additional features may include limit markers, access protection, etc.
> Granted, this is a particular way of implementing a more general stack -
> but it is this single particular implementation that is meant here.
 
If what you say is true, then you couldn't run C on IBM mainframes -
which have no hardware stack or assembler instructions which support a
stack.
 
On these systems, automatic allocation is implemented with a linked
list. There is no "stack pointer that indicates the current depth of
the stack".
 
But obviously you CAN run C programs (and even Linux) on these machines.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
Robert Wessel <robertwessel2@yahoo.com>: Apr 17 04:54PM -0500

On Sun, 17 Apr 2016 22:09:06 +0200, David Brown
>> list, and I'm very sorry, but that's complete idiocy.
 
>You can use a linked list to implement a stack, yes. You can even do so
>using a singly linked list, though it will be very inefficient.
 
 
Why? Assuming the usual usage pattern for a stack (where you can add
or remove things only from the top, and possible peek a few items down
from the top), why would you need more than a singly-linked list,
starting from the topmost element?
 
 
>Additional features may include limit markers, access protection, etc.
>Granted, this is a particular way of implementing a more general stack -
>but it is this single particular implementation that is meant here.
 
 
The word means both things. The C standard clearly specifies certain
behaviors that require a stack in the general LIFO sense. On some
implementations that's implemented on the traditional (x86-like)
hardware stack. The former is required for a full implementation of
C, at least for some programs, the latter is an implementation detail
(and *not* a universal one*). Failing to distinguish between the two
leads to long and silly Usenet debates.
 
 
*There have been implementations that use a linked-list-based stack
(some S/360 family implementations, for example), and implementations
that use multiple parallel stacks (SPARC and IPF, for example) to
implement the one "stack" required by the C standard.
Robert Wessel <robertwessel2@yahoo.com>: Apr 17 05:00PM -0500

On Sun, 17 Apr 2016 17:27:38 -0400, Jerry Stuckle
 
>On these systems, automatic allocation is implemented with a linked
>list. There is no "stack pointer that indicates the current depth of
>the stack".
 
 
Sometimes, sometimes not. Most of the C compilers for mainframes will
use a more contiguous stack for much of the code, and use the S/360
traditional linked-list (R13-based) mechanism only for functions that
call or are called from outside. Forcing the traditional (and quite
slow) mechanism for the very many calls to very short routines common
in C would be very painful. Obviously there are no "real" stack
manipulation instructions (discounting the unrelated stacking Program
Call instructions), but adding and subtracting to/from a register is
hardly a big deal. But yes, most C code being executed on S/360
family machines uses a stack structure very similar to that used by
typical x86 implementations. As do many of the implementations on
RISCs that also lack hardware stacks.
jt@toerring.de (Jens Thoms Toerring): Apr 17 10:28PM


> • in the context of Norwegian, which is also irrelevant, "stakk" is an
> old word that means a skirt;
 
> • in the context of restaurant kitchens, …
 
What's bitten you? The OP mentioned "stack" and it was clear (at
least to me) from the context that he didn't mean some abstract
implementation of a LIFO but the "stack" that most people with
some knowledge about common hardware know about (and some assume
to be the only way it can be done), i.e. the one that is made up
of (at least) a piece of memory and a stack pointer.
 
All I tried to express was that such a "stack" isn't something
that's prescribed by the standard and that it's thus not rea-
sonable to expect some order of creation of local variables in
memory that would only make sense (if it were mandated) if such
a "stack" were required.
Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
jt@toerring.de (Jens Thoms Toerring): Apr 17 10:38PM

> > Address of myArray is: 0033FE10
> > Address of dblePtr is: 0033FE08
> > Address of dblePtrToPtr is: 0033FE0C
 
Another point: stacks can grow either from lower to higher addres-
ses or the other way round. What would be the "expected ordering"
if the stack grows from high to low addresses? If the compiler
first "sees" variables 'A' and makes room for it on the stack and
then sees 'B' and does it again, on a system where the stack grows
from lower to higher addresses 'A' might appear at a lower address
than 'B', but on a system where the stack grows in the other direc-
tion it might be just the other way round. That's another reason
why there can't be an "expected order".
 
Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
Kalle Olavi Niemitalo <kon@iki.fi>: Apr 17 10:32AM +0300


> If you use a font for iso_8859-1 encoding XDrawstring() will
> render them as 'Ã' and '¼', but if you'd use a UTF-8 font it
> would be rendered as 'ü'.
 
I don't think UTF-8 fonts are feasible in the X11 core protocol.
http://www.x.org/releases/X11R7.7/doc/xproto/x11protocol.html#glossary
(X Window System Protocol; X Version 11, Release 7.7; Version 1.0)
says about Font, "The client simply indicates values used to
index the glyph array." These values are 1-byte or 2-byte.
If you used UTF-8 there, it would only support U+0000 to U+07FF
(encoded as 0xDF 0xBF).
Kalle Olavi Niemitalo <kon@iki.fi>: Apr 17 09:54PM +0300


>> string test = "Hüh";
 
> in your code then what is stored in 'test' depends on what
> encoding your editor uses.
 
Even if the text in the source file is UTF-8, that doesn't mean
the bytes in the string variable will be UTF-8 too. The compiler
may recode the string. GCC nowadays has -finput-charset and
-fexec-charset options for controlling this, and Microsoft's
compiler likewise has /source-charset and /execution-charset:
https://blogs.msdn.microsoft.com/vcblog/2016/02/22/new-options-for-managing-character-sets-in-the-microsoft-cc-compiler/
 
For example, if the source code says "Hüh" and you use
g++ -fexec-charset=EBCDIC-AT-DE, then the string will contain
{ 0xC8, 0xD0, 0x88 } at run time. But if the source code
says u8"Hüh", then you get the UTF-8 { 0x48, 0xC3, 0xBC, 0x68 }
regardless of the execution character set.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)