From 5fffbb72d9871ab7c4b46306dc52dae68fb375ab Mon Sep 17 00:00:00 2001 From: Nikodemus Siivola Date: Sun, 9 Sep 2007 12:39:16 +0000 Subject: [PATCH] 1.0.9.50: O(1) weak pointer scavenging * Use self-pointer instead of NULL to mark the end of scavenged weak pointer list in GC, which allows identifying unscavenged pointers by the NULL next pointers. * Scavenging a single weak pointer in gencgc is now an O(1) operation instead of O(#scanned pointers so far). Thanks to Paul Khuong. --- NEWS | 3 +++ src/runtime/gc-common.c | 10 ++++++++-- src/runtime/gencgc.c | 32 ++++++++++++-------------------- version.lisp-expr | 2 +- 4 files changed, 24 insertions(+), 23 deletions(-) diff --git a/NEWS b/NEWS index 875c36c..56b67a4 100644 --- a/NEWS +++ b/NEWS @@ -4,6 +4,9 @@ changes in sbcl-1.0.10 relative to sbcl-1.0.9: associates .lisp and .fasl files with the installed SBCL. * minor incompatible change: :UNIX is no longer present in *FEATURES* on Windows. (thanks to Luis Oliviera) + * optimization: scavenging weak pointers is now more efficient, + requiring O(1) instead of O(N) per weak pointer to identify + scanvenged vs. unscavenged pointers. (thanks to Paul Khuong) * optimization: SLOT-VALUE &co are now ~50% faster for variable slot names, when the class of the instance is a direct instance STANDARD-CLASS or FUNCALLABLE-STANDARD-CLASS (making them only 3x diff --git a/src/runtime/gc-common.c b/src/runtime/gc-common.c index 02b78db..584f9d7 100644 --- a/src/runtime/gc-common.c +++ b/src/runtime/gc-common.c @@ -1523,11 +1523,17 @@ size_weak_pointer(lispobj *where) void scan_weak_pointers(void) { - struct weak_pointer *wp; - for (wp = weak_pointers; wp != NULL; wp=wp->next) { + struct weak_pointer *wp, *next_wp; + for (wp = weak_pointers, next_wp = NULL; wp != NULL; wp = next_wp) { lispobj value = wp->value; lispobj *first_pointer; gc_assert(widetag_of(wp->header)==WEAK_POINTER_WIDETAG); + + next_wp = wp->next; + wp->next = NULL; + if (next_wp == wp) /* gencgc uses a ref to self for end of list */ + next_wp = NULL; + if (!(is_lisp_pointer(value) && from_space_p(value))) continue; diff --git a/src/runtime/gencgc.c b/src/runtime/gencgc.c index 7091554..d16a44c 100644 --- a/src/runtime/gencgc.c +++ b/src/runtime/gencgc.c @@ -2050,29 +2050,21 @@ size_lutex(lispobj *where) static long scav_weak_pointer(lispobj *where, lispobj object) { - struct weak_pointer *wp = weak_pointers; - /* Push the weak pointer onto the list of weak pointers. - * Do I have to watch for duplicates? Originally this was - * part of trans_weak_pointer but that didn't work in the - * case where the WP was in a promoted region. + /* Since we overwrite the 'next' field, we have to make + * sure not to do so for pointers already in the list. + * Instead of searching the list of weak_pointers each + * time, we ensure that next is always NULL when the weak + * pointer isn't in the list, and not NULL otherwise. + * Since we can't use NULL to denote end of list, we + * use a pointer back to the same weak_pointer. */ + struct weak_pointer * wp = (struct weak_pointer*)where; - /* Check whether it's already in the list. */ - while (wp != NULL) { - if (wp == (struct weak_pointer*)where) { - break; - } - wp = wp->next; - } - if (wp == NULL) { - /* Add it to the start of the list. */ - wp = (struct weak_pointer*)where; - if (wp->next != weak_pointers) { - wp->next = weak_pointers; - } else { - /*SHOW("avoided write to weak pointer");*/ - } + if (NULL == wp->next) { + wp->next = weak_pointers; weak_pointers = wp; + if (NULL == wp->next) + wp->next = wp; } /* Do not let GC scavenge the value slot of the weak pointer. diff --git a/version.lisp-expr b/version.lisp-expr index c5a1f62..ae6a471 100644 --- a/version.lisp-expr +++ b/version.lisp-expr @@ -17,4 +17,4 @@ ;;; checkins which aren't released. (And occasionally for internal ;;; versions, especially for internal versions off the main CVS ;;; branch, it gets hairier, e.g. "0.pre7.14.flaky4.13".) -"1.0.9.49" +"1.0.9.50" -- 1.7.10.4