Marking objects for graph traversals.
dawid.weiss at gmail.com
Thu Mar 22 16:02:52 PDT 2012
I realize the answer is probably "your jvm will core dump", but I
can't resist to ask nonetheless...
There are many problems that process object graphs in which a "accept
each object once" idiom is required. An example in the standard
library would be Arrays#deepToString but virtually any graph-scanning
(including garbage collectors) will face the same problem of detecting
whether a node has been traversed or not.
Typically one just uses a "Set<Object> visited" and shoves references
in there as they are traversed but this requires a lot of memory for
I admit I intellectually exercised the idea of fiddling with oops and
somehow "tainting" object references in-place with the possibility of
reverting them after the traversal... Would this be possible at all
(given the possibility of a safepoint and gc at any time)? Yes, I
realize it's beyond dirty -- I am looking for theoretical options
rather than something that could be run on production machines.
Or maybe there are other ways of doing this?
More information about the hotspot-dev