Commits

Armin Rigo  committed e30b950

in-progress: start rewriting the builder

  • Participants
  • Parent commits 53b334a
  • Branches stringbuilder-perf

Comments (0)

Files changed (1)

File rpython/rtyper/lltypesystem/rbuilder.py

 from rpython.rlib import rgc, jit
 from rpython.rlib.objectmodel import enforceargs
 from rpython.rlib.rarithmetic import ovfcheck
+from rpython.rlib.debug import ll_assert
 from rpython.rtyper.rptr import PtrRepr
-from rpython.rtyper.lltypesystem import lltype, rstr
+from rpython.rtyper.lltypesystem import lltype, llmemory, rffi, rstr
 from rpython.rtyper.lltypesystem.lltype import staticAdtMethod, nullptr
 from rpython.rtyper.lltypesystem.rstr import (STR, UNICODE, char_repr,
     string_repr, unichar_repr, unicode_repr)
 from rpython.rtyper.rbuilder import AbstractStringBuilderRepr
 from rpython.tool.sourcetools import func_with_new_name
+from rpython.rtyper.llannotation import SomePtr
+from rpython.rlib.objectmodel import we_are_translated
+from rpython.rlib.rgc import must_be_light_finalizer
 
-# Think about heuristics below, maybe we can come up with something
-# better or at least compare it with list heuristics
-
-GROW_FAST_UNTIL = 100 * 1024 * 1024      # 100 MB
 
 def new_grow_func(name, mallocfn, copycontentsfn):
     @enforceargs(None, int)
     def stringbuilder_grow(ll_builder, needed):
+        XXX
         allocated = ll_builder.allocated
         #if allocated < GROW_FAST_UNTIL:
         #    new_allocated = allocated << 1
 unicodebuilder_grow = new_grow_func('unicodebuilder_grow', rstr.mallocunicode,
                                     rstr.copy_unicode_contents)
 
+STRINGPIECE = lltype.GcStruct('stringpiece',
+    ('raw_ptr', rffi.CCHARP),
+    ('piece_size', lltype.Signed),
+    ('prev_piece', lltype.Ptr(lltype.GcForwardReference())),
+    )
+STRINGPIECE.prev_piece.TO.become(STRINGPIECE)
+
+@must_be_light_finalizer
+def ll_destroy_string_piece(piece):
+    lltype.free(piece.raw_ptr, flavor='raw')
+
 STRINGBUILDER = lltype.GcStruct('stringbuilder',
-    ('allocated', lltype.Signed),
-    ('used', lltype.Signed),
-    ('buf', lltype.Ptr(STR)),
+    ('current_buf', lltype.Ptr(STR)),
+    ('current_ofs', lltype.Signed),
+    ('current_end', lltype.Signed),
+    ('total_size', lltype.Signed),
+    ('extra_pieces', lltype.Ptr(STRINGPIECE)),
     adtmeths={
         'grow': staticAdtMethod(stringbuilder_grow),
         'copy_raw_to_string': staticAdtMethod(rstr.copy_raw_to_string),
     }
 )
 
-MAX = 16*1024*1024
+class BaseStringBuilderRepr(AbstractStringBuilderRepr):
 
-class BaseStringBuilderRepr(AbstractStringBuilderRepr):
+    def rtyper_new(self, hop):
+        destrptr = hop.rtyper.annotate_helper_fn(
+            ll_destroy_string_piece, [SomePtr(lltype.Ptr(STRINGPIECE))])
+        lltype.attachRuntimeTypeInfo(STRINGPIECE, destrptr=destrptr)
+        return AbstractStringBuilderRepr.rtyper_new(self, hop)
+
     def empty(self):
         return nullptr(self.lowleveltype.TO)
 
     @classmethod
     def ll_new(cls, init_size):
-        if init_size < 0:
-            init_size = MAX
+        init_size = max(min(init_size, 1280), 32)
         ll_builder = lltype.malloc(cls.lowleveltype.TO)
-        ll_builder.allocated = init_size
-        ll_builder.used = 0
-        ll_builder.buf = cls.mallocfn(init_size)
+        ll_builder.current_buf = cls.mallocfn(init_size)
+        ofs = rffi.offsetof(STR, 'chars') + rffi.itemoffsetof(STR.chars, 0)
+        if not we_are_translated():
+            ofs = llmemory.raw_malloc_usage(ofs)    # for direct run
+        ll_builder.current_ofs = ofs
+        ll_builder.current_end = ofs + init_size
+        ll_builder.total_size = init_size
         return ll_builder
 
     @staticmethod
     def ll_append(ll_builder, ll_str):
-        used = ll_builder.used
         lgt = len(ll_str.chars)
-        needed = lgt + used
-        if needed > ll_builder.allocated:
-            ll_builder.grow(ll_builder, lgt)
-        ll_str.copy_contents(ll_str, ll_builder.buf, 0, used, lgt)
-        ll_builder.used = needed
+        ofs = ll_builder.current_ofs
+        newofs = ofs + lgt
+        if newofs > ll_builder.current_end:
+            ll_builder.append_overflow(ll_builder, ll_str)
+        else:
+            ll_builder.current_ofs = newofs
+            # --- no GC! ---
+            raw = rffi.cast(rffi.CCHARP, ll_builder.current_buf)
+            data_start = llmemory.cast_ptr_to_adr(ll_str) + \
+                rffi.offsetof(STR, 'chars') + rffi.itemoffsetof(STR.chars, 0)
+            rffi.c_memcpy(rffi.ptradd(raw, ofs),
+                          rffi.cast(rffi.CCHARP, data_start),
+                          lgt)
+            # --- end ---
 
     @staticmethod
     def ll_append_char(ll_builder, char):
-        if ll_builder.used == ll_builder.allocated:
+        ofs = ll_builder.current_ofs
+        if ofs == ll_builder.current_end:
             ll_builder.grow(ll_builder, 1)
-        ll_builder.buf.chars[ll_builder.used] = char
-        ll_builder.used += 1
+        # --- no GC! ---
+        raw = rffi.cast(rffi.CCHARP, ll_builder.current_buf)
+        raw[ofs] = char
+        # --- end ---
+        ll_builder.current_ofs = ofs + 1
 
     @staticmethod
     def ll_append_slice(ll_builder, ll_str, start, end):
-        needed = end - start
-        used = ll_builder.used
-        if needed + used > ll_builder.allocated:
-            ll_builder.grow(ll_builder, needed)
-        assert needed >= 0
-        ll_str.copy_contents(ll_str, ll_builder.buf, start, used, needed)
-        ll_builder.used = needed + used
+        lgt = end - start
+        ofs = ll_builder.current_ofs
+        newofs = ofs + lgt
+        if newofs > ll_builder.current_end:
+            ll_str = rstr.LLHelpers.ll_stringslice_startstop(ll_str, start, end)
+            ll_builder.append_overflow(ll_builder, ll_str)
+        else:
+            ll_builder.current_ofs = newofs
+            # --- no GC! ---
+            raw = rffi.cast(rffi.CCHARP, ll_builder.current_buf)
+            data_start = llmemory.cast_ptr_to_adr(ll_str) + \
+               rffi.offsetof(STR, 'chars') + rffi.itemoffsetof(STR.chars, start)
+            rffi.c_memcpy(rffi.ptradd(raw, ofs),
+                          rffi.cast(rffi.CCHARP, data_start),
+                          lgt)
+            # --- end ---
 
     @staticmethod
     @jit.look_inside_iff(lambda ll_builder, char, times: jit.isconstant(times) and times <= 4)
     def ll_append_multiple_char(ll_builder, char, times):
-        used = ll_builder.used
-        if times + used > ll_builder.allocated:
-            ll_builder.grow(ll_builder, times)
-        for i in range(times):
-            ll_builder.buf.chars[used] = char
-            used += 1
-        ll_builder.used = used
+        lgt = times
+        ofs = ll_builder.current_ofs
+        newofs = ofs + lgt
+        if newofs > ll_builder.current_end:
+            ll_str = rstr.LLHelpers.ll_char_mul(char, times)
+            ll_builder.append_overflow(ll_builder, ll_str)
+        else:
+            ll_builder.current_ofs = newofs
+            # --- no GC! ---
+            raw = rffi.cast(rffi.CCHARP, ll_builder.current_buf)
+            while ofs < newofs:
+                raw[ofs] = char
+                ofs += 1
+            # --- end ---
 
     @staticmethod
     def ll_append_charpsize(ll_builder, charp, size):
+        XXX
         used = ll_builder.used
         if used + size > ll_builder.allocated:
             ll_builder.grow(ll_builder, size)
 
     @staticmethod
     def ll_getlength(ll_builder):
+        XXX
         return ll_builder.used
 
     @staticmethod
     def ll_build(ll_builder):
-        final_size = ll_builder.used
-        assert final_size >= 0
-        if final_size < ll_builder.allocated:
-            ll_builder.allocated = final_size
-            ll_builder.buf = rgc.ll_shrink_array(ll_builder.buf, final_size)
-        return ll_builder.buf
+        final_size = ll_builder.total_size - (ll_builder.current_end -
+                                              ll_builder.current_ofs)
+        ll_assert(final_size >= 0, "negative final_size")
+
+        buf = ll_builder.current_buf
+        if final_size < len(buf.chars):
+            buf = rgc.ll_shrink_array(buf, final_size)
+        return buf
 
     @classmethod
     def ll_bool(cls, ll_builder):