Allocation
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.