Maciej Fijalkowski avatar Maciej Fijalkowski committed aee0aac

Pass the first direct test. Right now both ll_getitem_fast and ll_setitem_fast
would check for boundaries. To be changed in future I believe

Comments (0)

Files changed (4)

pypy/rpython/lltypesystem/lltype.py

 from pypy.rlib.rarithmetic import (r_int, r_uint, intmask, r_singlefloat,
                                    r_ulonglong, r_longlong, base_int,
                                    normalizedinttype)
-from pypy.rlib.objectmodel import Symbolic
+from pypy.rlib.objectmodel import Symbolic, specialize
 from pypy.tool.uid import Hashable
 from pypy.tool.tls import tlsobject
 from pypy.lib.identity_dict import identity_dict
     _gckind = 'raw'
     __name__ = 'array'
     _anonym_struct = False
-    
+
     def __init__(self, *fields, **kwds):
         if len(fields) == 1 and isinstance(fields[0], LowLevelType):
             self.OF = fields[0]
     def _inline_is_varsize(self, last):
         raise TypeError("cannot inline a GC array inside a structure")
 
+@specialize.memo()
+def new_gc_array(arg):
+    return GcArray(arg)
 
 class FixedSizeArray(Struct):
     # behaves more or less like a Struct with fields item0, item1, ...

pypy/rpython/lltypesystem/rlist.py

      GcForwardReference, Ptr, GcArray, GcStruct, \
      Void, Signed, malloc, typeOf, Primitive, \
      Bool, nullptr, typeMethod
-from pypy.rpython.lltypesystem import rstr
+from pypy.rpython.lltypesystem import rstr, lltype
 from pypy.rpython import robject
 from pypy.rlib.debug import ll_assert
 from pypy.rlib.rarithmetic import ovfcheck
 from pypy.rpython.lltypesystem.lloperation import llop
 from pypy.rlib import rgc
 
+MIN_CHUNKED_SIZE = 32*1024 # should be somehow correlated with size of GC
+# structure that gets allocated using raw_malloc in the hybrid gc
+CHUNK_SIZE = MIN_CHUNKED_SIZE
+
 # ____________________________________________________________
 #
 #  Concrete implementation of RPython lists:
                                           "ll_newemptylist": ll_newemptylist,
                                           "ll_length": ll_length,
                                           "ll_items": ll_items,
+                                          'll_chunks': ll_chunks,
                                           "ITEM": ITEM,
                                           "ll_getitem_fast": ll_getitem_fast,
                                           "ll_setitem_fast": ll_setitem_fast,
             new_allocated = ovfcheck(newsize + some)
         except OverflowError:
             raise MemoryError
-    # XXX consider to have a real realloc
     # new_allocated is a bit more than newsize, enough to ensure an amortized
     # linear complexity for e.g. repeated usage of l.append().
     items = l.items
-    newitems = malloc(typeOf(l).TO.items.TO, new_allocated)
+    ARRAYTP = typeOf(l).TO.items.TO
     before_len = l.length
     if before_len:   # avoids copying GC flags from the prebuilt_empty_array
         if before_len < newsize:
             p = before_len
         else:
             p = newsize
-        rgc.ll_arraycopy(items, newitems, 0, 0, p)
+    else:
+        p = 0
+    if new_allocated > MIN_CHUNKED_SIZE:
+        newarr = malloc(lltype.new_gc_array(lltype.Ptr(ARRAYTP)),
+                        (new_allocated / CHUNK_SIZE) + 1)
+        if before_len <= MIN_CHUNKED_SIZE:
+            # copy unchunked list -> chunked list, always grow
+            i = 0
+            start = 0
+            while i < (new_allocated / CHUNK_SIZE) + 1:
+                newarr[i] = malloc(ARRAYTP, CHUNK_SIZE)
+                if start < before_len:
+                    size = CHUNK_SIZE
+                    if start + size > before_len:
+                        size = before_len - start
+                    rgc.ll_arraycopy(items, newarr[i], start, 0, size)
+                start += CHUNK_SIZE
+                i += 1
+        else:
+            # copy chunked list -> larger chunked list
+            raise NotImplementedError
+        l.length = newsize
+        l.items = rffi.cast(lltype.Ptr(ARRAYTP), newarr)
+    else:
+        if before_len > MIN_CHUNKED_SIZE:
+            # copy chunked list -> unchunked list
+            raise NotImplementedError
+        newitems = malloc(ARRAYTP, new_allocated)
+        if p:
+            rgc.ll_arraycopy(items, newitems, 0, 0, p)
+        l.items = newitems
     l.length = newsize
-    l.items = newitems
 _ll_list_resize_really._annenforceargs_ = (None, int)
 
 # this common case was factored out of _ll_list_resize
 def ll_items(l):
     return l.items
 
+def ll_chunks(l):
+    ARRAYTP = lltype.typeOf(l).TO.items
+    return rffi.cast(Ptr(lltype.new_gc_array(ARRAYTP)), l.items)
+
 def ll_getitem_fast(l, index):
-    if l.length == 0:
-        raise IndexError
     ll_assert(index < l.length, "getitem out of bounds")
+    if l.length > MIN_CHUNKED_SIZE:
+        return l.ll_chunks()[index / CHUNK_SIZE][index % CHUNK_SIZE]
     return l.ll_items()[index]
 ll_getitem_fast.oopspec = 'list.getitem(l, index)'
 
 def ll_setitem_fast(l, index, item):
     ll_assert(index < l.length, "setitem out of bounds")
-    l.ll_items()[index] = item
+    if l.length > MIN_CHUNKED_SIZE:
+        l.ll_chunks()[index / CHUNK_SIZE][index % CHUNK_SIZE] = item
+    else:
+        l.ll_items()[index] = item
 ll_setitem_fast.oopspec = 'list.setitem(l, index, item)'
 
 # fixed size versions

pypy/rpython/lltypesystem/test/test_rlist.py

 
 from pypy.rpython.lltypesystem import rlist as ll_rlist
 from pypy.rpython.rlist import ADTIList
-from pypy.rpython.lltypesystem import lltype
-from pypy.rpython.lltypesystem.lltype import GcStruct, Signed, Ptr
+from pypy.rpython.lltypesystem import lltype, rffi
+from pypy.rpython.lltypesystem.lltype import GcStruct, Signed, Ptr, GcArray
 
 class TestRListDirect(object):
     def setup_class(cls):
                                   "ll_newemptylist": ll_rlist.ll_newemptylist,
                                   "ll_length": ll_rlist.ll_length,
                                   "ll_items": ll_rlist.ll_items,
+                                  "ll_chunks": ll_rlist.ll_chunks,
                                   "ITEM": ITEM,
                                   "ll_getitem_fast": ll_rlist.ll_getitem_fast,
                                   "ll_setitem_fast": ll_rlist.ll_setitem_fast,
         ll_rlist.CHUNK_SIZE = cls.CHUNK_SIZE
     
     def test_resize_unchunked_chunked(self):
-        l = self.LISTTP.ll_newlist(self.CHUNK_SIZE - 3)
+        l = self.LISTTP.ll_newlist(ll_rlist.MIN_CHUNKED_SIZE - 3)
+        for i in range(l.length):
+            l.ll_setitem_fast(i, i)
+        l._ll_resize(ll_rlist.MIN_CHUNKED_SIZE + 10)
+        for i in range(ll_rlist.MIN_CHUNKED_SIZE - 3,
+                       ll_rlist.MIN_CHUNKED_SIZE + 10):
+            l.ll_setitem_fast(i, 10*i)
+        # this should resize above the chunked threshold
+        CHUNK_TP = Ptr(GcArray(Ptr(GcArray(Signed))))
+        chunked_items = rffi.cast(CHUNK_TP, l.items)
+        CHUNK_SIZE = ll_rlist.CHUNK_SIZE
+        assert chunked_items[0][10] == 10
+        assert chunked_items[0][CHUNK_SIZE - 1] == (CHUNK_SIZE - 1) * 10
+        assert chunked_items[1][0] == CHUNK_SIZE * 10
+        assert chunked_items[1][9] == (CHUNK_SIZE + 9) * 10

pypy/rpython/test/test_rlist.py

         assert func1.oopspec == 'list.getitem_foldable(l, index)'
         assert func2.oopspec == 'list.getitem(l, index)'
 
+class TestLLtypeChunkedList(BaseRtypingTest, LLRtypeMixin):
+    def setup_class(cls):
+        cls.MIN_CHUNKED_SIZE = ll_rlist.MIN_CHUNKED_SIZE
+        cls.CHUNK_SIZE = ll_rlist.CHUNK_SIZE
+        ll_rlist.MIN_CHUNKED_SIZE = 100
+        ll_rlist.CHUNK_SIZE = 100
+
+    def teardown_class(cls):
+        ll_rlist.MIN_CHUNKED_SIZE = cls.MIN_CHUNKED_SIZE
+        ll_rlist.CHUNK_SIZE = cls.CHUNK_SIZE
+            
+    def test_big_getitem(self):
+        def f(i):
+            l = [0] * (ll_rlist.MIN_CHUNKED_SIZE - 3)
+            for k in range(10):
+                l.append(i)
+            return l[-1]
+
+        res = self.interpret(f, [38])
+        assert res == 38
+
 class TestOOtype(BaseTestRlist, OORtypeMixin):
     rlist = oo_rlist
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.