assigned TLABs and if that's more than some percentage of the
nursery size, reduce the TLAB size.
+ *) Explore placing unreachable objects on unused nursery memory.
+ Instead of memset'ng a region to zero, place an int[] covering it.
+ A good place to start is add_nursery_frag. The tricky thing here is
+ placing those objects atomically outside of a collection.
+
+
*/
#include "config.h"
#ifdef HAVE_SGEN_GC
static long long stat_global_remsets_processed = 0;
static long long stat_global_remsets_discarded = 0;
+static long long stat_wasted_fragments_used = 0;
+static long long stat_wasted_fragments_bytes = 0;
+
static int stat_wbarrier_set_field = 0;
static int stat_wbarrier_set_arrayref = 0;
static int stat_wbarrier_arrayref_copy = 0;
*/
static guint32 tlab_size = (1024 * 4);
+/*How much space is tolerable to be wasted from the current fragment when allocating a new TLAB*/
+#define MAX_NURSERY_TLAB_WASTE 512
+
/* fragments that are free and ready to be used for allocation */
static Fragment *nursery_fragments = NULL;
/* freeelist of fragment structures */
static void null_link_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation);
static void null_links_for_domain (MonoDomain *domain, int generation);
static gboolean search_fragment_for_size (size_t size);
+static int search_fragment_for_size_range (size_t desired_size, size_t minimum_size);
static void build_nursery_fragments (int start_pin, int end_pin);
static void clear_nursery_fragments (char *next);
static void pin_from_roots (void *start_nursery, void *end_nursery);
return gap;
}
-#if 0
-static int
-compare_addr (const void *a, const void *b)
-{
- return *(const void **)a - *(const void **)b;
-}
-#endif
-
-/* sort the addresses in array in increasing order */
+/* Sort the addresses in array in increasing order.
+ * Done using a by-the book heap sort. Which has decent and stable performance, is pretty cache efficient.
+ */
static void
sort_addresses (void **array, int size)
{
- /*
- * qsort is slower as predicted.
- * qsort (array, size, sizeof (gpointer), compare_addr);
- * return;
- */
- int gap = size;
- int swapped, end;
- while (TRUE) {
- int i;
- gap = new_gap (gap);
- swapped = FALSE;
- end = size - gap;
- for (i = 0; i < end; i++) {
- int j = i + gap;
- if (array [i] > array [j]) {
- void* val = array [i];
- array [i] = array [j];
- array [j] = val;
- swapped = TRUE;
- }
+ int i;
+ void *tmp;
+
+ for (i = 1; i < size; ++i) {
+ int child = i;
+ while (child > 0) {
+ int parent = (child - 1) / 2;
+
+ if (array [parent] >= array [child])
+ break;
+
+ tmp = array [parent];
+ array [parent] = array [child];
+ array [child] = tmp;
+
+ child = parent;
+ }
+ }
+
+ for (i = size - 1; i > 0; --i) {
+ int end, root;
+ tmp = array [i];
+ array [i] = array [0];
+ array [0] = tmp;
+
+ end = i - 1;
+ root = 0;
+
+ while (root * 2 + 1 <= end) {
+ int child = root * 2 + 1;
+
+ if (child < end && array [child] < array [child + 1])
+ ++child;
+ if (array [root] >= array [child])
+ break;
+
+ tmp = array [root];
+ array [root] = array [child];
+ array [child] = tmp;
+
+ root = child;
}
- if (gap == 1 && !swapped)
- break;
}
}
fragment_total += frag_size;
} else {
/* Clear unused fragments, pinning depends on this */
+ /*TODO place an int[] here instead of the memset if size justify it*/
memset (frag_start, 0, frag_size);
}
}
mono_counters_register ("# nursery copy_object() failed forwarded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_forwarded);
mono_counters_register ("# nursery copy_object() failed pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_pinned);
+ mono_counters_register ("# wasted fragments used", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_used);
+ mono_counters_register ("bytes in wasted fragments", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_bytes);
+
mono_counters_register ("Store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets);
mono_counters_register ("Unique store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets_unique);
mono_counters_register ("Saved remsets 1", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_saved_remsets_1);
return obj->data;
}
+static void
+setup_fragment (Fragment *frag, Fragment *prev, size_t size)
+{
+ /* remove from the list */
+ if (prev)
+ prev->next = frag->next;
+ else
+ nursery_fragments = frag->next;
+ nursery_next = frag->fragment_start;
+ nursery_frag_real_end = frag->fragment_end;
+
+ DEBUG (4, fprintf (gc_debug_file, "Using nursery fragment %p-%p, size: %zd (req: %zd)\n", nursery_next, nursery_frag_real_end, nursery_frag_real_end - nursery_next, size));
+ frag->next = fragment_freelist;
+ fragment_freelist = frag;
+}
+
/* check if we have a suitable fragment in nursery_fragments to be able to allocate
* an object of size @size
* Return FALSE if not found (which means we need a collection)
prev = NULL;
for (frag = nursery_fragments; frag; frag = frag->next) {
if (size <= (frag->fragment_end - frag->fragment_start)) {
- /* remove from the list */
- if (prev)
- prev->next = frag->next;
- else
- nursery_fragments = frag->next;
- nursery_next = frag->fragment_start;
- nursery_frag_real_end = frag->fragment_end;
-
- DEBUG (4, fprintf (gc_debug_file, "Using nursery fragment %p-%p, size: %zd (req: %zd)\n", nursery_next, nursery_frag_real_end, nursery_frag_real_end - nursery_next, size));
- frag->next = fragment_freelist;
- fragment_freelist = frag;
+ setup_fragment (frag, prev, size);
return TRUE;
}
prev = frag;
return FALSE;
}
+/*
+ * Same as search_fragment_for_size but if search for @desired_size fails, try to satisfy @minimum_size.
+ * This improves nursery usage.
+ */
+static int
+search_fragment_for_size_range (size_t desired_size, size_t minimum_size)
+{
+ Fragment *frag, *prev, *min_prev;
+ DEBUG (4, fprintf (gc_debug_file, "Searching nursery fragment %p, desired size: %zd minimum size %zd\n", nursery_frag_real_end, desired_size, minimum_size));
+
+ if (nursery_frag_real_end > nursery_next && nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
+ /* Clear the remaining space, pinning depends on this */
+ memset (nursery_next, 0, nursery_frag_real_end - nursery_next);
+
+ min_prev = GINT_TO_POINTER (-1);
+ prev = NULL;
+
+ for (frag = nursery_fragments; frag; frag = frag->next) {
+ int frag_size = frag->fragment_end - frag->fragment_start;
+ if (desired_size <= frag_size) {
+ setup_fragment (frag, prev, desired_size);
+ return desired_size;
+ }
+ if (minimum_size <= frag_size)
+ min_prev = prev;
+
+ prev = frag;
+ }
+
+ if (min_prev != GINT_TO_POINTER (-1)) {
+ int frag_size;
+ if (min_prev)
+ frag = min_prev->next;
+ else
+ frag = nursery_fragments;
+
+ frag_size = frag->fragment_end - frag->fragment_start;
+ HEAVY_STAT (++stat_wasted_fragments_used);
+ HEAVY_STAT (stat_wasted_fragments_bytes += frag_size);
+
+ setup_fragment (frag, min_prev, minimum_size);
+ return frag_size;
+ }
+
+ return 0;
+}
+
/*
* Provide a variant that takes just the vtable for small fixed-size objects.
* The aligned size is already computed and stored in vt->gc_descr.
/* FIXME: handle OOM */
void **p;
char *new_next;
- gboolean res;
TLAB_ACCESS_INIT;
HEAVY_STAT (++stat_objects_alloced);
return p;
}
+ /*FIXME This codepath is current deadcode since tlab_size > MAX_SMALL_OBJ_SIZE*/
if (size > tlab_size) {
/* Allocate directly from the nursery */
if (nursery_next + size >= nursery_frag_real_end) {
if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
memset (p, 0, size);
} else {
+ int alloc_size = tlab_size;
+ int available_in_nursery = nursery_frag_real_end - nursery_next;
if (TLAB_START)
DEBUG (3, fprintf (gc_debug_file, "Retire TLAB: %p-%p [%ld]\n", TLAB_START, TLAB_REAL_END, (long)(TLAB_REAL_END - TLAB_NEXT - size)));
- if (nursery_next + tlab_size >= nursery_frag_real_end) {
- res = search_fragment_for_size (tlab_size);
- if (!res) {
- minor_collect_or_expand_inner (tlab_size);
- if (degraded_mode) {
- p = alloc_degraded (vtable, size);
- return p;
+ if (alloc_size >= available_in_nursery) {
+ if (available_in_nursery > MAX_NURSERY_TLAB_WASTE && available_in_nursery > size) {
+ alloc_size = available_in_nursery;
+ } else {
+ alloc_size = search_fragment_for_size_range (tlab_size, size);
+ if (!alloc_size) {
+ alloc_size = tlab_size;
+ minor_collect_or_expand_inner (tlab_size);
+ if (degraded_mode) {
+ p = alloc_degraded (vtable, size);
+ return p;
+ }
}
}
}
/* Allocate a new TLAB from the current nursery fragment */
TLAB_START = nursery_next;
- nursery_next += tlab_size;
+ nursery_next += alloc_size;
TLAB_NEXT = TLAB_START;
- TLAB_REAL_END = TLAB_START + tlab_size;
- TLAB_TEMP_END = TLAB_START + MIN (SCAN_START_SIZE, tlab_size);
+ TLAB_REAL_END = TLAB_START + alloc_size;
+ TLAB_TEMP_END = TLAB_START + MIN (SCAN_START_SIZE, alloc_size);
if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
- memset (TLAB_START, 0, tlab_size);
+ memset (TLAB_START, 0, alloc_size);
/* Allocate from the TLAB */
p = (void*)TLAB_NEXT;