Comment by jokoon | Hacker News Reader

Comment by jokoon | Hacker News Reader

I wonder, isn't it working on the stack much faster than working on the heap anyway?

So when you query data on the heap, shouldn't you just query larger objects to put it on the stack, and work from there, instead of using the heap so often ?

With that in mind wouldn't that render garbage collecting almost irrelevant if your code is well designed, by not working too much on the heap ?

It's true that more ram makes the GC more relevant, but if it's an excuse for negligent software design, maybe GCs are not such a good idea. It's good to have features that make the job of the programmer easier, but if it only save the time of the skilled programmers who knows a little about how it works underneath, is it such a good idea ?

You can hardly convince that simple tools and predictable behaviors in machines are not the safest way of having fair results.

A programming language is already a big shortcut to work faster, and I doubt you should try to work even faster if it means creating new drawbacks.

The stack and the heap are both just regions of memory, so there's nothing inherently faster about using the stack. The difference is the memory management strategy: Usually, stack variables are all allocated at the beginning of a function, and all deallocated at the end. If all of the memory your program needs is tied to a particular scope like that, then it's certainly faster than any other memory-management strategy. If you need to share data between scopes, build complicated data structures of indeterminate compile-time size, or allocate large blocks of memory (the stack is usually limited in size), then you have to do something different (like use the heap).

That said, I think the Rust approach to memory management is really interesting: try to tie all allocated memory to some scope, and keep track of when ownership is borrowed by or moved to a different scope.

The inherent benefit to the stack is the memory region stays hot in cache due to natural use of the stack. That's your fast reusable buffer for temporaries.

In addition, of course, cleanup/reclaim of the stack space is pointer bump, so you get pointer bump allocation and deallocation, effectively.

True, but you could do the same thing in any region of memory. The only thing that using "the stack" buys you is that there are a few special instructions to allocate / deallocate one machine word at a time (if you store the "top-of-heap" pointer in a specific register), and you get a bit more locality by virtue of return addresses being stored next to your locals and temporaries. (For x86 processors at least; maybe other architectures treat the stack in a more special way, I don't know.)

I'm almost positive that x86 doesn't really have special stack instructions, aside from call (push pc +sizeof(call)) onto $esp and jump.

I know MIPS (and possibly other RISC architectures) don't have an implicit 'stack' register, just one that used by convention. They do have jump and link instructions which write $pc+4 into another register.

Afaik, LLVM and quite possibly GCC just add/subtract $esp for the initial allocation / final deallocation of the stack.

More recent intel x86 process I believe have a small separate d-cache for the stack.

There's also push/pop.

You got me there. I do now recall staring at the disassembly of LLVM produced code (LLVM 3.0ish) and seeing pushs/pops.

> True, but you could do the same thing in any region of memory. The only thing that using "the stack" buys you is that there are a few special instructions to allocate / deallocate one machine word at a time (if you store the "top-of-heap" pointer in a specific register)

This is pretty much what a TLAB is in Hotspot JVM, except of course the pointer never moves backwards (once the TLAB is filled up, it retires, and then can get assigned to a different thread to start allocating from the beginning). Each allocation into the TLAB moves allocations further into the region -- there's never any reuse until the TLAB starts afresh.

The stack locality comes from the rest of the stack execution mechanics keeping this region very warm, and the majority of the read/write action to the stack is localized (apart from large stack allocations that may temporarily expand the region's use).

Except that a TLAB is worse for cache than a stack.

Look at what happens when you call a bunch of small methods that each allocate a couple things. With a stack, everything stays in nice proximity automaticially. With a TLAB, you quickly fill the TLAB, get another one, get another one, and so on.

Effectively: the stack does any garbage collection that can be statically determined for free, keeping data in cache that actually matters, whereas with TLABs you need to wait for it to pass through GC before any of it is reused.

Right, that's why it bothers me when TLAB and stack are compared.

Garbage collection worries about reachability of objects, not of access patterns. Some GC setups may not apply read/write barriers to stack objects as they are not required.

The difficultly with stack centric working is that you have to ensure that any object produced that is put back into the heap only references heap objects. Otherwise, by any sane language/style definition, you've made a mistake in referencing stack objects from the heap.

Accesses to the stack or heap, except in very specific circumstances[1] are equal but allocation/deallocation process are widely different.

Avoiding introducing GC work has/(can have) the tendency to "fight the language" problems. Consider writing Haskell code that does not allocate on the heap for example, it's damn near impossible. Otoh a Java program can shift some heap allocations into stack allocations.

[1] Afaik, some intel processors have small dedicated D-caches from stack relative load/stores. On the order of 128 bytes. I am probably wrong though.

Sure, but on modern servers, the amount of data you can put on the stack (or stacks) amounts to no more a few percent of RAM. The smartest thing you can do with the rest, is put as much of your DB data there, and that data has an arbitrary lifetime, and is read -- and written -- concurrently. So most of the memory activity on large servers is going to be on the heap. If you put on the stack everything that can be done on the stack, you've reduced your heap usage by, say, 2%. True, the kind of memory work on the stack and on the heap is very different, but the two problems are of entirely different magnitude and nature.

I think the reason many people say "just use the stack more", is that most people delegate the hard work to a DB, and let the DB engineers worry about using the heap well. But the best way to use a DB is if it is in memory and in process.

> I wonder, isn't it working on the stack much faster than working on the heap anyway?

Working on GC-managed memory is faster still.

Remember, not all allocations involve an actual heap allocation. Conversely, not all deletions cause a 'free()' operation on the heap.

> Working on GC-managed memory is faster still.

Care to elaborate?

Replying to GP comment and you as such.

Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads.

This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform general heap allocations into thread local or stack allocations.

[1] Let me define reachability type as {can be accessed from anything, can be accessed from this thread only but is of indefinite lifetime, can be accessed from this thread only and it's reference is not take by any object allocated onto my local heap, ...}

Hotspot JVM C2 compiler does this optimization, with varying degree of success but generally brittle and completely opaque. It doesn't actually stack allocate them technically speaking, just scalarizes them into registers. Should also mention that this requires sufficient inlining to take place at minimum (unfortunately, hotspot does not do flow sensitive analysis so any conditional logic that makes the object escape, even if not taken, will be regarded as escaping - graal handles this better), which doesn't always happen for a variety of reasons.

But what does this have to do with heap being faster than stack? This is doing roughly the same thing as a compiler that supports explicit stack allocations.

Reply on news.ycombinator.com