Before you start reading, I want to clarify that this is not a technical article on the Mark and Sweep Algorithm.
This is a story about weapon possed by a great warrior called Barbarika. Barbarika was grandson of Gadothgaja (Bheema’s son). He possessed a very powerful weapon — a bow and quiver with 3 arrows.
The speciality of the weapon is that with just those 3 arrows he can vanquish the enemies and win any war.
This is how it worked.
First arrow — marks everyone in the vicinity.
Second arrow — marks the allies.
Third arrow — kills everyone not marked as an ally.
The ancient warrior’s weapon had quite an elaborate and effective way to wipe things out. Not so different, I must say, from our modern-day garbage collectors!
The first arrow gets references to all the root objects in the heap; the second arrow traverses depth-first and marks all reachable objects; the third arrow deallocates all unreferenced objects.
Technically, Mark & Sweep is usually described in two phases — but what’s the harm in stretching it a bit for a fun mapping with mythology?
(In classic Mark & Sweep these are often collapsed into two phases — mark and sweep — but for the sake of our mythological mapping we treat root‐identification as a distinct “first arrow.”)
Without GC, the memory is indeed a battlefield :)