Author: Carl Friedrich Bolz <cfb...@gmx.de>
Branch:
Changeset: r62910:b2356b60368c
Date: 2013-04-01 09:11 +0200
http://bitbucket.org/pypy/pypy/changeset/b2356b60368c/
Log: kill the _bisect accelerator module. the JIT makes the Python
version faster than the RPython version, because it can specialize
on the content of the lists
diff --git a/pypy/module/_bisect/__init__.py b/pypy/module/_bisect/__init__.py
deleted file mode 100644
--- a/pypy/module/_bisect/__init__.py
+++ /dev/null
@@ -1,27 +0,0 @@
-"""
-Mixed-module definition for the _bisect module.
-This is an optional module; if not present, bisect.py uses the
-pure Python version of these functions.
-"""
-
-from pypy.interpreter.mixedmodule import MixedModule
-
-
-class Module(MixedModule):
- """\
-This module provides support for maintaining a list in sorted order without
-having to sort the list after each insertion. For long lists of items with
-expensive comparison operations, this can be an improvement over the more
-common approach."""
-
- appleveldefs = {
- 'insort': 'app_bisect.insort_right',
- 'insort_left': 'app_bisect.insort_left',
- 'insort_right': 'app_bisect.insort_right',
- }
-
- interpleveldefs = {
- 'bisect': 'interp_bisect.bisect_right',
- 'bisect_left': 'interp_bisect.bisect_left',
- 'bisect_right': 'interp_bisect.bisect_right',
- }
diff --git a/pypy/module/_bisect/app_bisect.py
b/pypy/module/_bisect/app_bisect.py
deleted file mode 100644
--- a/pypy/module/_bisect/app_bisect.py
+++ /dev/null
@@ -1,23 +0,0 @@
-from _bisect import bisect_left, bisect_right
-
-
-def insort_left(a, x, lo=0, hi=-1):
- """Insert item x in list a, and keep it sorted assuming a is sorted.
-
-If x is already in a, insert it to the left of the leftmost x.
-
-Optional args lo (default 0) and hi (default len(a)) bound the
-slice of a to be searched."""
- n = bisect_left(a, x, lo, hi)
- a.insert(n, x)
-
-
-def insort_right(a, x, lo=0, hi=-1):
- """Insert item x in list a, and keep it sorted assuming a is sorted.
-
-If x is already in a, insert it to the right of the rightmost x.
-
-Optional args lo (default 0) and hi (default len(a)) bound the
-slice of a to be searched."""
- n = bisect_right(a, x, lo, hi)
- a.insert(n, x)
diff --git a/pypy/module/_bisect/interp_bisect.py
b/pypy/module/_bisect/interp_bisect.py
deleted file mode 100644
--- a/pypy/module/_bisect/interp_bisect.py
+++ /dev/null
@@ -1,53 +0,0 @@
-from pypy.interpreter.error import OperationError
-from pypy.interpreter.gateway import unwrap_spec
-from rpython.rlib.rarithmetic import intmask, r_uint
-
-
-@unwrap_spec(lo=int, hi=int)
-def bisect_left(space, w_a, w_x, lo=0, hi=-1):
- """Return the index where to insert item x in list a, assuming a is sorted.
-
-The return value i is such that all e in a[:i] have e < x, and all e in
-a[i:] have e >= x. So if x already appears in the list, i points just
-before the leftmost x already there.
-
-Optional args lo (default 0) and hi (default len(a)) bound the
-slice of a to be searched."""
- if lo < 0:
- raise OperationError(space.w_ValueError,
- space.wrap("lo must be non-negative"))
- if hi == -1:
- hi = space.len_w(w_a)
- while lo < hi:
- mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
- w_litem = space.getitem(w_a, space.wrap(mid))
- if space.is_true(space.lt(w_litem, w_x)):
- lo = mid + 1
- else:
- hi = mid
- return space.wrap(lo)
-
-
-@unwrap_spec(lo=int, hi=int)
-def bisect_right(space, w_a, w_x, lo=0, hi=-1):
- """Return the index where to insert item x in list a, assuming a is sorted.
-
-The return value i is such that all e in a[:i] have e <= x, and all e in
-a[i:] have e > x. So if x already appears in the list, i points just
-beyond the rightmost x already there
-
-Optional args lo (default 0) and hi (default len(a)) bound the
-slice of a to be searched."""
- if lo < 0:
- raise OperationError(space.w_ValueError,
- space.wrap("lo must be non-negative"))
- if hi == -1:
- hi = space.len_w(w_a)
- while lo < hi:
- mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
- w_litem = space.getitem(w_a, space.wrap(mid))
- if space.is_true(space.lt(w_x, w_litem)):
- hi = mid
- else:
- lo = mid + 1
- return space.wrap(lo)
diff --git a/pypy/module/_bisect/test/__init__.py
b/pypy/module/_bisect/test/__init__.py
deleted file mode 100644
diff --git a/pypy/module/_bisect/test/test_bisect.py
b/pypy/module/_bisect/test/test_bisect.py
deleted file mode 100644
--- a/pypy/module/_bisect/test/test_bisect.py
+++ /dev/null
@@ -1,100 +0,0 @@
-
-class AppTestBisect:
- spaceconfig = dict(usemodules=['_bisect'])
-
- def test_bisect_left(self):
- from _bisect import bisect_left
- a = [0, 5, 6, 6, 6, 7]
- assert bisect_left(a, None) == 0
- assert bisect_left(a, -3) == 0
- assert bisect_left(a, 0) == 0
- assert bisect_left(a, 3) == 1
- assert bisect_left(a, 5) == 1
- assert bisect_left(a, 5.5) == 2
- assert bisect_left(a, 6) == 2
- assert bisect_left(a, 6.0) == 2
- assert bisect_left(a, 6.1) == 5
- assert bisect_left(a, 7) == 5
- assert bisect_left(a, 8) == 6
- a = []
- assert bisect_left(a, 123) == 0
- a = [9]
- assert bisect_left(a, -123) == 0
- assert bisect_left(a, 9) == 0
- assert bisect_left(a, 123) == 1
- a = [9, 9]
- assert bisect_left(a, -123) == 0
- assert bisect_left(a, 9) == 0
- assert bisect_left(a, 123) == 2
- a = [4, 6, 6, 9]
- assert bisect_left(a, 6, 0) == 1
- assert bisect_left(a, 6, 1) == 1
- assert bisect_left(a, 6, 2) == 2
- assert bisect_left(a, 6, 3) == 3
- assert bisect_left(a, 6, 4) == 4
- assert bisect_left(a, 6, 0, 0) == 0
- assert bisect_left(a, 6, 0, 1) == 1
- assert bisect_left(a, 6, 0, 2) == 1
- assert bisect_left(a, 6, 0, 3) == 1
- assert bisect_left(a, 6, 0, 4) == 1
-
- raises(ValueError, bisect_left, [1, 2, 3], 5, -1, 3)
-
- def test_bisect_right(self):
- from _bisect import bisect_right
- a = [0, 5, 6, 6, 6, 7]
- assert bisect_right(a, None) == 0
- assert bisect_right(a, -3) == 0
- assert bisect_right(a, 0) == 1
- assert bisect_right(a, 3) == 1
- assert bisect_right(a, 5) == 2
- assert bisect_right(a, 5.5) == 2
- assert bisect_right(a, 6) == 5
- assert bisect_right(a, 6.0) == 5
- assert bisect_right(a, 6.1) == 5
- assert bisect_right(a, 7) == 6
- assert bisect_right(a, 8) == 6
- a = []
- assert bisect_right(a, 123) == 0
- a = [9]
- assert bisect_right(a, -123) == 0
- assert bisect_right(a, 9) == 1
- assert bisect_right(a, 123) == 1
- a = [9, 9]
- assert bisect_right(a, -123) == 0
- assert bisect_right(a, 9) == 2
- assert bisect_right(a, 123) == 2
- a = [4, 6, 6, 9]
- assert bisect_right(a, 6, 0) == 3
- assert bisect_right(a, 6, 1) == 3
- assert bisect_right(a, 6, 2) == 3
- assert bisect_right(a, 6, 3) == 3
- assert bisect_right(a, 6, 4) == 4
- assert bisect_right(a, 6, 0, 0) == 0
- assert bisect_right(a, 6, 0, 1) == 1
- assert bisect_right(a, 6, 0, 2) == 2
- assert bisect_right(a, 6, 0, 3) == 3
- assert bisect_right(a, 6, 0, 4) == 3
-
- def test_insort_left(self):
- from _bisect import insort_left
- a = [0, 5, 6, 6, 6, 7]
- insort_left(a, 6.0)
- assert a == [0, 5, 6.0, 6, 6, 6, 7]
- assert map(type, a) == [int, int, float, int, int, int, int]
-
- def test_insort_right(self):
- from _bisect import insort_right
- a = [0, 5, 6, 6, 6, 7]
- insort_right(a, 6.0)
- assert a == [0, 5, 6, 6, 6, 6.0, 7]
- assert map(type, a) == [int, int, int, int, int, float, int]
-
- def test_bisect_overflow(self):
- from _bisect import bisect_left, bisect_right
- import sys
-
- size = sys.maxsize
- data = xrange(size - 1)
- assert bisect_left(data, size - 3) == size - 3
- assert bisect_right(data, size - 3) == size - 2
diff --git a/pypy/module/_bisect/test/test_ztranslation.py
b/pypy/module/_bisect/test/test_ztranslation.py
deleted file mode 100644
--- a/pypy/module/_bisect/test/test_ztranslation.py
+++ /dev/null
@@ -1,4 +0,0 @@
-from pypy.objspace.fake.checkmodule import checkmodule
-
-def test_checkmodule():
- checkmodule('_bisect')
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
