[prev in list] [next in list] [prev in thread] [next in thread]
List: sbcl-commits
Subject: [Sbcl-commits] master: Further speed up GC scavenging.
From: "Douglas Katzman" <snuglas () users ! sourceforge ! net>
Date: 2017-03-27 22:51:24
Message-ID: 1490655084.319040.6658 () sfp-scm-7 ! v30 ! ch3 ! sourceforge ! com
[Download RAW message or body]
The branch "master" has been updated in SBCL:
via a4b16e5ee235e7691ad14b5f520f3d09c1e3cf0e (commit)
from 41415f05a1582403dce499a5239df97b72801fe8 (commit)
- Log -----------------------------------------------------------------
commit a4b16e5ee235e7691ad14b5f520f3d09c1e3cf0e
Author: Douglas Katzman <dougk@google.com>
Date: Mon Mar 27 18:47:18 2017 -0400
Further speed up GC scavenging.
- scavenge() no longer looks for object headers, only pointers.
This is a win because stacks don't contain object headers,
nor do nested calls to scavenge() on partially boxed objects.
- New heap_scavenge() function is exactly what scavenge() was,
but instead of taking 'n_words' it wants a 'limit' argument
which simplifies a few call sites.
- instance_scan() is faster when there are raw slots and the
layout bitmap is a fixnum, which is usually is.
- scav_boxed() no longer tries to be clever by doing nothing.
It examines the number of words indicated by the object header.
Same goes for short boxed and tiny boxed objects.
- As a corollary to the preceding, mark-and-sweep no longer invokes
a sizing function prior to calling scavenge() - it just dispatches
by widetag to an object-specific scavenger.
---
src/compiler/generic/late-objdef.lisp | 6 +-
src/runtime/gc-common.c | 156 ++++++++++++++++++----------------
src/runtime/gc-internal.h | 3 +-
src/runtime/gencgc.c | 33 ++++---
src/runtime/marknsweepgc.c | 27 +++---
5 files changed, 117 insertions(+), 108 deletions(-)
diff --git a/src/compiler/generic/late-objdef.lisp b/src/compiler/generic/late-objdef.lisp
index 3ac58e5..7becc42 100644
--- a/src/compiler/generic/late-objdef.lisp
+++ b/src/compiler/generic/late-objdef.lisp
@@ -47,15 +47,15 @@
;; The scavenge function for fun-header is basically "lose",
;; but it's only defined on non-x86 platforms for some reason.
(simple-fun-header ,(or #!+(or x86 x86-64) "lose" "fun_header") "fun_header" "lose")
- (closure-header ,(or #!+(or x86 x86-64) "closure_header" "boxed")
+ (closure-header ,(or #!+(or x86 x86-64) "closure_header" "short_boxed")
"short_boxed")
- (funcallable-instance-header ,(or #!+compact-instance-header "funinstance" "boxed")
+ (funcallable-instance-header ,(or #!+compact-instance-header "funinstance" "short_boxed")
"short_boxed")
;; These have a scav and trans function, but no size function.
#!-(or x86 x86-64) (return-pc-header "return_pc_header" "return_pc_header" "lose")
(value-cell-header "boxed")
- (symbol-header "boxed" "tiny_boxed")
+ (symbol-header "tiny_boxed")
(character "immediate")
(sap "unboxed")
(unbound-marker "immediate")
diff --git a/src/runtime/gc-common.c b/src/runtime/gc-common.c
index f82c296..43e74c8 100644
--- a/src/runtime/gc-common.c
+++ b/src/runtime/gc-common.c
@@ -98,12 +98,8 @@ static inline boolean pinned_p(lispobj obj, page_index_t page)
}
#endif
-void
-scavenge(lispobj *start, sword_t n_words)
+static inline void scav1(lispobj* object_ptr, lispobj object)
{
- lispobj *end = start + n_words;
- lispobj *object_ptr;
-
// GENCGC only:
// * With 32-bit words, is_lisp_pointer(object) returns true if object_ptr
// points to a forwarding pointer, so we need a sanity check inside the
@@ -132,36 +128,44 @@ scavenge(lispobj *start, sword_t n_words)
else /* Scavenge that pointer. */ \
(void)scavtab[widetag_of(object)](object_ptr, object); \
}
+#ifdef LISP_FEATURE_IMMOBILE_SPACE
+ page_index_t page;
+ // It would be fine, though suboptimal, to use from_space_p() here.
+ // If it returns false, we don't want to call immobile_space_p()
+ // unless the pointer is *not* into dynamic space.
+ if ((page = find_page_index((void*)object)) >= 0) {
+ if (page_table[page].gen == from_space && !pinned_p(object, page))
+ FIX_POINTER();
+ } else if (immobile_space_p(object)) {
+ lispobj *ptr = native_pointer(object);
+ if (immobile_obj_gen_bits(ptr) == from_space)
+ promote_immobile_obj(ptr, 1);
+ }
+#else
+ if (from_space_p(object)) {
+ FIX_POINTER();
+ } else {
+#if (N_WORD_BITS == 32) && defined(LISP_FEATURE_GENCGC)
+ if (forwarding_pointer_p(object_ptr))
+ lose("unexpected forwarding pointer in scavenge: %p, start=%p, n=%ld\n",
+ object_ptr, start, n_words);
+#endif
+ /* It points somewhere other than oldspace. Leave it
+ * alone. */
+ }
+#endif
+}
+
+// Scavenge a block of memory from 'start' to 'end'
+// that may contain object headers.
+void heap_scavenge(lispobj *start, lispobj *end)
+{
+ lispobj *object_ptr;
for (object_ptr = start; object_ptr < end;) {
lispobj object = *object_ptr;
if (is_lisp_pointer(object)) {
-#ifdef LISP_FEATURE_IMMOBILE_SPACE
- page_index_t page;
- // It would be fine, though suboptimal, to use from_space_p() here.
- // If it returns false, we don't want to call immobile_space_p()
- // unless the pointer is *not* into dynamic space.
- if ((page = find_page_index((void*)object)) >= 0) {
- if (page_table[page].gen == from_space && !pinned_p(object, page))
- FIX_POINTER();
- } else if (immobile_space_p(object)) {
- lispobj *ptr = native_pointer(object);
- if (immobile_obj_gen_bits(ptr) == from_space)
- promote_immobile_obj(ptr, 1);
- }
-#else
- if (from_space_p(object)) {
- FIX_POINTER();
- } else {
-#if (N_WORD_BITS == 32) && defined(LISP_FEATURE_GENCGC)
- if (forwarding_pointer_p(object_ptr))
- lose("unexpected forwarding pointer in scavenge: %p, start=%p, n=%ld\n",
- object_ptr, start, n_words);
-#endif
- /* It points somewhere other than oldspace. Leave it
- * alone. */
- }
-#endif
+ scav1(object_ptr, object);
object_ptr++;
}
else if (fixnump(object)) {
@@ -178,6 +182,19 @@ scavenge(lispobj *start, sword_t n_words)
object_ptr, start, end);
}
+// Scavenge a block of memory from 'start' extending for 'n_words'
+// that must not contain any object headers.
+sword_t scavenge(lispobj *start, sword_t n_words)
+{
+ lispobj *end = start + n_words;
+ lispobj *object_ptr;
+ for (object_ptr = start; object_ptr < end; object_ptr++) {
+ lispobj object = *object_ptr;
+ if (is_lisp_pointer(object)) scav1(object_ptr, object);
+ }
+ return n_words;
+}
+
static lispobj trans_fun_header(lispobj object); /* forward decls */
static lispobj trans_short_boxed(lispobj object);
@@ -524,12 +541,6 @@ size_immediate(lispobj *where)
}
-static sword_t
-scav_boxed(lispobj *where, lispobj object)
-{
- return 1;
-}
-
boolean positive_bignum_logbitp(int index, struct bignum* bignum)
{
/* If the bignum in the layout has another pointer to it (besides the layout)
@@ -685,12 +696,22 @@ scav_instance(lispobj *where, lispobj header)
#endif
sword_t nslots = instance_length(header) | 1;
- lispobj bitmap = ((struct layout*)layout)->bitmap;
- if (bitmap == make_fixnum(-1))
+ lispobj lbitmap = ((struct layout*)layout)->bitmap;
+ if (lbitmap == make_fixnum(-1))
scavenge(where+1, nslots);
- else
- instance_scan(scavenge, where+1, nslots, bitmap);
-
+ else if (!fixnump(lbitmap))
+ instance_scan((void(*)(lispobj*,sword_t))scavenge,
+ where+1, nslots, lbitmap);
+ else {
+ sword_t bitmap = (sword_t)lbitmap >> N_FIXNUM_TAG_BITS; // signed integer!
+ sword_t n = nslots;
+ lispobj obj;
+ for ( ; n-- ; bitmap >>= 1) {
+ ++where;
+ if ((bitmap & 1) && is_lisp_pointer(obj = *where))
+ scav1(where, obj);
+ }
+ }
return 1 + nslots;
}
@@ -707,42 +728,27 @@ scav_funinstance(lispobj *where, lispobj header)
}
#endif
-static lispobj trans_boxed(lispobj object)
-{
- gc_dcheck(is_lisp_pointer(object));
- sword_t length = HeaderValue(*native_pointer(object)) + 1;
- return copy_object(object, CEILING(length, 2));
-}
+//// Boxed object scav/trans/size functions
-static sword_t size_boxed(lispobj *where)
-{
- sword_t length = HeaderValue(*where) + 1;
- return CEILING(length, 2);
-}
+#define BOXED_NWORDS(obj) (1+(HeaderValue(obj) | 1))
+// Payload count expressed in 15 bits
+#define SHORT_BOXED_NWORDS(obj) (1+((HeaderValue(obj) & SHORT_HEADER_MAX_WORDS) | 1))
+// Payload count expressed in 8 bits
+#define TINY_BOXED_NWORDS(obj) (1+((HeaderValue(obj) & 0xFF) | 1))
-static lispobj trans_short_boxed(lispobj object) // Payload count expressed in 15 bits
-{
- sword_t length = (HeaderValue(*native_pointer(object)) & SHORT_HEADER_MAX_WORDS) + 1;
- return copy_object(object, CEILING(length, 2));
-}
+#define DEF_SCAV_BOXED(suffix, sizer) \
+ static sword_t __attribute__((unused)) \
+ scav_##suffix(lispobj *where, lispobj header) { \
+ return scavenge(where, sizer(header)); \
+ } \
+ static lispobj trans_##suffix(lispobj object) { \
+ return copy_object(object, sizer(*native_pointer(object))); \
+ } \
+ static sword_t size_##suffix(lispobj *where) { return sizer(*where); }
-static sword_t size_short_boxed(lispobj *where)
-{
- sword_t length = (HeaderValue(*where) & SHORT_HEADER_MAX_WORDS) + 1;
- return CEILING(length, 2);
-}
-
-static lispobj trans_tiny_boxed(lispobj object) // Payload count expressed in 8 bits
-{
- sword_t length = (HeaderValue(*native_pointer(object)) & 0xFF) + 1;
- return copy_object(object, CEILING(length, 2));
-}
-
-static sword_t size_tiny_boxed(lispobj *where)
-{
- sword_t length = (HeaderValue(*where) & 0xFF) + 1;
- return CEILING(length, 2);
-}
+DEF_SCAV_BOXED(boxed, BOXED_NWORDS)
+DEF_SCAV_BOXED(short_boxed, SHORT_BOXED_NWORDS)
+DEF_SCAV_BOXED(tiny_boxed, TINY_BOXED_NWORDS)
/* Note: on the sparc we don't have to do anything special for fdefns, */
/* 'cause the raw-addr has a function lowtag. */
diff --git a/src/runtime/gc-internal.h b/src/runtime/gc-internal.h
index 7de1ef7..6785bda 100644
--- a/src/runtime/gc-internal.h
+++ b/src/runtime/gc-internal.h
@@ -189,7 +189,8 @@ extern sword_t (*sizetab[256])(lispobj *where);
extern struct weak_pointer *weak_pointers; /* in gc-common.c */
extern struct hash_table *weak_hash_tables; /* in gc-common.c */
-extern void scavenge(lispobj *start, sword_t n_words);
+extern void heap_scavenge(lispobj *start, lispobj *limit);
+extern sword_t scavenge(lispobj *start, sword_t n_words);
extern void scavenge_interrupt_contexts(struct thread *thread);
extern void scav_weak_hash_tables(void);
extern void scan_weak_hash_tables(void);
diff --git a/src/runtime/gencgc.c b/src/runtime/gencgc.c
index ed70abb..e5dfab6 100644
--- a/src/runtime/gencgc.c
+++ b/src/runtime/gencgc.c
@@ -2170,7 +2170,8 @@ static void
scavenge_pinned_range(void* page_base, int start, int count)
{
// 'start' and 'count' are expressed in units of dwords
- scavenge((lispobj*)page_base + 2*start, 2*count);
+ lispobj *where = (lispobj*)page_base + 2*start;
+ heap_scavenge(where, where + 2*count);
}
static void
@@ -2538,9 +2539,9 @@ scavenge_generations(generation_index_t from, generation_index_t to)
break;
}
if (!write_protected) {
- scavenge(page_address(i),
- ((uword_t)(page_bytes_used(last_page) + npage_bytes(last_page-i)))
- /N_WORD_BYTES);
+ heap_scavenge(page_address(i),
+ (lispobj*)((char*)page_address(last_page)
+ + page_bytes_used(last_page)));
/* Now scan the pages and write protect those that
* don't have pointers to younger generations. */
@@ -2663,12 +2664,10 @@ scavenge_newspace_generation_one_scan(generation_index_t generation)
/* Do a limited check for write-protected pages. */
if (!all_wp) {
- sword_t nwords = (page_bytes_used(last_page) + npage_bytes(last_page-i)
- + page_scan_start_offset(i)) / N_WORD_BYTES;
new_areas_ignore_page = last_page;
-
- scavenge(page_scan_start(i), nwords);
-
+ heap_scavenge(page_scan_start(i),
+ (lispobj*)((char*)page_address(last_page)
+ + page_bytes_used(last_page)));
}
i = last_page;
}
@@ -2778,9 +2777,10 @@ scavenge_newspace_generation(generation_index_t generation)
for (i = 0; i < previous_new_areas_index; i++) {
page_index_t page = (*previous_new_areas)[i].page;
size_t offset = (*previous_new_areas)[i].offset;
- size_t size = (*previous_new_areas)[i].size / N_WORD_BYTES;
- gc_assert((*previous_new_areas)[i].size % N_WORD_BYTES == 0);
- scavenge(page_address(page)+offset, size);
+ size_t size = (*previous_new_areas)[i].size;
+ gc_assert(size % N_WORD_BYTES == 0);
+ lispobj *start = (lispobj*)((char*)page_address(page) + offset);
+ heap_scavenge(start, (lispobj*)((char*)start + size));
}
scav_weak_hash_tables();
@@ -3427,7 +3427,6 @@ static void
garbage_collect_generation(generation_index_t generation, int raise)
{
page_index_t i;
- uword_t static_space_size;
struct thread *th;
gc_assert(generation <= HIGHEST_NORMAL_GENERATION);
@@ -3650,15 +3649,13 @@ garbage_collect_generation(generation_index_t generation, int raise)
}
/* Scavenge static space. */
- static_space_size =
- (lispobj *)SymbolValue(STATIC_SPACE_FREE_POINTER,0) -
- (lispobj *)STATIC_SPACE_START;
if (gencgc_verbose > 1) {
FSHOW((stderr,
"/scavenge static space: %d bytes\n",
- static_space_size * sizeof(lispobj)));
+ SymbolValue(STATIC_SPACE_FREE_POINTER,0) - STATIC_SPACE_START));
}
- scavenge( (lispobj *) STATIC_SPACE_START, static_space_size);
+ heap_scavenge((lispobj*)STATIC_SPACE_START,
+ (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0));
/* All generations but the generation being GCed need to be
* scavenged. The new_space generation needs special handling as
diff --git a/src/runtime/marknsweepgc.c b/src/runtime/marknsweepgc.c
index dec7ded..e4579cf 100644
--- a/src/runtime/marknsweepgc.c
+++ b/src/runtime/marknsweepgc.c
@@ -512,7 +512,6 @@ static void full_scavenge_immobile_newspace()
if (!(fixedobj_pages[page].gens & bit)) continue;
// Skip amount within the loop is in bytes.
int obj_spacing = page_obj_align(page) << WORD_SHIFT;
- int n_words = page_obj_size(page);
lispobj* obj = low_page_address(page);
// Use an inclusive, not exclusive, limit. On pages with dense packing
// (i.e. non-LAYOUT), if the object size does not evenly divide the page
@@ -524,7 +523,8 @@ static void full_scavenge_immobile_newspace()
for ( ; obj <= limit ; obj = (lispobj*)((char*)obj + obj_spacing) ) {
if (!fixnump(*obj) && __immobile_obj_gen_bits(obj) == new_space) {
set_visited(obj);
- scavenge(obj, n_words);
+ lispobj header = *obj;
+ scavtab[widetag_of(header)](obj, header);
}
}
}
@@ -540,12 +540,14 @@ static void full_scavenge_immobile_newspace()
lispobj* obj = varyobj_scan_start(page);
do {
lispobj* limit = (lispobj*)low_page_address(page) + WORDS_PER_PAGE;
- int widetag, n_words;
+ int n_words;
for ( ; obj < limit ; obj += n_words ) {
- n_words = sizetab[widetag = widetag_of(*obj)](obj);
+ lispobj header = *obj;
if (__immobile_obj_gen_bits(obj) == new_space) {
set_visited(obj);
- scavenge(obj, n_words);
+ n_words = scavtab[widetag_of(header)](obj, header);
+ } else {
+ n_words = sizetab[widetag_of(header)](obj);
}
}
page = find_immobile_page_index(obj);
@@ -595,7 +597,8 @@ void scavenge_immobile_newspace()
--immobile_scav_queue_count;
if (!(__immobile_obj_gen_bits(obj) & IMMOBILE_OBJ_VISITED_FLAG)) {
set_visited(obj);
- scavenge(obj, sizetab[widetag_of(*obj)](obj));
+ lispobj header = *obj;
+ scavtab[widetag_of(header)](obj, header);
}
} while (i != queue_index_to);
}
@@ -640,7 +643,6 @@ scavenge_immobile_roots(generation_index_t min_gen, generation_index_t max_gen)
if (fixedobj_page_wp(page) || !(fixedobj_pages[page].gens & genmask))
continue;
int obj_spacing = page_obj_align(page) << WORD_SHIFT;
- int n_words = page_obj_size(page);
lispobj* obj = low_page_address(page);
lispobj* limit = (lispobj*)((char*)obj +
IMMOBILE_CARD_BYTES - obj_spacing);
@@ -651,7 +653,8 @@ scavenge_immobile_roots(generation_index_t min_gen, generation_index_t max_gen)
do {
if (!fixnump(*obj) && (genmask >> (gen=__immobile_obj_gen_bits(obj)) & 1)) {
if (gen == new_space) { set_visited(obj); }
- scavenge(obj, n_words);
+ lispobj header = *obj;
+ scavtab[widetag_of(header)](obj, header);
}
} while ((obj = (lispobj*)((char*)obj + obj_spacing)) <= limit);
}
@@ -664,12 +667,14 @@ scavenge_immobile_roots(generation_index_t min_gen, generation_index_t max_gen)
lispobj* obj = varyobj_scan_start(page);
do {
lispobj* limit = (lispobj*)low_page_address(page) + WORDS_PER_PAGE;
- int widetag, n_words, gen;
+ int n_words, gen;
for ( ; obj < limit ; obj += n_words ) {
- n_words = sizetab[widetag = widetag_of(*obj)](obj);
+ lispobj header = *obj;
if (genmask >> (gen=__immobile_obj_gen_bits(obj)) & 1) {
if (gen == new_space) { set_visited(obj); }
- scavenge(obj, n_words);
+ n_words = scavtab[widetag_of(header)](obj, header);
+ } else {
+ n_words = sizetab[widetag_of(header)](obj);
}
}
page = find_immobile_page_index(obj);
-----------------------------------------------------------------------
hooks/post-receive
--
SBCL
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Sbcl-commits mailing list
Sbcl-commits@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-commits
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic