I've heard about scanning of the stack but I'm not sure if I get it. Is the strategy literally to not keep track of references at all, and simply do a sequential scan over the entire memory looking for bytes that look like they're pointers into the heap, and then assuming they are roots? And then you look them up in the allocation records and mark them as still in use? You'd have to scan them in turn as well to know if they've got references to other heap locations right?
Edit: ah he says assume the heap is precisely traced (somehow?) so I guess it would already been known what references are in there.
Both strategies start from roots (e.g. the stack) and then transitively chase pointers. Any memory reachable this way is live.
To do this chasing precisely you need some metadata, saying which fields are pointers vs other data like ints. For OOP languages this metadata is stored with the vtables for objects. For the stack you need similar metadata, at the very least how many pointers there are if you put them first in the stackframe.
Not having this metadata and conservatively treating random ints as pointers isn't always catastrophic, but it has some drawbacks. Two big ones:
- a moving GC is tough, you have to update pointers after moving an object but can't risk updating random ints that happen to have that value
- You do more work during GC chasing random non-pointers, and free less memory meaning more GC runs
Generating ths precise GC metadata for stackframes is sort-of easy.You need specific Safe-Points where all data is at known locations for the GC to work anyway, usually by spilling resgisters to the stack. These GC checkpoints usually coincide with heap allocation, which is why long non-allocating loops can block stop-the-world GC and send other threads into a spin-lock in many GC implementations
Maybe a non-precise GC could treat registers as possible pointers and skip spilling to the stack for Safe-Points? There are alternatives to spilling like a precise stack-map for each program instruction (so every instruction is a safe point), but those are expensive to process. Usually only used for debugging or exception handling, not something frequent like GC
Pretty much, yes. There are optimizations done so it would not need to scan every possible location. Pointers should be properly aligned of course but also things like having separate heap regions for data that has no pointers in it (large data arrays) to skip scanning entirely.
the heap is a lot easier to trace than the stack because objects on the heap are put there explicitly, so as long as you know their type, it's pretty easy to know where their pointers are. the tricky part of the stack is that once your compiler has figured out that something can go in the stack, it also might want to do things like store part of the object only in registers or something like that.
Comments
I've heard about scanning of the stack but I'm not sure if I get it. Is the strategy literally to not keep track of references at all, and simply do a sequential scan over the entire memory looking for bytes that look like they're pointers into the heap, and then assuming they are roots? And then you look them up in the allocation records and mark them as still in use? You'd have to scan them in turn as well to know if they've got references to other heap locations right?
Edit: ah he says assume the heap is precisely traced (somehow?) so I guess it would already been known what references are in there.
Both strategies start from roots (e.g. the stack) and then transitively chase pointers. Any memory reachable this way is live.
To do this chasing precisely you need some metadata, saying which fields are pointers vs other data like ints. For OOP languages this metadata is stored with the vtables for objects. For the stack you need similar metadata, at the very least how many pointers there are if you put them first in the stackframe.
Not having this metadata and conservatively treating random ints as pointers isn't always catastrophic, but it has some drawbacks. Two big ones:
- a moving GC is tough, you have to update pointers after moving an object but can't risk updating random ints that happen to have that value
- You do more work during GC chasing random non-pointers, and free less memory meaning more GC runs
Generating ths precise GC metadata for stackframes is sort-of easy.You need specific Safe-Points where all data is at known locations for the GC to work anyway, usually by spilling resgisters to the stack. These GC checkpoints usually coincide with heap allocation, which is why long non-allocating loops can block stop-the-world GC and send other threads into a spin-lock in many GC implementations
Maybe a non-precise GC could treat registers as possible pointers and skip spilling to the stack for Safe-Points? There are alternatives to spilling like a precise stack-map for each program instruction (so every instruction is a safe point), but those are expensive to process. Usually only used for debugging or exception handling, not something frequent like GC
Pretty much, yes. There are optimizations done so it would not need to scan every possible location. Pointers should be properly aligned of course but also things like having separate heap regions for data that has no pointers in it (large data arrays) to skip scanning entirely.
the heap is a lot easier to trace than the stack because objects on the heap are put there explicitly, so as long as you know their type, it's pretty easy to know where their pointers are. the tricky part of the stack is that once your compiler has figured out that something can go in the stack, it also might want to do things like store part of the object only in registers or something like that.