We need to talk about garbage collection
The weekday program of last chapter showed a memory leak in our RPN machine. Every time you call the operator, the string and array constants fill the heap and never go away. This will be a problem if you create operators that are used often.
So we need to remove the entries in the heap when they are not used any more. This is not trivial. How do we know that a string will not be used any more?
A strategy is reference counting. In the RPN, a string or an array can either be referenced by the stack or by a key in a dictionary. For each string or array, the reference counter increases when it is pushed on a stack or assigned to a key. The references counter decreases when it is consumed in the stack or the key in the dictionary is assigned a new value.
We create a new class rpnHeapElement which implements a counter, which is initially 0 and two methods. inc() increases the counter. dec() decreases the counter and checks if the counter is 0. If it is 0, the heap value is set to null.
This removes the values from the heap but will still keep them as null in the array, so the heap array still grows. To contain that, instead of growing the array on each instance of a new string or array, we will reuse the values that are null. We rewrite the constructors to achieve that.
Special case: When we destroy an array, we also have to dec() all elements referenced by the array.
We use this occasion to add unitTest also to the RPN parser to check every branch of the parser is used at least once.
We need to adapt the representation of the heap in the postScriptEditor console.
Only some operators work on strings and arrays, so we modify these.
Basically, the garbage collection seems to work. The heap fills with (abc), (def), (ghi) then (abc) is freed an used by (jkl) and (ghi) is freed.
| code | heap |
| /foo (abc) | (abc) |
| def | (abc) |
| /bar foo def | (abc) |
| /foo (def) | (abc) (def) |
| def | (abc) (def) |
| /bar (ghi) | (abc) (def) (ghi) |
| def | null (def) (ghi) |
| /bar (jkl) | (jkl) (def) (ghi) |
| def | (jkl) (def) null |
We try the garbage collection on the weekday algorithm.
Seems to work.
The codebase including the unitTest has now 950 lines ps20240710.js