4 ms·
> Imagine a degenerate scenario: using up all of your memory to allocate a single linked list, and then dropping it all at once. Sorry, I am not sure I follow
by joakleaf 10y ago
> Imagine a degenerate scenario: using up all of your memory to allocate a single linked list, and then dropping it all at once.
Sorry, I am not sure I follow this example. I assume you create a list O(n) in size where n is the maximum allowed by memory (not sure memory matters).
For RC: You drop the single list, as you drop the head, you decrease reference counts to each member (one-by-one), check reference counts for 0, and free them. I.e. taking O(n) time.
For Tracing GC: You'll eventually sweep, then check if each members is unreachable as determined by the sweeper, and free each member. I.e. also taking O(n) time.
Am I overlooking something?
- sklogic 10y ago> You'll eventually sweep That's the key here. Eventually. When it is convenient to do so. You have a very fine grained control over when sweeper process may do its dirty job. It's far more complicated with RC to ensure that it only does a certain small amount of work once in a while. And with a loop detection, you have to do everything at once. Also, with mark&sweep you can keep your tags somewhere else altogether and avoid touching (and invalidating) the actual data at all, at no additional cost.
- joakleaf 10y agoOK, it wasn't clear to me that we were talking about RC with cycle detection.
- deleted 10y ago[deleted]