Stack vs. Heap Question, Please Help

[arcticool]

I had an interview today and I got destroyed
The question was why have a stack and a heap?
I could answer all the practical stuff like value types live on the
stack, enums are on the stack, as are structs, where classes are on
the heap... when value types go out of scope the memory is re-
allocated, object remain in memory waiting to be cleaned up by the
garbage collector, etc, but he responded 'so why not just put say a
class on the stack? why bother having a heap at all?' I said I
didn't know and he responded 'oh that's just the way of the world
then eh?' like a real smart a**. I felt pretty small. So can someone
please explain this to me so hopefully I never have to feel like
that again.
Thanks,

Jeff
--

 

[Mike]

I had an interview today and I got destroyed
The question was why have a stack and a heap?
I could answer all the practical stuff like value types live on the
stack, enums are on the stack, as are structs, where classes are on
the heap... when value types go out of scope the memory is re-
allocated, object remain in memory waiting to be cleaned up by the
garbage collector, etc, but he responded 'so why not just put say a
class on the stack? why bother having a heap at all?' I said I
didn't know and he responded 'oh that's just the way of the world
then eh?' like a real smart a**. I felt pretty small. So can someone
please explain this to me so hopefully I never have to feel like
that again.
Thanks,

You can't put everything on the stack for a simple reason -- anything on the
stack goes away when the stack unwinds (when you return from a function.)
If you kept a class instance on the stack and passed out a reference to it,
the reference would point to garbage at any point in the future after the
function defining it exits. (Or possibily even earlier, if the compiler
decides that no more references are possible.)
This is a common error in languages like C(++) -- for example, passing the
address of a stack variable to another thread and having that threa
read/write some random stack frame in the future - with obviously bad
results. This type of error is impossible in managed-only c#.

m

 

[Stephany Young]

And what was the interview in aid of?

 

[Michael Nemtsev]

Hello arcticool,

http://en.wikipedia.org/wiki/Stack_(data_structure)
http://en.wikipedia.org/wiki/Heap_(data_structure)

a> I had an interview today and I got destroyed
a> The question was why have a stack and a heap?
a> I could answer all the practical stuff like value types live on the
a> stack, enums are on the stack, as are structs, where classes are on
a> the heap... when value types go out of scope the memory is re-
a> allocated, object remain in memory waiting to be cleaned up by the
a> garbage collector, etc, but he responded 'so why not just put say a
a> class on the stack? why bother having a heap at all?' I said I
a> didn't know and he responded 'oh that's just the way of the world
a> then eh?' like a real smart a**. I felt pretty small. So can someone
a> please explain this to me so hopefully I never have to feel like
a> that again.
a> Thanks,
a> Jeff
a>
---
WBR,
Michael Nemtsev :: blog: http://spaces.msn.com/laflour

"At times one remains faithful to a cause only because its opponents do not
cease to be insipid." (c) Friedrich Nietzsch

 

[Mike]

Hello arcticool,

http://en.wikipedia.org/wiki/Stack_(data_structure)
http://en.wikipedia.org/wiki/Heap_(data_structure)

I don't think the OP was talking about Stacks and Heaps as general data
structures, but as language implementation constructs.

Jeff (OP) -- for fun you may also want to take a look at the (standard)
Forth langauge (if you're not familiar with it already) which has two
stacks - a return stack and a data stack. (Most mainstream languages
intertwine the data and call stacks.) This will give you an idea of what you
can accomplish without a heap, or classic variables for that matter. (If
looking at a big forth "word" doesn't make your brain hurt, it may be for
you!) Forth probably has the largest expressive-power /
language-implemetation-size ratio of any language, and is still pretty cool
after all these years...

m

 

[arcticool]

Mike,
Thanks for the response, though I think I need an example to grasp
your meaning. I'll see if I can put a framework down and maybe you
could show me where the class would fall off the stack.
Say for example we have a class circle that takes one arguement for
it's radius, and has an area method. It might look something like
this:

public class Circle
{
private int r;
pubic Circle(int radius)
(
r= radius;
}
public int Area()
{
return math.pie * r * r;
}
}

//and we call it from main...
class Test
{
static void main()
{
circle c = new circle(4);
int area = c.Area();
}
}

Could you please say where this would fall off the stack in your
example? Yes I am new to this all, but appreciate any help I can
get.
Thanks again,

Jeff
--

 

[arcticool]

Sorry, not sure I understand your question Stephany...
The interview was 'in aid of' my paying bills and general employment
and otherwise having something interesting to do durring the
daylight hours
--

 

[arcticool]

Michael,
Thanks for the links, I'll read up a bit.
Was 'googling' for a good sight, looks like you found it.
BTW, thanks for the quote, don't know if that's for me, but it
definitely fits right now.

Jeff
--

 

[Stephany Young]

I was asking what sort of job was it for?

I was gobsmacked that someone would actually need to ask such a question in
any reasonable interview!

 

[Larry Lard]

I had an interview today and I got destroyed
The question was why have a stack and a heap?
I could answer all the practical stuff like value types live on the
stack, enums are on the stack, as are structs, where classes are on
the heap... when value types go out of scope the memory is re-
allocated, object remain in memory waiting to be cleaned up by the
garbage collector, etc, but he responded 'so why not just put say a
class on the stack? why bother having a heap at all?' I said I
didn't know and he responded 'oh that's just the way of the world
then eh?' like a real smart a**. I felt pretty small. So can someone
please explain this to me so hopefully I never have to feel like
that again.

Well, if you are working at a sufficiently low level that such
implementation details *matter*, then you *should* know; but for many
..NET programmers writing typical business applications, I would argue
that it's really not relevant to know why to have a stack and a heap,
or even (this is controversial) _what they are_. We don't ask software
developers to know the difference between L1 and L2 cache, say, becuase
it simply doesn't matter. Similarly, as far as most business apps are
concerned, memory is just an abstract concept - we write to it, and
later, we read from it. End of story.

One could go even further and say, for example, for a programmer of
dull-as-dishwater CRUD apps, something like the difference between
O(2^n), O(n^2), and O(n log n) could be regarded as not being required
knowledge.

 

[RichS]

Hi,

Personnally I think this is a very good interview question. Memory
management is a very important topic in all programming languages and
it is important to know the potential effects of a particular
implementation approach. Even garbage collected languages ( Java, .Net
) will perform differently depending on stack vs heap memory usage.

There are a huge range of bugs / errors that can be introduced into
software if memory management is not understood ( i.e. references to
items on the stack, memory loss, etc.. ). I'm sure memory management
issues form a large percentage of real-world bugs.

As a very very basic guideline, if you wish to re-use something put it
in the heap, if it is only temporary put it on the stack.

RichS

 

[Nick Hounsome]

Well, if you are working at a sufficiently low level that such
implementation details *matter*, then you *should* know; but for many
.NET programmers writing typical business applications, I would argue
that it's really not relevant to know why to have a stack and a heap,
or even (this is controversial) _what they are_. We don't ask software
developers to know the difference between L1 and L2 cache, say, becuase
it simply doesn't matter. Similarly, as far as most business apps are
concerned, memory is just an abstract concept - we write to it, and
later, we read from it. End of story.

One could go even further and say, for example, for a programmer of
dull-as-dishwater CRUD apps, something like the difference between
O(2^n), O(n^2), and O(n log n) could be regarded as not being required
knowledge.

I disagree. Unless I have misunderstood the term reading in a large set of
data and sorting it would be CRUD and n really does matter.

Re. The stack - the only practical difference between stack and heap at the
app level is that stack is faster. This is solely because logically it
cannot become fragmented or need GC. I believe that there are or were
micro-controllers that didn't have one.

 

[Mike]

I disagree. Unless I have misunderstood the term reading in a large set of
data and sorting it would be CRUD and n really does matter.

Re. The stack - the only practical difference between stack and heap at
the app level is that stack is faster.

Not necessarily. Assuming your entity lifetime matches the defining scope of
the stack var, this may be true - but otherwise often not.
That's why many C++ programs that are improperly using value semantics run
much faster when ported to C# -
it avoids the invocation of copy constunctors, etc., every time an instance
is passed on the stack.
Sure, this may not be a properly designed program, but it not always easy to
see where this is going to happen in complex code.

Arcticool - it seems like half the responses are for stack vs. heap
*datastructures* and half were stack vs. heap memory *allocation* responses
(mine included.) These are related but really different questions -- what
where you asking??
MichaelN's great wikipedia links are regarding the fomer, whereas given your
mention of

I'm assuming the former is what you were after.

m

 

[Mike]

Mike,
Thanks for the response, though I think I need an example to grasp
your meaning. I'll see if I can put a framework down and maybe you
could show me where the class would fall off the stack.
Say for example we have a class circle that takes one arguement for
it's radius, and has an area method. It might look something like
this:

public class Circle
{
private int r;
pubic Circle(int radius)
(
r= radius;
}
public int Area()
{
return math.pie * r * r;
}
}

//and we call it from main...
class Test
{
static void main()
{
circle c = new circle(4);
int area = c.Area();
}
}

Could you please say where this would fall off the stack in your
example? Yes I am new to this all, but appreciate any help I can
get.
Thanks again,

Circle is a class, not a struct, so creation of the circle goes on the heap.
(Or so as to not confuse it with the datastructure of the same same, let's
just say the "data pool".) The *reference* to that object is stored on the
stack, inside the stackframe of "main". (Note that if your struct is
*inside* a class instance, the struct is allocated on the heap with the rest
of the class...)
When you exit "main", the stack is unwould and the reference to "c" goes
away, and seeing in this case it's the sole reference to the object in the
memory pool, our circle object will deallocated when the GC finds the time
to do so. (Ignoring any clever optimizations by the compiler.)

For "c" to be allocated on the stack in c#, it would have to be a struct. In
that case, the memory stack allocation would be enough to hold all its
memebers, not just enough for a reference (in this they're the same size)
and if you passed "c" to another function (which you don't in your example)
the enitre object would get *copied* into the stack of the called fn's
stackframe, vs. just the reference to the heap (think "pointer that you
can't change") getting copied in the "class" case. Everything in c# is
passed by value, including object *references*, as long as we ignore ref/out
parameters.

So in contrast to most languages, in c# the stack vs. memory-pool descision
is not made at the point of allocation, but at the point of object (class
vs. struct) definition.

You may also want to look at "using" and "IDispose" - it combines heap
allocation with the scope-based pattern you get with stacks.

m

 

[Kevin Spencer]

I agree that it's a good interview question, but for slightly different
reasons. The purpose of any evaluation is to measure the extent of the
knowledge and capabilities of the person being evaluated. If no difficult
questions are asked, it is more difficult to determine the upper limit of
the interviewee. As an example, imagine that people are being evaluated for
physical strength. They are given a set of weights to lift. If the heaviest
of these weights is 100 lbs, it will not be possible to determine the upper
limit of the physical strength of anyone who is able to lift the 100-lb
weight. In other words, in any evaluation, some problems must be very
difficult for almost anyone to solve in order to determine the upper limit
of anyone evaluated. The point of a good evaluation is not to determine
whether the interviewee is able to answer all of the questions correctly,
but what the upper limit of that interviewee is. It is entirely possible
that the OP was evaluated as capable of the job he or she was seeking.

--
HTH,

Kevin Spencer
Microsoft MVP
Professional Numbskull

Show me your certification without works,
and I'll show my certification
*by* my works.

 

[Jon Skeet [C# MVP]]

I had an interview today and I got destroyed
The question was why have a stack and a heap?
I could answer all the practical stuff like value types live on the
stack, enums are on the stack, as are structs, where classes are on
the heap... when value types go out of scope the memory is re-
allocated, object remain in memory waiting to be cleaned up by the
garbage collector, etc, but he responded 'so why not just put say a
class on the stack? why bother having a heap at all?' I said I
didn't know and he responded 'oh that's just the way of the world
then eh?' like a real smart a**. I felt pretty small. So can someone
please explain this to me so hopefully I never have to feel like
that again.

One quick point (I haven't got time to answer fully just now) - your
summary of "value types live on the stack" isn't true. It would suggest
that an int which is part of a reference type would live on the stack,
even though the rest of the type lived on the heap...

See http://www.pobox.com/~skeet/csharp/memory.html for a bit more on
this.

 

[Jon Skeet [C# MVP]]

Re. The stack - the only practical difference between stack and heap at the
app level is that stack is faster. This is solely because logically it
cannot become fragmented or need GC. I believe that there are or were
micro-controllers that didn't have one.

I don't know - I think that the idea of variables being on the stack or
on the heap (along with the concept of stack frames) is very important
when it comes to understanding threading, and why if two threads are
running the same method at the same time (or even a single thread
running a method recursively) they get separate local variables, but if
they access the same object on the heap, that data is shared.

Now, the low-level details of what those mean in terms of allocation
aren't terribly important IMO, but the concepts themselves are.

 

[Bruce Wood]

The sample program you gave doesn't have the right stuff to demonstrate
what Mike was talking about. Here's a similar sample that should help:

public class Circle
{
private Point _centre;
private double _radius;

public Circle(Point centre, double radius)
{
this._centre = centre;
this_radius = radius;
}

public double Radius { get { return this._radius; } }

public bool SameSize(Circle otherCircle)
{
return this._radius == otherCircle._radius;
}
}

class Test
{
static Circle Function1()
{
return new Circle(new Point(0, 0), 15.0);
}

static bool IsFifteen(Circle c)
{
return c.IsSameSize(new Circle(new Point(0, 0), 15));
}

static void Main()
{
Circle aCircle = Function1();
Console.WriteLine("Circle has radius of fifteen: {0}.",
IsFifteen(aCircle));
}
}

So, let's look at what would happen if everything were on the stack and
there were no heap. The answer is that it would mess up object
lifetimes, so that's what we're going to examine.

The first thing Main does is call Function1. It doesn't pass any
arguments, so nothing is pushed on the stack (except return addresses
and such).

Function1 instantiates a new Circle object. So, let's say that
(contrary to the way that .NET really works) this goes on the stack,
not the heap.

Function1 now returns the Circle, which really means that it returns a
reference to the Circle object by placing that reference on the stack.
So, just before Function1 exits, the stack looks something like (top to
bottom):

a Circle object
a reference to the Circle (the return value)
return addresses and other housekeeping information

I'm not so sure about where the return value sits relative to the other
items, but you get the idea.

So, now Function1 returns. In the process, the stack is unwound. So
far, we're safe: Main has a reference to the circle in aCircle (which
is also on the stack, lower down) which points to the Circle object,
which is higher up the stack.

Now Main calls IsFifteen, passing it a reference to the Circle object,
farther up the stack. The argument, a reference, is pushed on the
stack. At this point the stack may or may not have arrived at where the
original Circle is stored, but like the shark in Jaws, it's getting
awfully close.

The first thing that IsFifteen does is allocate a new Circle that it
wants to pass to the original Circle's "SameSize" method. Well, if
passing the Circle reference to IsFifteen didn't overwrite the original
Circle, this surely did. Passing SameSize a reference to the new circle
just seals it.

So what happened? The original Circle object, allocated by Function1
and left behind on the stack, was overwritten by arguments and local
variables for other methods later on. When Function1 returned, the
stack was unwound, leaving the original Circle object high and dry, but
as Main called other methods, they ate up stack space and eventually
overwrote the Circle object. This left references to the original
Circle object pointing into the middle of... well, junk. Stack stuff
that belonged to other methods.

So, we need a heap because often objects live longer than the lifetime
of a single method call. The method returns but the object lives on (as
happened in Function1: the function ended, but the Circle object lived
on). Since the stack is re-used as methods are called, and released as
methods return, we can't use it for long-term storage of objects; it's
too volatile. We need some other place to put things whose lifetimes
don't dovetail with the lifetimes of method calls. That place is the
heap.

 

[Marcus Andrén]

I had an interview today and I got destroyed
The question was why have a stack and a heap?
I could answer all the practical stuff like value types live on the
stack, enums are on the stack, as are structs, where classes are on
the heap... when value types go out of scope the memory is re-
allocated, object remain in memory waiting to be cleaned up by the
garbage collector, etc, but he responded 'so why not just put say a
class on the stack? why bother having a heap at all?' I said I
didn't know and he responded 'oh that's just the way of the world
then eh?' like a real smart a**. I felt pretty small. So can someone
please explain this to me so hopefully I never have to feel like
that again.
Thanks,

Jeff

stack vs heap is just a question of the lifetime of the information
that is handled.

The compiler can choose to place anything on the stack as long as it
can guarantee that it won't be accessed after the end of the method
call in which it was created.

A compiler can even choose to place class instances on the stack as
long as all references to the instance are inside the same stack
frame. (The .Net CLR doesn't do this as far as I know, but it is
possible)

 

[arcticool]

I am applying for an entry level tester job at M$ and have had
several interviews with no luck but this was the worst...
M$ is currently firing all their testers (they call it RIF) and
offshoring to India where they are being replaced with cheaper
developers. I am just trying to keep my career in IT so for a tester
now that means develper certification is a must, esp for me since I
don't have an IT degree.

The question from my last interview was 'make a pivot table in SQL
using case statements'. Yes, it is getting pretty tough out there...
--