stack

The entangling sentence refers to what was being described in the previous paragraph. You only have so much memory in a computer. In order to run a program you need to load the program into memory. You also need a place to store data. In the old days, you'd stick the program on one end of memory. One way to visualize things is like this:

+------------+-------------------------------------------------------------+|program code|                                                             |+------------+-------------------------------------------------------------+

When you run a function, you need to stick data for that function on the other side of memory. This data includes local variables and some bookkeeping information like where the function was called from.

+------------+---------------------------------------------------------+---+|program code|                                                         |###|+------------+---------------------------------------------------------+---+                                                                         ^                                                              function data

If the function called another function, the second function would get a block of memory right next to the first function's data.

                                                           function 2 data                                                                    \/+------------+-----------------------------------------------------+---+---+|program code|                                                     |###|###|+------------+-----------------------------------------------------+---+---+                                                                         ^                                                            function 1 data

If function 2 calls another function, then it's data gets added next to function 2's.

                                                           function 2 data                                                                    \/+------------+-------------------------------------------------+---+---+---+|program code|                                                 |###|###|###|+------------+-------------------------------------------------+---+---+---+                                                                 ^       ^                                                    function 3 data      |                                                                         |                                                            function 1 data

If function 3 returned, then it's data would no longer be needed.

                                                           function 2 data                                                                    \/+------------+-----------------------------------------------------+---+---+|program code|                                                     |###|###|+------------+-----------------------------------------------------+---+---+                                                                         ^                                                            function 1 data

Since a function can't return before the functions it called has returned, the data is allocated in a last in, first out manner, which is like a stack of dishes: If you want to take off the dish on the bottom you need to take all the dishes off the top first.

Now let's say that we've called a lot of functions (or one function recursively a lot).

+------------+-+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+|program code| |###|###|###|###|###|###|###|###|###|###|###|###|###|###|###|+------------+-+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Now while I've drawn each of the stack blocks the same size, in real situations, each function usually uses up a different amount of memory. Now let's call one more function.

+----------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+|program co|###|###|###|###|###|###|###|###|###|###|###|###|###|###|###|###|+----------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Thwack! Now we've written over the program code. This is a bad thing, and is what he was talking about with regard to stack entangling with code.

Thankfully, this isn't how code and data is arranged in modern computer systems.

Quote:

Original post by TheTroll Let me see if I can explain this. One of the problems with memory is that when you try to grow it to a larger size you might end up with memory fragmentation, that means that it is no longer a contentious block of memory. Well with LIFO (last in first out) of the stack, memory fragmentation could lead to data memory getting mixed in with your program code.

This conflates a number of issues and really isn't accurate to the point where I have trouble identifying a place to start.

Ok, in all systems, the stack doesn't suffer from memory fragmentation; it's allocated in a contiguous block. Stack members may refer to objects in code, static memory or heap memory, but this isn't fragmentation, just lack of spatial locality. For fragmentation you need to either allocate memory you never intend to use (internal fragmentation) or you need to have spaces between memory you have allocated (external fragmentation). Neither applies to the stack.

In really old systems, the stack is allocated in a fixed location and grows in one direction, usually towards where the code is placed. When the stack gets too big, it clobbers the code.

In C#, speaking in broad, general terms, the heap can suffer from memory fragmentation, but because of .NET's garbage collection it doesn't. Each thread has its own stack, and the memory for the stack is pre-allocated up front. If a given thread exceeds its allocated space you get a StackOverflowException.

Quote:

The stack holds both your program code and your stack data. So the design of the stack is to make sure to keep the two separate and in a continuous block.

The stack generally doesn't hold code, and never does in C#. (In less safe languages there are evil things you can do with runtime code generation and the stack, but none of those can be done in .NET)

Quote:

Original post by SiCraneIf a given thread exceeds its allocated space you get a StackOverflowException.

Has anyone ever experienced a situation where they have needed more space than the stack allows? Like if you needed to call a recursive function so many times that it caused an overflow, but it was a perfectly valid (read: not heading to infinity) thread of execution?

Or is the stack big enough so it never happens?

That is what I get for answering questions at 4:00 am with little sleep.

theTroll

Quote:

Original post by Endar Quote: Original post by SiCraneIf a given thread exceeds its allocated space you get a StackOverflowException. Has anyone ever experienced a situation where they have needed more space than the stack allows? Like if you needed to call a recursive function so many times that it caused an overflow, but it was a perfectly valid (read: not heading to infinity) thread of execution? Or is the stack big enough so it never happens?

I have done this in my AI class while trying to write a TicTacToe player (in Java, see below) and IIRC, the stack can grow larger so long as the Operating System will give the executing process more memory. Once the OS determines that it cannot give up any more memory to the process the exception is raised. So basically, if your computer has enough free memory to run the recursive function until it exits then it will otherwise it raises an exception.

One final thing, the Java Virtual Machine (or JVM) has a predefined upper limit that cannot be exceeded on the amount of memory it uses. So using the same recursive function in Java with the JVM you could theoretically run into a situation where your computer still has memory out there but the JVM will refuse to ask for it. The CLR (the virtual machine for C#) has no upper limit on the amount of memory that it can ask for.

That's not really right either. In Win32, there's a section in the executable header that specifies the stack size threads receive when threads start up. This has two components: the reserved and committed size. The operating system then sets aside amount of the address space equal to the reserve size and then commits an amount of memory equal to the commit size. Diagram:

+--------------+---+-----------------+----------+-----------------+| Other memory |   | Reserved memory |          | Other allocated |+--------------+---+-----------------+----------+-----------------+                 ^                        ^Committed stack memory         Other unallocated address space (This may not exist)

The stack data is placed into committed memory. As the stack grows, it will run out of committed memory. At this point the operating system will then commit additional memory from the reserved memory.

+--------------+-------+-------------+----------+-----------------+| Other memory |       |erved memory |          | Other allocated |+--------------+-------+-------------+----------+-----------------+                 ^                        ^Committed stack memory         Other unallocated address space

Eventually, if the stack keeps growing, it'll eat up the reserved memory.

+--------------+---------------------+----------+-----------------+| Other memory |                     |          | Other allocated |+--------------+---------------------+----------+-----------------+                 ^                        ^Committed stack memory         Other unallocated address space

At this point if the stack needs to grow one of two things will happen: In Windows 95/98/ME you have a stack overflow. On an NT machine (including 2000, XP and basically everything but 95/98/ME) if the stack needs to grow further it eats into any unallocated address space next to the stack, if any exists.

+--------------+--------------------------------+-----------------+| Other memory | Committed stack memory         | Other allocated |+--------------+--------------------------------+-----------------+

Once it uses that up, then the stack can grow no further no matter how much free physical or even virtual memory is available to the computer. This applies both to native and managed applications.

From the link given to me for further reference about stack and heap:

http://www.c-sharpcorner.com/UploadFile/rmcochran/csharp_memory01122006130034PM/csharp_memory.aspx

Quote:

If we have the following MyInt class (which is a Reference Type because it is a class): public class MyInt { public int MyValue; } and the following method is executing: public MyInt AddFive(int pValue) { MyInt result = new MyInt(); result.MyValue = pValue + 5; return result; }

The method, it is a constructor no? Because it has the same name as the class? Could someone break that down for me, please?

Also,

Quote:

public int ReturnValue() { int x = new int(); x = 3; int y = new int(); y = x; y = 4; return x; }

It looks like he's creating value type variables the same way that reference type variables are created(I mean from what I've seen from the book so far). Just like the creation of an object.
So, when I saw this for variables;
int x = 4;
was a shortcut?
Object ThisObject = new Object();
I guess it was just something to consider...

Quote:

Original post by foolios The method, it is a constructor no?

No.

Quote:

Because it has the same name as the class?

Only it doesn't have the same name as the class. It's named 'AddFive'.

Quote:

Could someone break that down for me, please?

public MyInt AddFive(int pValue)

public - The modifier to say that anyone anywhere may call the method.
MyInt - The return type. This method will return a reference to a MyInt. (because the return type MyInt is a class)
AddFive - The name of the method.
int - The type of the first parameter that should be specified when calling the method.
pValue - A poor name for the first parameter that AddFive accepts.

MyInt result = new MyInt();
Create a new reference to a MyInt named 'result'. Create a new instance of MyInt, and make result refer to it.

result.MyValue = pValue + 5;
Take the value of pValue, add 5 to it, and copy that value into result's MyValue.

return result;
Return result to the calling location.

Quote:

It looks like he's creating value type variables the same way that reference type variables are created(I mean from what I've seen from the book so far). Just like the creation of an object. So, when I saw this for variables; int x = 4; was a shortcut?

... for all practical purposes.

ooooooohhhhh

Quote:

MyInt - The return type

awe man! That tricked me!

Thank you so much!