ability to allocate fixed buffer runtime in stack frame initiation

[palsmo]

original discussion: https://discord.com/channels/605571803288698900/1247340253065384006 recognizing Robert R for his insights and participation in the discord discussion.

Demonstration

My original issue was trying to replace recursion for an iterative approach, to gain performance and memory safety ⚡

recursive:

fn quickSort(comptime T: type, items: []T, lo: usize, hi: usize) void {
  if (lo < hi) {
    const p = partition(T, items, lo, hi); // lo favored
    quickSort(T, items, lo, @min(p, p -% 1);
    quickSort(T, items, p + 1, hi);
  }
}

iterative:

fn quickSort(comptime T: type, items: []T) void {

    if (items.len == 0) return;

    const size = items.len * 2; // worst-case "recursion" depth O(n), 2 values per frame
    const U = math.IntFittingRange(0, items.len - 1);
    const V = math.IntFittingRange(0, size);

    var stack: [size]U = undefined;
    var top: U = 0;

    stack[1] = 0; // lo
    stack[2] = items.len - 1; // hi
    top = 2;

    while (top > 0) {
        const hi = stack[top];
        top -= 1;
        const lo = stack[top];
        top -= 1;

        const p = partition(T, items, lo, hi);

        if (p > lo) {
            // explore elements left of pivot
            top += 1;
            stack[top] = lo;
            top += 1;
            stack[top] = p - 1;
        }

        if (p + 1 < hi) {
            // explore elements right of pivot
            top += 1;
            stack[top] = p + 1;
            top += 1;
            stack[top] = hi;
        }
    }
}

The Case

From Zen: Memory is a resource. In lang charter/introduction: Write programs the best way they can behave and perform. Precisely communicate intent to the compiler and other programmers. Possibly others with some motivation.

In the recursive approach, every stack frame has a known size, but number of recursive calls are never known – this is a non Zig Zen case. Even though memory usage is uncertain it's still allowed in zig because of the utility and flexibility it brings.

For the iterative approach, the size of the single stack frame is/can be know at function call – and is therefore in accordance with Zig Zen. The behavior of the program is also more precisely communicated.

Observations:

• The first case is allowed while the latter is prohibited.
• The iterative solution turns an otherwise non Zen circumstance into one in accordance with Zen.

I there's a strong case made for supporting this kind of fixed buffer allocation, it makes the language closer inlined with its charter and brings a solution for avoiding unsafe and less performant approaches.

// thanks for reading the proposal, let's get some traction!

[silversquirl]

duplicate of #3952

[silversquirl]

What you are asking for is VLAs. A stack-allocated array of runtime-known size is called a VLA.

[palsmo]

@silversquirl my comment was not informed (decided to remove). A maybe possible option after thinking some more would be to check if not in comptime and in that case do a heap allocation, including an optional allocator in the function declaration.

[mnemnion]

Both of these algorithms are using variable amounts of stack space, known only at runtime. Allocating that space as a data structure, rather than via recursive function calls, doesn't change that basic dynamic.

In the recursive version, the compiler will know the size of each call frame, and generate better code as a result. Your referring to this allocation as "fixed" is incorrect, just as it would be incorrect if I described the recursive version as having a fixed number of function calls. It's true that both of these numbers can be deduced from the length of the slice: but this is only known at runtime, therefore, it varies based on the data. We call this variable allocation, for a reason.

I don't think you've made a coherent case here.