From b319e134efc9d4d52593969f6354de825e85aca0 Mon Sep 17 00:00:00 2001
From: Vlad Brezae <brezaevlad@gmail.com>
Date: Sat, 24 Jun 2017 23:40:48 +0300
Subject: [PATCH] [sgen] Compact allocated block list

It helps with its repeated traversal and improves work distribution when using parallel modes.
---
 mono/sgen/sgen-array-list.c | 23 +++++++++++++++++++++++
 mono/sgen/sgen-array-list.h |  2 +-
 mono/sgen/sgen-marksweep.c  | 15 +++++++++++++++
 3 files changed, 39 insertions(+), 1 deletion(-)

diff --git a/mono/sgen/sgen-array-list.c b/mono/sgen/sgen-array-list.c
index 0247a6b1269..2fd54d986d0 100644
--- 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 12e8bcdecf7..2ae3e63c2e2 100644
--- 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 edefa9e1e08..f2d80765a97 100644
--- 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
-- 
2.25.1