The Crystal Programming Language Forum

What happens to Tuples (stack allocated) that are inside heap memory?

Example code:

alias ItemTuple = {Int64, Int32, String, Int16}

class Item
  property i : ItemTuple
  def initialize(@i)
  end
end

class Client
  property items = Hash(Int64, Item).new
end

p1 = Client.new

p1.items[1] = Item.new( {0_i64, 25, "test", 5_i16} )
 

pp p1

Hash is allocated on the heap, however, Tuple is allocated on the stack.

Questions:

  • If stack allocated memory (Tuple) is a child of heap memory (Hash), does this mean Tuple is now allocated on the heap?

  • Using this example code, and creating xx of items, is it possible to achieve a stack overflow error?

If stack allocated memory (Tuple) is a child of heap memory (Hash), does this mean Tuple is now allocated on the heap?

Yes

Using this example code, and creating xx of items, is it possible to achieve a stack overflow error?

No you can’t, because it’s not in the stack.

Basically when you have a value type (like a tuple, an integer, as opposed to a reference type like a class):

  • using it in a method will use some space in the stack frame of the method, because that’s where local variables are located.
  • using it in a type (a struct or class) as an instance variable, will use some space in that type, in the area used by the fields of that type. When a value type is embedded in a class it will effectively be in the heap, because that’s where the class’s internal memory is…

I can make a schema later if you need, I’m on the phone right now, it would be close to impossible ^^

1 Like

I think it’s helpful to think it like this:

  • classes are reference types: they are a pointer to the actual data
  • structs are value types: their data is inlined

What that means is when you do:

x  = SomeClass.new

x will be a pointer pointing to the data that SomeClass holds. Something like:

x = pointer -> [...data (instance vars)...]

and [...data...] is allocated on the heap.

If you have a type that has an instance variable of type SomeClass, that instance variable is also a pointer to the data. When you assign x to that instance variable that pointer is copied.

Note that when you do x = SomeClass.new, the pointer for x is stored on the stack.

With a struct, the data is inlined:

x = SomeStruct.new

so essentially x is the data:

x = [...data...]

and x is allocated on the stack.

If you have a type with an instance variable of type SomeStruct, that instance variable will not be a pointer to the data but it will have all the space for the struct. When you assign x to that instance variable, the data will be copied to that space.

So let’s say SomeClass has an instance variable s of type SomeStruct, and SomeStruct has two instance variables of type Int32. You do:

c = SomeClass.new
c.s = SomeStruct.new

it will be:

c = pointer -> [s = [x: Int32, y : Int32]]

note that everything after -> is in heap memory, which in this case will be 8 bytes.

When you do c.s = SomeStruct.new, that entire data is moved (copied) into the heap.

If it’s the other way around, and SomeStruct has an instance variable of type SomeClass, which in turn has two integers:

s = SomeStruct.new
s.c = SomeClass.new

it will be like this:

s = [c = pointer -> [x: Int32, y : Int32]]

Note that s in this case has its data inlined, and because it only holds a SomeClass, which is represented as a pointer, s's data is just a pointer. The data for that pointer always lives on the heap.

When you do:

c = SomeClass.new
s.c = c

the pointer for c, which lives in the stack (but the data lives in the heap) is copied from the stack to the struct (which in this case also lives in the stack).

I hope this is clear!

4 Likes

Wow, very interesting!

Yes, this is very clear.

When you do c.s = SomeStruct.new , that entire data is moved (copied) into the heap.

OHHHHHH. So if I got this right…

{0_i64, 25, "test", 5_i16} is stack-allocated on creation, however, it’s being stored in a heap allocated type (Hash), so it gets copied and put into heap memory.

Do I got that right? If so, when doing

pp typeof(p1.items[1].i)

It converts the heap memory storage of i back to a stack-allocated Tuple when accessing it?

So, theoretically… IF tons of items are being accessed, this could cause a stack overflow? But not when storing the items in a Hash (because they are copied and stored on the heap).

Please tell me I am close to understanding this 100%!

Even if I don’t understand this 100%, I trust you guys. And you have answered my questions and it really put my mind at ease regarding ItemTuple and its possibility of stack overflow errors. Appreciate it.

If you do:

x1 = # some struct
x2 = # some struct
...

and so on, a lot of times, then yes, you will get a stack overflow.

But it’s important to know that the compiler (well, LLVM) will reuse the stack. For example if you have a loop:

loop do
  x = # some struct
end

it doesn’t matter that # some struct is copied from somewhere to the stack, because it’s always copied to the same stack position.

In short, I would never worry about stack overflow when using structs. Stack overflow happens when you recurse too much into a function.

1 Like

There is a lot of intricacies in programming. Especially at the low-level. I’m just not used to it all (starting my gameserver with nodejs probably didn’t help :laughing:)!

With that said, I’m eager to learn and get as much information as my brain will comprehend!