Closure allocation

The only object that requires allocation is a closure. Different allocation policies can be applied depending on the specifics of the closure.

  • Empty. There is no content in the closure. The procedure can be inlined.
  • Unallocated. The closure is never allocated. The procedure is dead code.
  • Constant. The closure is a compile time constant. The procedure can be inlined.
  • Unique. There will be either zero or one instance of the closure. It can be statically allocated. Allocations can overlap provided liveliness analysis shows they don’t co-occur.
  • Stack. There can zero or more instances, but they are deallocated in reverse order of allocation. They can be managed using a stack.
  • Other. These closures require a garbage collection mechanism.

Heap allocation algorithms

https://www.freertos.org/a00111.html

Reference counting

https://stackoverflow.com/questions/3125310/for-real-time-programming-does-reference-counting-have-an-advantage-over-garbag

Here are the guarantees you can provide with reference counting:

Constant time overhead at an assignment to adjust reference counts.

Constant time to free an object whose reference count goes to zero. (The key is that you must not decrement that object's children right away; instead you must do it lazily when the object is used to satisfy a future allocation request.)

Constant time to allocate a new object when the relevant free list is not empty. This guarantee is conditional and isn't worth much.

Here are some things you can’t guarantee with reference counting:

Constant time to allocate a new object. (In the worst case, the heap may be growing, and depending on the system the delay to organize new memory may be considerable. Or even worse, you may fill the heap and be unable to allocate.)

All unreachable objects are reclaimed and reused while maintaining constant time for other operations. (A standard reference counter can't collect cyclic garbage. There are a variety of ingenious workarounds, but generally they invalidate constant-time guarantees for simple operations.)

http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

http://www.cs.technion.ac.il/%7Eerez/Papers/refcount.pdf

With 64 bit pointers the reference counter can be stored in the lower three bits or many of the upper bits.