On 06/27/2011 02:56 PM, Paolo Bonzini wrote:
On 06/21/2011 12:00 AM, Gwenael Casaccio wrote:
This bench stresses well the it. mark patch and crashes the rec. mark.
But I guess there are still bugs with contexts (I should take a look),
there is a strange crash (DNU with #printNl lookup symbol is not found
but it's present...). But that's a good start :-)
It's possible instead of the iterative version to use a mark with a
pointer reversal but it's harder to debug, requires high time-cost:
visits each branch-node at least (n+1) times, each visit requires
additional memory fetches, and each visit cycles 4 values +
reading/writing mark-flags.
Another solution is to use a stack guard (v8 does it) and checks
overflow Knuth propose something similar
Modulo the usual comments about irrelevant hunks :) it looks good,
thanks! Can you however ensure the invariant that the queue is empty
upon entry to _gst_mark, by making it accept an OOP? I believe this
simplifies the code and lets you add back the tail recursion
optimization you removed.
And it would be even better if you could keep the distinction between
marking one OOP and marking a range, because it removes a lot of traffic
to/from the mark queue (a bit cheaper than the stack because of no stack
frame overhead, but still expensive cache-wise). Which in turn means,
keep the API as is! :)
Anyway, good start!
Paolo
Is it better Paolo ?
Cheers,
Gwen
Btw
Thanks for all the time you spend for the review :)
>From ba3bede253f1c9c53a558809d41d97612859edb6 Mon Sep 17 00:00:00 2001
From: Gwenael Casaccio <[email protected]>
Date: Wed, 15 Jun 2011 00:51:00 +0200
Subject: [PATCH 1/2] safe mark
---
libgst/oop.c | 145 +++++++++++++---------------------------
libgst/oop.h | 9 ++-
libgst/oop.inl | 3 +-
snprintfv/snprintfv/filament.h | 4 +-
snprintfv/snprintfv/printf.h | 8 +-
snprintfv/snprintfv/stream.h | 4 +-
6 files changed, 64 insertions(+), 109 deletions(-)
diff --git a/libgst/oop.c b/libgst/oop.c
index 0a34f95..a80a45d 100644
--- a/libgst/oop.c
+++ b/libgst/oop.c
@@ -353,6 +353,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old,
_gst_inc_init_registry ();
}
+ _gst_mem.markQueue = xcalloc (4 * K, sizeof (*_gst_mem.markQueue));
+ _gst_mem.currentMarkQueue = &_gst_mem.markQueue[0];
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * K];
}
void _gst_update_object_memory_oop (OOP oop)
@@ -2216,114 +2219,58 @@ mark_ephemeron_oops (void)
} while(0)
void
-_gst_mark_an_oop_internal (OOP oop)
+_gst_add_an_oop_to_mark_queue (OOP oop)
{
- OOP *curOOP, *atEndOOP;
- goto markOne;
+ if (!IS_OOP (oop) || IS_OOP_MARKED (oop))
+ return ;
- markRange:
- { /* in the loop! */
-#if defined (GC_DEBUGGING)
- gst_object obj = (gst_object) (curOOP - 1); /* for debugging */
-#endif
- for (;;)
- {
- /* in a loop, do next iteration */
- oop = *curOOP;
- PREFETCH_LOOP (curOOP, PREF_READ | PREF_NTA);
- curOOP++;
- if (IS_OOP (oop))
- {
-#if defined (GC_DEBUGGING)
- if UNCOMMON (!IS_OOP_ADDR (oop))
- {
- printf
- ("Error! Invalid OOP %p was found inside %p!\n",
- oop, obj);
- abort ();
- }
- else
-#endif
- if (!IS_OOP_MARKED (oop))
- {
- PREFETCH_START (oop->object, PREF_READ | PREF_NTA);
-
- /* On the last object in the set, reuse the
- current invocation. oop is valid, so we go to
- the single-object case */
- if UNCOMMON (curOOP == atEndOOP)
- goto markOne;
-
- _gst_mark_an_oop_internal (oop);
- continue;
- }
- }
+ if (_gst_mem.currentMarkQueue == _gst_mem.lastMarkQueue)
+ {
+ OOP *oldMarkQueue = _gst_mem.markQueue;
+ size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue;
- /* Place the check here so that the continue above skips it. */
- if UNCOMMON (curOOP == atEndOOP)
- return;
- }
- }
+ _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 4 * size);
+ _gst_mem.currentMarkQueue = &_gst_mem.markQueue[_gst_mem.currentMarkQueue - oldMarkQueue];
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * size];
+ }
- markOne:
- {
- OOP objClass;
- gst_object object;
- uintptr_t size;
+ oop->flags |= F_REACHABLE;
+ *_gst_mem.currentMarkQueue = oop;
+ _gst_mem.currentMarkQueue++;
+}
-#if defined (GC_DEBUGGING)
- if UNCOMMON (IS_OOP_FREE (oop))
- {
- printf ("Error! Free OOP %p is being marked!\n", oop);
- abort ();
- return;
- }
-#endif
+void
+_gst_mark (void)
+{
+ while (_gst_mem.currentMarkQueue > _gst_mem.markQueue)
+ {
+ int i, n;
+ OOP oop;
-#if defined(GC_DEBUG_OUTPUT)
- printf (">Mark ");
- _gst_display_oop (oop);
-#endif
+ PREFETCH_LOOP (_gst_mem.currentMarkQueue, PREF_READ | PREF_NTA);
+ _gst_mem.currentMarkQueue--;
+ oop = *_gst_mem.currentMarkQueue;
- /* see if the object has pointers, set up to copy them if so.
- */
- oop->flags |= F_REACHABLE;
- object = OOP_TO_OBJ (oop);
- objClass = object->objClass;
- if UNCOMMON (oop->flags & F_CONTEXT)
- {
- gst_method_context ctx;
- intptr_t methodSP;
- ctx = (gst_method_context) object;
- methodSP = TO_INT (ctx->spOffset);
- /* printf("setting up for loop on context %x, sp = %d\n",
- ctx, methodSP); */
- TAIL_MARK_OOPRANGE (&ctx->objClass,
- ctx->contextStack + methodSP + 1);
+ if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK))
+ {
+ if (oop->flags & F_EPHEMERON)
+ _gst_add_buf_pointer (oop);
- }
- else if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK))
- {
- if (oop->flags & F_EPHEMERON)
- _gst_add_buf_pointer (oop);
-
- /* In general, there will be many instances of a class,
- but only the first time will it be unmarked. So I'm
- marking this as uncommon. */
- if UNCOMMON (!IS_OOP_MARKED (objClass))
- TAIL_MARK_OOP (objClass);
- }
- else
- {
- size = NUM_OOPS (object);
- if COMMON (size)
- TAIL_MARK_OOPRANGE (&object->objClass,
- object->data + size);
+ _gst_add_an_oop_to_mark_queue (oop->object->objClass);
+ }
+ else
+ {
+ n = scanned_fields_in (OOP_TO_OBJ (oop), oop->flags) - 1;
- else if UNCOMMON (!IS_OOP_MARKED (objClass))
- TAIL_MARK_OOP (objClass);
- }
- }
+ for (i = 0; i < n; i++)
+ {
+ OOP newOOP = OOP_TO_OBJ (oop)->data[i];
+
+ if (IS_OOP (newOOP) && !IS_OOP_MARKED (newOOP))
+ _gst_add_an_oop_to_mark_queue (newOOP);
+ }
+ }
+ }
}
void
diff --git a/libgst/oop.h b/libgst/oop.h
index 6816b3f..b33e645 100644
--- a/libgst/oop.h
+++ b/libgst/oop.h
@@ -193,6 +193,9 @@ struct memory_space
struct new_space eden;
struct surv_space surv[2], tenuring_queue;
+ OOP *markQueue;
+ OOP *currentMarkQueue, *lastMarkQueue;
+
/* The current state of the copying collector's scan phase. */
struct cheney_scan_state scan;
@@ -381,7 +384,11 @@ extern void _gst_grey_oop_range (PTR from,
ATTRIBUTE_HIDDEN;
/* Mark OOP and the pointers pointed by that. */
-extern void _gst_mark_an_oop_internal (OOP oop)
+extern void _gst_add_an_oop_to_mark_queue (OOP oop)
+ ATTRIBUTE_HIDDEN;
+
+/* Do the mark step with the current queue. */
+extern void _gst_mark (void)
ATTRIBUTE_HIDDEN;
/* Fully initialize the builtin objects, possible after the respective
diff --git a/libgst/oop.inl b/libgst/oop.inl
index 279dd1b..cda21d0 100644
--- a/libgst/oop.inl
+++ b/libgst/oop.inl
@@ -64,7 +64,8 @@ static inline OOP alloc_oop (PTR obj, intptr_t flags);
and already-marked OOPs are not processed silently. */
#define MAYBE_MARK_OOP(oop) do { \
if (IS_OOP(oop) && !IS_OOP_MARKED(oop)) { \
- _gst_mark_an_oop_internal((oop)); \
+ _gst_add_an_oop_to_mark_queue((oop)); \
+ _gst_mark(); \
} \
} while(0)
diff --git a/snprintfv/snprintfv/filament.h b/snprintfv/snprintfv/filament.h
index 4a91eb6..8a7ce6c 100644
--- a/snprintfv/snprintfv/filament.h
+++ b/snprintfv/snprintfv/filament.h
@@ -1,4 +1,4 @@
-#line 1 "../../../snprintfv/snprintfv/filament.in"
+#line 1 "./filament.in"
/* -*- Mode: C -*- */
/* filament.h --- a bit like a string but different =)O|
@@ -118,7 +118,7 @@ extern char * fildelete (Filament *fil);
extern void _fil_extend (Filament *fil, size_t len, boolean copy);
-#line 61 "../../../snprintfv/snprintfv/filament.in"
+#line 61 "./filament.in"
/* Save the overhead of a function call in the great majority of cases. */
#define fil_maybe_extend(fil, len, copy) \
diff --git a/snprintfv/snprintfv/printf.h b/snprintfv/snprintfv/printf.h
index 49a2e9f..1437dd5 100644
--- a/snprintfv/snprintfv/printf.h
+++ b/snprintfv/snprintfv/printf.h
@@ -1,4 +1,4 @@
-#line 1 "../../../snprintfv/snprintfv/printf.in"
+#line 1 "./printf.in"
/* -*- Mode: C -*- */
/* printf.in --- printf clone for argv arrays
@@ -266,7 +266,7 @@ enum
} \
} SNV_STMT_END
-#line 269 "../../../snprintfv/snprintfv/printf.in"
+#line 269 "./printf.in"
/**
* printf_generic_info:
* @pinfo: the current state information for the format
@@ -302,7 +302,7 @@ extern int printf_generic_info (struct printf_info *const pinfo, size_t n, int *
extern int printf_generic (STREAM *stream, struct printf_info *const pinfo, union printf_arg const *args);
-#line 270 "../../../snprintfv/snprintfv/printf.in"
+#line 270 "./printf.in"
/**
* register_printf_function:
* @spec: the character which will trigger @func, cast to an unsigned int.
@@ -789,7 +789,7 @@ extern int snv_vasprintf (char **result, const char *format, va_list ap);
extern int snv_asprintfv (char **result, const char *format, snv_constpointer const args[]);
-#line 271 "../../../snprintfv/snprintfv/printf.in"
+#line 271 "./printf.in"
/* If you don't want to use snprintfv functions for *all* of your string
formatting API, then define COMPILING_SNPRINTFV_C and use the snv_
diff --git a/snprintfv/snprintfv/stream.h b/snprintfv/snprintfv/stream.h
index 496bd33..0bebce1 100644
--- a/snprintfv/snprintfv/stream.h
+++ b/snprintfv/snprintfv/stream.h
@@ -1,4 +1,4 @@
-#line 1 "../../../snprintfv/snprintfv/stream.in"
+#line 1 "./stream.in"
/* -*- Mode: C -*- */
/* stream.h --- customizable stream routines
@@ -180,7 +180,7 @@ extern int stream_puts (char *s, STREAM *stream);
extern int stream_get (STREAM *stream);
-#line 88 "../../../snprintfv/snprintfv/stream.in"
+#line 88 "./stream.in"
#ifdef __cplusplus
#if 0
/* This brace is so that emacs can still indent properly: */
--
1.7.4.1
>From 75b4a2108bf0e7c403dac4c676b3fd04b1829bb7 Mon Sep 17 00:00:00 2001
From: Gwenael Casaccio <[email protected]>
Date: Mon, 20 Jun 2011 23:35:18 +0200
Subject: [PATCH 2/2] iterative mark
---
libgst/interp-bc.inl | 2 +
libgst/oop.c | 57 ++++++++++++++++++++++++++++++++++++--------------
2 files changed, 43 insertions(+), 16 deletions(-)
diff --git a/libgst/interp-bc.inl b/libgst/interp-bc.inl
index 9a1243e..3ee042b 100644
--- a/libgst/interp-bc.inl
+++ b/libgst/interp-bc.inl
@@ -173,6 +173,7 @@
} while(0)
+
void
_gst_send_message_internal (OOP sendSelector,
int sendArgs,
@@ -192,6 +193,7 @@ _gst_send_message_internal (OOP sendSelector,
zeros. */
_gst_sample_counter++;
+
hashIndex = METHOD_CACHE_HASH (sendSelector, method_class);
methodData = &method_cache[hashIndex];
diff --git a/libgst/oop.c b/libgst/oop.c
index a80a45d..9d7b242 100644
--- a/libgst/oop.c
+++ b/libgst/oop.c
@@ -66,6 +66,7 @@
/* Define this flag to turn on debugging code for OOP table management */
/* #define GC_DEBUGGING */
+#define GC_DEBUGGING
/* Define this flag to disable incremental garbage collection */
/* #define NO_INCREMENTAL_GC */
@@ -353,9 +354,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old,
_gst_inc_init_registry ();
}
- _gst_mem.markQueue = xcalloc (4 * K, sizeof (*_gst_mem.markQueue));
+ _gst_mem.markQueue = xcalloc (128 * K, sizeof (*_gst_mem.markQueue));
_gst_mem.currentMarkQueue = &_gst_mem.markQueue[0];
- _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * K];
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[128 * K];
}
void _gst_update_object_memory_oop (OOP oop)
@@ -2226,12 +2227,11 @@ _gst_add_an_oop_to_mark_queue (OOP oop)
if (_gst_mem.currentMarkQueue == _gst_mem.lastMarkQueue)
{
- OOP *oldMarkQueue = _gst_mem.markQueue;
- size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue;
+ const size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue;
- _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 4 * size);
- _gst_mem.currentMarkQueue = &_gst_mem.markQueue[_gst_mem.currentMarkQueue - oldMarkQueue];
- _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * size];
+ _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 10 * size * sizeof (*_gst_mem.markQueue));
+ _gst_mem.currentMarkQueue = &_gst_mem.markQueue[size];
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[10 * size];
}
oop->flags |= F_REACHABLE;
@@ -2246,29 +2246,54 @@ _gst_mark (void)
{
int i, n;
OOP oop;
+ gst_object obj;
PREFETCH_LOOP (_gst_mem.currentMarkQueue, PREF_READ | PREF_NTA);
_gst_mem.currentMarkQueue--;
oop = *_gst_mem.currentMarkQueue;
+ obj = OOP_TO_OBJ (oop);
- if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK))
+#if defined(GC_DEBUG_OUTPUT)
+ printf (">Mark ");
+ _gst_display_oop (oop);
+
+ if UNCOMMON (!IS_OOP_ADDR (oop))
+ {
+ printf
+ ("Error! Invalid OOP %p was found inside %p!\n",
+ oop, obj);
+ abort ();
+ }
+#endif
+
+ if UNCOMMON (oop->flags & F_CONTEXT)
+ {
+ gst_method_context ctx;
+ intptr_t methodSP;
+ ctx = (gst_method_context) obj;
+ methodSP = TO_INT (ctx->spOffset);
+ n = ctx->contextStack + methodSP + 1 - obj->data;
+
+ for (i = 0; i < n; i++)
+ _gst_add_an_oop_to_mark_queue (obj->data[i]);
+
+ _gst_add_an_oop_to_mark_queue (obj->objClass);
+ }
+ else if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK))
{
if (oop->flags & F_EPHEMERON)
_gst_add_buf_pointer (oop);
- _gst_add_an_oop_to_mark_queue (oop->object->objClass);
+ _gst_add_an_oop_to_mark_queue (obj->objClass);
}
else
{
- n = scanned_fields_in (OOP_TO_OBJ (oop), oop->flags) - 1;
+ n = NUM_OOPS (obj);
for (i = 0; i < n; i++)
- {
- OOP newOOP = OOP_TO_OBJ (oop)->data[i];
-
- if (IS_OOP (newOOP) && !IS_OOP_MARKED (newOOP))
- _gst_add_an_oop_to_mark_queue (newOOP);
- }
+ _gst_add_an_oop_to_mark_queue (obj->data[i]);
+
+ _gst_add_an_oop_to_mark_queue (obj->objClass);
}
}
}
--
1.7.4.1
_______________________________________________
help-smalltalk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-smalltalk
