[sgen] Compact allocated block list

It helps with its repeated traversal and improves work distribution when using parallel modes.

diff --git a/mono/sgen/sgen-array-list.c b/mono/sgen/sgen-array-list.c
index 0247a6b12695c3e1368d327fefd5f58dd31fd2da..2fd54d986d0d6ded4b26dc3efb5203198bd4d3ec 100644 (file)
--- a/mono/sgen/sgen-array-list.c
+++ b/mono/sgen/sgen-array-list.c
@@ -207,4 +207,27 @@ sgen_array_list_default_is_slot_set (volatile gpointer *slot)
        return *slot != NULL;
 }
 
+/* Removes all NULL pointers from the array. Not thread safe */
+void
+sgen_array_list_remove_nulls (SgenArrayList *array)
+{
+       guint32 start = 0;
+       volatile gpointer *slot;
+       gboolean skipped = FALSE;
+
+       SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
+               if (*slot) {
+                       *sgen_array_list_get_slot (array, start++) = *slot;
+                       if (skipped)
+                               *slot = NULL;
+               } else {
+                       skipped = TRUE;
+               }
+       } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
+
+       mono_memory_write_barrier ();
+       array->next_slot = start;
+       array->slot_hint = start;
+}
+
 #endif

diff --git a/mono/sgen/sgen-array-list.h b/mono/sgen/sgen-array-list.h
index 12e8bcdecf70f419c23c0cc65bcad7faac32e396..2ae3e63c2e2e5a3566af29a6dba2c369ee570807 100644 (file)
--- a/mono/sgen/sgen-array-list.h
+++ b/mono/sgen/sgen-array-list.h
@@ -135,6 +135,6 @@ guint32 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gbool
 guint32 sgen_array_list_find (SgenArrayList *array, gpointer ptr);
 gboolean sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data);
 gboolean sgen_array_list_default_is_slot_set (volatile gpointer *slot);
-
+void sgen_array_list_remove_nulls (SgenArrayList *array);
 
 #endif

diff --git a/mono/sgen/sgen-marksweep.c b/mono/sgen/sgen-marksweep.c
index edefa9e1e0814ac36e02d23d437050f0f7ad0a27..f2d80765a97f2e65642712571d8dd774438debef 100644 (file)
--- a/mono/sgen/sgen-marksweep.c
+++ b/mono/sgen/sgen-marksweep.c
@@ -212,6 +212,7 @@ static SgenArrayList allocated_blocks = SGEN_ARRAY_LIST_INIT (NULL, sgen_array_l
 /* non-allocated block free-list */
 static void *empty_blocks = NULL;
 static size_t num_empty_blocks = 0;
+static gboolean compact_blocks = FALSE;
 
 /*
  * We can iterate the block list also while sweep is in progress but we
@@ -1611,6 +1612,8 @@ sweep_start (void)
 
        sgen_workers_foreach (GENERATION_NURSERY, sgen_worker_clear_free_block_lists);
        sgen_workers_foreach (GENERATION_OLD, sgen_worker_clear_free_block_lists);
+
+       compact_blocks = TRUE;
 }
 
 static void sweep_finish (void);
@@ -1984,6 +1987,18 @@ major_start_nursery_collection (void)
 #endif
 
        old_num_major_sections = num_major_sections;
+
+       /* Compact the block list if it hasn't been compacted in a while and nobody is using it */
+       if (compact_blocks && !sweep_in_progress () && !sweep_blocks_job && !sgen_concurrent_collection_in_progress ()) {
+               /*
+                * We support null elements in the array but do regular compaction to avoid
+                * excessive traversal of the array and to facilitate splitting into well
+                * balanced sections for parallel modes. We compact as soon as possible after
+                * sweep.
+                */
+               sgen_array_list_remove_nulls (&allocated_blocks);
+               compact_blocks = FALSE;
+       }
 }
 
 static void