OSDN -- オープンソース・ソフトウェアの開発とダウンロード
日本語の翻訳状況 translation status for ja
  • R/O
  • SSH
Fork

quipu: コミット

quipu mercurial repository


コミットメタ情報

リビジョンaa77bec1d5b3d0370d4123946d0fe3d7fe40d93a (tree)
日時2018-03-10 05:08:24
作者Agustina Arzille <avarzille@rise...>
コミッターAgustina Arzille

ログメッセージ

Improve GC algorithm with explicit mark stack

変更サマリ

差分

diff -r 21654390f900 -r aa77bec1d5b3 config.h
--- a/config.h Fri Mar 09 16:33:29 2018 -0300
+++ b/config.h Fri Mar 09 17:08:24 2018 -0300
@@ -193,4 +193,7 @@
193193
194194 #define QP_EXPORT extern
195195
196+// Size of the mark stack.
197+#define QP_MARK_STACK_SIZE 128
198+
196199 #endif
diff -r 21654390f900 -r aa77bec1d5b3 memory.cpp
--- a/memory.cpp Fri Mar 09 16:33:29 2018 -0300
+++ b/memory.cpp Fri Mar 09 17:08:24 2018 -0300
@@ -155,6 +155,42 @@
155155 return (ptr->as_obj ());
156156 }
157157
158+static void gc_mark (object, uint32_t);
159+
160+class mark_stack
161+{
162+public:
163+ object *stack;
164+ object *sub;
165+ int nelem;
166+ int size;
167+
168+ void flush_once (uint32_t mask)
169+ {
170+ int n = min (this->nelem, this->size);
171+ memcpy (this->sub, this->stack, n * sizeof (object));
172+
173+ this->nelem -= n;
174+ for (int i = 0; i < n; ++i)
175+ gc_mark (sub[i], mask);
176+ }
177+
178+ void flush (uint32_t mask)
179+ {
180+ do
181+ flush_once (mask);
182+ while (this->nelem == this->size);
183+ }
184+
185+ void push (object obj, uint32_t mask)
186+ {
187+ if (this->nelem == this->size)
188+ this->flush (mask);
189+
190+ this->stack[this->nelem++] = obj;
191+ }
192+};
193+
158194 // GC-specific information.
159195 class gcinfo
160196 {
@@ -172,6 +208,8 @@
172208 memmgr *free_mgrs;
173209 uint32_t vo_size_limit;
174210 uint32_t vo_nelem_limit;
211+ object space[QP_MARK_STACK_SIZE * 2];
212+ mark_stack mkstack;
175213
176214 bool init ()
177215 {
@@ -221,6 +259,11 @@
221259 this->free_mgrs = nullptr;
222260 lwlock_init (&this->xlock);
223261
262+ this->mkstack.size = (int)QP_NELEM (this->space);
263+ this->mkstack.stack = this->space;
264+ this->mkstack.sub = this->mkstack.stack + this->mkstack.size;
265+ this->mkstack.nelem = 0;
266+
224267 return (this->event.init ());
225268 }
226269
@@ -262,15 +305,16 @@
262305 }
263306
264307 void do_gc (interpreter *interp, bool full);
308+ void mark (object obj, uint32_t mask);
265309
266310 void update_alloc (interpreter *interp, size_t size)
267311 {
268312 if ((this->acc_bytes += size) >= this->limit)
269313 this->do_gc (interp, this->full_gc);
270314 }
271-
315+
272316 static varobj**
273- sweep_varobjs (varobj **lpp, uint32_t mask, size_t *outp)
317+ sweep_varobjs (varobj **lpp, uint32_t mask, size_t& out)
274318 {
275319 while (*lpp != nullptr)
276320 {
@@ -284,7 +328,7 @@
284328 { // Unreachable object - Free the storage.
285329 *lpp = ptr->link;
286330 fini_varobj (ptr);
287- *outp -= ptr->size;
331+ out -= ptr->size;
288332 }
289333 }
290334
@@ -296,7 +340,7 @@
296340 /* Unmarked objects that belong to the old generation are still
297341 * considered reachable by the garbage collector. */
298342 varobj **retp = sweep_varobjs (&this->vgens[0],
299- FLAGS_GCMARKED | FLAGS_OLDGEN, &this->acc_bytes);
343+ FLAGS_GCMARKED | FLAGS_OLDGEN, this->acc_bytes);
300344
301345 // Move the survivors to the old generation.
302346 *retp = this->vgens[1];
@@ -310,7 +354,7 @@
310354 {
311355 /* Sweep the old generation first, otherwise, we would iterate
312356 * over the young generation twice. */
313- sweep_varobjs (&this->vgens[1], FLAGS_GCMARKED, &this->acc_bytes);
357+ sweep_varobjs (&this->vgens[1], FLAGS_GCMARKED, this->acc_bytes);
314358 this->sweep_young_varobjs ();
315359 }
316360
@@ -505,7 +549,7 @@
505549
506550 void sweep (uint32_t mask, gcinfo& gc)
507551 {
508- gcinfo::sweep_varobjs (&this->vo_head, mask, &gc.acc_bytes);
552+ gcinfo::sweep_varobjs (&this->vo_head, mask, gc.acc_bytes);
509553 if (!this->pages)
510554 return;
511555
@@ -726,61 +770,9 @@
726770 // Marking routines.
727771
728772 static void
729-gc_mark (object obj, uint32_t mask);
730-
731-static inline bool
732-gc_mark_varobj (varobj *vp, uint32_t mask)
733-{
734- if (vp->flags & mask)
735- return (false);
736-
737- vp->flags |= mask;
738- return (true);
739-}
740-
741-#define MARK_VAROBJ(x, mask) \
742- if (!gc_mark_varobj (x, mask)) \
743- return
744-
745-static void
746-gc_mark_array (array *ap, uint32_t mask)
747-{
748- MARK_VAROBJ (ap, mask);
749- for (int i = 0; i < ap->len; ++i)
750- gc_mark (ap->data[i], mask);
751-}
752-
753-static void
754-gc_mark_table (table *tp, uint32_t mask)
773+mark_pkg (gcinfo& gc, package *pkgp, uint32_t mask)
755774 {
756- MARK_VAROBJ (tp, mask);
757- gc_mark_array (as_array (tp->vector), mask);
758- gc_mark (tp->cmpfct, mask);
759- gc_mark (tp->hashfct, mask);
760-}
761-
762-static void
763-gc_mark_tree (tree *tp, uint32_t mask)
764-{
765- MARK_VAROBJ (tp, mask);
766- gc_mark_array (as_array (tp->head), mask);
767- gc_mark (tp->test, mask);
768-}
769-
770-static void
771-gc_mark_stream (stream *strmp, uint32_t mask)
772-{
773- MARK_VAROBJ (strmp, mask);
774- gc_mark (strmp->extra, mask);
775- gc_mark_varobj (as_varobj (strmp->ilock), mask);
776-}
777-
778-static void gc_mark_symbol (symbol *, uint32_t);
779-
780-static void
781-mark_pkg_helper (package *pkgp, uint32_t mask)
782-{
783- gc_mark_varobj (as_varobj (pkgp->name), mask);
775+ gc.mkstack.push (pkgp->name, mask);
784776
785777 /* For a package's symbol table, we don't want to mark temporary
786778 * symbols such as those produced by 'let' and function bindings,
@@ -797,50 +789,116 @@
797789 // Note: Index 0 is an integer value - Don't bother marking it.
798790 for (int i = 1; i < syms->len; ++i)
799791 {
800- if ((syms->data[i] & EXTRA_BIT) != 0)
801- continue;
802-
803- symbol *sp = as_symbol (syms->data[i]);
804- if (sp->value != UNBOUND)
805- // Bound symbol - Mark it.
806- gc_mark_symbol (sp, mask);
792+ object s = syms->data[i];
793+ if ((s & EXTRA_BIT) == 0 && symval (s) != UNBOUND)
794+ gc.mkstack.push (s, mask);
795+ }
796+}
797+
798+void gcinfo::mark (object obj, uint32_t mask)
799+{
800+ // Unmask the extra bit and check for common values.
801+ obj &= ~EXTRA_BIT;
802+ if (obj == NIL || obj == UNBOUND || obj == ((~(object)0) & ~EXTRA_BIT))
803+ return;
804+
805+ int tp = itype (obj);
806+
807+ if (tp == typecode::INT || tp == typecode::CHAR)
808+ return;
809+ else if (tp == typecode::CONS)
810+ {
811+ cons *cnp = as_cons (obj);
812+ if (!cnp->gc_mark ())
813+ return;
814+
815+ this->mkstack.push (cnp->car, mask);
816+ this->mkstack.push (cnp->cdr, mask);
817+ return;
818+ }
819+
820+ varobj *vp = as_varobj (obj);
821+ if (vp->flags & mask)
822+ return;
823+
824+ vp->flags |= mask;
825+ switch (tp)
826+ {
827+ case typecode::ARRAY:
828+ {
829+ array *ap = (array *)vp;
830+ for (int i = 0; i < ap->len; ++i)
831+ this->mkstack.push (ap->data[i], mask);
832+
833+ break;
834+ }
835+
836+ case typecode::TABLE:
837+ {
838+ table *tp = (table *)vp;
839+ this->mkstack.push (tp->vector, mask);
840+ this->mkstack.push (tp->cmpfct, mask);
841+ this->mkstack.push (tp->hashfct, mask);
842+
843+ break;
844+ }
845+
846+ case typecode::TREE:
847+ {
848+ tree *tp = (tree *)vp;
849+ this->mkstack.push (tp->head, mask);
850+ this->mkstack.push (tp->test, mask);
851+
852+ break;
853+ }
854+
855+ case typecode::STREAM:
856+ {
857+ stream *strmp = (stream *)vp;
858+ this->mkstack.push (strmp->bvec, mask);
859+ this->mkstack.push (strmp->ilock, mask);
860+ this->mkstack.push (strmp->extra, mask);
861+
862+ break;
863+ }
864+
865+ case typecode::SYMBOL:
866+ {
867+ symbol *sp = (symbol *)vp;
868+ this->mkstack.push (sp->name, mask);
869+ this->mkstack.push (sp->value, mask);
870+ this->mkstack.push (sp->pkg, mask);
871+
872+ break;
873+ }
874+
875+ case typecode::PKG:
876+ {
877+ package *pkgp = (package *)vp;
878+ mark_pkg (*this, pkgp, mask);
879+ break;
880+ }
881+
882+ case typecode::FCT:
883+ {
884+ if (vp->flags & native_function::native_flag)
885+ return;
886+
887+ function *fp = (function *)vp;
888+ this->mkstack.push (fp->bcode, mask);
889+ this->mkstack.push (fp->vals, mask);
890+ this->mkstack.push (fp->env, mask);
891+ this->mkstack.push (fp->name, mask);
892+
893+ break;
894+ }
807895 }
808896 }
809897
810898 static void
811-gc_mark_pkg (package *pkgp, uint32_t mask)
812-{
813- MARK_VAROBJ (pkgp, mask);
814- mark_pkg_helper (pkgp, mask);
815-}
816-
817-static void
818-gc_mark_symbol (symbol *sp, uint32_t mask)
899+gc_mark (object obj, uint32_t mask)
819900 {
820- MARK_VAROBJ (sp, mask);
821- gc_mark_varobj (as_varobj (sp->name), mask);
822- gc_mark (sp->value, mask);
823-
824- if (sp->pkg != UNBOUND && sp->pkg != kword_package)
825- gc_mark_pkg (as_package (sp->pkg), mask);
826-}
827-
828-static void
829-gc_mark_fct (function *fp, uint32_t mask)
830-{
831- MARK_VAROBJ (fp, mask);
832- gc_mark (fp->bcode, mask);
833- gc_mark (fp->vals, mask);
834- gc_mark (fp->env, mask);
835- gc_mark (fp->name, mask);
836-}
837-
838-static void
839-gc_mark_continuation (continuation *cnp, uint32_t mask)
840-{
841- MARK_VAROBJ (cnp, mask);
842- gc_mark (cnp->value, mask);
843- gc_mark (cnp->argv, mask);
901+ QP_gc.mark (obj, mask);
844902 }
845903
846904 static uintptr_t*
@@ -879,92 +937,6 @@
879937 atomic_or ((atomic_t *)bp, mask);
880938 }
881939
882-static void
883-gc_mark_cons (cons *ptr, uint32_t mask)
884-{
885- if (!ptr->gc_mark ())
886- return;
887-
888- while (true)
889- {
890- gc_mark (ptr->car, mask);
891- if (!xcons_p (ptr->cdr))
892- {
893- gc_mark (ptr->cdr, mask);
894- break;
895- }
896- else if (ptr->cdr == NIL || !as_cons(ptr->cdr)->gc_mark ())
897- break;
898-
899- ptr = as_cons (ptr->cdr);
900- }
901-}
902-
903-static void
904-gc_mark (object obj, uint32_t mask)
905-{
906- // Unmask the extra bit and check for common values.
907- obj &= ~EXTRA_BIT;
908- if (obj == NIL || obj == UNBOUND || obj == ((~(object)0) & ~EXTRA_BIT))
909- return;
910-
911- switch (itype (obj))
912- {
913- // Immediate types.
914- case typecode::INT:
915- case typecode::CHAR:
916- break;
917-
918- // Conses.
919- case typecode::CONS:
920- gc_mark_cons (as_cons (obj), mask);
921- break;
922-
923- // Simple varobjs.
924- case typecode::BIGINT:
925- case typecode::FLOAT:
926- case typecode::BIGFLOAT:
927- case typecode::BVECTOR:
928- case typecode::STR:
929- case typecode::LOCK:
930- case typecode::CONDVAR:
931- gc_mark_varobj (as_varobj (obj), mask);
932- break;
933-
934- // Composite varobjs.
935- case typecode::ARRAY:
936- gc_mark_array (as_array (obj), mask);
937- break;
938-
939- case typecode::TABLE:
940- gc_mark_table (as_table (obj), mask);
941- break;
942-
943- case typecode::TREE:
944- gc_mark_tree (as_tree (obj), mask);
945- break;
946-
947- case typecode::STREAM:
948- gc_mark_stream (as_stream (obj), mask);
949- break;
950-
951- case typecode::SYMBOL:
952- gc_mark_symbol (as_symbol (obj), mask);
953- break;
954-
955- case typecode::FCT:
956- gc_mark_fct (as_fct (obj), mask);
957- break;
958-
959- case typecode::CONTINUATION:
960- gc_mark_continuation (as_continuation (obj), mask);
961- break;
962-
963- default:
964- break;
965- }
966-}
967-
968940 void gcinfo::do_gc (interpreter *interp, bool full)
969941 {
970942 uint32_t mask = FLAGS_GCMARKED;
@@ -1017,11 +989,11 @@
1017989
1018990 // Mark the global symbols.
1019991 as_package(root_package)->flags |= mask;
1020- mark_pkg_helper (as_package (root_package), mask);
992+ mark_pkg (*this, as_package (root_package), mask);
1021993
1022994 // Mark the objects in the local package.
1023995 as_package(local_package)->flags |= mask;
1024- mark_pkg_helper (as_package (local_package), mask);
996+ mark_pkg (*this, as_package (local_package), mask);
1025997
1026998 /* For the keyword package, we only mark the package object and
1027999 * the symbol table. The reason being, keywords will always survive,
@@ -1029,6 +1001,9 @@
10291001 as_package(kword_package)->flags |= mask;
10301002 as_array(as_package(kword_package)->syms)->flags |= mask;
10311003
1004+ while (this->mkstack.nelem != 0)
1005+ this->mkstack.flush_once (mask);
1006+
10321007 // Now the mark phase is over. Sweep the garbage.
10331008 for (dlist::iterator it (&all_threads); it.valid (); it.adv ())
10341009 ((thread *)it.getp ())->interp->mmgr->sweep (mask, *this);
旧リポジトリブラウザで表示