Author: Remi Meier <remi.me...@inf.ethz.ch>
Branch: c8-faster-smallobj-sync
Changeset: r1931:b37387a2af20
Date: 2015-08-11 14:17 +0200
http://bitbucket.org/pypy/stmgc/changeset/b37387a2af20/
Log: WIP
diff --git a/c8/TODO b/c8/TODO
--- a/c8/TODO
+++ b/c8/TODO
@@ -23,6 +23,8 @@
- avoid __builtin_frame_address(0) in precisely the performance-critical
functions like the interpreter main loop
+- some lists in PSEGMENT can only grow and never shrink again
+ check if it matters
---------------------------
DONE:
diff --git a/c8/stm/core.c b/c8/stm/core.c
--- a/c8/stm/core.c
+++ b/c8/stm/core.c
@@ -1155,6 +1155,7 @@
assert(list_is_empty(STM_PSEGMENT->modified_old_objects));
assert(list_is_empty(STM_PSEGMENT->large_overflow_objects));
+ assert(list_is_empty(STM_PSEGMENT->small_overflow_obj_ranges));
assert(list_is_empty(STM_PSEGMENT->objects_pointing_to_nursery));
assert(list_is_empty(STM_PSEGMENT->young_weakrefs));
assert(tree_is_cleared(STM_PSEGMENT->young_outside_nursery));
@@ -1243,6 +1244,7 @@
list_clear(STM_PSEGMENT->objects_pointing_to_nursery);
list_clear(STM_PSEGMENT->old_objects_with_cards_set);
list_clear(STM_PSEGMENT->large_overflow_objects);
+ list_clear(STM_PSEGMENT->small_overflow_obj_ranges);
if (tl != NULL)
timing_event(tl, event);
@@ -1273,20 +1275,32 @@
#endif
}
-static void push_large_overflow_objects_to_other_segments(void)
+static void push_overflow_objects_to_other_segments(void)
{
- if (list_is_empty(STM_PSEGMENT->large_overflow_objects))
- return;
+ if (!list_is_empty(STM_PSEGMENT->large_overflow_objects)) {
+ acquire_privatization_lock(STM_SEGMENT->segment_num);
+ LIST_FOREACH_R(STM_PSEGMENT->large_overflow_objects, object_t *,
+ ({
+ assert(!(item->stm_flags & GCFLAG_WB_EXECUTED));
+ synchronize_object_enqueue(item);
+ }));
+ synchronize_objects_flush();
+ release_privatization_lock(STM_SEGMENT->segment_num);
+ }
- /* XXX: also pushes small ones right now */
- acquire_privatization_lock(STM_SEGMENT->segment_num);
- LIST_FOREACH_R(STM_PSEGMENT->large_overflow_objects, object_t *,
- ({
- assert(!(item->stm_flags & GCFLAG_WB_EXECUTED));
- synchronize_object_enqueue(item);
- }));
- synchronize_objects_flush();
- release_privatization_lock(STM_SEGMENT->segment_num);
+ if (!list_is_empty(STM_PSEGMENT->small_overflow_obj_ranges)) {
+ acquire_privatization_lock(STM_SEGMENT->segment_num);
+
+ struct list_s *lst = STM_PSEGMENT->small_overflow_obj_ranges;
+ while (!list_is_empty(lst)) {
+ ssize_t len = (ssize_t)list_pop_item(lst);
+ stm_char *start = (stm_char*)list_pop_item(lst);
+ _synchronize_fragment(start, len);
+ }
+
+ synchronize_objects_flush();
+ release_privatization_lock(STM_SEGMENT->segment_num);
+ }
/* we can as well clear the list here, since the
objects are only useful if the commit succeeds. And
@@ -1297,6 +1311,7 @@
unknown-to-the-segment/uncommitted things.
*/
list_clear(STM_PSEGMENT->large_overflow_objects);
+ list_clear(STM_PSEGMENT->small_overflow_obj_ranges);
}
@@ -1335,7 +1350,7 @@
s_mutex_unlock();
}
- push_large_overflow_objects_to_other_segments();
+ push_overflow_objects_to_other_segments();
/* push before validate. otherwise they are reachable too early */
@@ -1517,6 +1532,7 @@
list_clear(pseg->objects_pointing_to_nursery);
list_clear(pseg->old_objects_with_cards_set);
list_clear(pseg->large_overflow_objects);
+ list_clear(pseg->small_overflow_obj_ranges);
list_clear(pseg->young_weakrefs);
#pragma pop_macro("STM_SEGMENT")
#pragma pop_macro("STM_PSEGMENT")
@@ -1709,7 +1725,6 @@
}
-
static void synchronize_object_enqueue(object_t *obj)
{
assert(!_is_young(obj));
@@ -1785,3 +1800,41 @@
DEBUG_EXPECT_SEGFAULT(true);
}
+
+
+
+static void small_overflow_obj_ranges_add(object_t *obj)
+{
+ assert(is_small_uniform(obj));
+
+ ssize_t obj_size = stmcb_size_rounded_up(
+ (struct object_s *)REAL_ADDRESS(STM_SEGMENT->segment_base, obj));
+ OPT_ASSERT(obj_size >= 16);
+
+ struct list_s *lst = STM_PSEGMENT->small_overflow_obj_ranges;
+ if (!list_is_empty(lst)) {
+ /* try to merge with other ranges (XXX: quadratic, problem?) */
+ stm_char *obj_start = (stm_char*)obj;
+ long i;
+ for (i = lst->count - 2; i >= 0; i -= 2) {
+ stm_char *start = (stm_char*)lst->items[i];
+ ssize_t size = (ssize_t)lst->items[i+1];
+
+ if (start + size == obj_start) {
+ /* merge!
+ Note: we cannot overlap pages by adding to a range
+ in this way, since the first slot in a smallmalloc
+ page is always unused. Thus, we never merge the
+ last obj in a page with the first obj in a successor
+ page. */
+ lst->items[i+1] = size + obj_size;
+ return;
+ }
+ }
+ }
+
+ /* no merge was found */
+ STM_PSEGMENT->small_overflow_obj_ranges =
+ list_append2(STM_PSEGMENT->small_overflow_obj_ranges,
+ (uintptr_t)obj, (uintptr_t)obj_size);
+}
diff --git a/c8/stm/core.h b/c8/stm/core.h
--- a/c8/stm/core.h
+++ b/c8/stm/core.h
@@ -104,10 +104,17 @@
/* list of objects created in the current transaction and
that survived at least one minor collection. They need
to be synchronized to other segments on commit, but they
- do not need to be in the commit log entry.
- XXX: for now it also contains small overflow objs */
+ do not need to be in the commit log entry. */
struct list_s *large_overflow_objects;
+ /* lists the memory ranges of uncommitted/overflow objs that
+ need to be flushed to other segments on commit (like
+ large_overflow_objects). (unsorted, a range never overlaps
+ pages) */
+ /* XXX: not much different from before. Maybe try a ranges list
+ per size class. */
+ struct list_s *small_overflow_obj_ranges;
+
uint8_t privatization_lock; // XXX KILL
uint8_t safe_point;
@@ -303,8 +310,10 @@
static void touch_all_pages_of_obj(object_t *obj, size_t obj_size);
+static inline void _synchronize_fragment(stm_char *frag, ssize_t frag_size);
static void synchronize_object_enqueue(object_t *obj);
static void synchronize_objects_flush(void);
+static void small_overflow_obj_ranges_add(object_t *obj);
static void _signal_handler(int sig, siginfo_t *siginfo, void *context);
static bool _stm_validate(void);
diff --git a/c8/stm/forksupport.c b/c8/stm/forksupport.c
--- a/c8/stm/forksupport.c
+++ b/c8/stm/forksupport.c
@@ -98,6 +98,7 @@
STM_PSEGMENT->safe_point = SP_NO_TRANSACTION;
list_clear(STM_PSEGMENT->objects_pointing_to_nursery);
list_clear(STM_PSEGMENT->large_overflow_objects);
+ list_clear(STM_PSEGMENT->small_overflow_obj_ranges);
s_mutex_unlock();
return;
diff --git a/c8/stm/gcpage.c b/c8/stm/gcpage.c
--- a/c8/stm/gcpage.c
+++ b/c8/stm/gcpage.c
@@ -597,6 +597,9 @@
}
}
+ /* XXX: fix small_overflow_obj_ranges */
+ abort();
+
/* Remove from 'modified_old_objects' all old hashtables that die */
{
lst = pseg->modified_old_objects;
diff --git a/c8/stm/nursery.c b/c8/stm/nursery.c
--- a/c8/stm/nursery.c
+++ b/c8/stm/nursery.c
@@ -57,7 +57,7 @@
static object_t *find_existing_shadow(object_t *obj);
#define GCWORD_MOVED ((object_t *) -1)
#define FLAG_SYNC_LARGE 0x01
-
+#define FLAG_SYNC_SMALL 0x02
static void minor_trace_if_young(object_t **pobj)
{
@@ -96,6 +96,8 @@
dprintf(("has_shadow(%p): %p, sz:%lu\n",
obj, nobj, size));
+ /* XXX: shadows are always large-mallocd */
+ nobj_sync_now = FLAG_SYNC_LARGE;
goto copy_large_object;
}
@@ -106,10 +108,12 @@
/* case 1: object is not small enough.
Ask gcpage.c for an allocation via largemalloc. */
nobj = (object_t *)allocate_outside_nursery_large(size);
+ nobj_sync_now = FLAG_SYNC_LARGE;
}
else {
/* case "small enough" */
nobj = (object_t *)allocate_outside_nursery_small(size);
+ nobj_sync_now = FLAG_SYNC_SMALL;
}
//dprintf(("move %p -> %p\n", obj, nobj));
@@ -118,7 +122,7 @@
char *realnobj = REAL_ADDRESS(STM_SEGMENT->segment_base, nobj);
memcpy(realnobj, realobj, size);
- nobj_sync_now = ((uintptr_t)nobj) | FLAG_SYNC_LARGE;
+ nobj_sync_now |= (uintptr_t)nobj; /* SYNC_LARGE set above */
pforwarded_array[0] = GCWORD_MOVED;
pforwarded_array[1] = nobj;
@@ -133,6 +137,7 @@
/* a young object outside the nursery */
nobj = obj;
tree_delete_item(STM_PSEGMENT->young_outside_nursery, (uintptr_t)nobj);
+ assert(!is_small_uniform(nobj));
nobj_sync_now = ((uintptr_t)nobj) | FLAG_SYNC_LARGE;
}
@@ -363,31 +368,42 @@
while (!list_is_empty(lst)) {
uintptr_t obj_sync_now = list_pop_item(lst);
- object_t *obj = (object_t *)(obj_sync_now & ~FLAG_SYNC_LARGE);
+ object_t *obj = (object_t *)(obj_sync_now &
~(FLAG_SYNC_LARGE|FLAG_SYNC_SMALL));
assert(!_is_in_nursery(obj));
_collect_now(obj);
assert(!(obj->stm_flags & GCFLAG_CARDS_SET));
- if (obj_sync_now & FLAG_SYNC_LARGE) {
- /* XXX: SYNC_LARGE even set for small objs right now */
- /* this is a newly allocated obj in this transaction. We must
- either synchronize the object to other segments now, or
- add the object to large_overflow_objects list */
- struct stm_priv_segment_info_s *pseg =
get_priv_segment(STM_SEGMENT->segment_num);
- if (pseg->minor_collect_will_commit_now) {
- acquire_privatization_lock(pseg->pub.segment_num);
- synchronize_object_enqueue(obj);
- release_privatization_lock(pseg->pub.segment_num);
- } else {
+ /* the list could have moved while appending */
+ lst = STM_PSEGMENT->objects_pointing_to_nursery;
+
+ if (!(obj_sync_now & (FLAG_SYNC_LARGE|FLAG_SYNC_SMALL)))
+ continue;
+
+ /* obj is a newly allocated obj in this transaction. We must
+ either synchronize the object to other segments now, or
+ add the object to large_overflow_objects list */
+ struct stm_priv_segment_info_s *pseg =
get_priv_segment(STM_SEGMENT->segment_num);
+ if (pseg->minor_collect_will_commit_now) {
+ /* small or large obj are directly synced now */
+ acquire_privatization_lock(pseg->pub.segment_num);
+ synchronize_object_enqueue(obj);
+ release_privatization_lock(pseg->pub.segment_num);
+
+ if (obj_sync_now & FLAG_SYNC_LARGE) {
+ _cards_cleared_in_object(pseg, obj, false);
+ }
+ } else {
+ /* remember them in lists to sync on commit */
+ if (obj_sync_now & FLAG_SYNC_LARGE) {
LIST_APPEND(STM_PSEGMENT->large_overflow_objects, obj);
+ _cards_cleared_in_object(pseg, obj, false);
+ } else { // SYNC_SMALL
+ small_overflow_obj_ranges_add(obj);
}
- _cards_cleared_in_object(pseg, obj, false);
}
- /* the list could have moved while appending */
- lst = STM_PSEGMENT->objects_pointing_to_nursery;
}
/* flush all overflow objects to other segments now */
diff --git a/c8/stm/setup.c b/c8/stm/setup.c
--- a/c8/stm/setup.c
+++ b/c8/stm/setup.c
@@ -101,6 +101,7 @@
pr->pub.segment_base = segment_base;
pr->modified_old_objects = list_create();
pr->large_overflow_objects = list_create();
+ pr->small_overflow_obj_ranges = list_create();
pr->young_weakrefs = list_create();
pr->old_weakrefs = list_create();
pr->objects_pointing_to_nursery = list_create();
@@ -158,7 +159,9 @@
list_free(pr->old_objects_with_cards_set);
list_free(pr->modified_old_objects);
assert(list_is_empty(pr->large_overflow_objects));
+ assert(list_is_empty(pr->small_overflow_obj_ranges));
list_free(pr->large_overflow_objects);
+ list_free(pr->small_overflow_obj_ranges);
list_free(pr->young_weakrefs);
list_free(pr->old_weakrefs);
tree_free(pr->young_outside_nursery);
diff --git a/c8/stm/smallmalloc.h b/c8/stm/smallmalloc.h
--- a/c8/stm/smallmalloc.h
+++ b/c8/stm/smallmalloc.h
@@ -50,12 +50,6 @@
struct small_malloc_data_s {
struct small_free_loc_s *loc_free[GC_N_SMALL_REQUESTS];
- /* lists the memory ranges of uncommitted/overflow objs that
- need to be flushed to other segments on commit (like
- large_overflow_objects). (unsorted, a range never overlaps
- pages) */
- struct list_s *uncommitted_ranges;
-
/* with "uncommitted_ranges", we do the following during major GCs:
for seg in segments:
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
