I was working on a Treap implementation to accelerate the GC
add/remove root/range functions when I realised it is not
specified how multiple calls to addRange with the same parameter
p (and possibly different size parameter,) should be handled.
Currently the case for add/remove root is if you call addRoot
with the same parameter N times, then the GC will only stop
scanning the root once N calls to removeRoot are made.
The current situation for removeRange is different: it assumes
FiFo order.
For example:
GC.addRange(p, 64);
GC.addRange(p, 32);
GC.addRange(p, 16);
// assumes we want to remove scanning of p[32..64]
GC.removeRange(p);
// assumes we want to remove scanning of p[16..32]
GC.removeRange(p);
// assumes we want to remove scanning of p[0..16]
GC.removeRange(p);
This behaviour seems like it might lead to non-deterministic
behaviour in a system which relies heavily on this API.
My question is: how should multiple calls to add/remove
range/root with the same parameter p be handled?
One possibility is to conservatively remove ranges and add
another removeRange function which takes a size parameter to
allow non-conservative removal.
Another possibility would be to specify that the stops scanning a
root/range after the first call to remove root/range (i.e.
duplicate calls are ignored.) This would be a higher performance
option but would also cause breakage.
Either way, we should _specify_ how the duplicate call case
should be handled!
Please discuss!
