Commits

Armin Rigo committed 69b168a

Issue1599: quadratic time in list.extend(sometuple): test and fix

  • Participants
  • Parent commits a78e297

Comments (0)

Files changed (3)

File rpython/rtyper/lltypesystem/rlist.py

     """
     assert newsize >= 0, "negative list length"
     allocated = len(l.items)
-    if allocated < newsize or newsize < (allocated >> 1) - 5:
-        _ll_list_resize_hint_really(l, newsize, False)
+    if newsize > allocated:
+        overallocate = True
+    elif newsize < (allocated >> 1) - 5:
+        overallocate = False
+    else:
+        return
+    _ll_list_resize_hint_really(l, newsize, overallocate)
 
 @signature(types.any(), types.int(), types.bool(), returns=types.none())
 def _ll_list_resize_really(l, newsize, overallocate):
     with the realloc() to shrink the list.
     """
     cond = newsize < (len(l.items) >> 1) - 5
+    # note: overallocate=False should be safe here
     if jit.isconstant(len(l.items)) and jit.isconstant(newsize):
         if cond:
             _ll_list_resize_hint_really(l, newsize, False)

File rpython/rtyper/rlist.py

 ADTIList = ADTInterface(ADTIFixedList, {
     # grow the length if needed, overallocating a bit
     '_ll_resize_ge':   (['self', Signed        ], Void),
-    # shrink the length, keeping it overallocated if useful
+    # shrink the length; if reallocating, don't keep any overallocation
     '_ll_resize_le':   (['self', Signed        ], Void),
-    # resize to exactly the given size
+    # resize to exactly the given size; no overallocation
     '_ll_resize':      (['self', Signed        ], Void),
-    # realloc the underlying list
+    # give a hint about the size; does overallocation if growing
     '_ll_resize_hint': (['self', Signed        ], Void),
 })
 

File rpython/rtyper/test/test_rlist.py

             assert res == sum(map(ord, 'abcdef'))
         finally:
             rlist.ll_getitem_foldable_nonneg = prev
+
+    def test_extend_was_not_overallocating(self):
+        from rpython.rlib import rgc
+        from rpython.rlib.objectmodel import resizelist_hint
+        from rpython.rtyper.lltypesystem import lltype
+        old_arraycopy = rgc.ll_arraycopy
+        try:
+            GLOB = lltype.GcStruct('GLOB', ('seen', lltype.Signed))
+            glob = lltype.malloc(GLOB, immortal=True)
+            glob.seen = 0
+            def my_arraycopy(*args):
+                glob.seen += 1
+                return old_arraycopy(*args)
+            rgc.ll_arraycopy = my_arraycopy
+            def dummyfn():
+                lst = []
+                i = 0
+                while i < 30:
+                    i += 1
+                    resizelist_hint(lst, i)
+                    lst.append(i)
+                return glob.seen
+            res = self.interpret(dummyfn, [])
+        finally:
+            rgc.ll_arraycopy = old_arraycopy
+        #
+        assert 2 <= res <= 10