On 07/05/2011 08:32 AM, Paolo Bonzini wrote:
On 07/04/2011 09:42 PM, Gwenael Casaccio wrote:
I've made some changes:
1) I keep _gst_mark_an_oop_internal and removed
_gst_add_an_oop_to_mark_queue for adding an OOP in the Queue. So like
the previous one, it has an OOP has argument and visit it.
2) in _gst_mark_an_oop_internal when visiting one OOP I keep the same
behavior with TAIL_MARK_OOP, and TAIL_MARK_OOPRANGE add OOPs in the
Queue.
3) _gst_mark_oop_range keeps the same behavior as the old one
The patch is tested and produced with master (all tests are green)
Thanks, these are the minimum changes required. I'll tweak it a bit to
remove the final push/pop and commit it.
Here is what I committed.
Paolo
>From be9fe1f2fe9115f9cf116d923abd6ef882d14558 Mon Sep 17 00:00:00 2001
From: Paolo Bonzini <[email protected]>
Date: Wed, 27 Jul 2011 10:04:50 +0200
Subject: [PATCH] replace recursion with mark stack
libgst:
2011-07-04 Gwenael Casaccio <[email protected]>
Paolo Bonzini <[email protected]>
* libgst/oop.c: Use mark stack.
* libgst/oop.h: Define mark stack data structures.
---
libgst/ChangeLog | 6 +++
libgst/oop.c | 99 ++++++++++++++++++++++++++++++++++++------------------
libgst/oop.h | 7 ++++
3 files changed, 79 insertions(+), 33 deletions(-)
diff --git a/libgst/ChangeLog b/libgst/ChangeLog
index 5436066..121fb5a 100644
--- a/libgst/ChangeLog
+++ b/libgst/ChangeLog
@@ -1,3 +1,9 @@
+2011-07-04 Gwenael Casaccio <[email protected]>
+ Paolo Bonzini <[email protected]>
+
+ * libgst/oop.c: Use mark stack.
+ * libgst/oop.h: Define mark stack data structures.
+
2011-07-27 Paolo Bonzini <[email protected]>
* libgst/oop.c: Clean up reset_incremental_gc.
diff --git a/libgst/oop.c b/libgst/oop.c
index e94b3e2..eea6565 100644
--- a/libgst/oop.c
+++ b/libgst/oop.c
@@ -348,6 +348,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old,
_gst_inc_init_registry ();
}
+ _gst_mem.markQueue = (struct mark_queue *)
+ xcalloc (8 * K, sizeof (struct mark_queue));
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[8 * K];
}
void _gst_update_object_memory_oop (OOP oop)
@@ -2185,50 +2188,70 @@ void
_gst_mark_an_oop_internal (OOP oop)
{
OOP *curOOP, *atEndOOP;
+ struct mark_queue *markQueue = _gst_mem.markQueue;
+ struct mark_queue *lastMarkQueue = _gst_mem.lastMarkQueue;
+ struct mark_queue *currentMarkQueue = markQueue;
goto markOne;
markRange:
- { /* in the loop! */
-#if defined (GC_DEBUGGING)
- gst_object obj = (gst_object) (curOOP - 1); /* for debugging */
-#endif
- for (;;)
+ {
+ OOP firstOOP = NULL;
+
+ /* The first unmarked OOP is used for tail recursion. */
+ while (curOOP < atEndOOP)
+ {
+ oop = *curOOP++;
+ if (IS_OOP (oop) && !IS_OOP_MARKED (oop))
+ {
+ oop->flags |= F_REACHABLE;
+ firstOOP = oop;
+ break;
+ }
+ }
+
+ /* The second unmarked OOP is the first that is placed on the mark
+ queue. TODO: split REACHABLE and VISITED flags. An object is
+ marked REACHABLE here, and REACHABLE|VISITED in the markOne label.
+ At the end of GC, all REACHABLE objects are also VISITED.
+ The above loop should seek an object that is not VISITED so
+ that it can be marked. For the loop below, however, REACHABLE
+ objects are known to be somewhere else on the mark stack, and can
+ be skipped.
+
+ Skipping objects after the first unmarked OOP is still useful,
+ because it keeps the stack size a bit lower in the relatively common
+ case of many integer or nil instance variables. */
+ while (curOOP < atEndOOP)
{
- /* in a loop, do next iteration */
oop = *curOOP;
- PREFETCH_LOOP (curOOP, PREF_READ | PREF_NTA);
- curOOP++;
- if (IS_OOP (oop))
+
+ if (IS_OOP (oop) && !IS_OOP_MARKED (oop))
{
-#if defined (GC_DEBUGGING)
- if UNCOMMON (!IS_OOP_ADDR (oop))
+ if (currentMarkQueue == lastMarkQueue)
{
- printf
- ("Error! Invalid OOP %p was found inside %p!\n",
- oop, obj);
- abort ();
+ const size_t size = lastMarkQueue - markQueue;
+
+ _gst_mem.markQueue = (struct mark_queue *)
+ xrealloc (_gst_mem.markQueue, 2 * size * sizeof (struct mark_queue));
+ _gst_mem.lastMarkQueue = &_gst_mem.markQueue[2 * size];
+
+ markQueue = _gst_mem.markQueue;
+ lastMarkQueue = _gst_mem.lastMarkQueue;
+ currentMarkQueue = &_gst_mem.markQueue[size];
}
- 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;
- }
+ currentMarkQueue->firstOOP = curOOP;
+ currentMarkQueue->endOOP = atEndOOP;
+ currentMarkQueue++;
+ break;
}
- /* Place the check here so that the continue above skips it. */
- if UNCOMMON (curOOP == atEndOOP)
- return;
+ curOOP++;
}
+
+ if (!firstOOP)
+ goto pop;
+
+ TAIL_MARK_OOP (firstOOP);
}
markOne:
@@ -2290,6 +2313,16 @@ _gst_mark_an_oop_internal (OOP oop)
TAIL_MARK_OOP (objClass);
}
}
+
+ pop:
+ {
+ if (currentMarkQueue > markQueue)
+ {
+ currentMarkQueue--;
+ TAIL_MARK_OOPRANGE (currentMarkQueue->firstOOP,
+ currentMarkQueue->endOOP);
+ }
+ }
}
void
diff --git a/libgst/oop.h b/libgst/oop.h
index fa89dd0..c20dfc3 100644
--- a/libgst/oop.h
+++ b/libgst/oop.h
@@ -187,12 +187,19 @@ typedef struct cheney_scan_state {
OOP current; /* Currently scanned object */
} cheney_scan_state;
+struct mark_queue
+{
+ OOP *firstOOP, *endOOP;
+};
+
struct memory_space
{
heap_data *old, *fixed;
struct new_space eden;
struct surv_space surv[2], tenuring_queue;
+ struct mark_queue *markQueue, *lastMarkQueue;
+
/* The current state of the copying collector's scan phase. */
struct cheney_scan_state scan;
--
1.7.6
_______________________________________________
help-smalltalk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-smalltalk
