Author: Armin Rigo <[email protected]>
Branch:
Changeset: r75895:5eb6bfa9ec8e
Date: 2015-02-15 15:49 +0100
http://bitbucket.org/pypy/pypy/changeset/5eb6bfa9ec8e/
Log: Simplify the logic in rweaklist.
diff --git a/rpython/rlib/rweaklist.py b/rpython/rlib/rweaklist.py
--- a/rpython/rlib/rweaklist.py
+++ b/rpython/rlib/rweaklist.py
@@ -1,50 +1,40 @@
import weakref
from rpython.rlib.rweakref import dead_ref
-
-def _reduced_value(s):
- while True:
- divide = s & 1
- s >>= 1
- if not divide:
- return s
+INITIAL_SIZE = 4
class RWeakListMixin(object):
_mixin_ = True
def initialize(self):
- self.handles = []
- self.look_distance = 0
+ self.handles = [dead_ref] * INITIAL_SIZE
+ self.free_list = range(INITIAL_SIZE)
def get_all_handles(self):
return self.handles
def reserve_next_handle_index(self):
- # The reservation ordering done here is tweaked for pypy's
- # memory allocator. We look from index 'look_distance'.
- # Look_distance increases from 0. But we also look at
- # "look_distance/2" or "/4" or "/8", etc. If we find that one
- # of these secondary locations is free, we assume it's because
- # there was recently a minor collection; so we reset
- # look_distance to 0 and start again from the lowest locations.
- length = len(self.handles)
- for d in range(self.look_distance, length):
- if self.handles[d]() is None:
- self.look_distance = d + 1
- return d
- s = _reduced_value(d)
- if self.handles[s]() is None:
- break
- # restart from the beginning
- for d in range(0, length):
- if self.handles[d]() is None:
- self.look_distance = d + 1
- return d
- # full! extend, but don't use '+=' here
- self.handles = self.handles + [dead_ref] * (length // 3 + 5)
- self.look_distance = length + 1
- return length
+ # (this algorithm should be amortized constant-time)
+ # get the next 'free_list' entry, if any
+ free_list = self.free_list
+ try:
+ return free_list.pop()
+ except IndexError:
+ pass
+ # slow path: collect all now-free handles in 'free_list'
+ handles = self.handles
+ for i in range(len(handles)):
+ if handles[i]() is None:
+ free_list.append(i)
+ # double the size of the self.handles list, but don't do that
+ # if there are more than 66% of handles free already
+ if len(free_list) * 3 < len(handles) * 2:
+ free_list.extend(range(len(handles), len(handles) * 2))
+ # don't use '+=' on 'self.handles'
+ self.handles = handles = handles + [dead_ref] * len(handles)
+ #
+ return free_list.pop()
def add_handle(self, content):
index = self.reserve_next_handle_index()
diff --git a/rpython/rlib/test/test_rweaklist.py
b/rpython/rlib/test/test_rweaklist.py
--- a/rpython/rlib/test/test_rweaklist.py
+++ b/rpython/rlib/test/test_rweaklist.py
@@ -1,20 +1,5 @@
import gc
-from rpython.rlib.rweaklist import RWeakListMixin, _reduced_value as
reduced_value
-
-
-def test_reduced_value():
- assert reduced_value(0) == 0
- assert reduced_value(1) == 0
- assert reduced_value(2) == 1
- assert reduced_value(3) == 0
- assert reduced_value(4) == 2
- assert reduced_value(5) == 1
- assert reduced_value(6) == 3
- assert reduced_value(7) == 0
- assert reduced_value(8) == 4
- assert reduced_value(9) == 2
- assert reduced_value(10) == 5
- assert reduced_value(11) == 1
+from rpython.rlib.rweaklist import RWeakListMixin, INITIAL_SIZE
class A(object):
@@ -25,29 +10,30 @@
a1 = A(); a2 = A()
wlist = RWeakListMixin(); wlist.initialize()
i = wlist.add_handle(a1)
- assert i == 0
+ assert i == INITIAL_SIZE - 1
i = wlist.reserve_next_handle_index()
- assert i == 1
+ assert i == INITIAL_SIZE - 2
wlist.store_handle(i, a2)
- assert wlist.fetch_handle(0) is a1
- assert wlist.fetch_handle(1) is a2
+ assert wlist.fetch_handle(INITIAL_SIZE - 1) is a1
+ assert wlist.fetch_handle(INITIAL_SIZE - 2) is a2
#
del a2
for i in range(5):
gc.collect()
- if wlist.fetch_handle(1) is None:
+ if wlist.fetch_handle(INITIAL_SIZE - 2) is None:
break
else:
- raise AssertionError("handle(1) did not disappear")
- assert wlist.fetch_handle(0) is a1
+ raise AssertionError("second handle() did not disappear")
+ assert wlist.fetch_handle(INITIAL_SIZE - 1) is a1
def test_reuse():
alist = [A() for i in range(200)]
wlist = RWeakListMixin(); wlist.initialize()
+ mapping = []
for i in range(200):
j = wlist.reserve_next_handle_index()
- assert j == i
- wlist.store_handle(i, alist[i])
+ mapping.append(j)
+ wlist.store_handle(j, alist[i])
#
del alist[1::2]
del alist[1::2]
@@ -57,8 +43,8 @@
for i in range(5):
gc.collect()
#
- for i in range(200):
- a = wlist.fetch_handle(i)
+ for i, j in enumerate(mapping):
+ a = wlist.fetch_handle(j)
if i % 32 == 0:
assert a is alist[i // 32]
else:
@@ -67,6 +53,7 @@
maximum = -1
for i in range(200):
j = wlist.reserve_next_handle_index()
+ assert wlist.fetch_handle(j) is None
maximum = max(maximum, j)
wlist.store_handle(j, A())
- assert maximum <= 240
+ assert maximum < 256
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
