[tialaramex]

Casey spends a lot of effort on what he considers an anti-pattern where you're making a huge number of separate objects. I think a lot of this comes from Java, a language where all the user defined types actually are obliged to be heap allocations. If I make a Goose type, and I say I want a Goose, Java will allocate space on the heap for the Goose and put my Goose there, that's really how Java works. If I make a growable array of them ArrayList<Goose>, and add each of 500 geese, that's 500 allocations for geese plus maybe 8 allocations for the ArrayList, so 508 total. Ouch. If making a Goose was itself cheap this overhead hurts badly.

But a lot of languages aren't like that, and so this doesn't translate. Obviously in Rust with Vec<Goose> that's only 8 allocations, each local Goose lives in the stack - or, if you knew up front there were 500 geese, you Vec::with_capacity(500) and it's a single allocation - but similar is true in many languages, Java is an outlier.

[gf000]

Java doesn't mandate the usage of a heap - it can in certain cases avoid doing so and allocate on the stack (escape analysis).

Besides, as mentioned java's allocations are much closer to something like using an arena in a low-level language, then a "slow" malloc. It uses thread-local allocation buffers, where you have a large buffer with a pointer pointing to the start of the free region. Allocation is just a pointer bump, not even needing synchronization since it is per a single thread. As it gets full, the GC moves out still alive objects in the background and resets the buffer.

This is pretty much the most efficient one can be after per-object type arenas and simply not allocating.

[tialaramex]

You're correct that by an "as if" rule the JIT may in some cases be able to do this trick, but the specification says you're getting a heap allocation and so in most cases, including the example I gave that's exactly what happens.

It doesn't matter that you say this is "much closer to something like using an arena". It's definitely work that we needn't do at all and that's AFAICT that's how Casey ends up over-correcting so badly.

> This is pretty much the most efficient one can be after per-object type arenas and simply not allocating.

Sure. "A C is pretty much the highest grade one can get in this class, after grades A and B".

[gf000]

What "work" do we do needlessly? It's a pointer bump. With reclamation being no work. Comparatively a malloc call will have to do extra work to defragment.

Also, a stack is not a separate hardware element of the RAM, it's not faster than a sufficiently hot part of the heap - it just so happens that the current stack frame is pretty likely to be in cache.

[tialaramex]

> What "work" do we do needlessly? It's a pointer bump

Any work here was needless. There was no need to do work.

[gf000]

On the allocation happy path there is literally less work in case of Java. Like at least try to get what I'm saying and argue with that - I'm not saying that Java is faster or whatever, but that it has chosen different tradeoffs, and "stack vs heap" is an oversimplified model that doesn't help us understand the real performance impacts.

A pointer bump is a pointer bump, vs a malloc call that will try to find place, do some housekeeping, etc. And your Vec will need at least a single allocation, the backing buffer is not on the stack.

[tialaramex]

> On the allocation happy path there is literally less work in case of Java

Doing more allocations isn't "less work". No matter how many times you mumble "But it's just a pointer bump" the alternative was no work.

> it has chosen different tradeoffs

Sure, it's easier to implement this, the New Jersey style. But that's not a benefit to anybody else, so if you're not Sun Microsystems (which you aren't, Sun no longer exists) then that's not actually a benefit at all and this was a bad trade.

Which is why people have expended an eyewatering amount of effort on Project Valhalla to some day fix this stuff.

[ahtihn]

Maybe I'm missing something but when would the 500 geese instances ever be stack allocated in Rust? That comparison seems unfair, the lifetime of that kind of object isn't going to be compatible with stack allocation.

Allocations are really really cheap in Java by the way, so I don't get how 500 allocations would even be an issue.

[tialaramex]

When you make a local variable with a Goose in Java, that's a heap allocation

    Goose jim = make_a_goose_somehow();  // Java, so jim is on the Heap, no way around it

When you make that variable in Rust...

    let jim : Goose = make_a_goose_somehow();  // Rust, jim is on the stack

Now, if we make a bunch of geese, maybe in a loop, and we put them into our growable array type...

    ArrayList<Goose> geese = new ArrayList<Goose>();
    // ... some loop eventually
      Goose a_goose = somehow_get_this_goose();   // That's an allocation
      geese.add(a_goose);

But in Rust...

    let geese: Vec<Goose> = Vec::new();
    // ... some loop eventually
      let a_goose : Goose = somehow_get_this_goose(); // But this is not
      geese.push(a_goose);

[gf000]

Memory is memory, stack is not a unique hardware element. It just tends to be hot, but so can certain part of "the heap".

Of course this is a toy example, but were the compiler not smart enough (it is surely smart enough in this case) then the "too simple rust" version may actually be slower - it would allocate a Vec on the stack, but only a length, capacity and a pointer is stored there, the actual backing array is on the heap. Then it would create stuff on the stack, and copy over those bytes to the heap, object by object (it's a move).

Meanwhile the java version would have a continuous region of memory, next to it it would have objects, and it would just write pointers to said objects without moving/copying anything.

Surely enough rust is smart enough to optimize out this useless move in this case, but I think you are painting a way too simplified picture here.

[kibwen]

What tialaramex is saying is that, in the Java code, there will be a separate allocation for every `a_goose` that gets added to the ArrayList, whereas the Rust code only has a single allocation for the backing storage for the Vec (not counting the resizes that occur as the ArrayList/Vec grows (both cases have ways to preallocate the proper size to avoid any resizes)). The context of this subthread is just to explain why someone who has Java experience might be prone to overcorrection when it comes to avoiding heap allocations.

[gf000]

But one is a "malloc allocation" and the other is a special "java allocation".

The two are apples and oranges and it makes no sense to compare them -- the latter is severalfold cheaper. Of course this comes at a price (read/write barriers, complex runtime, etc).

> The context of this subthread is just to explain why someone who has Java experience might be prone to overcorrection when it comes to avoiding heap allocations

That's what I don't really understand: if anything, someone with Java experience should be prone to avoid heap allocation in something like Rust as it is more expensive on almost every other platform. This is what I'm talking about, and apparently I wasn't clear.

[torginus]

This isn't necessarily true - at least not in a meaningful way - if Goose has a Vec in it, that'll end up on the heap no matter what.

[tialaramex]

(Sigh)

Fine. If we put a growable array type inside Goose the backing store for such a type would [if needed] live on the heap, unfortunately in Java we're not allowed to use a primitive type like the signed integer here, so lets put a growable array of Doodads where each Doodad is 64 bits.

So now each Java Goose has an ArrayList<Doodad> and yup, each Doodad goes on the heap, and then the ArrayList's backing store goes on the heap with pointers to the Doodads, and then the rest of the Goose goes on the heap too.

In Rust we skip most of those steps for Vec<Doodad> but if there's at least one Doodad we do need to actually have the backing store, the Doodads live directly in that backing store.

Of course if there aren't any Doodads, Java still pays to make the backing store anyway, that's just how Java works again. Rust doesn't do that, an empty Vec<Doodad> is just a dangling pointer, zero capacity, zero length. Since the length and capacity are zero we'll never dereference the pointer.

The story doesn't get better for Java if you make it more convoluted, that's not how any of this works.

[torginus]

To be clear I am not picking nits, nor am I trying to prove that 'language X' is better than Rust - but if you want to mention stack allocation as an advantage, then it has to be general enough to work all the time - in my sibling comment I mentioned arenas, which fix this issue. If you malloc in a function-local arena, both the Goose and the Vec inside it end up in there, and will be automatically freed on return.

[torginus]

Actually, this is my personal opinion, but in Java, allocating an object is just bumping a pointer, so it's much cheaper than doing a malloc in C. I personally don't think the stack is a good place to put temp values and I'm sure neither does Jon Blow, considering he put temporary arena backed allocators right in the language.

[tialaramex]

Having an arena allocator is completely unrelated. It's one of the features all of these languages out of the Handmade Community seem to have, including Odin (the subject of this thread) and Zig. It's not useless but it's a weird niche to target first.

Local variables don't somehow live in this arena allocator in Odin or Zig, and presumably (I haven't used it) not in Jai either. The obvious place for a local to live is the stack - unless you're Java and you need all your user defined types to live on the heap so that they have unique identities. So that's where locals live in Rust, Zig, Odin, C, C#, Go ...