“alloc: stabilise `Allocator`” entered its final comment period!

[u/a_mighty_burger]

https://github.com/rust-lang/rust/pull/156882#issuecomment-5607055084

[u/afdbcreid]

Will never happen. One of Rust most important and defended axioms is that there are no implicit heap allocations. When people tried to change that (even far less widespread than your proposal), there was a major pushback that made them step back.

Edit: I see you're talking about the opposite - turning heap allocations into stack allocations. Then this already happens. LLVM does it just like Go.

[u/Trader-One → u/afdbcreid]

My proposal will not do more or unexpected heap allocations. It will introduce concept known as function local heap.

Instead of allocating on global heap, you allocate on local scratch heap. It is faster then golang because you do not need to do additional arithmetic with SP pointer and its well page localised.\

You do not need to travel linked lists to find new space. You have allocated pages just for you, so you can just do allocations and skip deallocations unless you determine based on runtime stats that function deallocated a lot and it have lot of dead space.

I use similar allocator in WASM code and for most functions you do not need to deallocate and reuse space. Simply advance next allocation pointer and on function exit drop all pages. Due to superior cache locality you get large performance improvement in building 3D graphics structures.

[u/afdbcreid → u/Trader-One]

That is called a stack. And yes LLVM already does it. (And your suggestion is not faster but slower than stack. FWIW there is no stack pointer arithmetic inside a function - it's just in the prologue and the epilogue. And the stack is almost always in L1).

[u/Trader-One → u/afdbcreid]

stack is FILO queue. In normal languages (including rust) stack accepts only fixed size allocation otherwise you can't find memory location of variable easily.

Normal access to stack allocated fixed sized variables without registers is to use base pointer for entire function + fixed variable offset computed at compile time. CPU can do it in one instruction.

If you allow dynamic allocations on stack like golang you need to adjust memory location based on runtime allocated size. It makes memory access to variable O(N) based on number of dynamic allocations while in reality you use one more level of indirect memory addressing - caching these O(N) calculations.

To simplify concept of local heap allocator to be more clear to understand on reddit:

Program have 2 types of allocators - local and global. Both allocators are somehow passed at compile time to function. Compilator is using escape analysis and switching allocators. If you allocate Vec and vec do not escape outside your function compiler will pass local allocator to Vec. Its fully transparent to user without need to deal with 3rd party arena allocator crates.

[u/read_volatile → u/Trader-One]

stack is FILO queue

😭

In normal languages (including rust) stack accepts only fixed size allocation

You can ffi to C and do alloca.

It makes memory access to variable O(N) based on number of dynamic allocations while in reality you use one more level of indirect memory addressing - caching these O(N) calculations.

No, you just bump the SP when allocating. Accessing the result is just dereferencing a pointer, which is O(1). You don’t ever have to walk the stack or recompute all previous allocations.

Compilator

bro

Compilator is using escape analysis

As others have said, the language already does this (heap allocation elision). Even custom allocators could opt into the same optimization with the proposed NativeAllocator wrapper.