[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.

diff --git a/mono/sgen/sgen-gray.c b/mono/sgen/sgen-gray.c
index 3c9fcd5c5731f905fe09821c44fa226a18b990bf..bb8f58c05904e77743be1c6bd7f45f598feb1d23 100644 (file)
--- 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 51371c5061c591fff39ad48b0b70a890a95dce85..a380a18bb0a916e9a71682f427d685f0064122a2 100644 (file)
--- 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 f32d593186d9471b1f1e73f12f30a30df259c8e9..80e8ae36ffe46f927b9711f53556c676910bdcab 100644 (file)
--- 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)