• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
MilchoPenchev

Goto and Loops - NOT a goto discussion

20 posts in this topic

First - this isn't meant as a question whether using gotos is appropriate to use in an OO langauge. That's been overdone, so please don't let it degenerate to that type of discussion.

 

I DID however use a goto recently in a nested loop to escape it, and it got me thinking about the variables used in a loop, and the flow.

 

I tested the following minimal, working, c++ code:

#include <iostream>
using namespace std;

int main ()
{
  if (true)
  {
    for ( int i = 0 ; i < 3; i++)
    {
    looped:
      cout << i << " ";
    }
  }
  cout << "\nexit loop\n";
  int j = -1;
  // cout << i; // does not compile, obviously as expected
  goto looped;
}

 

This actually ends up printing:

 

0
1
2
exit loop
3
exit loop
4
exit loop
5
exit loop
6

 

And so on, forever

So... I expected i to be popped off the stack once the loop exited naturally (the first time), and the declaration of j to replace it on the stack. 

I'm using Visual Studio 2012 Express to test this. I haven't tested it on anything else yet. Why does it look like the declaration of i isn't popped off the stack at all?

 

This also makes me wonder what happens when I use a goto to escape the loop - does the variable declared in the loop's header stay on the stack? It seems like it should, but after this experiment, I'm not feeling too confident in how I know the stack to work.

 

Anyone have any comments?

2

Share this post


Link to post
Share on other sites
I'll take a punt on "undefined behaviour". Typically the stack pointer is set up only once per function, not once per scope (i.e. the curly brackets), and the compiler could share the same stack location for i and j, maybe the goto has made it realise you jump into another scope so it doesn't? Did you test it in release mode/optimisations on as well?

It definitely wouldn't work like that if there was a nontrivial destructor for i...
0

Share this post


Link to post
Share on other sites
I'll take a punt on "undefined behaviour". Typically the stack pointer is set up only once per function, not once per scope (i.e. the curly brackets), and the compiler could share the same stack location for i and j, maybe the goto has made it realise you jump into another scope so it doesn't? Did you test it in release mode/optimisations on as well?

It definitely wouldn't work like that if there was a nontrivial destructor for i...

 

I was testing this in release mode - as for optimizations /OPT:REF is set, but that's only supposed to be to eliminate variables that are never referenced, not to keep variables like that.

 

 

But then, based on your last line, I tried this code (also fixing my lack of return statement in main... shame on me :) )

#include <iostream>
using namespace std;

class Nontrivial
{
public:
Nontrivial () { i = 0; }
~Nontrivial () { i = -100; }
int i;
};

int main ()
{
  if (true)
  {
    for ( Nontrivial n; n.i < 3; n.i++)
    {
      looped:
      cout << n.i << " ";
    }
  }
  cout << "\nexit loop\n";
  int j = -1;
  // cout << i; // does not compile
  goto looped;
  return 0;
}

This.... didn't compile at all:

 

Error 1 error C2362: initialization of 'n' is skipped by 'goto looped' 

Yeah.... 
 

0

Share this post


Link to post
Share on other sites
This should be totally well-defined AFAIK.

The lifetime of the stack slot is an implementation detail; the language semantics only care about the lifetime of the data placed in that slot. If you place a variable definition inside a loop, it'd be wasteful to push and pop the stack every loop iteration to reserve stack space for the variable; as an optimization, it is common to reserve all needed stack space in a single shot when entering a function, and clean it all up in one pop at the end. (Note that this depends on calling conventions and other details.)

If you put an object with nontrivial construction/destruction in place of a primitive, the compiler will construct and destruct it on scope entry/exit as you would expect. It will typically reuse stack slots as far as is safe, but since you can easily construct cases that can't be statically proven safe, the compiler will often not reuse stack slots specifically to avoid mashing two things into the same slot.


[edit] The reason this fails with your nontrivial example is that the compiler can't statically figure out how to safely construct the object for every possible flow scenario. Edited by ApochPiQ
2

Share this post


Link to post
Share on other sites
Why does it look like the declaration of i isn't popped off the stack at all?
Because you never left the function. The stack pointer won’t be modified until you enter or exit a function.
And what you are seeing is undefined behavior. When it goes back into the loop it simply takes the value at the address of “i” and keeps working on it.

Not to confuse you further, but nothing really “leaves” the stack. It is just a series of addresses and a pointer to somewhere in them that gets shifted up and down as you enter/leave functions.
The pointer gets shifted but the data all over the stack is not changed when this happens. Through undefined behavior and hacks you can access values on the stack from the caller of your current function, for example. You can also modify values “ahead” of your current stack position and change data that the next function you call will use.

You are basically associating scopes with stacks. This is wrong. Scopes are a language constraint. Just because a variable goes out of scope does not mean the stack gets modified in any way (destructors can cause this to happen though). Nothing happens to “i” just because you leave the for-loop.


L. Spiro

 

Ok, I understand that nothing "leaves" the stack, no confusion there :). That's why I had put in the declaration of j. But the fact that the stack is allocated/deallocated on a per-function basis would actually explain this, I suppose.

0

Share this post


Link to post
Share on other sites
main is the only function that returns a value that you are allowed to skip the return statement ;) It implicitly returns 0 if you omit it.
0

Share this post


Link to post
Share on other sites
Actually, this is a should-have-failed-to-compile situation according to the standard. If you jump into a block where a variable with automatic storage duration with an initializer is in scope from a place where it isn't in scope, the program is ill-formed. (Relevant section is 6.7 of all of C++98, C++03 and C++11.) MSVC permits this as an extension. If you disable language extensions it fails to compile with a C2362.

Yes, you're correct, disabling language extensions I get the "initialization skipped" error.

Oddly however, I left the loop definition like this, without initializing i to 0:

for ( int i; i < 3; i++)

and it compiled. Value of i was obviously random, but it compiled and ran just fine, printing a random number and continuously incrementing it.

 

I don't know why I had the idea that the stack was dealt with inside a function, instead of only on a function level. I suppose language syntax and scoping rules made me assume it worked like that, but in retrospect, I don't think I've read anything to indicate it.

0

Share this post


Link to post
Share on other sites
Welcome to undefined behavior: stuff that makes zero sense, compiles, runs, and might (if you're lucky) indicate something is broken before it's too late.
0

Share this post


Link to post
Share on other sites
Oddly however, I left the loop definition like this, without initializing i to 0:
for ( int i; i < 3; i++)
and it compiled.


As I said, it's illegal to jump in a block with an automatic variable with an initializer. If it's a POD type, like an int, without an initializer, it's legal to jump into a block that contains it. In C++98/03 it's illegal to jump into a scope with a non-POD type with or without an intializer. In C++11 the rules are basically the same, but are described in a more complex manner because of the shades of what is considered POD.
0

Share this post


Link to post
Share on other sites
I don't know why I had the idea that the stack was dealt with inside a function, instead of only on a function level. I suppose language syntax and scoping rules made me assume it worked like that, but in retrospect, I don't think I've read anything to indicate it.

It's a sensible assumption about the implementation of the underlying C++ memory model.  There is in fact nothing in C++ that mandates the use of a stack for anything.  It is quite possible (provably so, because it's been done) to have a C compiler for hardware that does not support stack operations, and I imagine it's equally as possible to do so for C++. I'm not saying it wouldn't be a pain, but technically possible.

 

The very use of the common misnomers "on the stack" or "on the heap" when referring to automatic or free storage respectively can cause a good deal of confusion when people find out that's not how things really work.

1

Share this post


Link to post
Share on other sites
The very use of the common misnomers "on the stack" or "on the heap" when referring to automatic or free storage respectively can cause a good deal of confusion when people find out that's not how things really work.

 

 

How are those misnomers? If you look in the Wikipedia page about memory management, dynamic memory allocation is described as "allocating portions of a large pool of memory called the heap". The C standard doesn't mention "heap" anywhere, but it doesn't mention "free storage" either. 

 

The C standard doesn't talk about "the stack", but it also doesn't talk about "local variables". I am happy to talk about local variables in the context of the C language, and the implementation of local variables in a C compiler has to be a stack of some sort, at least if we are dealing with recursive functions. So I don't see the problem with calling this space "the stack" either. This stack doesn't have to be the same as the call stack, although that is the case in every compiler I have ever used, and when debugging some problems, it has been useful to understand something about the memory layout of these things.

 

 

I knew about the stack and the heap before I knew about C or C++, and I have a hard time using other terms. The mental pictures of the stack and the heap still serve me well, and when I ask my compiler to turn some piece of code into assembly language, it still looks like the stack and the heap are being used. I don't see why the terms used in the language description should be preferred.

 

I guess I just don't allow programming-language standards to determine how I talk about things that are larger than the programming language. For instance, a byte to me is 8 bits, but the standard specifies that a byte is whatever a char is, which could be something other than 8 bits. That might be the convention used in that document, but when I use the word "byte", I mean 8 bits.

 

While I am in rant mode, I call my .c and .cpp files "modules", and not "translation units", and I don't know anybody who uses the latter.

Edited by Álvaro
1

Share this post


Link to post
Share on other sites

As far as I understand (same as others), that should be invalid syntax. Variable 'I" should be only valid in the for loop.

Also, even it's valid syntax, I would never write that kind of code because it's so confusing. Indeed I would not spend my any time on studying "goto". I will stop here, otherwise will bring a flame war of "goto" discussion.

-1

Share this post


Link to post
Share on other sites
I don't know why I had the idea that the stack was dealt with inside a function, instead of only on a function level. I suppose language syntax and scoping rules made me assume it worked like that, but in retrospect, I don't think I've read anything to indicate it.

It's a sensible assumption about the implementation of the underlying C++ memory model.  There is in fact nothing in C++ that mandates the use of a stack for anything.  It is quite possible (provably so, because it's been done) to have a C compiler for hardware that does not support stack operations, and I imagine it's equally as possible to do so for C++. I'm not saying it wouldn't be a pain, but technically possible.

 

The very use of the common misnomers "on the stack" or "on the heap" when referring to automatic or free storage respectively can cause a good deal of confusion when people find out that's not how things really work.

 

I'm also not sure why you refer to these terms as misnomers. These terms were created for the exact purpose of the stack / heap allocation that exists on computers, they are still applicable as far as I'm know. Trying to allocate a large enough local variable will cause a crash, as you run out of space on the stack, yet using new for the same size allocation on the heap works just fine - so there's still a definite difference between the two. It has been a couple of years since I took my OS design courses, and the knowledge there is a bit simplified over the real things, but the 'on the stack' and 'on the heap' should be correctly describing of what's actually going on.

 

The major reason why I posted this is because I wanted to know about the exact specifics of of the stack management and how this specific case was handled. At any rate, I think the previous posts in this thread did describe the reasoning behind this fairly well.

0

Share this post


Link to post
Share on other sites
I'm also not sure why you refer to these terms as misnomers

The C++ standard uses his wording -- "the stack" is automatic storage and "the heap" is the free store.
"The stack" and "the heap" are just colloquialisms carried over by C programmers. Arguing that these terms are wrong is a bit of a pedantic thing to do though, like pointing out that "The STL" is wrong as should just be called the standard library, instead of just quietly admitting that you know what people mean by these phrases wink.png The point though, is that "the stack" isn't necessarily a stack, and "the heap" isn't necessarily a heap. They're abstract concepts in the C++ standard, and the implementations we're used to are concrete compiler decisions that fulfil those concepts.

Edited by Hodgman
1

Share this post


Link to post
Share on other sites

This post is similar to the one above. I am not trying to beat a dead horse, but perhaps gain some understanding. So please point out if I am wrong about anything below (which is very plausible).

 

 

The point though, is that "the stack" isn't necessarily a stack, and "the heap" isn't necessarily a heap.

 

 

How could the automatic storage not be a stack? If you have a recursive function with parameters and local variables, there must be a stack of some sort somewhere to handle different calls to the function being "active" at any given time. It might not be the x86 stack, but it has to be a stack of some sort. And the large pool of memory from which you dynamically allocate portions is called the heap, and that is just a name, not a statement of a particular implementation of the concept.

 

 

They're abstract concepts in the C++ standard, and the implementations we're used to are concrete compiler decisions that fulfil those concepts.

 

 

Although there is nothing technically wrong with that statement, I think it confuses the history of these things: A beginner will get the impression that the C++ standard was created in a vacuum and then people came along and settled on these particular implementations, as if by some sort of accident. The reality is that the implementations came first and these concepts were well established before the C++ standard was created. The C++ standard is simply a contract between the programmer and the compiler writer as to what things are guaranteed to work. I don't understand why the standard didn't use the prevailing terminology: Calling the heap "the free store" gives the impression that they are allowing more flexibility in the implementations than if they had called it "the heap", but this is not the case.

Edited by Álvaro
1

Share this post


Link to post
Share on other sites

The code won't compile using gcc:

 

 

In function "int main()":
10: error: jump to label "looped"
17: error:   from here
8: error:   skips initialization of "int i"
 
0

Share this post


Link to post
Share on other sites

[quote name='Álvaro' timestamp='1357819659' post='5019839']
How could the automatic storage not be a stack? If you have a recursive function with parameters and local variables, there must be a stack of some sort somewhere to handle different calls to the function being "active" at any given time. It might not be the x86 stack, but it has to be a stack of some sort. And the large pool of memory from which you dynamically allocate portions is called the heap, and that is just a name, not a statement of a particular implementation of the concept.
[/quote]The point about these being a misnomer is only because the standard doesn't actually use those names. "The stack" and "the heap" are what we all call them, but the standard doesn't call them that, so it's informal language.

 

The "call stack" does act like a stack (pushing and popping stack frames), and the stack data-structure can be implemented in different ways (e.g. we're used to the call-stack being an array, but it could also be a linked list). But perhaps on some particular machine it's possible to have a call-tree instead of a call-stack -- e.g. for co-routines -- such a machine could implement a standard C or C++ compiler, with it's own co-routine extensions to the language to make use of it's call-tree, which would allow for yield/resume as well as call/return, etc... It would likely use a linked-list based tree for automatic storage ("the call-stack") instead of an array-based stack.

 

"The heap" could be implemented as a heap, or many other structures. I'm not sure why we call the free-store "the heap"... maybe it was originally implemented as a heap data structure? Or maybe because there's a whole heap of bytes in it cool.png

 

n.b. I did make the point that it's awfully pedantic to argue over whether we should call it the heap or the free-store, etc... I prefer the informal colloquialisms because they're more prevalent (it's what i was taught to call them in Uni, anyway).

1

Share this post


Link to post
Share on other sites
As Hodgman pointed out, "stack" doesn't imply a particular implementation: It just means it's a data structure where you push things ("stack frames", in this case) at the top and you only ever access the top thing. Whether this is implemented by moving a pointer in an array or by using a sliding window of an array of registers (Sparc) or by a linked list, it's still a stack.
As to the phrase 'on the heap' when referring to the free store, there was never a heap in the technical computer-science sense of the word.
"Heap" means more than one thing. They are both technical computer-science definitions. Actually, the Wikipedia disambiguation page on "heap" has both meanings under "Computer Science".

I think the confusion in this thread has nothing to do with the use of the word "stack": This thread is about the futility of studying what compilers do when undefined behavior is invoked.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0