17:14
Okay so I went for a walk and I thought about the garbage collector on my walk and I want to start by specifying the goals of what I actually want and how it acts:
- It is synchronous, only a single thread may allocate an object at once.
- It is reference counted, so objects are considered free when there are no longer any references to them.
- It is pooled, just allocate and reserve a chunk of memory and just use that instead of making tons of mini allocations. This would of course allow for pools to be allocated in additional chunks and such. It makes fitting things potentially difficult if fragmentation happens but that could be mitigated by aligning objects (small objects together, large objects alone) and not using the first available space.
- Allow reference counting to happen even as the allocator is doing things or garbage collecting things. That way there needs to be no locks and such when increasing or decreasing counts.
- Lazy freeing, objects which are no longer referenced are not cleared out of the pool unless an allocation overwrites it.
- Minimal amount of memory, keep it tiny.
- Object bits: (At a minimum)
- 1b: Object cycle bit
- 11b: Object size???
- Maybe logarithmic or bit shift.
- 5 bits can represent 1, 2, 4, ..., 4294967296
- 12b: Object class type, index to some class table.
- 16b: Object hash code.
- I wanted to give this less bits, but that makes hashes a bit bad so I want to keep it to 16-bits for performance.
- 1b: Reference count overflow bit.
- If this is set then reference counter overflowed and bad things happen now.
- 23b: Reference count
- This is 24-bits, this value will never drop below zero so there will never be any sign flipping issues.
- Object bits: (At a minimum)
- See if it is possible to have a null object which can be operated on with
reference counts but it has no value. This means though that any such
fields and such will need to be initialized to this specific
null
reference. However, if this is done then it would solve the fact that references are not needed. Although the issue is that we would have to check. But any code which checks againstnull
could just have a constantnull
value index to be compared against. So this makes the stuff less complicated. Just the memory for each object must have the fields initialized tonull
in the object code as zero memory is not going to work. - Reference counting is always atomic.
- When memory is exhausted a mark and sweep garbage collection might able to be ran, however the issue here is that we would need to know about objects and such which would add more memory and code. So since this needs to be small and not need this memory, no mark and sweep is to be used. If there are cyclic references they shall remain forever.
The garbage collector will have a cycle bit and each object will have a cycle bit. If the cycle bit matches then that means the object was not yet traversed during garbage collection, but if it does not match then it was. All allocations that happen will be set to the current cycle bit. As a note other objects are reference count increased first before the old one is decreased so no objects are lost ever.
It would be nice to have implicit object sizes though, like using a logarithmic or exponential scale. That way size can be encoded in the object data as needed.
18:09
With 2048 different size values, a full 31-bit range is with the following algorithm:
- 2^(2^log(x*44))
Also, regions which are in the free state free do not need a reference count they can pretty much be:
- 32b: Flag for free space
- 32b: How big this chunk is.
18:19
I would need a linked list of free chunks if I want to allocate certain objects at the ends.