Why stack is faster than heap and what exactly is stack?

10

[Edit: The original post was incorrect in describing how automatic arrays are implemented. I couldn’t edit it, so I’ve deleted it and I’m reposting with more accurate information. Sorry everything is out of order now.]

I didn’t answer the second part of your question: The stack is a region of memory that is set aside for your program by the operating system. In theory all variables declared in your functions are located “on the stack”. As your program enters and leaves functions, the amount of stack your program uses expands and contracts. All this is rigged by the compiler at compile-time. As such, the compiler has a good deal of information about the location of these variables in memory, and can optimize accordingly.

Things that are not known at compile-time have to be allocated on “the heap”. This requires going through a memory allocator, which is a complex and slow beast. This list includes any allocatable arrays or variables. One important special case is when you declare an array based on an integer dummy argument. The example below shows the 3 main possibilities.

subroutine do_cool_stuff(n)
    integer, intent(in) :: n    ! stack variable

    real :: stack_array(4)
    real, allocatable :: heap_array(:)
    real :: stack_or_heap_array(n)
end subroutine

The first stack_array has a size that is known at compile-time, so the compiler will put it on the stack. The size of the heap_array is not known at compile-time, so when you allocate it, it will be placed on the heap. As I’ve mentioned, this is slow, and should be done as little as possible.

[Edit: My original incorrect description :slightly_frowning_face:]
The size of the stack_or_heap_array is not known at compile time, so what will the compiler do? In this case, it actually is possible to allocate an unknown amount on the stack, however, the stack is a finite resource. If you pass in n = 437289473289 , you could very well exhaust the stack and produce a ‘stack overflow’ error (See where the name comes from??) To prevent this, most fortran compilers set a limit, so that if n is larger than some value, it will allocate stack_or_heap_array on the heap, instead of on the stack.

In my opinion, using this “feature” of fortran is counter-productive and should not be used, as it can produce sudden performance drops without telling you why. It is analogous to the ‘Variable Length Arrays’ in C, which are frowned upon in some circles.

And don’t worry about toggling all those little parameters, the defaults should be good enough.

[Edit: The correct description :grinning:]
The size of the stack_or_heap_array is not known at compile time, so what will the compiler do? This is compiler dependent. Some compilers choose to allocate on the stack, others choose to allocate on the heap. If placed on the stack, then the performance will be fast, but runs the risk of causing a stack overflow, since the stack size is limited by the operating system. If placed on the heap, then allocation/deallocation of these arrays will be be slow, but avoids causing a stack overflow.

If you use automatic arrays, it is important to know how your compiler will handle these, and what the performance implications are. You will need to understand the appropriate compiler-specific flags that control these behaviors, like the stack size and whether they are put on the stack or the heap. If on the stack, you will need to know how to set the stack size of your program. (Don’t ask me, I don’t know how to do it)

I still would avoid automatic variables, as I don’t really want to have to read about each compiler that I compile with and learn all the tricky little flags. You can avoid that headache by just not using automatic arrays.

1 Like