3 ms·
Don't know if any GCs use it, but if modifying the pointers is not possible then one alternative is Floyd's cycle-finding algorithm[1] which uses constant stora
by magicalhippo 6y ago
Don't know if any GCs use it, but if modifying the pointers is not possible then one alternative is Floyd's cycle-finding algorithm[1] which uses constant storage (two pointers).
[1]: https://en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tortoise_and_Hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tort...
- necubi 6y ago"Finding cycles" is not really the problem a GC is trying to solve. It's trying to find all of the non-reachable data, across a possibly cyclic graph. It just has to ensure that it doesn't loop infinitely while traversing that graph.
- magicalhippo 6y agoAnd that would be the reminder not to post before breakfast :) Still, fun algorithm.
- throwaway_pdp09 6y agoI purposefully used the word 'efficient' in my original post. Of course you can find cycles many ways, but floyd's (or similar) are not acceptably fast and never can be in general.