Concurrent, incremental, and generational mark and sweep garbage collection

A system for garbage collection of objects in a computer storage, the system comprising:

• at least one processor;
• and
• a memory communicatively coupled to the at least one processor, the memory storing instructions, which, when executed by the at least one processor, perform a method comprising:
• providing a logical clock, the logical clock being configured to monotonically increase a current wave value;
• organizing each of the objects into a directed acyclic graph;
• associating each of the objects with a mark wave number;
• associating each of the objects with a subgraph wave number, the subgraph wave number being a minimum of the mark wave numbers associated with other objects in the directed acyclic graph to which the object refers;
• when the logical clock increases the current wave value:
• deleting, from the computer storage, objects in the directed acyclic graph with the mark wave number less than the current wave value of the logical clock;
• and
• when at least one new object is added to the directed acyclic graph in the computer storage:
• setting the mark wave number associated with the at least one new object to a new mark wave number, the new mark wave number being equal to or greater than the current wave value of the logical clock;
• and
• updating the mark wave number of each object in a new subgraph of the directed acyclic graph to which the at least one new object refers, the updated mark wave number being a function of the mark wave number associated with each object and the current wave value of the logical clock at which the mark wave number was set.

A non-transitory computer-readable storage medium having embodied thereon instructions, which, when executed by one or more processors, perform a method for garbage collection of objects in a computer storage, the method comprising:

• providing a logical clock, the logical clock being configured to monotonically increase a current wave value;
• organizing each of the objects into a directed acyclic graph;
• associating each of the objects with a mark wave number;
• associating each of the objects with a subgraph wave number, the subgraph wave number being a minimum of the mark wave numbers associated with other objects in the directed acyclic graph to which the object refers;
• when the logical clock increases the current wave value:
• deleting, from the computer storage, objects in the directed acyclic graph with the mark wave number less than the current wave value of the logical clock;
• and
• when at least one new object is added to the directed acyclic graph in the computer storage:
• setting the mark wave number associated with the at least one new object to a new mark wave number, the new mark wave number being equal to or greater than the current wave value of the logical clock;
• and
• updating the mark wave number of each object in a new subgraph of the directed acyclic graph to which the at least one new object refers, the updated mark wave number being a function of the mark wave number associated with each object and the current wave value of the logical clock at which the mark wave number was set.