How much temporary data can be stored with Tuples?

Help & Support
1

I was reading about Tuples
One thing that stood out from the API docs:

A tuple is a fixed-size, immutable, stack-allocated sequence of values of possibly different types.

For my gameserver, the player’s item information is stored as a Tuple:

alias ItemTuple = {Int64, Int32, String, Int16, Int8, String, Int8, Int16, Int16, Int16, Int16, Int16, Int16, Int16, String, String}
property items = Hash(Int64, ItemTuple).new

I then stumbled upon this question (similar to mine):

And the part I’m worried about is:

  • The amount of memory available through stack-based allocation is commonly far less than the amount of memory available through heap-based memory allocation.
  • Once you are out of stack-based available memory your process will crash.

My Game class also has a loot property, which uses ItemTuple… There is going to be a lot of “stack allocated tuples” floating around on the gameserver. Especially once players are slaying monsters and items drop.

What’s the max amount of “stack memory” (or in this case, a lot of ItemTuples) that can be generated/created before the app crashes? Or, is this all managed by the OS, and I’m possibly overthinking stuff again?

2

I think it’s important to understand the memory model for native code even with GC, so I think this is a very valid line of inquiery. Having said that I don’t really know the stack magic either. I was trying to exhaust the stack space, but wasn’t able to do so with a reasonable amount of data in a loop (like tens of megabytes iirc), so I think you’re safe here. What you should be aware of is the runaway recursion that will crash your program.

1 Like
3

First of all, you shouldn’t use a tuple for such complex data. Using a struct is essentially the same concerning memory and usability, but you get named properties instead of having to rely on the order of elements in a tuple. But since both are allocated on the stack, this doesn’t matter regarding the question of this topic, the implications of using stack memory.

I don’t really understand your intentions to store game status on the stack. I’m pretty sure that won’t work out anyway. You’ll most likely need to be able to access such data from different stacks in order to interact with it. Such data is usually stored on the heap and that’s what it’s made for.

The amount of stack memory varies depending on the operating system, environment and compiler configuration. AFAIK typical values are usually between 1 MB and 8 MB. Your ItemType tuple has a size of 72 bytes, so you should be able to comfortably put thousands of them on the stack if you ever need to do so.

But in reality, I don’t see how you would get anywhere near such a number. These values are usually stored on heap memory (for examples in the items has, and most likely also the loot property) and you only put single instances on the stack for performing operations.

That seems unlikely. On a POSIX system ulimit -s prints the stack size. You can check that. On a modern linux OS for example, that should be 8192 kilobytes by default. Unless you have some custom configuration, I don’t think you could have put tens of megabytes on the stack.

2 Likes
4

Thanks for the info! Can you clarify the distinction here between “stored on heap memory”, vs “stack-allocated sequence of values of possibly different types.”?

Nevermind the above, I read this wrong, my bad!

Is “on the stack” referring to when they are being created / allocated? Not when they are stored inside the items hash? I was thinking if they are stored inside that hash, they are still allocated on the stack (using the stack memory)?

edit: Regarding structs, I personally found a Tuple to be much easier to work with, especially when querying data with the crystal-db module. (as: ItemTuple.types is all you need). And ItemTuple can also be used for the Games loot, the Player's items, etc. Same Tuple/Type all over = win win for me. However, moving to heap memory seems like it might be better. From what I am reading so far.

5

“on the stack” refers to where the memory is initially allocated. Value types are put on the stack, reference types on the heap.

A hash is a Reference and has memory allocated on the heap. When you add a value to the hash, it is stored in the memory buffer allocated for that hash. In case of reference type, that’s just a pointer, but in case of a value type, the entire value is copied there. If it would just store the pointer address from the stack, everything falls apart as soon as the original value is popped from the stack.
The next time you retrieve that value from the hash, it’s copied from the heap to the stack.

1 Like
6

Um, guys, is there something strange going on?

macro sa; StaticArray(Int32, {{ env("SIZE").to_i }}).new 0 end
def what; sa end
a = what
p a.size

(I was clearing cache between runs, just in case)

$ time SIZE=1 crystal build -p -t -s ./test3.cr
Codegen (bc+obj):                  00:00:01.372025483 (  42.65MB)
real    0m2.402s
user    0m2.872s
sys     0m0.559s
$ wc -c test3
1269428 test3

$ time SIZE=4000 crystal build -p -t -s ./test3.cr
Codegen (bc+obj):                  00:00:15.461629773 (  42.65MB)
real    0m16.473s
user    0m17.300s
sys     0m1.403s
$ wc -c test3
1818352 test3

$ time SIZE=8000 crystal build -p -t -s ./test3.cr
Codegen (bc+obj):                  00:01:04.420997949 (  43.26MB)
real    1m5.371s
user    1m1.860s
sys     0m9.392s
$ wc -c test3
2371312 test3
7

Yes, I was clearly getting memory from the heap, sorry for misinformation. I can’t seem to find a way to devise a program that would fill up a megabyte of stack without recursion and compile within a reasonable timeframe.

8

So If I got this right (let me try to see if I do):
The items property is a reference type, because it’s a hash. So it’s storing those references to the Tuples on the heap. HOWEVER, when accessing/checking the value of those Tuples with local variables, or “modifying the tuple” (re-creating a new one with a new value in a certain index), is all using stack memory.

So the problem of an app crash doesn’t come from storing these Tuples, it comes from when too many are being accessed and the stack is exhausted?

9

I created a test script:

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

class Test
  property hash = Hash(Int64, ItemTuple).new

  def looper
    loop do
      time_start = Time.now.to_unix_ms

      accessed_how_many = 0_i64
      hash.each do |itemid, v|
        # "Modify" the tuple's 1 index, and set it to a random number between 1 and 1 million
        hash[itemid] = modify_item_tuple(v, 1, rand(1..1000000))
        accessed_how_many += 1
      end

      puts "Size of ItemTuple: #{hash.size}, Tuples re-created on the stack per second: #{accessed_how_many}, Time Taken: #{Time.now.to_unix_ms - time_start}ms"
      sleep 1
    end
  end

  def initialize
    spawn looper

    index = 0_i64
    loop do
      index += 1

      hash[index] = {100_i64, 25, "", 5_i8, ""}
      sleep 0.0000001
    end
  end
end

Test.new

class Test
  def modify_item_tuple(tuple, index, new_value)
    index0 = index == 0 ? new_value.to_i64 : tuple[0]
    index1 = index == 1 ? new_value.to_i : tuple[1]
    index2 = index == 2 ? new_value.to_s : tuple[2]
    index3 = index == 3 ? new_value.to_i8 : tuple[3]
    index4 = index == 4 ? new_value.to_s : tuple[4]

    {index0, index1, index2, index3, index4}
  end
end

Output after 20 seconds or so:

Size of ItemTuple: 1, Tuples re-created on the stack per second: 1, Time Taken: 0ms
Size of ItemTuple: 269286, Tuples re-created on the stack per second: 269286, Time Taken: 85ms
Size of ItemTuple: 522544, Tuples re-created on the stack per second: 522544, Time Taken: 194ms
Size of ItemTuple: 741516, Tuples re-created on the stack per second: 741516, Time Taken: 307ms
Size of ItemTuple: 924413, Tuples re-created on the stack per second: 924413, Time Taken: 411ms
Size of ItemTuple: 1080371, Tuples re-created on the stack per second: 1080371, Time Taken: 510ms
Size of ItemTuple: 1207186, Tuples re-created on the stack per second: 1207186, Time Taken: 607ms
Size of ItemTuple: 1308039, Tuples re-created on the stack per second: 1308039, Time Taken: 690ms
Size of ItemTuple: 1311019, Tuples re-created on the stack per second: 1311019, Time Taken: 478ms
Size of ItemTuple: 1450014, Tuples re-created on the stack per second: 1450014, Time Taken: 521ms
Size of ItemTuple: 1583022, Tuples re-created on the stack per second: 1583022, Time Taken: 577ms
Size of ItemTuple: 1703355, Tuples re-created on the stack per second: 1703355, Time Taken: 622ms
Size of ItemTuple: 1809964, Tuples re-created on the stack per second: 1809964, Time Taken: 654ms
Size of ItemTuple: 1906472, Tuples re-created on the stack per second: 1906472, Time Taken: 700ms
Size of ItemTuple: 1990610, Tuples re-created on the stack per second: 1990610, Time Taken: 734ms
Size of ItemTuple: 2064413, Tuples re-created on the stack per second: 2064413, Time Taken: 770ms
Size of ItemTuple: 2128317, Tuples re-created on the stack per second: 2128317, Time Taken: 795ms
Size of ItemTuple: 2171176, Tuples re-created on the stack per second: 2171176, Time Taken: 808ms
Size of ItemTuple: 2224756, Tuples re-created on the stack per second: 2224756, Time Taken: 830ms
Size of ItemTuple: 2272636, Tuples re-created on the stack per second: 2272636, Time Taken: 859ms
Size of ItemTuple: 2312242, Tuples re-created on the stack per second: 2312242, Time Taken: 867ms
Size of ItemTuple: 2349165, Tuples re-created on the stack per second: 2349165, Time Taken: 884ms
Size of ItemTuple: 2381380, Tuples re-created on the stack per second: 2381380, Time Taken: 902ms
Size of ItemTuple: 2407954, Tuples re-created on the stack per second: 2407954, Time Taken: 917ms
Size of ItemTuple: 2430788, Tuples re-created on the stack per second: 2430788, Time Taken: 919ms
Size of ItemTuple: 2452947, Tuples re-created on the stack per second: 2452947, Time Taken: 931ms
Size of ItemTuple: 2471942, Tuples re-created on the stack per second: 2471942, Time Taken: 938ms
Size of ItemTuple: 2488830, Tuples re-created on the stack per second: 2488830, Time Taken: 944ms
Size of ItemTuple: 2504129, Tuples re-created on the stack per second: 2504129, Time Taken: 952ms
Size of ItemTuple: 2517045, Tuples re-created on the stack per second: 2517045, Time Taken: 959ms
Size of ItemTuple: 2527984, Tuples re-created on the stack per second: 2527984, Time Taken: 970ms
Size of ItemTuple: 2535793, Tuples re-created on the stack per second: 2535793, Time Taken: 963ms
Size of ItemTuple: 2545559, Tuples re-created on the stack per second: 2545559, Time Taken: 977ms
Size of ItemTuple: 2551598, Tuples re-created on the stack per second: 2551598, Time Taken: 979ms
Size of ItemTuple: 2557123, Tuples re-created on the stack per second: 2557123, Time Taken: 982ms
Size of ItemTuple: 2561845, Tuples re-created on the stack per second: 2561845, Time Taken: 986ms
Size of ItemTuple: 2565515, Tuples re-created on the stack per second: 2565515, Time Taken: 988ms
Size of ItemTuple: 2568723, Tuples re-created on the stack per second: 2568723, Time Taken: 981ms
Size of ItemTuple: 2573921, Tuples re-created on the stack per second: 2573921, Time Taken: 980ms
Size of ItemTuple: 2579046, Tuples re-created on the stack per second: 2579046, Time Taken: 991ms
Size of ItemTuple: 2581329, Tuples re-created on the stack per second: 2581329, Time Taken: 998ms
Size of ItemTuple: 2581971, Tuples re-created on the stack per second: 2581971, Time Taken: 1017ms
Size of ItemTuple: 2581972, Tuples re-created on the stack per second: 2581972, Time Taken: 995ms
Size of ItemTuple: 2583503, Tuples re-created on the stack per second: 2583503, Time Taken: 996ms
Size of ItemTuple: 2584680, Tuples re-created on the stack per second: 2584680, Time Taken: 995ms
Size of ItemTuple: 2586037, Tuples re-created on the stack per second: 2586037, Time Taken: 997ms
Size of ItemTuple: 2586986, Tuples re-created on the stack per second: 2586986, Time Taken: 1007ms
Size of ItemTuple: 2586987, Tuples re-created on the stack per second: 2586987, Time Taken: 995ms
Size of ItemTuple: 2588384, Tuples re-created on the stack per second: 2588384, Time Taken: 1005ms
Size of ItemTuple: 2588385, Tuples re-created on the stack per second: 2588385, Time Taken: 992ms

From my understanding, it levels off after reaching around 2588385 Tuples of re-creation per second. Which is way beyond what I need! This is assuming my testing code is doing what I think it’s doing :stuck_out_tongue:

edit: It should say, Size of Hash of ItemTuples

10

It’s not storing references, but the actual tuples.

Exactly. And this stack exhaustion can usually only happen when you have a deeply recursive control flow which would cause the stack to grow very large.

1 Like
11

I don’t think I should have brought up the hash part in my code, I just made it more confusing. So, Tuples are “stack-allocated” when they are created, but when stored in a Hash, they use heap memory?

12

This struct/class difference also exists in C#, it’s probably better to search Google about this instead of continuing the discussion here, because there will probably be thousands of answers out there, like this one.

13

Struct issue was brought up by straight-shoota. I don’t want to use structs, I like my Tuples (for reasons above). I am just confused a bit because straight-shoota said

Your ItemType tuple has a size of 72 bytes, so you should be able to comfortably put thousands of them on the stack if you ever need to do so.

But if you look at my example code above (assuming it’s coded correctly), there are millions of Tuples that get generated on the stack, not just thousands. That’s is a big difference, is my code doing what I think it’s doing?

14

Tuples are essentially the same as structs. The same applies for both.

I don’t really follow what your example is meant to show, but it’s certainly not putting millions of tuples on the stack. hash.size returns the number of elements in the hash. As already explained, the hash table is allocated on the heap.

15 
      accessed_how_many = 0_i64
      hash.each do |itemid, v|
        # "Modify" the tuple's 1 index, and set it to a random number between 1 and 1 million
        hash[itemid] = modify_item_tuple(v, 1, rand(1..1000000))
        accessed_how_many += 1
      end

      puts "Size of ItemTuple: #{hash.size}, Tuples re-created on the stack per second: #{accessed_how_many}, Time Taken: #{Time.now.to_unix_ms - time_start}ms"
      sleep 1

This part, it loops through the hash and creates millions of Tuples per second. Tuples are created on the stack?

Or, since it’s assigning the Tuple to the hash, that’s on the heap? But the Tuple itself is still being created? I don’t know tbh, just thinking out loud

16

To better understand what’s going on look at both parts of an assignment. The left part will typically tell you where the data is going and the right part is important to reason whether you assign data (Value) or a pointer (Reference).

Something like this:

a = {1,2,3}

means that there is one 12 bytes (3 x int32s 4 bytes each) memory “block” that lives on stack, named a.

a = {1,2,3}
a = {4,5,6}

means that there is still one 12-bytes block, the second line will not allocate another stack block.

On the other hand, something like this:

hash[itemid] = {1,2,3}

means that there is no stack space used at all. These 12 bytes live “inside” the hash, in heap. Stack is only used to store the hash variable itself, which is an 8-byte pointer (on amd64).

Note that this:

a = [1,2,3]
a = [4,5,6]

is substantially different than the tuples example above, because the first line will malloc memory and store the pointer. The second line then will malloc another memory block and overwrite the pointer. The already allocated memory from the first line will not go away until GC frees it hopefully sometime in the future.

Hope that helps.

17

So when storing a Tuple inside a hash, it’s now not allocating on the stack, but on the heap? I’m so confused :/

18

I’ll try to explain, but fundamentally this is not specific to Crystal, so my advice is to explore the topic in general.

When you type a = <expression> the machine has to first evaluate the expression, and second somehow link the name a with a memory address (we’ll ignore registers for simplicity). There are three large approaches to memory allocation:

  1. global static space: the compiler allocates all global variables at compile time. All the sizes have to be known at compile time also. The memory is allocated once when the program is started and is only reclaimed upon program exit.
  2. global dynamic space, or heap: malloc and friends will allocate memory during runtime, free will reclaim it. This approach is the only one that allows work with memory chunks with sizes that are only known during the program execution (run time).
  3. stack space: when a function takes control, it will allocate a fixed size of memory from the shared stack block for the variables that should only exist during execution of this function. This is also a static memory, so all the sizes have to be known before the program is run.

Now, in C you are able to easily-ish differentiate how the variable is stored, because most of the time you allocate the heap yourself, so you know where the variable lives. In Crystal you don’t – if instantiate a Reference, it is always allocated on heap, and vice versa, if you allocate a Value, it is never allocated on heap.

Finally, there are levels of indirection, so let’s consider this example:

a = {1,2,3} # easy, a lives on stack and holds a Tuple, because a Tuple is a Value
            # memory allocations:
            # a: stack, 12 bytes

b = [{1,2,3}, {4,5,6}] # b is and Array, so b itself lives on stack
                       # and holds a pointer to an allocated heap space,
                       # which in turn holds Tuples, but not pointers to Tuples
                       # memory allocations:
                       # b: stack, 8 bytes
                       # array_of_tuples: heap, 24 bytes + N
                       # (N being some additional Array bits, like @size and whatnot)

c = [[1,2,3], [4,5,6]] # c lives on stack, and holds a pointer to a place,
                       # let's name it "array_of_pointers", which as the name suggests
                       # contains 2 pointers, each of them to some other heap-allocated place.
                       # memory allocations:
                       # c: stack, 8 bytes
                       # array_of_arrays: heap, 16 bytes + N
                       # array_of_ints_1: heap, 12 bytes + N
                       # array_of_ints_2: heap, 12 bytes + N

You don’t have to think in pointers using Crystal, which is very good indeed, but it helps to understand the ideas behind automatic memory management.

4 Likes
19

That’s a lot of information for me, it is appreciated.
From what I understand so far, basically… Only a Tuple literal that is assigned to a local variable (NOT A HASH) is actually allocated on the stack. (your first example) – This is not the case when Tuples are stored inside Hashes, and other reference types.

So in reality, Tuples are sometimes stack allocated… dependent on where the Tuple is going to be stored.

Am I getting closer to fully wrapping my head around this?

20

Yes, allocation is about storage, that’s correct. Let’s once again take Tuple and Array as examples (again, simplified for clarity):

  • An Array will never be allocated on stack, because it’s a Reference, so once you have [1,2,3] the compiler will malloc a chunk of memory and write three ints there. The result of this expression is a Pointer, so next when the compilers sees a = it’s gonna a) remember that this function’s stack needs 8 more bytes to store a Pointer; b) actually write out CPU instructions to store an integer in memory.
  • A Tuple is a Value, so there is never going to be any pointers to a Tuple. {1,2,3} means literally twelve bytes in memory and in the resulting binary, because all the types only really exist in compile time. So if these 12 bytes are assigned to a local variable, they are going to live on stack, but if they are assigned to some data structure that is already allocated on heap, then they are going there. So once again, if next a compiler sees a = (it’s going right to left), it will extend the stack space by the tuple’s size and generate the code that writes data.
2 Likes