[pypy-commit] pypy py3.7-tracemalloc: Expose tracemalloc C API

[Stian Andreassen]

Author: Stian Andreassen
Branch: py3.7-tracemalloc
Changeset: r98262:c31bb71da53e
Date: 2019-12-09 17:09 +0100
http://bitbucket.org/pypy/pypy/changeset/c31bb71da53e/

Log:Expose tracemalloc C API

diff --git a/pypy/module/cpyext/api.py b/pypy/module/cpyext/api.py
--- a/pypy/module/cpyext/api.py
+++ b/pypy/module/cpyext/api.py
@@ -655,7 +655,7 @@
 'PyMem_RawMalloc', 'PyMem_RawCalloc', 'PyMem_RawRealloc', 'PyMem_RawFree',
 'PyMem_Malloc', 'PyMem_Calloc', 'PyMem_Realloc', 'PyMem_Free',
 'PyObject_CallFinalizerFromDealloc',
-'_PyTraceMalloc_Track', '_PyTraceMalloc_Untrack',
+'PyTraceMalloc_Track', 'PyTraceMalloc_Untrack',
 'PyBytes_FromFormat', 'PyBytes_FromFormatV',
 
 'PyType_FromSpec',
diff --git a/pypy/module/cpyext/include/pymem.h 
b/pypy/module/cpyext/include/pymem.h
--- a/pypy/module/cpyext/include/pymem.h
+++ b/pypy/module/cpyext/include/pymem.h
@@ -61,9 +61,9 @@
 #define PyMem_DEL   PyMem_FREE
 
 
-/* From CPython 3.6, with a different goal.  _PyTraceMalloc_Track()
+/* From CPython 3.6, with a different goal.  PyTraceMalloc_Track()
  * is equivalent to __pypy__.add_memory_pressure(size); it works with
- * or without the GIL.  _PyTraceMalloc_Untrack() is an empty stub.
+ * or without the GIL.  PyTraceMalloc_Untrack() is an empty stub.
  * You can check if these functions are available by using:
  *
  *#if defined(PYPY_TRACEMALLOC) || \
@@ -71,11 +71,9 @@
  */
 #define PYPY_TRACEMALLOC1
 
-typedef unsigned int _PyTraceMalloc_domain_t;
-
-PyAPI_FUNC(int) _PyTraceMalloc_Track(_PyTraceMalloc_domain_t domain,
+PyAPI_FUNC(int) PyTraceMalloc_Track(unsigned int domain,
  uintptr_t ptr, size_t size);
-PyAPI_FUNC(int) _PyTraceMalloc_Untrack(_PyTraceMalloc_domain_t domain,
+PyAPI_FUNC(int) PyTraceMalloc_Untrack(unsigned int domain,
uintptr_t ptr);
 
 
diff --git a/pypy/module/cpyext/src/pymem.c b/pypy/module/cpyext/src/pymem.c
--- a/pypy/module/cpyext/src/pymem.c
+++ b/pypy/module/cpyext/src/pymem.c
@@ -94,7 +94,7 @@
 free(ptr);
 }
 
-int _PyTraceMalloc_Track(_PyTraceMalloc_domain_t domain,
+int PyTraceMalloc_Track(unsigned int domain,
  uintptr_t ptr, size_t size)
 {
 /* to avoid acquiring/releasing the GIL too often, only do it
@@ -133,7 +133,7 @@
 /* Should we return -2 or 0?  In theory it should be -2, because
we're not using the info to really track the allocations.
But I'm sure someone is too clever somewhere and stops calling
-   _PyTraceMalloc_Track() if it returns -2.  On the other hand,
+   PyTraceMalloc_Track() if it returns -2.  On the other hand,
returning 0 might lead to expectations that importing
'tracemalloc' works on Python 3.  Oh well, in that case we'll
just crash with ImportError during 'import tracemalloc'.
@@ -141,7 +141,7 @@
 return 0;
 }
 
-int _PyTraceMalloc_Untrack(_PyTraceMalloc_domain_t domain,
+int PyTraceMalloc_Untrack(unsigned int domain,
uintptr_t ptr)
 {
 /* nothing to do */
diff --git a/pypy/module/cpyext/test/test_object.py 
b/pypy/module/cpyext/test/test_object.py
--- a/pypy/module/cpyext/test/test_object.py
+++ b/pypy/module/cpyext/test/test_object.py
@@ -391,7 +391,7 @@
 module = self.import_extension('foo', [
 ("foo", "METH_O",
 """
-_PyTraceMalloc_Track(0, 0, PyLong_AsLong(args) - sizeof(long));
+PyTraceMalloc_Track(0, 0, PyLong_AsLong(args) - sizeof(long));
 Py_INCREF(Py_None);
 return Py_None;
 """)])
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: The test for my previous commit

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r98131:f49f7df7c633
Date: 2019-11-21 18:15 +0100
http://bitbucket.org/pypy/pypy/changeset/f49f7df7c633/

Log:The test for my previous commit

diff --git a/pypy/module/cpyext/test/test_pyerrors.py 
b/pypy/module/cpyext/test/test_pyerrors.py
--- a/pypy/module/cpyext/test/test_pyerrors.py
+++ b/pypy/module/cpyext/test/test_pyerrors.py
@@ -3,6 +3,7 @@
 import StringIO
 
 from pypy.module.cpyext.state import State
+from pypy.module.cpyext.pyobject import make_ref
 from pypy.module.cpyext.test.test_api import BaseApiTest
 from pypy.module.cpyext.test.test_cpyext import AppTestCpythonExtensionBase
 from rpython.rtyper.lltypesystem import rffi
@@ -108,6 +109,30 @@
 assert recieved == ['ok']
 assert api.PyOS_InterruptOccurred()
 
+def test_restore_traceback(self, space, api):
+string = rffi.str2charp("spam and eggs")
+api.PyErr_SetString(space.w_ValueError, string)
+
+state = space.fromcache(State)
+operror = state.clear_exception()
+
+# Fake a traceback.
+operror.set_traceback(space.w_True) # this doesn't really need to be a 
real traceback for this test.
+
+w_type = operror.w_type
+w_value = operror.get_w_value(space)
+w_tb = operror.get_w_traceback(space)
+
+assert not space.eq_w(w_tb, space.w_None)
+
+api.PyErr_Restore(make_ref(space, w_type), make_ref(space, w_value), 
make_ref(space, w_tb))
+
+operror = state.clear_exception()
+w_tb_restored = operror.get_w_traceback(space)
+
+assert space.eq_w(w_tb_restored, w_tb)
+rffi.free_charp(string)
+
 class AppTestFetch(AppTestCpythonExtensionBase):
 
 def test_occurred(self):
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Remove the XXX about w_traceback

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r98129:2916cb12db62
Date: 2019-11-21 16:31 +0100
http://bitbucket.org/pypy/pypy/changeset/2916cb12db62/

Log:Remove the XXX about w_traceback

diff --git a/pypy/module/cpyext/pyerrors.py b/pypy/module/cpyext/pyerrors.py
--- a/pypy/module/cpyext/pyerrors.py
+++ b/pypy/module/cpyext/pyerrors.py
@@ -84,7 +84,7 @@
 w_type = get_w_obj_and_decref(space, py_type)
 w_value = get_w_obj_and_decref(space, py_value)
 w_traceback = get_w_obj_and_decref(space, py_traceback)
-# XXX do something with w_traceback
+
 if w_type is None:
 state.clear_exception()
 return
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Fix issue #3120, do restore traceback in PyErr_Restore.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r98125:3b12b6935197
Date: 2019-11-21 15:46 +0100
http://bitbucket.org/pypy/pypy/changeset/3b12b6935197/

Log:Fix issue #3120, do restore traceback in PyErr_Restore.

diff --git a/pypy/module/cpyext/pyerrors.py b/pypy/module/cpyext/pyerrors.py
--- a/pypy/module/cpyext/pyerrors.py
+++ b/pypy/module/cpyext/pyerrors.py
@@ -88,7 +88,7 @@
 if w_type is None:
 state.clear_exception()
 return
-state.set_exception(OperationError(w_type, w_value))
+state.set_exception(OperationError(w_type, w_value, w_traceback))
 
 @cpython_api([PyObjectP, PyObjectP, PyObjectP], lltype.Void)
 def PyErr_NormalizeException(space, exc_p, val_p, tb_p):
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: ~1% speedup to GCD.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r96962:f138227813b8
Date: 2019-07-10 22:41 +0200
http://bitbucket.org/pypy/pypy/changeset/f138227813b8/

Log:~1% speedup to GCD.

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -3013,7 +3013,7 @@
 a, b = b, a
 
 while b.size > 1:
-a_ms = a.digit(a.size-1)
+a_ms = a.digit(abs(a.size-1))
 
 x = 0
 while a_ms & (0xFF << SHIFT-8) == 0:
@@ -3024,12 +3024,12 @@
 a_ms <<= 1
 x += 1
 
-a_ms |= a.digit(a.size-2) >> SHIFT-x
+a_ms |= a.digit(abs(a.size-2)) >> SHIFT-x
 
 if a.size == b.size:
-b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x)
+b_ms = (b.digit(abs(b.size-1)) << x) | (b.digit(abs(b.size-2)) >> 
SHIFT-x)
 elif a.size == b.size+1:
-b_ms = b.digit(b.size-1) >> SHIFT-x
+b_ms = b.digit(abs(b.size-1)) >> SHIFT-x
 else:
 b_ms = 0
 
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy py3.6: ~1% speedup to GCD.

[Stian Andreassen]

Author: Stian Andreassen
Branch: py3.6
Changeset: r96961:ab71ab09aca2
Date: 2019-07-10 22:41 +0200
http://bitbucket.org/pypy/pypy/changeset/ab71ab09aca2/

Log:~1% speedup to GCD.

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -3013,7 +3013,7 @@
 a, b = b, a
 
 while b.size > 1:
-a_ms = a.digit(a.size-1)
+a_ms = a.digit(abs(a.size-1))
 
 x = 0
 while a_ms & (0xFF << SHIFT-8) == 0:
@@ -3024,12 +3024,12 @@
 a_ms <<= 1
 x += 1
 
-a_ms |= a.digit(a.size-2) >> SHIFT-x
+a_ms |= a.digit(abs(a.size-2)) >> SHIFT-x
 
 if a.size == b.size:
-b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x)
+b_ms = (b.digit(abs(b.size-1)) << x) | (b.digit(abs(b.size-2)) >> 
SHIFT-x)
 elif a.size == b.size+1:
-b_ms = b.digit(b.size-1) >> SHIFT-x
+b_ms = b.digit(abs(b.size-1)) >> SHIFT-x
 else:
 b_ms = 0
 
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy math-improvements: merge heads

[Stian Andreassen]

Author: Stian Andreassen
Branch: math-improvements
Changeset: r95498:a344a7cb2d95
Date: 2018-12-15 03:59 +0100
http://bitbucket.org/pypy/pypy/changeset/a344a7cb2d95/

Log:merge heads

diff too long, truncating to 2000 out of 3510 lines

diff --git a/extra_tests/__init__.py b/extra_tests/__init__.py
new file mode 100644
diff --git a/pypy/module/test_lib_pypy/cffi_tests/__init__.py 
b/extra_tests/cffi_tests/__init__.py
rename from pypy/module/test_lib_pypy/cffi_tests/__init__.py
rename to extra_tests/cffi_tests/__init__.py
diff --git a/pypy/module/test_lib_pypy/cffi_tests/cffi0/__init__.py 
b/extra_tests/cffi_tests/cffi0/__init__.py
rename from pypy/module/test_lib_pypy/cffi_tests/cffi0/__init__.py
rename to extra_tests/cffi_tests/cffi0/__init__.py
diff --git a/pypy/module/test_lib_pypy/cffi_tests/cffi0/backend_tests.py 
b/extra_tests/cffi_tests/cffi0/backend_tests.py
rename from pypy/module/test_lib_pypy/cffi_tests/cffi0/backend_tests.py
rename to extra_tests/cffi_tests/cffi0/backend_tests.py
--- a/pypy/module/test_lib_pypy/cffi_tests/cffi0/backend_tests.py
+++ b/extra_tests/cffi_tests/cffi0/backend_tests.py
@@ -3,7 +3,7 @@
 import platform
 import sys, ctypes
 from cffi import FFI, CDefError, FFIError, VerificationMissing
-from pypy.module.test_lib_pypy.cffi_tests.support import *
+from extra_tests.cffi_tests.support import *
 
 SIZE_OF_INT   = ctypes.sizeof(ctypes.c_int)
 SIZE_OF_LONG  = ctypes.sizeof(ctypes.c_long)
diff --git a/pypy/module/test_lib_pypy/cffi_tests/cffi0/callback_in_thread.py 
b/extra_tests/cffi_tests/cffi0/callback_in_thread.py
rename from pypy/module/test_lib_pypy/cffi_tests/cffi0/callback_in_thread.py
rename to extra_tests/cffi_tests/cffi0/callback_in_thread.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_module/setup.py 
b/extra_tests/cffi_tests/cffi0/snippets/distutils_module/setup.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_module/setup.py
rename to extra_tests/cffi_tests/cffi0/snippets/distutils_module/setup.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_module/snip_basic_verify.py
 b/extra_tests/cffi_tests/cffi0/snippets/distutils_module/snip_basic_verify.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_module/snip_basic_verify.py
rename to 
extra_tests/cffi_tests/cffi0/snippets/distutils_module/snip_basic_verify.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_1/setup.py
 b/extra_tests/cffi_tests/cffi0/snippets/distutils_package_1/setup.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_1/setup.py
rename to extra_tests/cffi_tests/cffi0/snippets/distutils_package_1/setup.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_1/snip_basic_verify1/__init__.py
 
b/extra_tests/cffi_tests/cffi0/snippets/distutils_package_1/snip_basic_verify1/__init__.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_1/snip_basic_verify1/__init__.py
rename to 
extra_tests/cffi_tests/cffi0/snippets/distutils_package_1/snip_basic_verify1/__init__.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_2/setup.py
 b/extra_tests/cffi_tests/cffi0/snippets/distutils_package_2/setup.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_2/setup.py
rename to extra_tests/cffi_tests/cffi0/snippets/distutils_package_2/setup.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_2/snip_basic_verify2/__init__.py
 
b/extra_tests/cffi_tests/cffi0/snippets/distutils_package_2/snip_basic_verify2/__init__.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/distutils_package_2/snip_basic_verify2/__init__.py
rename to 
extra_tests/cffi_tests/cffi0/snippets/distutils_package_2/snip_basic_verify2/__init__.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/infrastructure/setup.py 
b/extra_tests/cffi_tests/cffi0/snippets/infrastructure/setup.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/infrastructure/setup.py
rename to extra_tests/cffi_tests/cffi0/snippets/infrastructure/setup.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/infrastructure/snip_infrastructure/__init__.py
 
b/extra_tests/cffi_tests/cffi0/snippets/infrastructure/snip_infrastructure/__init__.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/infrastructure/snip_infrastructure/__init__.py
rename to 
extra_tests/cffi_tests/cffi0/snippets/infrastructure/snip_infrastructure/__init__.py
diff --git 
a/pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/setuptools_module/setup.py
 b/extra_tests/cffi_tests/cffi0/snippets/setuptools_module/setup.py
rename from 
pypy/module/test_lib_pypy/cffi_tests/cffi0/snippets/setuptools_module/setup.py
rename to extra_tests/cffi_tests/cffi0/snippets/setuptools_module/setup.py
diff

[pypy-commit] pypy math-improvements: Revert the inplace invert from rshift as it may break things

[Stian Andreassen]

Author: Stian Andreassen
Branch: math-improvements
Changeset: r95497:fc1d97a72983
Date: 2018-12-15 03:56 +0100
http://bitbucket.org/pypy/pypy/changeset/fc1d97a72983/

Log:Revert the inplace invert from rshift as it may break things

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -1231,43 +1231,30 @@
 raise ValueError("negative shift count")
 elif int_other == 0:
 return self
-invert = False
 if self.sign == -1 and not dont_invert:
-first = self.digit(0)
-if first == 0:
-a = self.invert().rshift(int_other)
-return a.invert()
-invert = True
+a = self.invert().rshift(int_other)
+return a.invert()
 
 wordshift = int_other / SHIFT
-loshift = int_other % SHIFT
 newsize = self.numdigits() - wordshift
 if newsize <= 0:
-if invert:
-return ONENEGATIVERBIGINT
-else:
-return NULLRBIGINT
-
-
+return NULLRBIGINT
+
+loshift = int_other % SHIFT
 hishift = SHIFT - loshift
 z = rbigint([NULLDIGIT] * newsize, self.sign, newsize)
 i = 0
 while i < newsize:
-digit = self.udigit(wordshift)
-if i == 0 and invert and wordshift == 0:
-digit -= 1
-newdigit = (digit >> loshift)
+newdigit = (self.digit(wordshift) >> loshift)
 if i+1 < newsize:
-newdigit |= (self.udigit(wordshift+1) << hishift)
+newdigit |= (self.digit(wordshift+1) << hishift)
 z.setdigit(i, newdigit)
 i += 1
 wordshift += 1
-if invert:
-z.setdigit(0, z.digit(0)+1)
 z._normalize()
 return z
-rshift._always_inline_ = 'try' # It's so fast that it's always beneficial.
-
+rshift._always_inline_ = 'try' # It's so fast that it's always benefitial.
+
 @jit.elidable
 def rqshift(self, int_other):
 wordshift = int_other / SHIFT
diff --git a/rpython/rlib/test/test_rbigint.py 
b/rpython/rlib/test/test_rbigint.py
--- a/rpython/rlib/test/test_rbigint.py
+++ b/rpython/rlib/test/test_rbigint.py
@@ -652,6 +652,9 @@
 # test special optimization case in rshift:
 assert rbigint.fromlong(-(1 << 100)).rshift(5).tolong() == -(1 << 100) 
>> 5
 
+# Chek value accuracy.
+assert rbigint.fromlong(18446744073709551615L).rshift(1).tolong() == 
18446744073709551615L >> 1
+
 def test_qshift(self):
 for x in range(10):
 for y in range(1, 161, 16):
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy math-improvements: Fix _x_divrem (thanks Carl Friedrich Bolz-Tereick for the test)

[Stian Andreassen]

Author: Stian Andreassen
Branch: math-improvements
Changeset: r95475:918c7b88d892
Date: 2018-12-13 18:10 +0100
http://bitbucket.org/pypy/pypy/changeset/918c7b88d892/

Log:Fix _x_divrem (thanks Carl Friedrich Bolz-Tereick for the test)

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -2073,12 +2073,15 @@
 if j >= size_v:
 vtop = 0
 else:
-vtop = v.widedigit(j) << SHIFT
-
-vv = vtop | v.digit(abs(j-1))
+vtop = v.widedigit(j)
+assert vtop <= wm1
+
+vv = (vtop << SHIFT) | v.widedigit(abs(j-1))
+
 # Hints to make division just as fast as doing it unsigned. But avoids 
casting to get correct results.
 assert vv >= 0
 assert wm1 >= 1
+
 q = vv / wm1
 r = vv % wm1 # This seems to be slightly faster on widen digits than 
vv - wm1 * q.
 vj2 = v.digit(abs(j-2))
___
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: No need to mask the carry bit.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r64581:ccb0ca253584
Date: 2013-05-27 14:50 +0200
http://bitbucket.org/pypy/pypy/changeset/ccb0ca253584/

Log:No need to mask the carry bit.

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -189,7 +189,7 @@
 carry = ival  SHIFT
 if carry:
 return rbigint([_store_digit(ival  MASK),
-_store_digit(carry  MASK)], sign, 2)
+_store_digit(carry)], sign, 2)
 else:
 return rbigint([_store_digit(ival  MASK)], sign, 1)
 
@@ -566,7 +566,7 @@
 res = b.widedigit(0) * a.widedigit(0)
 carry = res  SHIFT
 if carry:
-return rbigint([_store_digit(res  MASK), 
_store_digit(carry  MASK)], a.sign * b.sign, 2)
+return rbigint([_store_digit(res  MASK), 
_store_digit(carry)], a.sign * b.sign, 2)
 else:
 return rbigint([_store_digit(res  MASK)], a.sign * 
b.sign, 1)
 
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: - Use the same way to create longs on 32bit.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r64590:6bb363cd7367
Date: 2013-05-27 21:10 +0200
http://bitbucket.org/pypy/pypy/changeset/6bb363cd7367/

Log:- Use the same way to create longs on 32bit.
- Remove unnecesary left over special case from _x_sub.
- Comment out one sign bit from _x_sub. Tests pass without it. Its an
unsigned. Not a widedigit.

diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -180,34 +180,15 @@
 ival = r_uint(intval)
 else:
 return NULLRBIGINT
-# Count the number of Python digits.
-# We used to pick 5 (big enough for anything), but that's a
-# waste of time and space given that 5*15 = 75 bits are rarely
-# needed.
-# XXX: Even better!
-if SHIFT = 63:
-carry = ival  SHIFT
-if carry:
-return rbigint([_store_digit(ival  MASK),
-_store_digit(carry)], sign, 2)
-else:
-return rbigint([_store_digit(ival  MASK)], sign, 1)
+
+carry = ival  SHIFT
+if carry:
+return rbigint([_store_digit(ival  MASK),
+_store_digit(carry)], sign, 2)
+else:
+return rbigint([_store_digit(ival  MASK)], sign, 1)
 
-t = ival
-ndigits = 0
-while t:
-ndigits += 1
-t = SHIFT
-v = rbigint([NULLDIGIT] * ndigits, sign, ndigits)
-t = ival
-p = 0
-while t:
-v.setdigit(p, t)
-t = SHIFT
-p += 1
-
-return v
-
+
 @staticmethod
 def frombool(b):
 # This function is marked as pure, so you must not call it and
@@ -1107,10 +1088,6 @@
 def _x_sub(a, b):
  Subtract the absolute values of two integers. 
 
-# Special casing.
-if a is b:
-return NULLRBIGINT
-
 size_a = a.numdigits()
 size_b = b.numdigits()
 sign = 1
@@ -1141,13 +1118,13 @@
 borrow = a.udigit(i) - b.udigit(i) - borrow
 z.setdigit(i, borrow)
 borrow = SHIFT
-borrow = 1 # Keep only one sign bit
+#borrow = 1 # Keep only one sign bit
 i += 1
 while i  size_a:
 borrow = a.udigit(i) - borrow
 z.setdigit(i, borrow)
 borrow = SHIFT
-borrow = 1
+#borrow = 1
 i += 1
 
 assert borrow == 0
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Lets try these cflags with the official benchmark. Great results locally (14% better pidigits etc).

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r59447:3b95bf4a907e
Date: 2012-12-15 16:35 +0100
http://bitbucket.org/pypy/pypy/changeset/3b95bf4a907e/

Log:Lets try these cflags with the official benchmark. Great results
locally (14% better pidigits etc).

diff --git a/pypy/translator/platform/linux.py 
b/pypy/translator/platform/linux.py
--- a/pypy/translator/platform/linux.py
+++ b/pypy/translator/platform/linux.py
@@ -14,6 +14,7 @@
 extra_libs = ('-lrt',)
 cflags = tuple(
  ['-O3', '-pthread', '-fomit-frame-pointer',
+  '-fgcse-sm', '-fgcse-las', '-fmodulo-sched', 
'-fmodulo-sched-allow-regmoves', '-fmerge-all-constants',
   '-Wall', '-Wno-unused']
  + os.environ.get('CFLAGS', '').split())
 standalone_only = ()
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Backout 3b95bf4a907e. No significans

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r59448:78309907a0e7
Date: 2012-12-15 19:56 +0100
http://bitbucket.org/pypy/pypy/changeset/78309907a0e7/

Log:Backout 3b95bf4a907e. No significans

diff --git a/pypy/translator/platform/linux.py 
b/pypy/translator/platform/linux.py
--- a/pypy/translator/platform/linux.py
+++ b/pypy/translator/platform/linux.py
@@ -14,7 +14,6 @@
 extra_libs = ('-lrt',)
 cflags = tuple(
  ['-O3', '-pthread', '-fomit-frame-pointer',
-  '-fgcse-sm', '-fgcse-las', '-fmodulo-sched', 
'-fmodulo-sched-allow-regmoves', '-fmerge-all-constants',
   '-Wall', '-Wno-unused']
  + os.environ.get('CFLAGS', '').split())
 standalone_only = ()
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Give rbigint.eq a faster path (atleast it benchmarks slightly faster)

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r58739:e70778239285
Date: 2012-11-05 15:47 +0100
http://bitbucket.org/pypy/pypy/changeset/e70778239285/

Log:Give rbigint.eq a faster path (atleast it benchmarks slightly
faster)

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -337,6 +337,11 @@
 if (self.sign != other.sign or
 self.numdigits() != other.numdigits()):
 return False
+
+# Fast path.
+if len(self._digits) == len(other._digits):
+return self._digits == other._digits
+
 i = 0
 ld = self.numdigits()
 while i  ld:
diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py
--- a/pypy/rlib/test/test_rbigint.py
+++ b/pypy/rlib/test/test_rbigint.py
@@ -300,6 +300,13 @@
 assert not f1.eq(f2)
 assert not f1.eq(f3)
 
+def test_eq_fastpath(self):
+x = 1234
+y = 1234
+f1 = rbigint.fromint(x)
+f2 = rbigint.fromint(y)
+assert f1.eq(f2)
+
 def test_lt(self):
 val = [0, 0x, 0x1112, 0x1112]
 for x in gen_signs(val):
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Remove this assert, it's a condition for the while loop

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r58740:86ab7f9f73b7
Date: 2012-11-05 15:50 +0100
http://bitbucket.org/pypy/pypy/changeset/86ab7f9f73b7/

Log:Remove this assert, it's a condition for the while loop

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -845,7 +845,7 @@
 
 while i  1 and self._digits[i - 1] == NULLDIGIT:
 i -= 1
-assert i  0
+
 if i != self.numdigits():
 self.size = i
 if self.numdigits() == 1 and self._digits[0] == NULLDIGIT:
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Do sign checks directly.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r58761:bc1b37bec5b3
Date: 2012-11-05 23:41 +0100
http://bitbucket.org/pypy/pypy/changeset/bc1b37bec5b3/

Log:Do sign checks directly.

diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py
--- a/pypy/objspace/std/longobject.py
+++ b/pypy/objspace/std/longobject.py
@@ -251,7 +251,7 @@
 
 def pow__Long_Long_Long(space, w_long1, w_long2, w_long3):
 # XXX need to replicate some of the logic, to get the errors right
-if w_long2.num.lt(rbigint.fromint(0)):
+if w_long2.num.sign  0:
 raise OperationError(
 space.w_TypeError,
 space.wrap(
@@ -265,7 +265,7 @@
 
 def pow__Long_Long_None(space, w_long1, w_long2, w_long3):
 # XXX need to replicate some of the logic, to get the errors right
-if w_long2.num.lt(rbigint.fromint(0)):
+if w_long2.num.sign  0:
 raise FailedToImplementArgs(
 space.w_ValueError,
 space.wrap(long pow() too negative))
@@ -288,7 +288,7 @@
 
 def lshift__Long_Long(space, w_long1, w_long2):
 # XXX need to replicate some of the logic, to get the errors right
-if w_long2.num.lt(rbigint.fromint(0)):
+if w_long2.num.sign  0:
 raise OperationError(space.w_ValueError,
  space.wrap(negative shift count))
 try:
@@ -300,7 +300,7 @@
 
 def rshift__Long_Long(space, w_long1, w_long2):
 # XXX need to replicate some of the logic, to get the errors right
-if w_long2.num.lt(rbigint.fromint(0)):
+if w_long2.num.sign  0:
 raise OperationError(space.w_ValueError,
  space.wrap(negative shift count))
 try:
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Make test_decimal (the last test) pass.

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56892:92f8a4632989
Date: 2012-08-27 22:11 +0200
http://bitbucket.org/pypy/pypy/changeset/92f8a4632989/

Log:Make test_decimal (the last test) pass.

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -1554,7 +1554,10 @@
 at most (and usually exactly) k = size_v - size_w digits. 
 k = size_v - size_w
 if k == 0:
-return NULLRBIGINT, v1
+# We can't use v1, nor NULLRBIGINT here as some function modify the 
result.
+assert _v_rshift(w, v, size_w, d) == 0
+w._normalize()
+return rbigint([NULLDIGIT]), w
 
 assert k  0
 a = rbigint([NULLDIGIT] * k, 1, k)
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Disable an assert, we can't do this check in rpython. Fix lib-python crashes (tested locally)

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56828:41a49c1c5442
Date: 2012-08-23 19:52 +0200
http://bitbucket.org/pypy/pypy/changeset/41a49c1c5442/

Log:Disable an assert, we can't do this check in rpython. Fix lib-python
crashes (tested locally)

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -1582,7 +1582,7 @@
 q -= 1
 r += wm1
 
-assert q  MASK
+#assert q = MASK+1, We need to compare to BASE =, but ehm, it gives 
a buildin long error. So we ignore this.
 
 # subtract q*w0[0:size_w] from vk[0:size_w+1]
 zhi = 0
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Revert changes to rshift, and change a test so it fails, and fix it. All tests should now pass

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56815:31d713444087
Date: 2012-08-23 06:15 +0200
http://bitbucket.org/pypy/pypy/changeset/31d713444087/

Log:Revert changes to rshift, and change a test so it fails, and fix it.
All tests should now pass

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -21,7 +21,6 @@
 #SHIFT = (LONG_BIT // 2) - 1
 if SUPPORT_INT128:
 SHIFT = 63
-BASE = long(1  SHIFT)
 UDIGIT_TYPE = r_ulonglong
 if LONG_BIT = 64:
 UDIGIT_MASK = intmask
@@ -36,14 +35,13 @@
 UNSIGNED_TYPE = rffi.ULONGLONG
 else:
 SHIFT = 31
-BASE = int(1  SHIFT)
 UDIGIT_TYPE = r_uint
 UDIGIT_MASK = intmask
 STORE_TYPE = lltype.Signed
 UNSIGNED_TYPE = lltype.Unsigned
 LONG_TYPE = rffi.LONGLONG
 
-MASK = BASE - 1
+MASK = int((1  SHIFT) - 1)
 FLOAT_MULTIPLIER = float(1  SHIFT)
 
 # Debugging digit array access.
@@ -762,27 +760,24 @@
 elif int_other == 0:
 return self
 if self.sign == -1 and not dont_invert:
-a1 = self.invert()
-a2 = a1.rshift(int_other)
-return a2.invert()
+a = self.invert().rshift(int_other)
+return a.invert()
 
-wordshift = int_other // SHIFT
+wordshift = int_other / SHIFT
 newsize = self.numdigits() - wordshift
 if newsize = 0:
 return NULLRBIGINT
 
 loshift = int_other % SHIFT
 hishift = SHIFT - loshift
-# Not 100% sure here, but the reason why it won't be a problem is 
because
-# int is max 63bit, same as our SHIFT now.
-#lomask = UDIGIT_MASK((UDIGIT_TYPE(1)  hishift) - 1)
-#himask = MASK ^ lomask
+lomask = (1  hishift) - 1
+himask = MASK ^ lomask
 z = rbigint([NULLDIGIT] * newsize, self.sign, newsize)
 i = 0
 while i  newsize:
-newdigit = (self.udigit(wordshift)  loshift) # lomask
+newdigit = (self.digit(wordshift)  loshift)  lomask
 if i+1  newsize:
-newdigit += (self.udigit(wordshift+1)  hishift) # himask
+newdigit |= (self.digit(wordshift+1)  hishift)  himask
 z.setdigit(i, newdigit)
 i += 1
 wordshift += 1
@@ -1408,7 +1403,6 @@
 if not size:
 size = pin.numdigits()
 size -= 1
-
 while size = 0:
 rem = (rem  SHIFT) | pin.widedigit(size)
 hi = rem // n
@@ -1438,7 +1432,7 @@
 x[m-1], and the remaining carry (0 or 1) is returned.
 Python adaptation: x is addressed relative to xofs!
 
-carry = r_uint(0)
+carry = UDIGIT_TYPE(0)
 
 assert m = n
 i = _load_unsigned_digit(xofs)
@@ -1463,7 +1457,7 @@
 far as x[m-1], and the remaining borrow (0 or 1) is returned.
 Python adaptation: x is addressed relative to xofs!
 
-borrow = r_uint(0)
+borrow = UDIGIT_TYPE(0)
 
 assert m = n
 i = _load_unsigned_digit(xofs)
@@ -1559,13 +1553,17 @@
  Now v-ob_digit[size_v-1]  w-ob_digit[size_w-1], so quotient has
 at most (and usually exactly) k = size_v - size_w digits. 
 k = size_v - size_w
+if k == 0:
+return NULLRBIGINT, v1
+
 assert k  0
 a = rbigint([NULLDIGIT] * k, 1, k)
 
-wm1 = w.digit(abs(size_w-1))
+wm1 = w.widedigit(abs(size_w-1))
 wm2 = w.widedigit(abs(size_w-2))
 
-j = size_v
+j = size_v - 1
+k -= 1
 while k = 0:
 assert j = 0
  inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
@@ -1575,17 +1573,15 @@
 if j = size_v:
 vtop = 0
 else:
-vtop = v.digit(j)
+vtop = v.widedigit(j)
 assert vtop = wm1
 vv = (vtop  SHIFT) | v.widedigit(abs(j-1))
-q = UDIGIT_MASK(vv / wm1)
+q = vv / wm1
 r = vv - wm1 * q
 while wm2 * q  ((r  SHIFT) | v.widedigit(abs(j-2))):
 q -= 1
 r += wm1
-if r  MASK:
-break
-
+
 assert q  MASK
 
 # subtract q*w0[0:size_w] from vk[0:size_w+1]
@@ -1609,9 +1605,10 @@
 q -= 1
 
 # store quotient digit
+a.setdigit(k, q)
 k -= 1
 j -= 1
-a.setdigit(k, q)
+
 
 carry = _v_rshift(w, v, size_w, d)
 assert carry == 0
diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py
--- a/pypy/rlib/test/test_rbigint.py
+++ b/pypy/rlib/test/test_rbigint.py
@@ -547,7 +547,7 @@
 Rx = 1  130
 Rx2 = 1  150
 Ry = 1  127
-Ry2 = 1 130
+Ry2 = 1 150
 for i in range(10):
 x = long(randint(Rx, Rx2))
 y = long(randint(Ry, Ry2))
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Progress?

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56757:95fea225f922
Date: 2012-08-19 22:21 +0200
http://bitbucket.org/pypy/pypy/changeset/95fea225f922/

Log:Progress?

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -109,9 +109,10 @@
 hop.exception_cannot_occur()
 
 class rbigint(object):
+This is a reimplementation of longs using a list of digits.
 _immutable_ = True
 _immutable_fields_ = [_digits]
-This is a reimplementation of longs using a list of digits.
+
 
 def __init__(self, digits=[NULLDIGIT], sign=0, size=0):
 if not we_are_translated():
@@ -743,12 +744,12 @@
 
 z = rbigint([NULLDIGIT] * (oldsize + 1), self.sign, (oldsize + 1))
 accum = _widen_digit(0)
-
-for i in range(oldsize):
+i = 0
+while i  oldsize:
 accum += self.widedigit(i)  int_other
 z.setdigit(i, accum)
 accum = SHIFT
-
+i += 1
 z.setdigit(oldsize, accum)
 z._normalize()
 return z
@@ -1105,6 +1106,84 @@
 z._normalize()
 return z
 
+def _x_mul(a, b, digit=0):
+
+Grade school multiplication, ignoring the signs.
+Returns the absolute value of the product, or None if error.
+
+
+size_a = a.numdigits()
+size_b = b.numdigits()
+
+if a is b:
+# Efficient squaring per HAC, Algorithm 14.16:
+# http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
+# Gives slightly less than a 2x speedup when a == b,
+# via exploiting that each entry in the multiplication
+# pyramid appears twice (except for the size_a squares).
+z = rbigint([NULLDIGIT] * (size_a + size_b), 1)
+i = UDIGIT_TYPE(0)
+while i  size_a:
+f = a.widedigit(i)
+pz = i  1
+pa = i + 1
+
+carry = z.widedigit(pz) + f * f
+z.setdigit(pz, carry)
+pz += 1
+carry = SHIFT
+assert carry = MASK
+
+# Now f is added in twice in each column of the
+# pyramid it appears.  Same as adding f1 once.
+f = 1
+while pa  size_a:
+carry += z.widedigit(pz) + a.widedigit(pa) * f
+pa += 1
+z.setdigit(pz, carry)
+pz += 1
+carry = SHIFT
+if carry:
+carry += z.widedigit(pz)
+z.setdigit(pz, carry)
+pz += 1
+carry = SHIFT
+if carry:
+z.setdigit(pz, z.widedigit(pz) + carry)
+assert (carry  SHIFT) == 0
+i += 1
+z._normalize()
+return z
+
+elif digit:
+if digit  (digit - 1) == 0:
+return b.lqshift(ptwotable[digit])
+
+# Even if it's not power of two it can still be useful.
+return _muladd1(b, digit)
+
+z = rbigint([NULLDIGIT] * (size_a + size_b), 1)
+# gradeschool long mult
+i = UDIGIT_TYPE(0)
+while i  size_a:
+carry = 0
+f = a.widedigit(i)
+pz = i
+pb = 0
+while pb  size_b:
+carry += z.widedigit(pz) + b.widedigit(pb) * f
+pb += 1
+z.setdigit(pz, carry)
+pz += 1
+carry = SHIFT
+assert carry = MASK
+if carry:
+assert pz = 0
+z.setdigit(pz, z.widedigit(pz) + carry)
+assert (carry  SHIFT) == 0
+i += 1
+z._normalize()
+return z
 
 def _kmul_split(n, size):
 
@@ -1429,10 +1508,12 @@
 
 carry = 0
 assert 0 = d and d  SHIFT
-for i in range(m):
+i = 0
+while i  m:
 acc = a.widedigit(i)  d | carry
 z.setdigit(i, acc)
 carry = acc  SHIFT
+i += 1
 
 return carry
 
@@ -1446,10 +1527,12 @@
 mask = (1  d) - 1
 
 assert 0 = d and d  SHIFT
-for i in range(m-1, 0, -1):
+i = m-1
+while i = 0:
 acc = (carry  SHIFT) | a.widedigit(i)
 carry = acc  mask
 z.setdigit(i, acc  d)
+i -= 1
 
 return carry
 
@@ -1462,10 +1545,10 @@
 v = rbigint([NULLDIGIT] * (size_v + 1), 1, size_v + 1)
 w = rbigint([NULLDIGIT] * size_w, 1, size_w)
 
-/normalize: shift w1 left so that its top digit is = PyLong_BASE/2.
+ normalize: shift w1 left so that its top digit is = PyLong_BASE/2.
 shift v1 left by the same amount. Results go into w and v. 
 
-d = SHIFT - bits_in_digit(w1.digit(size_w-1))
+d = SHIFT - bits_in_digit(w1.digit(abs(size_w-1)))
 carry = _v_lshift(w, w1, size_w, d)
 assert carry == 0
 carry = _v_lshift(v, v1, size_v, d)
@@ -1475,16 +1558,14 @@
 
  Now v-ob_digit[size_v-1]  w-ob_digit[size_w-1], so quotient has
 at most (and usually exactly) k = size_v - size_w digits. 
-
-size_a

[pypy-commit] pypy improve-rbigint: Add test (and fix) for the eq issue. Remove _inplace_invert as it might break

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56437:a28203ac14e1
Date: 2012-07-24 22:10 +0200
http://bitbucket.org/pypy/pypy/changeset/a28203ac14e1/

Log:Add test (and fix) for the eq issue. Remove _inplace_invert as it
might break

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -326,16 +326,6 @@
 
 @jit.elidable
 def eq(self, other):
-# This code is temp only. Just to raise some more specific asserts
-# For a bug.
-# One of the values sent to eq have not gone through normalize.
-# Etc Aga x * p2 != x  n from test_long.py
-if self.sign == 0 and other.sign == 0:
-return True
-assert not (self.numdigits() == 1 and self._digits[0] == NULLDIGIT)
-assert not (other.numdigits() == 1 and other._digits[0] == NULLDIGIT)
-
-
 if (self.sign != other.sign or
 self.numdigits() != other.numdigits()):
 return False
@@ -715,16 +705,6 @@
 ret = self.add(ONERBIGINT)
 ret.sign = -ret.sign
 return ret
-
-def inplace_invert(self): # Used by rshift and bitwise to prevent a double 
allocation.
-if self.sign == 0:
-return ONENEGATIVERBIGINT
-if self.sign == 1:
-_v_iadd(self, 0, self.numdigits(), ONERBIGINT, 1)
-else:
- _v_isub(self, 0, self.numdigits(), ONERBIGINT, 1)
-self.sign = -self.sign
-return self
 
 @jit.elidable
 def lshift(self, int_other):
@@ -738,6 +718,9 @@
 remshift  = int_other - wordshift * SHIFT
 
 if not remshift:
+# So we can avoid problems with eq, AND avoid the need for 
normalize.
+if self.sign == 0:
+return self
 return rbigint([NULLDIGIT] * wordshift + self._digits, self.sign, 
self.size + wordshift)
 
 oldsize = self.numdigits()
@@ -789,7 +772,7 @@
 if self.sign == -1 and not dont_invert:
 a1 = self.invert()
 a2 = a1.rshift(int_other)
-return a2.inplace_invert()
+return a2.invert()
 
 wordshift = int_other // SHIFT
 newsize = self.numdigits() - wordshift
@@ -890,8 +873,9 @@
 return bits
 
 def __repr__(self):
-return rbigint digits=%s, sign=%s, %s % (self._digits,
- self.sign, self.str())
+return rbigint digits=%s, sign=%s, size=%d, len=%d, %s % 
(self._digits,
+self.sign, self.size, 
len(self._digits),
+self.str())
 
 ONERBIGINT = rbigint([ONEDIGIT], 1, 1)
 ONENEGATIVERBIGINT = rbigint([ONEDIGIT], -1, 1)
@@ -2240,7 +2224,7 @@
 if negz == 0:
 return z
 
-return z.inplace_invert()
+return z.invert()
 _bitwise._annspecialcase_ = specialize:arg(1)
 
 
diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py
--- a/pypy/rlib/test/test_rbigint.py
+++ b/pypy/rlib/test/test_rbigint.py
@@ -442,6 +442,12 @@
 res2 = getattr(operator, mod)(x, y)
 assert res1 == res2
 
+def test_mul_eq_shift(self):
+p2 = rbigint.fromlong(1).lshift(63)
+f1 = rbigint.fromlong(0).lshift(63)
+f2 = rbigint.fromlong(0).mul(p2)
+assert f1.eq(f2)
+
 def test_tostring(self):
 z = rbigint.fromlong(0)
 assert z.str() == '0'
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Don't do floordiv/divmod sub inplace as it can break if div = -2**63

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56438:5355a27bac5e
Date: 2012-07-24 23:18 +0200
http://bitbucket.org/pypy/pypy/changeset/5355a27bac5e/

Log:Don't do floordiv/divmod sub inplace as it can break if div = -2**63

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -479,11 +479,8 @@
 if mod.sign * other.sign == -1:
 if div.sign == 0:
 return ONENEGATIVERBIGINT
+div = div.sub(ONERBIGINT)
 
-if div.sign == 1:
-_v_isub(div, 0, div.numdigits(), ONERBIGINT, 1)
-else:
-_v_iadd(div, 0, div.numdigits(), ONERBIGINT, 1)
 return div
 
 def div(self, other):
@@ -549,10 +546,7 @@
 mod = mod.add(w)
 if div.sign == 0:
 return ONENEGATIVERBIGINT, mod
-if div.sign == 1:
-_v_isub(div, 0, div.numdigits(), ONERBIGINT, 1)
-else:
-_v_iadd(div, 0, div.numdigits(), ONERBIGINT, 1)
+div = div.sub(ONERBIGINT)
 return div, mod
 
 @jit.elidable
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Update benchmark results and lib-python tests pass (except for test_socket which is not relevant to the branch)

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56439:b67f6a67a882
Date: 2012-07-24 23:59 +0200
http://bitbucket.org/pypy/pypy/changeset/b67f6a67a882/

Log:Update benchmark results and lib-python tests pass (except for
test_socket which is not relevant to the branch)

diff --git a/pypy/translator/goal/targetbigintbenchmark.py 
b/pypy/translator/goal/targetbigintbenchmark.py
--- a/pypy/translator/goal/targetbigintbenchmark.py
+++ b/pypy/translator/goal/targetbigintbenchmark.py
@@ -35,24 +35,24 @@
 Sum:  142.686547
 
 Pypy with improvements:
-mod by 2:  0.005841
-mod by 1:  3.134566
-mod by 1024 (power of two):  0.009598
-Div huge number by 2**128: 2.117672
-rshift: 2.216447
-lshift: 1.318227
-Floordiv by 2: 1.518645
-Floordiv by 3 (not power of two): 4.349879
-2**50: 0.033484
-(2**N)**500 (power of two): 0.052457
-1 ** BIGNUM % 100 1.323458
-i = i * i: 3.964939
-n**1 (not power of two): 6.313849
-Power of two ** power of two: 0.013127
-v = v * power of two 3.537295
-v = v * v 6.310657
-v = v + v 2.765472
-Sum:  38.985613
+mod by 2:  0.006321
+mod by 1:  3.143117
+mod by 1024 (power of two):  0.009611
+Div huge number by 2**128: 2.138351
+rshift: 2.247337
+lshift: 1.334369
+Floordiv by 2: 1.555604
+Floordiv by 3 (not power of two): 4.275014
+2**50: 0.033836
+(2**N)**500 (power of two): 0.049600
+1 ** BIGNUM % 100 1.326477
+i = i * i: 3.924958
+n**1 (not power of two): 6.335759
+Power of two ** power of two: 0.013380
+v = v * power of two 3.497662
+v = v * v 6.359251
+v = v + v 2.785971
+Sum:  39.036619
 
 With SUPPORT_INT128 set to False
 mod by 2:  0.004103
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Close branch for merge

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56442:b627febbca4a
Date: 2012-07-25 02:13 +0200
http://bitbucket.org/pypy/pypy/changeset/b627febbca4a/

Log:Close branch for merge

___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy default: Merge improve-rbigint. This branch improves the performance on most long operations and use 64bit storage and __int128 for wide digits on systems where it is available.

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r56444:8a78c6bf2abb
Date: 2012-07-25 02:37 +0200
http://bitbucket.org/pypy/pypy/changeset/8a78c6bf2abb/

Log:Merge improve-rbigint. This branch improves the performance on most
long operations and use 64bit storage and __int128 for wide digits
on systems where it is available.

Special cases for power of two mod, division, multiplication.
Improvements to pow (see
pypy/translator/goal/targetbigintbenchmark.py for some runs on my
system), mark operations as elidable and various other tweaks.

Overall, it makes things run faster than CPython if the script
doesn't heavily rely on division.

diff --git a/pypy/module/sys/system.py b/pypy/module/sys/system.py
--- a/pypy/module/sys/system.py
+++ b/pypy/module/sys/system.py
@@ -48,8 +48,8 @@
 
 def get_long_info(space):
 #assert rbigint.SHIFT == 31
-bits_per_digit = 31 #rbigint.SHIFT
-sizeof_digit = rffi.sizeof(rffi.ULONG)
+bits_per_digit = rbigint.SHIFT
+sizeof_digit = rffi.sizeof(rbigint.STORE_TYPE)
 info_w = [
 space.wrap(bits_per_digit),
 space.wrap(sizeof_digit),
diff --git a/pypy/rlib/rarithmetic.py b/pypy/rlib/rarithmetic.py
--- a/pypy/rlib/rarithmetic.py
+++ b/pypy/rlib/rarithmetic.py
@@ -115,21 +115,16 @@
 n -= 2*LONG_TEST
 return int(n)
 
-if LONG_BIT = 64:
-def longlongmask(n):
-assert isinstance(n, (int, long))
-return int(n)
-else:
-def longlongmask(n):
-
-NOT_RPYTHON
-
-assert isinstance(n, (int, long))
-n = long(n)
-n = LONGLONG_MASK
-if n = LONGLONG_TEST:
-n -= 2*LONGLONG_TEST
-return r_longlong(n)
+def longlongmask(n):
+
+NOT_RPYTHON
+
+assert isinstance(n, (int, long))
+n = long(n)
+n = LONGLONG_MASK
+if n = LONGLONG_TEST:
+n -= 2*LONGLONG_TEST
+return r_longlong(n)
 
 def longlonglongmask(n):
 # Assume longlonglong doesn't overflow. This is perfectly fine for rbigint.
diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -23,7 +23,10 @@
 SHIFT = 63
 BASE = long(1  SHIFT)
 UDIGIT_TYPE = r_ulonglong
-UDIGIT_MASK = longlongmask
+if LONG_BIT = 64:
+UDIGIT_MASK = intmask
+else:
+UDIGIT_MASK = longlongmask
 LONG_TYPE = rffi.__INT128
 if LONG_BIT  SHIFT:
 STORE_TYPE = lltype.Signed
@@ -41,7 +44,7 @@
 LONG_TYPE = rffi.LONGLONG
 
 MASK = BASE - 1
-FLOAT_MULTIPLIER = float(1  LONG_BIT) # Because it works.
+FLOAT_MULTIPLIER = float(1  SHIFT)
 
 # Debugging digit array access.
 #
@@ -137,7 +140,7 @@
 udigit._always_inline_ = True
 
 def setdigit(self, x, val):
-val = val  MASK
+val = _mask_digit(val)
 assert val = 0
 self._digits[x] = _store_digit(val)
 setdigit._annspecialcase_ = 'specialize:argtype(2)'
@@ -448,8 +451,8 @@
 
 if asize = i:
 result = _x_mul(a, b)
-elif 2 * asize = bsize:
-result = _k_lopsided_mul(a, b)
+elif 2 * asize = bsize:
+result = _k_lopsided_mul(a, b)
 else:
 result = _k_mul(a, b)
 else:
@@ -465,10 +468,10 @@
 
 @jit.elidable
 def floordiv(self, other):
-if other.numdigits() == 1 and other.sign == 1:
+if self.sign == 1 and other.numdigits() == 1 and other.sign == 1:
 digit = other.digit(0)
 if digit == 1:
-return rbigint(self._digits[:], other.sign * self.sign, 
self.size)
+return rbigint(self._digits[:], 1, self.size)
 elif digit and digit  (digit - 1) == 0:
 return self.rshift(ptwotable[digit])
 
@@ -476,10 +479,8 @@
 if mod.sign * other.sign == -1:
 if div.sign == 0:
 return ONENEGATIVERBIGINT
-if div.sign == 1:
-_v_isub(div, 0, div.numdigits(), ONERBIGINT, 1)
-else:
-_v_iadd(div, 0, div.numdigits(), ONERBIGINT, 1)
+div = div.sub(ONERBIGINT)
+
 return div
 
 def div(self, other):
@@ -545,10 +546,7 @@
 mod = mod.add(w)
 if div.sign == 0:
 return ONENEGATIVERBIGINT, mod
-if div.sign == 1:
-_v_isub(div, 0, div.numdigits(), ONERBIGINT, 1)
-else:
-_v_iadd(div, 0, div.numdigits(), ONERBIGINT, 1)
+div = div.sub(ONERBIGINT)
 return div, mod
 
 @jit.elidable
@@ -567,11 +565,6 @@
 # XXX failed to implement
 raise ValueError(bigint pow() too negative)
 
-if b.sign == 0:
-return ONERBIGINT
-elif a.sign == 0:
-return NULLRBIGINT
-
 size_b = b.numdigits()
 
 if c is not None

[pypy-commit] pypy default: Update whatsnew with improve-rbigint

[Stian Andreassen]

Author: Stian Andreassen
Branch: 
Changeset: r56445:606d6a6c708f
Date: 2012-07-25 02:42 +0200
http://bitbucket.org/pypy/pypy/changeset/606d6a6c708f/

Log:Update whatsnew with improve-rbigint

diff --git a/pypy/doc/whatsnew-head.rst b/pypy/doc/whatsnew-head.rst
--- a/pypy/doc/whatsnew-head.rst
+++ b/pypy/doc/whatsnew-head.rst
@@ -20,6 +20,9 @@
 Implement better JIT hooks
 .. branch: virtual-arguments
 Improve handling of **kwds greatly, making them virtual sometimes.
+.. branch: improve-rbigint
+Introduce __int128 on systems where it's supported and improve the speed of
+rlib/rbigint.py greatly.
 
 .. uninteresting branches that we should just ignore for the whatsnew:
 .. branch: slightly-shorter-c
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: This should fix sys.long_object

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56402:f13bae13dc42
Date: 2012-07-23 11:26 +0200
http://bitbucket.org/pypy/pypy/changeset/f13bae13dc42/

Log:This should fix sys.long_object

diff --git a/pypy/module/sys/system.py b/pypy/module/sys/system.py
--- a/pypy/module/sys/system.py
+++ b/pypy/module/sys/system.py
@@ -48,8 +48,8 @@
 
 def get_long_info(space):
 #assert rbigint.SHIFT == 31
-bits_per_digit = 31 #rbigint.SHIFT
-sizeof_digit = rffi.sizeof(rffi.ULONG)
+bits_per_digit = rbigint.SHIFT
+sizeof_digit = rffi.sizeof(rbigint.STORE_TYPE)
 info_w = [
 space.wrap(bits_per_digit),
 space.wrap(sizeof_digit),
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: These cases only work when c = None, obviously

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56406:1a5e9ccdcaf6
Date: 2012-07-23 11:57 +0200
http://bitbucket.org/pypy/pypy/changeset/1a5e9ccdcaf6/

Log:These cases only work when c = None, obviously

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -593,9 +593,9 @@
 if a.sign  0:
 a = a.mod(c)
 
-if b.sign == 0:
+elif b.sign == 0:
 return ONERBIGINT
-if a.sign == 0:
+elif a.sign == 0:
 return NULLRBIGINT
 
 size_b = b.numdigits()
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Another fix for pow(), disable _k_lopsided (has less than 1% gain), fix _x_divrem crash.

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56418:dbe841278cef
Date: 2012-07-24 06:15 +0200
http://bitbucket.org/pypy/pypy/changeset/dbe841278cef/

Log:Another fix for pow(), disable _k_lopsided (has less than 1% gain),
fix _x_divrem crash.

There is one remaining known issue (with eq), may lake a _normalize
somewhere

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -326,6 +326,16 @@
 
 @jit.elidable
 def eq(self, other):
+# This code is temp only. Just to raise some more specific asserts
+# For a bug.
+# One of the values sent to eq have not gone through normalize.
+# Etc Aga x * p2 != x  n from test_long.py
+if self.sign == 0 and other.sign == 0:
+return True
+assert not (self.numdigits() == 1 and self._digits[0] == NULLDIGIT)
+assert not (other.numdigits() == 1 and other._digits[0] == NULLDIGIT)
+
+
 if (self.sign != other.sign or
 self.numdigits() != other.numdigits()):
 return False
@@ -451,8 +461,8 @@
 
 if asize = i:
 result = _x_mul(a, b)
-elif 2 * asize = bsize:
-result = _k_lopsided_mul(a, b)
+elif 2 * asize = bsize:
+result = _k_lopsided_mul(a, b)
 else:
 result = _k_mul(a, b)
 else:
@@ -571,6 +581,8 @@
 # XXX failed to implement
 raise ValueError(bigint pow() too negative)
 
+size_b = b.numdigits()
+
 if c is not None:
 if c.sign == 0:
 raise ValueError(pow() 3rd argument cannot be 0)
@@ -597,10 +609,7 @@
 return ONERBIGINT
 elif a.sign == 0:
 return NULLRBIGINT
-
-size_b = b.numdigits()
-
-if size_b == 1:
+elif size_b == 1:
 if b._digits[0] == NULLDIGIT:
 return ONERBIGINT if a.sign == 1 else ONENEGATIVERBIGINT
 elif b._digits[0] == ONEDIGIT:
@@ -692,12 +701,12 @@
 return z
 
 def neg(self):
-return rbigint(self._digits[:], -self.sign, self.size)
+return rbigint(self._digits, -self.sign, self.size)
 
 def abs(self):
 if self.sign != -1:
 return self
-return rbigint(self._digits[:], abs(self.sign), self.size)
+return rbigint(self._digits, 1, self.size)
 
 def invert(self): #Implement ~x as -(x + 1)
 if self.sign == 0:
@@ -1221,8 +1230,9 @@
 size_n = n.numdigits()
 size_lo = min(size_n, size)
 
-lo = rbigint(n._digits[:size_lo], 1)
-hi = rbigint(n._digits[size_lo:], 1)
+# We use or her to avoid having a check where list can be empty in 
_normalize.
+lo = rbigint(n._digits[:size_lo] or [NULLDIGIT], 1)
+hi = rbigint(n._digits[size_lo:n.size] or [NULLDIGIT], 1)
 lo._normalize()
 hi._normalize()
 return hi, lo
@@ -1246,7 +1256,10 @@
 # Split a  b into hi  lo pieces.
 shift = bsize  1
 ah, al = _kmul_split(a, shift)
-assert ah.sign == 1# the split isn't degenerate
+if ah.sign == 0:
+# This may happen now that _k_lopsided_mul ain't catching it.
+return _x_mul(a, b)
+#assert ah.sign == 1# the split isn't degenerate
 
 if a is b:
 bh = ah
@@ -1274,6 +1287,7 @@
 
 # 2. t1 - ah*bh, and copy into high digits of result.
 t1 = ah.mul(bh)
+
 assert t1.sign = 0
 assert 2*shift + t1.numdigits() = ret.numdigits()
 ret._digits[2*shift : 2*shift + t1.numdigits()] = t1._digits
@@ -1367,6 +1381,8 @@
 
 
 def _k_lopsided_mul(a, b):
+# Not in use anymore, only account for like 1% performance. Perhaps if we
+# Got rid of the extra list allocation this would be more effective.
 
 b has at least twice the digits of a, and a is big enough that Karatsuba
 would pay off *if* the inputs had balanced sizes.  View b as a sequence
@@ -1582,30 +1598,27 @@
 wm2 = w.widedigit(abs(size_w-2))
 j = size_v
 k = size_a - 1
+carry = _widen_digit(0)
 while k = 0:
-assert j = 2
+assert j  1
 if j = size_v:
 vj = 0
 else:
 vj = v.widedigit(j)
-
-carry = 0
-vj1 = v.widedigit(abs(j-1))
 
 if vj == wm1:
 q = MASK
-r = 0
 else:
-vv = ((vj  SHIFT) | vj1)
-q = vv // wm1
-r = _widen_digit(vv) - wm1 * q
-
-vj2 = v.widedigit(abs(j-2))
-while wm2 * q  ((r  SHIFT) | vj2):
+q = ((vj  SHIFT) + v.widedigit(abs(j-1))) // wm1
+
+while (wm2 * q 
+((
+(vj  SHIFT)
++ v.widedigit(abs(j-1))
+- q * wm1
+)  SHIFT)
++ v.widedigit

[pypy-commit] pypy improve-rbigint: this fixes lib-python test_pow.py, i think

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56395:bdfcec5f93d1
Date: 2012-07-23 01:33 +0200
http://bitbucket.org/pypy/pypy/changeset/bdfcec5f93d1/

Log:this fixes lib-python test_pow.py, i think

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -137,7 +137,7 @@
 udigit._always_inline_ = True
 
 def setdigit(self, x, val):
-val = val  MASK
+val = _mask_digit(val)
 assert val = 0
 self._digits[x] = _store_digit(val)
 setdigit._annspecialcase_ = 'specialize:argtype(2)'
@@ -553,9 +553,6 @@
 
 @jit.elidable
 def pow(a, b, c=None):
-if a.sign == 0:
-return NULLRBIGINT
-
 negativeOutput = False  # if x0 return negative output
 
 # 5-ary values.  If the exponent is large enough, table is
@@ -570,13 +567,6 @@
 # XXX failed to implement
 raise ValueError(bigint pow() too negative)
 
-if b.sign == 0:
-return ONERBIGINT
-elif a.sign == 0:
-return NULLRBIGINT
-
-size_b = b.numdigits()
-
 if c is not None:
 if c.sign == 0:
 raise ValueError(pow() 3rd argument cannot be 0)
@@ -592,15 +582,21 @@
 # return 0
 if c.numdigits() == 1 and c._digits[0] == ONEDIGIT:
 return NULLRBIGINT
-
+   
 # if base  0:
 # base = base % modulus
 # Having the base positive just makes things easier.
 if a.sign  0:
 a = a.mod(c)
-
 
-elif size_b == 1:
+if b.sign == 0:
+return ONERBIGINT
+if a.sign == 0:
+return NULLRBIGINT
+
+size_b = b.numdigits()
+
+if size_b == 1:
 if b._digits[0] == NULLDIGIT:
 return ONERBIGINT if a.sign == 1 else ONENEGATIVERBIGINT
 elif b._digits[0] == ONEDIGIT:
@@ -849,7 +845,7 @@
 
 def _normalize(self):
 i = self.numdigits()
-# i is always = 1
+
 while i  1 and self._digits[i - 1] == NULLDIGIT:
 i -= 1
 assert i  0
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Specialize 0**N, fix test_longobject.py

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56394:34a5cc2af0fe
Date: 2012-07-23 00:47 +0200
http://bitbucket.org/pypy/pypy/changeset/34a5cc2af0fe/

Log:Specialize 0**N, fix test_longobject.py

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -553,6 +553,9 @@
 
 @jit.elidable
 def pow(a, b, c=None):
+if a.sign == 0:
+return NULLRBIGINT
+
 negativeOutput = False  # if x0 return negative output
 
 # 5-ary values.  If the exponent is large enough, table is
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Only use rshift for power of two division if both are positive. This fixes the array tests

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56396:6a80b272ad85
Date: 2012-07-23 02:30 +0200
http://bitbucket.org/pypy/pypy/changeset/6a80b272ad85/

Log:Only use rshift for power of two division if both are positive. This
fixes the array tests

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -465,10 +465,10 @@
 
 @jit.elidable
 def floordiv(self, other):
-if other.numdigits() == 1 and other.sign == 1:
+if self.sign == 1 and other.numdigits() == 1 and other.sign == 1:
 digit = other.digit(0)
 if digit == 1:
-return rbigint(self._digits[:], other.sign * self.sign, 
self.size)
+return rbigint(self._digits[:], 1, self.size)
 elif digit and digit  (digit - 1) == 0:
 return self.rshift(ptwotable[digit])
 
@@ -476,6 +476,7 @@
 if mod.sign * other.sign == -1:
 if div.sign == 0:
 return ONENEGATIVERBIGINT
+
 if div.sign == 1:
 _v_isub(div, 0, div.numdigits(), ONERBIGINT, 1)
 else:
@@ -854,7 +855,7 @@
 if self.numdigits() == 1 and self._digits[0] == NULLDIGIT:
 self.sign = 0
 self._digits = [NULLDIGIT]
-
+
 _normalize._always_inline_ = True
 
 @jit.elidable
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Revert changes to longlongmask, and rather use intmask. This fixes objspace test

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56397:5c650b1b8752
Date: 2012-07-23 02:58 +0200
http://bitbucket.org/pypy/pypy/changeset/5c650b1b8752/

Log:Revert changes to longlongmask, and rather use intmask. This fixes
objspace test

diff --git a/pypy/rlib/rarithmetic.py b/pypy/rlib/rarithmetic.py
--- a/pypy/rlib/rarithmetic.py
+++ b/pypy/rlib/rarithmetic.py
@@ -115,21 +115,16 @@
 n -= 2*LONG_TEST
 return int(n)
 
-if LONG_BIT = 64:
-def longlongmask(n):
-assert isinstance(n, (int, long))
-return int(n)
-else:
-def longlongmask(n):
-
-NOT_RPYTHON
-
-assert isinstance(n, (int, long))
-n = long(n)
-n = LONGLONG_MASK
-if n = LONGLONG_TEST:
-n -= 2*LONGLONG_TEST
-return r_longlong(n)
+def longlongmask(n):
+
+NOT_RPYTHON
+
+assert isinstance(n, (int, long))
+n = long(n)
+n = LONGLONG_MASK
+if n = LONGLONG_TEST:
+n -= 2*LONGLONG_TEST
+return r_longlong(n)
 
 def longlonglongmask(n):
 # Assume longlonglong doesn't overflow. This is perfectly fine for rbigint.
diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -23,7 +23,10 @@
 SHIFT = 63
 BASE = long(1  SHIFT)
 UDIGIT_TYPE = r_ulonglong
-UDIGIT_MASK = longlongmask
+if LONG_BIT = 64:
+UDIGIT_MASK = intmask
+else:
+UDIGIT_MASK = longlongmask
 LONG_TYPE = rffi.__INT128
 if LONG_BIT  SHIFT:
 STORE_TYPE = lltype.Signed
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Find a better cutoff for karatsuba (The ideal in my tests was 38). This gives upto 20% performance increase while working in that range.

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56309:b095a819f98b
Date: 2012-06-21 22:17 +0200
http://bitbucket.org/pypy/pypy/changeset/b095a819f98b/

Log:Find a better cutoff for karatsuba (The ideal in my tests was 38).
This gives upto 20% performance increase while working in that
range. Disable a trick in _x_mul, this was about 20-25% slower than
the regular method.

 Etc: v = rbigint.fromint(2) for n in xrange(5):
v = v.mul(rbigint.fromint(2**62))

Went from 17.8s to 10.6s by just these changes alone.

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -18,7 +18,7 @@
 SHIFT = 31
 
 MASK = int((1  SHIFT) - 1)
-FLOAT_MULTIPLIER = float(1  SHIFT)
+FLOAT_MULTIPLIER = float(1  LONG_BIT) # Because it works.
 
 
 # Debugging digit array access.
@@ -31,10 +31,12 @@
 # both operands contain more than KARATSUBA_CUTOFF digits (this
 # being an internal Python long digit, in base BASE).
 
+# Karatsuba is O(N**1.585)
 USE_KARATSUBA = True # set to False for comparison
-KARATSUBA_CUTOFF = 70
+KARATSUBA_CUTOFF = 38
 KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF
 
+
 # For exponentiation, use the binary left-to-right algorithm
 # unless the exponent contains more than FIVEARY_CUTOFF digits.
 # In that case, do 5 bits at a time.  The potential drawback is that
@@ -629,18 +631,19 @@
 return l * self.sign
 
 def _normalize(self):
-if self.numdigits() == 0:
+i = self.numdigits()
+if i == 0:
 self.sign = 0
 self._digits = [NULLDIGIT]
 return
-i = self.numdigits()
+
 while i  1 and self.digit(i - 1) == 0:
 i -= 1
 assert i = 1
 if i != self.numdigits():
 self._digits = self._digits[:i]
-if self.numdigits() == 1 and self.digit(0) == 0:
-self.sign = 0
+if self.numdigits() == 1 and self.digit(0) == 0:
+self.sign = 0
 
 def bit_length(self):
 i = self.numdigits()
@@ -817,6 +820,8 @@
 size_a = a.numdigits()
 size_b = b.numdigits()
 z = rbigint([NULLDIGIT] * (size_a + size_b), 1)
+
+# Code below actually runs slower (about 20%). Dunno why, since it 
shouldn't.
 if a is b:
 # Efficient squaring per HAC, Algorithm 14.16:
 # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
@@ -853,28 +858,27 @@
 carry = SHIFT
 if carry:
 z.setdigit(pz, z.widedigit(pz) + carry)
-assert (carry  SHIFT) == 0
+assert (carry  63) == 0
 i += 1
-else:
-# a is not the same as b -- gradeschool long mult
-i = 0
-while i  size_a:
-carry = 0
-f = a.widedigit(i)
-pz = i
-pb = 0
-pbend = size_b
-while pb  pbend:
-carry += z.widedigit(pz) + b.widedigit(pb) * f
-pb += 1
-z.setdigit(pz, carry)
-pz += 1
-carry = SHIFT
-assert carry = MASK
-if carry:
-z.setdigit(pz, z.widedigit(pz) + carry)
-assert (carry  SHIFT) == 0
-i += 1
+else:
+# gradeschool long mult
+i = 0
+while i  size_a:
+carry = 0
+f = a.widedigit(i)
+pz = i
+pb = 0
+while pb  size_b:
+carry += z.widedigit(pz) + b.widedigit(pb) * f
+pb += 1
+z.setdigit(pz, carry)
+pz += 1
+carry = SHIFT
+assert carry = MASK
+if carry:
+z.setdigit(pz, z.widedigit(pz) + carry)
+assert (carry  SHIFT) == 0
+i += 1
 z._normalize()
 return z
 
@@ -1081,9 +1085,10 @@
 # Successive slices of b are copied into bslice.
 #bslice = rbigint([0] * asize, 1)
 # XXX we cannot pre-allocate, see comments below!
+
+nbdone = 0;
 bslice = rbigint([NULLDIGIT], 1)
 
-nbdone = 0;
 while bsize  0:
 nbtouse = min(bsize, asize)
 
@@ -1098,7 +1103,7 @@
 
 # Add into result.
 _v_iadd(ret, nbdone, ret.numdigits() - nbdone,
- product, product.numdigits())
+product, product.numdigits())
 
 bsize -= nbtouse
 nbdone += nbtouse
@@ -1106,7 +,6 @@
 ret._normalize()
 return ret
 
-
 def _inplace_divrem1(pout, pin, n, size=0):
 
 Divide bigint pin by non-zero digit n, storing quotient
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit

[pypy-commit] pypy improve-rbigint: Cleanup

[Stian Andreassen]

Author: Stian Andreassen
Branch: improve-rbigint
Changeset: r56310:db57975370e1
Date: 2012-06-21 22:22 +0200
http://bitbucket.org/pypy/pypy/changeset/db57975370e1/

Log:Cleanup

diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -858,7 +858,7 @@
 carry = SHIFT
 if carry:
 z.setdigit(pz, z.widedigit(pz) + carry)
-assert (carry  63) == 0
+assert (carry  SHIFT) == 0
 i += 1
 else:
 # gradeschool long mult
@@ -1085,10 +1085,9 @@
 # Successive slices of b are copied into bslice.
 #bslice = rbigint([0] * asize, 1)
 # XXX we cannot pre-allocate, see comments below!
+bslice = rbigint([NULLDIGIT], 1)
 
 nbdone = 0;
-bslice = rbigint([NULLDIGIT], 1)
-
 while bsize  0:
 nbtouse = min(bsize, asize)
 
@@ -1196,7 +1195,6 @@
 i += 1
 return borrow
 
-
 def _muladd1(a, n, extra=0):
 Multiply by a single digit and add a single digit, ignoring the sign.
 
@@ -1214,7 +1212,6 @@
 z._normalize()
 return z
 
-
 def _x_divrem(v1, w1):
  Unsigned bigint division with remainder -- the algorithm 
 size_w = w1.numdigits()
@@ -1289,7 +1286,6 @@
 rem, _ = _divrem1(v, d)
 return a, rem
 
-
 def _divrem(a, b):
  Long division with remainder, top-level routine 
 size_a = a.numdigits()
___
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit