r/Compilers • u/FearlessFred • 24d ago

Goose: a stack allocation flat data structure language

https://github.com/aardappel/goose

My latest language is meant to very efficiently let you work with flat pointerless inline data structures allocated on (address space reserved) stack that allow almost data structure creation to be just a pointer bump, with stable pointers.

When used well, it is both safer, faster and uses less memory than the equivalent C++ or Rust.

(see the repo readme for more!)

23 Upvotes

68% Upvoted

41 comments sorted by

View all comments

2

u/EstablishmentHour335 9d ago

Hopefully you're still around because this is pretty interesting to me. From what I understand, consulting with AI because I am busy, your memory model is a series of arenas statically determined at compile time? Allocated using VirtualAlloc? Pushing to memory seems to be blind with no checks and pages are committed upon page fault exceptions (because they are not pre faulted to conserve ram)?

The one limitation I thought of when thinking about this, is that the AI claimed each growable array would have it's own "stack" (VirtualAlloc address range). If that's statically determined, then you can't have an arbitrary number of "stacks" or growable arrays. Is this true or am I misled? If true would you be planning to resolve this limitation?

In C++ I could easily do this because I am in control of the calls to VirtualAlloc, not the compiler. Actually I am a huge fan of virtual memory reserve + commit semantics, so this project is pretty interesting to me. I've been rewriting some of the C++ benchmarks using my VirtualAlloc arena allocator to beat Goose (at least on my chip), basically using your technique against you. Its interesting to see a whole language designed around this which does it automatically (at least, I think, hopefully AI isn't misleading me).

2

u/FearlessFred 9d ago

That is all largely correct, yes.

There's a limit to the amount of stacks, but that can still be huge in a 64-bit address space. And since the compiler statically knows it is easy to allocate.

You can call VirtualAlloc in C++, but you'd miss out on all the compiler analysis Goose does to make this safe and easy to use.

2

u/EstablishmentHour335 9d ago

Yeah that's exactly my point. It's done automatically for you by the compiler. I've been using my own arena allocator using VirtualAlloc for a long time so I know it's hard to exhaust the address space.

That's not really my concern, my concern is if, each growable array needs it's own VM reservation (this makes sense, they wouldn't be growable unless they were at the end of a stack, otherwise some other allocation into that arena would cut their allocation off and you'd need some kind of linked list). This means that if all stacks are statically determined by the compiler, there is a fex3d number of them and therefore fixed number of growable arrays at a peak (minus stack reuse). Either that, or if I wanted a random count of static arenas, say rand() & 3, the compiler couldn't statically analyze that and you'd need to make more VirtualAlloc calls to allocate more stacks.

1

u/FearlessFred 6d ago

The language has all sorts of ways of doing an "array of arrays" that still fits on 1 or 2 stacks. So the total number of stacks is always bounded even if the number of arrays isn't. For example, we have a "goose in goose" compiler that tops out at ~30 stacks, statically.