Author: Armin Rigo <ar...@tunes.org>
Branch: stm
Changeset: r51633:5ab80750fca1
Date: 2012-01-22 11:17 +0100
http://bitbucket.org/pypy/pypy/changeset/5ab80750fca1/
Log: Add an explicit fifo queue implementation, instead of using
list.pop(0).
diff --git a/pypy/module/transaction/fifo.py b/pypy/module/transaction/fifo.py
new file mode 100644
--- /dev/null
+++ b/pypy/module/transaction/fifo.py
@@ -0,0 +1,34 @@
+
+class Fifo(object):
+ def __init__(self):
+ self.first = None
+ self.last = None
+
+ def append(self, newitem):
+ newitem.next = None
+ if self.last is None:
+ self.first = newitem
+ else:
+ self.last.next = newitem
+ self.last = newitem
+
+ def is_empty(self):
+ assert (self.first is None) == (self.last is None)
+ return self.first is None
+
+ def popleft(self):
+ item = self.first
+ self.first = item.next
+ if self.first is None:
+ self.last = None
+ return item
+
+ def steal(self, otherfifo):
+ if otherfifo.last is not None:
+ if self.last is None:
+ self.first = otherfifo.first
+ else:
+ self.last.next = otherfifo.first
+ self.last = otherfifo.last
+ otherfifo.first = None
+ otherfifo.last = None
diff --git a/pypy/module/transaction/interp_transaction.py
b/pypy/module/transaction/interp_transaction.py
--- a/pypy/module/transaction/interp_transaction.py
+++ b/pypy/module/transaction/interp_transaction.py
@@ -1,6 +1,7 @@
from pypy.interpreter.error import OperationError
from pypy.interpreter.gateway import unwrap_spec
from pypy.module.transaction import threadintf
+from pypy.module.transaction.fifo import Fifo
from pypy.rlib import rstm
@@ -13,7 +14,7 @@
self.__dict__.clear()
self.running = False
self.num_threads = NUM_THREADS_DEFAULT
- self.pending = []
+ self.pending = Fifo()
self.pending_lists = {0: self.pending}
self.ll_lock = threadintf.null_ll_lock
self.ll_no_tasks_pending_lock = threadintf.null_ll_lock
@@ -110,24 +111,23 @@
def add_list(new_pending_list):
- if len(new_pending_list) == 0:
+ if new_pending_list.is_empty():
return
- was_empty = len(state.pending) == 0
- state.pending += new_pending_list
- del new_pending_list[:]
+ was_empty = state.pending.is_empty()
+ state.pending.steal(new_pending_list)
if was_empty:
state.unlock_no_tasks_pending()
def _run_thread():
state.lock()
- my_pending_list = []
+ my_pending_list = Fifo()
my_thread_id = threadintf.thread_id()
state.pending_lists[my_thread_id] = my_pending_list
rstm.descriptor_init()
#
while True:
- if len(state.pending) == 0:
+ if state.pending.is_empty():
assert state.is_locked_no_tasks_pending()
state.num_waiting_threads += 1
if state.num_waiting_threads == state.num_threads:
@@ -143,8 +143,8 @@
if state.finished:
break
else:
- pending = state.pending.pop(0)
- if len(state.pending) == 0:
+ pending = state.pending.popleft()
+ if state.pending.is_empty():
state.lock_no_tasks_pending()
state.unlock()
pending.run()
@@ -164,7 +164,7 @@
state.w_error,
space.wrap("recursive invocation of transaction.run()"))
assert not state.is_locked_no_tasks_pending()
- if len(state.pending) == 0:
+ if state.pending.is_empty():
return
state.num_waiting_threads = 0
state.finished = False
@@ -177,7 +177,7 @@
state.lock_unfinished() # wait for all threads to finish
#
assert state.num_waiting_threads == 0
- assert len(state.pending) == 0
+ assert state.pending.is_empty()
assert state.pending_lists.keys() == [state.main_thread_id]
assert not state.is_locked_no_tasks_pending()
state.running = False
diff --git a/pypy/module/transaction/test/test_fifo.py
b/pypy/module/transaction/test/test_fifo.py
new file mode 100644
--- /dev/null
+++ b/pypy/module/transaction/test/test_fifo.py
@@ -0,0 +1,40 @@
+from pypy.module.transaction.fifo import Fifo
+
+class Item:
+ def __init__(self, value):
+ self.value = value
+
+def test_one_item():
+ f = Fifo()
+ assert f.is_empty()
+ f.append(Item(123))
+ assert not f.is_empty()
+ item = f.popleft()
+ assert f.is_empty()
+ assert item.value == 123
+
+def test_three_items():
+ f = Fifo()
+ for i in [10, 20, 30]:
+ f.append(Item(i))
+ assert not f.is_empty()
+ for i in [10, 20, 30]:
+ assert not f.is_empty()
+ item = f.popleft()
+ assert item.value == i
+ assert f.is_empty()
+
+def test_steal():
+ for n1 in range(3):
+ for n2 in range(3):
+ f1 = Fifo()
+ f2 = Fifo()
+ for i in range(n1): f1.append(Item(10 + i))
+ for i in range(n2): f2.append(Item(20 + i))
+ f1.steal(f2)
+ assert f2.is_empty()
+ for x in range(10, 10+n1) + range(20, 20+n2):
+ assert not f1.is_empty()
+ item = f1.popleft()
+ assert item.value == x
+ assert f1.is_empty()
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
