Author: Armin Rigo <ar...@tunes.org>
Branch: incremental-gc
Changeset: r67185:4ac5aa29679e
Date: 2013-10-07 17:34 +0200
http://bitbucket.org/pypy/pypy/changeset/4ac5aa29679e/
Log: Make minimarkpage.py support optionally incremental mass freeing.
diff --git a/rpython/memory/gc/minimarkpage.py
b/rpython/memory/gc/minimarkpage.py
--- a/rpython/memory/gc/minimarkpage.py
+++ b/rpython/memory/gc/minimarkpage.py
@@ -1,3 +1,4 @@
+import sys
from rpython.rtyper.lltypesystem import lltype, llmemory, llarena, rffi
from rpython.rlib.rarithmetic import LONG_BIT, r_uint
from rpython.rlib.objectmodel import we_are_translated
@@ -99,12 +100,10 @@
# a pointer to a page that has room for at least one more
# allocation of the given size.
length = small_request_threshold / WORD + 1
- self.page_for_size = lltype.malloc(rffi.CArray(PAGE_PTR), length,
- flavor='raw', zero=True,
- immortal=True)
- self.full_page_for_size = lltype.malloc(rffi.CArray(PAGE_PTR), length,
- flavor='raw', zero=True,
- immortal=True)
+ self.page_for_size = self._new_page_ptr_list(length)
+ self.full_page_for_size = self._new_page_ptr_list(length)
+ self.old_page_for_size = self._new_page_ptr_list(length)
+ self.old_full_page_for_size = self._new_page_ptr_list(length)
self.nblocks_for_size = lltype.malloc(rffi.CArray(lltype.Signed),
length, flavor='raw',
immortal=True)
@@ -143,6 +142,12 @@
self.total_memory_used = r_uint(0)
+ def _new_page_ptr_list(self, length):
+ return lltype.malloc(rffi.CArray(PAGE_PTR), length,
+ flavor='raw', zero=True,
+ immortal=True)
+
+
def malloc(self, size):
"""Allocate a block from a page in an arena."""
nsize = llmemory.raw_malloc_usage(size)
@@ -248,9 +253,7 @@
arena = arena.nextarena
- def allocate_new_arena(self):
- """Loads in self.current_arena the arena to allocate from next."""
- #
+ def _pick_next_arena(self):
# Pick an arena from 'arenas_lists[i]', with i as small as possible
# but > 0. Use caching with 'min_empty_nfreepages', which guarantees
# that 'arenas_lists[1:min_empty_nfreepages]' are all empty.
@@ -262,10 +265,25 @@
# Found it.
self.current_arena = self.arenas_lists[i]
self.arenas_lists[i] = self.current_arena.nextarena
- return
+ return True
#
i += 1
self.min_empty_nfreepages = i
+ return False
+
+
+ def allocate_new_arena(self):
+ """Loads in self.current_arena the arena to allocate from next."""
+ #
+ if self._pick_next_arena():
+ return
+ #
+ # Maybe we are incrementally collecting, in which case an arena
+ # could have more free pages thrown into it than arenas_lists[]
+ # account for. Rehash and retry.
+ self._rehash_arenas_lists()
+ if self._pick_next_arena():
+ return
#
# No more arena with any free page. We must allocate a new arena.
if not we_are_translated():
@@ -297,14 +315,32 @@
allocate_new_arena._dont_inline_ = True
- def mass_free(self, ok_to_free_func):
- """For each object, if ok_to_free_func(obj) returns True, then free
- the object.
+ def mass_free_prepare(self):
+ """Prepare calls to mass_free_incremental(): moves the chained lists
+ into 'self.old_xxx'.
"""
self.total_memory_used = r_uint(0)
#
- # For each size class:
size_class = self.small_request_threshold >> WORD_POWER_2
+ self.size_class_with_old_pages = size_class
+ #
+ while size_class >= 1:
+ self.old_page_for_size[size_class] = (
+ self.page_for_size[size_class])
+ self.old_full_page_for_size[size_class] = (
+ self.full_page_for_size[size_class])
+ self.page_for_size[size_class] = PAGE_NULL
+ self.full_page_for_size[size_class] = PAGE_NULL
+ size_class -= 1
+
+
+ def mass_free_incremental(self, ok_to_free_func, max_pages):
+ """For each object, if ok_to_free_func(obj) returns True, then free
+ the object. This returns True if complete, or False if the limit
+ 'max_pages' is reached.
+ """
+ size_class = self.size_class_with_old_pages
+ #
while size_class >= 1:
#
# Walk the pages in 'page_for_size[size_class]' and
@@ -313,10 +349,30 @@
# and become available for reuse by any size class. Pages
# not completely freed are re-chained either in
# 'full_page_for_size[]' or 'page_for_size[]'.
- self.mass_free_in_pages(size_class, ok_to_free_func)
+ max_pages = self.mass_free_in_pages(size_class, ok_to_free_func,
+ max_pages)
+ if max_pages <= 0:
+ self.size_class_with_old_pages = size_class
+ return False
#
size_class -= 1
#
+ self._rehash_arenas_lists()
+ return True
+
+
+ def mass_free(self, ok_to_free_func):
+ """For each object, if ok_to_free_func(obj) returns True, then free
+ the object.
+ """
+ self.mass_free_prepare()
+ #
+ res = self.mass_free_incremental(ok_to_free_func, sys.maxint)
+ ll_assert(res, "non-incremental mass_free_in_pages() returned False")
+
+
+ def _rehash_arenas_lists(self):
+ #
# Rehash arenas into the correct arenas_lists[i]. If
# 'self.current_arena' contains an arena too, it remains there.
(self.old_arenas_lists, self.arenas_lists) = (
@@ -353,18 +409,20 @@
self.min_empty_nfreepages = 1
- def mass_free_in_pages(self, size_class, ok_to_free_func):
+ def mass_free_in_pages(self, size_class, ok_to_free_func, max_pages):
nblocks = self.nblocks_for_size[size_class]
block_size = size_class * WORD
- remaining_partial_pages = PAGE_NULL
- remaining_full_pages = PAGE_NULL
+ remaining_partial_pages = self.page_for_size[size_class]
+ remaining_full_pages = self.full_page_for_size[size_class]
#
step = 0
while step < 2:
if step == 0:
- page = self.full_page_for_size[size_class]
+ page = self.old_full_page_for_size[size_class]
+ self.old_full_page_for_size[size_class] = PAGE_NULL
else:
- page = self.page_for_size[size_class]
+ page = self.old_page_for_size[size_class]
+ self.old_page_for_size[size_class] = PAGE_NULL
#
while page != PAGE_NULL:
#
@@ -392,12 +450,26 @@
# No object survives; free the page.
self.free_page(page)
+ #
+ max_pages -= 1
+ if max_pages <= 0:
+ # End of the incremental step: store back the unprocessed
+ # pages into self.old_xxx and return early
+ if step == 0:
+ self.old_full_page_for_size[size_class] = nextpage
+ else:
+ self.old_page_for_size[size_class] = nextpage
+ step = 99 # stop
+ break
+
page = nextpage
#
- step += 1
+ else:
+ step += 1
#
self.page_for_size[size_class] = remaining_partial_pages
self.full_page_for_size[size_class] = remaining_full_pages
+ return max_pages
def free_page(self, page):
diff --git a/rpython/memory/gc/test/test_minimarkpage.py
b/rpython/memory/gc/test/test_minimarkpage.py
--- a/rpython/memory/gc/test/test_minimarkpage.py
+++ b/rpython/memory/gc/test/test_minimarkpage.py
@@ -402,7 +402,7 @@
# ____________________________________________________________
-def test_random():
+def test_random(incremental=False):
import random
pagesize = hdrsize + 24*WORD
num_pages = 3
@@ -428,30 +428,52 @@
raise DoneTesting
a.mark_freed = my_mark_freed
ac.allocate_new_arena = my_allocate_new_arena
+
+ def allocate_object(live_objects):
+ size_class = random.randrange(1, 7)
+ obj = ac.malloc(size_class * WORD)
+ at = (obj.arena, obj.offset)
+ assert at not in live_objects
+ live_objects[at] = size_class * WORD
+
try:
while True:
#
# Allocate some more objects
for i in range(random.randrange(50, 100)):
- size_class = random.randrange(1, 7)
- obj = ac.malloc(size_class * WORD)
- at = (obj.arena, obj.offset)
- assert at not in live_objects
- live_objects[at] = size_class * WORD
+ allocate_object(live_objects)
#
# Free half the objects, randomly
ok_to_free = OkToFree(ac, lambda obj: random.random() < 0.5,
multiarenas=True)
- ac.mass_free(ok_to_free)
+ live_objects_extra = {}
+ fresh_extra = 0
+ if not incremental:
+ ac.mass_free(ok_to_free)
+ else:
+ ac.mass_free_prepare()
+ while not ac.mass_free_incremental(ok_to_free,
+ random.randrange(1, 3)):
+ print '[]'
+ prev = ac.total_memory_used
+ allocate_object(live_objects_extra)
+ fresh_extra += ac.total_memory_used - prev
#
# Check that we have seen all objects
assert sorted(ok_to_free.seen) == sorted(live_objects)
- surviving_total_size = 0
+ surviving_total_size = fresh_extra
for at, freed in ok_to_free.seen.items():
if freed:
del live_objects[at]
else:
surviving_total_size += live_objects[at]
assert ac.total_memory_used == surviving_total_size
+ #
+ assert not (set(live_objects) & set(live_objects_extra))
+ live_objects.update(live_objects_extra)
+ #
except DoneTesting:
pass
+
+def test_random_incremental():
+ test_random(incremental=True)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
