News for hackers. Stuff that matters.

A comment on ORC – Nim's new memory managment. Parent comment

Re:ORC – Nim's new memory managment by necubi on Tuesday December 08, 2020 @08:44PM (#25354345)
The simplest way to do this is to use the low bit of the address (so long as you align your memory to at least 2 bytes this is fine as all addresses will end in 0) as a marker for whether you've already visited that pointer.

See https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na%...

And yes, you're correct that GCs handle cycles without issue (that's a large part of the reason to use tracing GC over other memory management strategies like ObjC's auto-reference counting).

[ Parent | on HN ]
Re:ORC – Nim's new memory managment by magicalhippo on Wednesday December 09, 2020 @01:14AM (#25355859)
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_Tort...

[ Parent | on HN ]
Re:ORC – Nim's new memory managment by necubi on Wednesday December 09, 2020 @01:41AM (#25355984)
"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.
[ Parent | on HN ]
Re:ORC – Nim's new memory managment by magicalhippo on Wednesday December 09, 2020 @02:30AM (#25356222)
And that would be the reminder not to post before breakfast :)

Still, fun algorithm.

[ Parent | on HN ]
Re:ORC – Nim's new memory managment by throwaway_pdp09 on Wednesday December 09, 2020 @05:30AM (#25357206)
I 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.
[ Parent | on HN ]