Author: Maciej Fijalkowski <[email protected]>
Branch: gc-minimark-pinning
Changeset: r54376:3ada686cfd21
Date: 2012-04-15 20:29 +0200
http://bitbucket.org/pypy/pypy/changeset/3ada686cfd21/
Log: a sorting attempt
diff --git a/TODO b/TODO
--- a/TODO
+++ b/TODO
@@ -1,8 +1,4 @@
* implement limit on no of pinned objects + replace insert with qsort
-* use pinning
-
-* make sure objects with shadows work
-
* implement tracing for pinned objects (check that it works)
\ No newline at end of file
diff --git a/pypy/rpython/lltypesystem/rffi.py
b/pypy/rpython/lltypesystem/rffi.py
--- a/pypy/rpython/lltypesystem/rffi.py
+++ b/pypy/rpython/lltypesystem/rffi.py
@@ -2,11 +2,11 @@
from pypy.annotation import model as annmodel
from pypy.rpython.lltypesystem import lltype
from pypy.rpython.lltypesystem import ll2ctypes
-from pypy.rpython.lltypesystem.llmemory import cast_adr_to_ptr, cast_ptr_to_adr
+from pypy.rpython.lltypesystem.llmemory import cast_ptr_to_adr
from pypy.rpython.lltypesystem.llmemory import itemoffsetof, raw_memcopy
from pypy.annotation.model import lltype_to_annotation
from pypy.tool.sourcetools import func_with_new_name
-from pypy.rlib.objectmodel import Symbolic, CDefinedIntSymbolic
+from pypy.rlib.objectmodel import Symbolic, we_are_translated
from pypy.rlib.objectmodel import keepalive_until_here
from pypy.rlib import rarithmetic, rgc
from pypy.rpython.extregistry import ExtRegistryEntry
@@ -14,7 +14,6 @@
from pypy.rpython.tool.rfficache import platform
from pypy.translator.tool.cbuild import ExternalCompilationInfo
from pypy.rpython.annlowlevel import llhelper
-from pypy.rlib.objectmodel import we_are_translated
from pypy.rlib.rstring import StringBuilder, UnicodeBuilder, assert_str0
from pypy.rlib import jit
from pypy.rpython.lltypesystem import llmemory
@@ -715,14 +714,15 @@
free_nonmovingbuffer call.
"""
rgc.pin(data)
- if rgc.can_move(data):
+ if rgc.can_move(data) or not we_are_translated():
count = len(data)
buf = lltype.malloc(TYPEP.TO, count, flavor='raw')
for i in range(count):
buf[i] = data[i]
return buf
else:
- data_start = cast_ptr_to_adr(llstrtype(data)) + \
+ ll_s = llstrtype(data)
+ data_start = cast_ptr_to_adr(ll_s) + \
offsetof(STRTYPE, 'chars') + itemoffsetof(STRTYPE.chars, 0)
return cast(TYPEP, data_start)
get_nonmovingbuffer._annenforceargs_ = [strtype]
diff --git a/pypy/rpython/memory/gc/minimark.py
b/pypy/rpython/memory/gc/minimark.py
--- a/pypy/rpython/memory/gc/minimark.py
+++ b/pypy/rpython/memory/gc/minimark.py
@@ -205,6 +205,10 @@
# minimal allocated size of the nursery is 2x the following
# number (by default, at least 132KB on 32-bit and 264KB on 64-bit).
"large_object": (16384+512)*WORD,
+
+ # number of allowed pinned objects, must be smaller than the size
+ # of one chunk for address stack
+ "max_number_of_pinned_objects": 100,
}
def __init__(self, config,
@@ -216,6 +220,7 @@
major_collection_threshold=2.5,
growth_rate_max=2.5, # for tests
card_page_indices=0,
+ max_number_of_pinned_objects=100,
large_object=8*WORD,
ArenaCollectionClass=None,
**kwds):
@@ -226,6 +231,7 @@
self.small_request_threshold = small_request_threshold
self.major_collection_threshold = major_collection_threshold
self.growth_rate_max = growth_rate_max
+ self.max_number_of_pinned_objects = max_number_of_pinned_objects
self.num_major_collects = 0
self.min_heap_size = 0.0
self.max_heap_size = 0.0
@@ -309,6 +315,7 @@
# minor collect. This is a sorted deque that should be consulted when
# considering next nursery ceiling
self.nursery_barriers = self.AddressDeque()
+ self.pinned_objects_in_nursery = 0
#
# Allocate a nursery. In case of auto_nursery_size, start by
@@ -797,9 +804,13 @@
not self.header(obj).tid & GCFLAG_PINNED)
def pin(self, obj):
+ if self.pinned_objects_in_nursery >= self.max_number_of_pinned_objects:
+ return
+ self.pinned_objects_in_nursery += 1
self.header(obj).tid |= GCFLAG_PINNED
def unpin(self, obj):
+ self.pinned_objects_in_nursery -= 1
self.header(obj).tid &= ~GCFLAG_PINNED
def shrink_array(self, obj, smallerlength):
@@ -1264,6 +1275,8 @@
# the young arrays.
self.nursery_barriers.delete()
self.surviving_pinned_objects = self.AddressStack()
+ self.pinned_objects_in_nursery = 0
+ # we track only surviving objects, don't care about the rest
if self.young_rawmalloced_objects:
self.remove_young_arrays_from_old_objects_pointing_to_young()
#
@@ -1318,6 +1331,7 @@
nursery_barriers = self.AddressDeque()
prev = self.nursery
size_gc_header = self.gcheaderbuilder.size_gc_header
+ self.surviving_pinned_objects.sort()
while self.surviving_pinned_objects.non_empty():
next = self.surviving_pinned_objects.pop()
assert next >= prev
@@ -1501,7 +1515,8 @@
return
hdr.tid |= GCFLAG_VISITED
ll_assert(not self.header(obj).tid & GCFLAG_HAS_CARDS, "support
cards with pinning")
- self.surviving_pinned_objects.insert(
+ self.pinned_objects_in_nursery += 1
+ self.surviving_pinned_objects.append(
llarena.getfakearenaaddress(obj - size_gc_header))
return
#
diff --git a/pypy/rpython/memory/support.py b/pypy/rpython/memory/support.py
--- a/pypy/rpython/memory/support.py
+++ b/pypy/rpython/memory/support.py
@@ -1,6 +1,5 @@
from pypy.rpython.lltypesystem import lltype, llmemory
from pypy.rlib.objectmodel import free_non_gc_object, we_are_translated
-from pypy.rlib.rarithmetic import r_uint, LONG_BIT
from pypy.rlib.debug import ll_assert
from pypy.tool.identity_dict import identity_dict
@@ -59,7 +58,30 @@
unused_chunks = FreeList()
cache[chunk_size] = unused_chunks, null_chunk
- return unused_chunks, null_chunk
+
+ def partition(array, left, right):
+ last_item = array[right]
+ pivot = last_item
+ storeindex = left
+ for i in range(left, right):
+ if array[i] >= pivot:
+ array[i], array[storeindex] = array[storeindex], array[i]
+ storeindex += 1
+ # Move pivot to its final place
+ array[storeindex], array[right] = last_item, array[storeindex]
+ return storeindex
+
+ def quicksort(array, left, right):
+ # sort array[left:right+1] (i.e. bounds included)
+ if right > left:
+ pivotnewindex = partition(array, left, right)
+ quicksort(array, left, pivotnewindex - 1)
+ quicksort(array, pivotnewindex + 1, right)
+
+ def sort_chunk(chunk, size):
+ quicksort(chunk.items, 0, size - 1)
+
+ return unused_chunks, null_chunk, sort_chunk
def get_address_stack(chunk_size=DEFAULT_CHUNK_SIZE, cache={}):
@@ -68,7 +90,7 @@
except KeyError:
pass
- unused_chunks, null_chunk = get_chunk_manager(chunk_size)
+ unused_chunks, null_chunk, sort_chunk = get_chunk_manager(chunk_size)
class AddressStack(object):
_alloc_flavor_ = "raw"
@@ -173,46 +195,9 @@
chunk.items[count] = got
got = next
- def insert(self, addr):
- """ Insert addr in the already sorted stack to make sure
- the smallest one is on top
- """
- if self.used_in_last_chunk == 0:
- self.append(addr)
- return
- got = self.pop()
- read = self.used_in_last_chunk - 1
- if read == -1 and got <= addr:
- self.append(addr)
- self.append(got)
- return
- read_chunk = self.chunk
- self.append(got)
- if got > addr:
- self.append(addr)
- return
- write = self.used_in_last_chunk
- if self.used_in_last_chunk == chunk_size:
- self.enlarge()
- write = 0
- self.used_in_last_chunk += 1
- write_chunk = self.chunk
- while got < addr and not read_chunk is null_chunk:
- write_chunk.items[write] = got
- write -= 1
- if write < 0:
- write_chunk = write_chunk.next
- write = chunk_size - 1
- got = read_chunk.items[read]
- read -= 1
- if read < 0:
- read_chunk = read_chunk.next
- read = chunk_size - 1
- if got < addr:
- write_chunk.items[write] = got
- write_chunk.items[0] = addr
- else:
- write_chunk.items[write] = addr
+ def sort(self):
+ ll_assert(self.chunk.next == null_chunk, "too big for sorting")
+ sort_chunk(self.chunk, self.used_in_last_chunk - 1)
cache[chunk_size] = AddressStack
return AddressStack
diff --git a/pypy/rpython/memory/test/test_support.py
b/pypy/rpython/memory/test/test_support.py
--- a/pypy/rpython/memory/test/test_support.py
+++ b/pypy/rpython/memory/test/test_support.py
@@ -1,3 +1,5 @@
+
+import random
from pypy.rlib.objectmodel import free_non_gc_object
from pypy.rpython.memory.support import get_address_stack
from pypy.rpython.memory.support import get_address_deque
@@ -94,25 +96,20 @@
assert a == addrs[i]
assert not ll.non_empty()
- def test_insert(self):
- AddressStack = get_address_stack(chunk_size=5)
- ll = AddressStack()
- lla = llarena.arena_malloc(10, 2)
- addrs = [lla + i for i in range(10)]
- ll.insert(addrs[2])
- ll.insert(addrs[1])
- ll.insert(addrs[5])
- ll.insert(addrs[4])
- ll.insert(addrs[6])
- ll.insert(addrs[9])
- ll.insert(addrs[0])
- ll.insert(addrs[8])
- ll.insert(addrs[7])
- ll.insert(addrs[3])
- expected = range(10)
- for i in expected:
- a = ll.pop()
- assert a == addrs[i]
+ def test_sort(self):
+ AddressStack = get_address_stack(chunk_size=15)
+ for _ in range(13):
+ ll = AddressStack()
+ lla = llarena.arena_malloc(10, 2)
+ addrs = [lla + i for i in range(10)]
+ random.shuffle(addrs)
+ for i in addrs:
+ ll.append(i)
+ ll.sort()
+ expected = range(10)
+ for i in expected:
+ a = ll.pop()
+ assert a == addrs[i]
class TestAddressDeque:
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
