Search⌘ K
AI Features
Home
Courses
Advanced Programming Techniques in D

Call Stack

Discover how the call stack manages active function calls and local states in D programming. Learn how fibers allow multiple call stacks within a single thread to improve efficiency in concurrent execution and understand the role of recursion in call stack operations.

We'll cover the following...

A fiber is a thread of execution that enables a single thread to achieve multiple tasks. Compared to regular threads that are commonly used in parallelism and concurrency, it is more efficient to switch between fibers. Fibers are similar to coroutines and green threads.

Fibers enable multiple call stacks per thread. Therefore, to fully understand and appreciate fibers, one must first understand the call stack of a thread.

Call stack

The parameters, non-static local variables, return values, and temporary expressions of a function, as well as any additional information that may be needed during its execution, comprise the local state of that function. The local state of a function is allocated and initialized automatically at run time every time that function is called.

The storage space allocated for the local state of a function call is called a frame (or stack frame). As functions call other functions during the execution of a thread, their frames are conceptually placed on top of each other to form a stack of frames. The stack of frames of currently active function calls is the call stack of that thread.

For example, once the main thread of the following program starts executing the bar() function, there would be three levels of active function calls due to main() calling foo() and foo() calling bar():

D
import std.stdio;



void main() {

    int a;

    int b;



    int c = foo(a, b);

    writeln(c);

}



int foo(int x, int y) { 

    bar(x + y);

    return 42; 

}



void bar(int param) {

    string[] arr;

    // ...

}

During the execution of bar(), the call stack would consist of three frames storing the local states of those currently active function calls:

As layers of function calls get deeper as functions call other functions and shallower when functions return, the size of the call stack increases and decreases accordingly. For example, once bar() returns, its frame would no longer be needed and its space would later be used for another function call in the future:

We have been taking advantage of the call stack in every program that we have written so far. The advantages of the call stack are especially clear for recursive functions.

Recursion

Recursion is the situation where a function calls itself either directly or indirectly. Recursion greatly simplifies certain kinds of algorithms, like the ones that are classified as divide-and-conquer.

Let’s consider the following function, which calculates the sum of the elements of a slice. It achieves this task by calling itself recursively with a slice that is one element shorter than the one that it has received. The recursion continues until the slice becomes empty. The current result is carried over to the next recursion step as the second parameter:

D
import std.array;

import std.stdio;



int sum(int[] arr, int currentSum = 0) {

    if (arr.empty) {

        /* No element to add. The result is what has been

         * calculated so far. */

        return currentSum;

    }



    /* Add the front element to the current sum and call self

     * with the remaining elements. */

    return sum(arr[1..$], currentSum + arr.front);

}



void main() {

    writeln(sum([1, 2, 3]) == 6);

}

Note: The code above is only for demonstration. Otherwise, the sum of the elements of a range should be calculated by std.algorithm.sum, which uses special algorithms to achieve more accurate calculations for floating-point types.

When sum() is eventually called with an empty slice for the initial argument of [1, 2, 3] the relevant parts of the call stack would consist of the following frames. The value of each parameter is indicated after an == sign. Remember to read the frame contents from bottom to top:

Note: In practice, when the recursive function directly returns the result of calling itself, compilers use a technique called “tail-call optimization”, which eliminates separate frames for each recursive call.

In a multithreaded program, since each thread would be working on its own task, every thread gets its own call stack to maintain its own execution state.

The power of fibers is based on the fact that although a fiber is not a thread, it gets its own call stack, effectively enabling multiple call stacks per thread. Since one call stack maintains the execution state of one task, multiple call stacks enable that a thread works on multiple tasks.