proposal: Go 2: Heapless Go

[snadrus]

Author background

• Would you consider yourself a novice, intermediate, or experienced Go programmer? I've written Go professionally for 9 years. Significant in-production Go language changes have been based on my requests before.
• What other languages do you have experience with? C++, C, JS, Python

Related proposals

• Has this idea, or one like it, been proposed before? Never for any language that I'm aware of.
• Does this affect error handling? No
• Is this about generics? No

Proposal

• What is the proposed change? To eliminate the heap, garbage collection, and non-determinism.
• Who does this proposal help, and why? Performance needs. Determinism use-cases from games to motor control.
• Please describe as precisely as possible the change to the language.
• What would change in the language spec? A compile-time flag: --heapless which will block heap use.
• Please also describe the change informally, as in a class teaching Go.
  Through escape analysis improvements, memory lifetimes would become understood.
  Banning pointer passing between threads will ensure simple variable lifetimes, then bringing-back provable cases will enable most modern code's reuse without a heap.
  Through mid-stack growth, data can always be allocated in-stack at its lowest variable.
  Far more information below.
• Is this change backward compatible? Yes as it's behind a flag. Later phases do not break the guarantee even without the flag.
  • Breaking the Go 1 compatibility guarantee is a large cost and requires a large benefit.
• Orthogonality: how does this change interact or overlap with existing features?
• Is the goal of this change a performance improvement? Yes
  • If so, what quantifiable improvement should we expect? Performance. Determinism for pauses.
  • How would we measure it? GC overhead vs stack grow overhead in real-world cases.

Costs

• Would this change make Go easier or harder to learn, and why?
  -- Single-thread: no language change
  -- Multi-thread: Simpler. A prover would keep usage safe.
  -- C API/Unsafe: more difficult.
• What is the cost of this proposal? (Every language change has a cost).
  -- Better compiler technology around variable lifetimes. Changed cases for performance. Some highly-optimized code may not get to participate initially as it's unprovable.
• How many tools (such as vet, gopls, gofmt, goimports, etc.) would be affected? Compiler and Linker.
• What is the compile time cost? It will increase as the linker will be making stack layout decisions and compiler & linker provers will be running
• What is the run time cost? Significant reductions
• Can you describe a possible implementation? Below.
• Do you have a prototype? (This is not required.)

Who needs a heap?

• Hello World? It shouldn't need a heap
• What about a simple, single-thread CLI that reads, modifies, and writes? It's needed here, but what if instead of allocating those bytes on the heap, we allocated on the end of the stack? It would work as long as:
  A. we have sufficient stack space AND
  B. there are no variables past the end of that stack space that we are moving.
  C. all consumers are in frames below it AND
  Solutions
  A has a simple solution that works well already: stack growth.
  B could be arranged with improved layout and only 1 grower per stack frame. We may need to insert fake frames for later growers.
  C would a strategy. We could move everything in the frames above the growing object, then fix the pointers (since we know all pointers in Go). This "heavy" operation is still a mutex-free memcpy then a consultation of stack maps. It's not cheap, but it's probably cheaper than garbage collection and can be done at known times (by consulting the capacity field).

Globals
They could be on that Goroutine's stack.

Multi-threading
The simplest solution for the compiler writer is to ban all pointer passing between threads and hide this hideous language change behind a flag. That would result in deep copies everywhere, no pointers in globals or chan messages!
This would also obsolete sync & atomic, but would ensure any code written will not experience undefined memory errors.
Clearly that's excessive.
Though you could still write a global cache (with chan), most multi-thread libraries break.
But building from that could include a bigger concept of recognizing const for globals so they could have pointers. Then pointers could be passed when they have well-understood lifetimes, such as having all globals on the main thread's stack so they should outlive other threads. Although it may be best to allow only provably safe data exchanges to preserve that property, such as all variable writes on a shared object must have readers and writers mutex-protected.
Scatter-gather patterns (and others) could be detected where the parent outlives the children that interact with the objects, thereby knowing the lifetimes.
Handoff cases could also be determined where a chan-write is the last access, so the object gets literally copied over (with no out-pointers) like in the case of HTTP listeners.
A kind of cat-and-mouse of rich use-cases could grow here for years and result in nearly the same experience of today.

Stacks
Bigger stacks are inevitable here, as is growth. Having one large allocation makes good sense here. Optimizations could exist to provide enough capacity for later calls to grow lower stacks (PGO). The main stack will be exceptionally tall as it will hold globals. Stacks will clearly be allocated "in the heap" but it can be a simple mutexed allocator atop malloc/free, with the last pop being a stack free. Stack height management may need some care if stacks are re-used and have a huge top that remains unused.

Unsafe/CGO
These will need to have their pointers update-able for stack rearranges, so the API will change significantly to include a 'moved' callback.

Performance
It's not uncommon to see 10% of CPU usage in the allocator and 15% in the garbage collector. Add mutex time and you can get a significant load. The allocator is inline, and the garbage collector stops the world for a short while. Comparing those against the stack growth would be the real measure. But the allocator gets simpler: "Do I need to grow the target stack frame because the grower is at capacity?
Maniacal stack-growth-in-a-loop can't really happen much because that lower stack would stay grown. Stack shrinkage may become a need, but most apps grow to a size and stay there when they're long-running (like a cache getting populated).

[ianlancetaylor]

I'm not sure what to do with this proposal. There is no chance that the core Go team will work on this. But I can see that the idea has potential value. I suggest that you work with, or emulate, TinyGo (https://tinygo.org/), which seems like a closer fit for what you are interested in: a variant version of Go designed to work on smaller systems.

[ianlancetaylor]

This is not something that is feasible for the Go team to do, so as a proposal this is a likely decline. Leaving open for four weeks for final comments.

[ianlancetaylor]

No further comments.