I invented a novel stack in Zig! By the way, Today is my birthday. I'm 16!

Showcase
1

Introduction

Welcome to my collection module! I bet you will feel shocked at my design. This is the recommended collection which the one of collections in my library.
It’s negative stack.
Do you believe the indexes of my stack is decreasing from -1? (Like -1,-2,-3,-4,-5,…)
Do you believe the top pointer of my stack is less than the bottom pointer?
Do you believe the index of the bottom element is -1?
It’s negative stack! The bottom pointer is at the high address. You need to index negative integer number to get elements. It’s the origin of the name of negative stack.
More shocking is, it’s more efficient than normal dynamic collections. I swear. If you suspect it, please go on.

Create

Let’s create an empty stack.

var stack = cos.stack.negStack(u8).new();

If I tell you it’s stored in the thread stack, do you believe it?
Let’s reveal this secret.

Layout

If left is low address, right is high address, the layout in memory of empty negative stack is like:
|top pointer|bottom pointer&stack pointer|
The bottom pointer is equal to stack pointer in it. And the size of every cells is equal to the size of element.
Now, you will believe it is effecient. Because it’s not need the memory allocator to resize. Each methods of stack is all even inline. Why? I will tell you.
Besides, if you want to specify aligned elements, you can use cos.stack.negStackAligned.

Push

Now, let’s push some elements to the stack.

stack.push(73);
stack.push(42);
stack.push(211);

Now, the memory layout is like:
|top pointer|211|42|73|bottom pointer&stack pointer|

Pop

Let’s pop an element and print it.

std.debug.print("value: {}\n", .{stack.pop().?});

You will see 211.
The method pop will check whether the length of stack is empty. If it’s empty, will return null.
If you are sure that it’s not undefined behavior not to check length, please use popUnchecked method.
In the fact, many methods of stack have their matched unchecked method.

Risk

Well, We print it successfully.
Shall we print 42? Let’s try.

std.debug.print("value: {}\n", .{stack.pop().?});

Are you shocking? The result is unexpected barely.
Because we called the function std.debug.print, it created some local variables on the stack and pushed the return address into the stack.(Maybe pushed frame pointer too.)
Now, the layout is like:
|top pointer|a part of return address|bottom pointer&stack pointer|
Our data was covered by std.debug.print function! It means the elements are might undefined now.
In this situation, we can say it’s ill.
Thus, we should be careful to use stacks. Because the function might cover our data.
But we need only notice not inline function. Because inline function can’t cover our data.
It’s the reason why the method of stack is all inline.

Clear

Never mind. Let’s rebuild the stack.
We can use clear method to clear the stack.

stack.clear();

Now the stack is empty.
Let’s push some elements.

stack.push(73);
stack.push(42);
stack.push(211);

Save

If we hope the result is expected, we shouldn’t cover the data until the stack is useless. Let transfer data to the current frame(or registers)!

const third = stack.pop();
const second = stack.pop();

Now useful data was transfered from the stack. Now the stack is useless.

std.debug.print("second: {}, third: {}\n", .{second.?, third.?});

Now we print them successfully. Congratulations!

At

Let me demostrate something else.
I should rebuild the stack.

stack.clear();
stack.push(73);
stack.push(42);
stack.push(211);

We can get the element at a specified index.

const v2 = stack.at(-2);
const v3 = stack.at(-3);

Please care the order of indexes. It’s decreasing from -1.
Why? Because it base on the bottom pointer, and the bottom pointer is at top address.
It returns a optional pointer to element. If it’s besides the range that stack can access, will return null.
If you are sure that the index is in the range of stack, you can use atUnchecked method.

std.debug.print("value at index -2: {}, value at index -3: {}\n", .{v2.?.*, v3.?.*});

Will print 42 and 211.

Basic

We can get the bottom pointer and the length of stack.

const ptr = stack.ptr; // The bottom pointer, it's a multipointer, you can use `bottom` method too.
const limit = stack.limit; // The limit of the stack.

Be careful, in order to compare to length conveniently, we saved the limit that the bitwise NOT of length.

const length = stack.len(); // Use method `len` to get the length of stack.
std.debug.print("ptr: {*}, limit: {}, length: {}\n", .{ptr, limit, length});

Follow

We can construct another stack in the same frame.

var s2: cos.stack.negStack(u32) = stack.follow(cos.stack.negStack(u32).fromPtr);
s2.push(42);
s2.push(212);
std.debug.print("second: {}, first: {}\n", .{s2.pop().?, s2.pop().?});

Be careful, because the direction of increasing is occupied by second stack, the max length of the first stack will be the current length until the second stack is released.
That time, you can use the memory space of the second stack for the first stack.

Iterator

Rebuild the stack.

stack.clear();
stack.push(3);
stack.push(21);
stack.push(114);

The stack support iterator.
You can create an iterator.

var iter = stack.iter();

This iterator can yield pointers to elements.
Now, let’s use it!

while (iter.next()) |v| {
    v.* += 1;
}

Now, let’s print the stack!

std.debug.print("{}, {}, {}\n", .{stack.at(-1).?.*, stack.at(-2).?.*, stack.at(-3).?.*});

Adjust

stack.clear();
stack.push(42);
stack.push(211);

If you want to save elements but you won’t to move elemnts out, you can try to use adjust method.

stack.adjust(struct {
    fn print () void {
        std.debug.print("Hello world!\n", .{});
    }
}.print);

It will receive a function without parameters.

std.debug.print("first: {}, second: {}\n", .{stack.at(-1).?.*, stack.at(-2).?.*});

It will print correctly.

End

Now, you can use negative stack.
By the way, negative stack has an alia “sos”. It will save your program when you shout SOS. I suggest you use “sos” in your code.
Have a nice time!

Support

Now, cos just support x86/x86-16/x86-64.

Platform

It’s in GitCode.GitCode URL

2 Likes
2

Please communicate with me.

1 Like
3

It has only been 30 minutes and you posted quite a lot here, please be patient. For what it’s worth this looks very cool, but this is an internet forum, not a discord channel. From the topic title you’re quite young and perhaps new to this forum, but people will respond, the community here is great. Just wait :slight_smile: I’ll take a look myself after coffee, I always check ziggit in the mornings.

7 Likes
4

Might want to add .zig-cache and zig-out to .gitignore .

Are you using this code for anything in particular?

3 Likes
5

Before I take the time to dive into the code I’d like to make a few meta-comments, about your post.

  1. Please don’t tell a bunch of strangers on a public website that you’re 16. Nonetheless, happy birthday :tada:

  2. I don’t mind a joyful, informal or humorous tone. But your speech was trying to sell me something, with a fabricated narrative and assuming what I think and how I feel.

You can use this tone if you want, but know that it gave me eczéma.

  1. What do we want? Benchmarks! When do we want them? Now!

If you’re claiming that your way is faster, at least back it up with an explanation or a benchmark. A lone claim only tells that you care less about true efficiency and more about marketing. I’d like a comparaison with say std.ArrayList with a std.heap.FixedBufferAllocator.

  1. If you’re using a translator, it’s not doing a very good job :sweat_smile:. I’m not talking about harmless mistakes, I make them all the time. But sometimes your sentence is off, to the point where I can’t quite understand what you mean. I haven’t used it in a while, but I’ ve had a pretty good experience with DeepL. You’re allowed to use AI/LLM for translation.

I’ve only looked superficially at your repo and I can already give you a two tips:

  • You should add zig-build and .zig-cache to your .gitignore, they’re meant to be local.
  • Maybe write your own build.zig or strip the default one from the unnecessary steps and comments.
13 Likes
6

It’s cool that you’re trying low level programming and even assembly, but you have a completely wrong idea of the stack and how languages use memory.
You cannot grab your stack pointer and starting writing at arbitrary offsets from it. The compiler has space reserved for everything, and when you write at arbitrary addresses, you are overwriting whatever the compiler had placed there. Remember that memory always needs to be explicitly given to you before you can read or write from it.
There are two ways that you could have obtained that memory. One is to allocate the memory yourself. I see that you want to use the stack, and that’s great, but the proper way of using the stack is to declare a local variable:

const Stack = struct{
buffer: [5]u32,
};

pub fn main() void{
  var stack: Stack = undefined;
}

Here, the compiler will reserve the space for your Stack, which will have a maximum size of 5. You can take the size as a generic parameter. Take a look at the old BoundedArray.

Another way to receive memory is to ask the caller for it:

const Stack = struct{
  buffer: []u32,
  pub fn init(buffer: []u32) @This(){
    return .{ .buffer = buffer };
  }
};

In both cases, memory was explicitly given. In the first case, it was provided by the compiler. In the second case, it was provided by the caller.

5 Likes
7

Thanks, but I chose the Showcase. I will assume the speech online.

8

In my example. I stress the library is unsafe again and again. As long as obey the use of the library, it will be fine.

9

I want to use this in a Windows app and also in some embedded ARM Cortex-M code I’m writing — should it behave the same on those platforms as on x86-64 Linux? Anything I should know?

Can I put it inside an extern struct so it sits next to some related fields, like:

extern struct {
    buffer: [4]u64,
    stack: NegStack(u64),
}

I’d want buffer right there alongside the stack — is that a supported way to use it?

1 Like
10

I’ll try again. There is no way to use this correctly. It’s blatant undefined behavior. Note that as soon as you call a function, whatever you had on the stack will be trampled, and that’s assuming you are in a debug build and the compiler is behaving predictably. With optimizations, all bets are off.
Take a look at alloca. It’s C’s function that allocates space on the stack at runtime. It’s builtin, meaning it is impossible to implement it (correctly) inside the language itself.

14 Likes
11

Note that even if you don’t call any functions explicitly, the compiler can insert calls to memset and memcpy, which push function frames and overwrite your data: Compiler Explorer

5 Likes
12

The behavior in Windows is same as Linux. But In any architectures, you need be sure that the functions and interrupts can’t cover the stack data. And use NegStack as a field of struct is dangerous. You need use fromPtr method to receive buffer_addr + element_size * buffer_len(to get top pointer), and as long as data is not in thread stack, It will be allow to use any functions ant interrupt.

13

I published the bench test.

14

This has been explained multiple times by others, but I will do it again since you still don’t seem to understand.

Calling it “unsafe” is an understatement. “unsafe” things can be worked around, have safe things built on top of them. What you have made is neither of those things, anything from compiler optimisations to OS interrupts can change the data you are working with. It is not even a matter of not calling functions, that is simply the most reliable way to break it.

Something that can break at any time, anywhere, even if you don’t change your code at all, is undefined/illegal behaviour. It is far beyond what we call “unsafe”.

7 Likes
15

You should Google what the red zone is.

1 Like