From 4ea34f62a557dc9171bf912f4c8b55694c63c1bb Mon Sep 17 00:00:00 2001
From: Vlad Brezae <brezaevlad@gmail.com>
Date: Fri, 21 Oct 2016 14:05:35 +0300
Subject: [PATCH] [sgen] Spread the initial roots of workers

A parallel phase starts with enqueuing of jobs and of sections to the distribute gray queue. In order to have a good work distribution we split jobs into multiple smaller jobs. We now do the same with the initial gray queue sections, by trying to always have a minimum number of starting sections.
---
 mono/sgen/sgen-gray.c    | 62 ++++++++++++++++++++++++++++++++++++++++
 mono/sgen/sgen-gray.h    |  1 +
 mono/sgen/sgen-workers.c |  2 ++
 3 files changed, 65 insertions(+)

diff --git a/mono/sgen/sgen-gray.c b/mono/sgen/sgen-gray.c
index 3c9fcd5c573..bb8f58c0590 100644
--- a/mono/sgen/sgen-gray.c
+++ b/mono/sgen/sgen-gray.c
@@ -139,6 +139,68 @@ sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor de
 #endif
 }
 
+/*
+ * We attempt to spread the objects in the gray queue across a number
+ * of sections. If the queue has more sections, then it's already spread,
+ * if it doesn't have enough sections, then we allocate as many as we
+ * can.
+ */
+void
+sgen_gray_object_spread (SgenGrayQueue *queue, int num_sections)
+{
+	GrayQueueSection *section_start, *section_end;
+	int total_entries = 0, num_entries_per_section;
+	int num_sections_final;
+
+	if (queue->num_sections >= num_sections)
+		return;
+
+	if (!queue->first)
+		return;
+
+	/* Compute number of elements in the gray queue */
+	queue->first->size = queue->cursor - queue->first->entries + 1;
+	total_entries = queue->first->size;
+	for (section_start = queue->first->next; section_start != NULL; section_start = section_start->next) {
+		SGEN_ASSERT (0, section_start->size == SGEN_GRAY_QUEUE_SECTION_SIZE, "We expect all section aside from the first one to be full");
+		total_entries += section_start->size;
+	}
+
+	/* Compute how many sections we should have and elements per section */
+	num_sections_final = (total_entries > num_sections) ? num_sections : total_entries;
+	num_entries_per_section = total_entries / num_sections_final;
+
+	/* Allocate all needed sections */
+	while (queue->num_sections < num_sections_final)
+		sgen_gray_object_alloc_queue_section (queue);
+
+	/* Spread out the elements in the sections. By design, sections at the end are fuller. */
+	section_start = queue->first;
+	section_end = queue->last;
+	while (section_start != section_end) {
+		/* We move entries from end to start, until they meet */
+		while (section_start->size < num_entries_per_section) {
+			GrayQueueEntry entry;
+			if (section_end->size <= num_entries_per_section) {
+				section_end = section_end->prev;
+				if (section_end == section_start)
+					break;
+			}
+			if (section_end->size <= num_entries_per_section)
+				break;
+
+			section_end->size--;
+			entry = section_end->entries [section_end->size];
+			section_start->entries [section_start->size] = entry;
+			section_start->size++;
+		}
+		section_start = section_start->next;
+	}
+
+	queue->cursor = queue->first->entries + queue->first->size - 1;
+	queue->num_sections = num_sections_final;
+}
+
 GrayQueueEntry
 sgen_gray_object_dequeue (SgenGrayQueue *queue)
 {
diff --git a/mono/sgen/sgen-gray.h b/mono/sgen/sgen-gray.h
index 51371c5061c..a380a18bb0a 100644
--- a/mono/sgen/sgen-gray.h
+++ b/mono/sgen/sgen-gray.h
@@ -129,6 +129,7 @@ void sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescript
 GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue);
 GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue);
 GrayQueueSection* sgen_gray_object_steal_section (SgenGrayQueue *queue);
+void sgen_gray_object_spread (SgenGrayQueue *queue, int num_sections);
 void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section);
 void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue);
 void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list);
diff --git a/mono/sgen/sgen-workers.c b/mono/sgen/sgen-workers.c
index f32d593186d..80e8ae36ffe 100644
--- a/mono/sgen/sgen-workers.c
+++ b/mono/sgen/sgen-workers.c
@@ -459,6 +459,8 @@ sgen_workers_assert_gray_queue_is_empty (void)
 void
 sgen_workers_take_from_queue (SgenGrayQueue *queue)
 {
+	sgen_gray_object_spread (queue, sgen_workers_get_job_split_count ());
+
 	for (;;) {
 		GrayQueueSection *section = sgen_gray_object_dequeue_section (queue);
 		if (!section)
-- 
2.25.1