Carl Friedrich Bolz-Tereick pushed to branch branch/better-storesink-2 at PyPy / pypy
Commits: 5af4ae79 by Carl Friedrich Bolz-Tereick at 2022-09-12T22:12:41+02:00 #3805 implement a sub-quadratic algorithm for int(<some huge string>), O(len(s) ** 1.58) adapted from pure python code in https://github.com/python/cpython/pull/96673 --HG-- branch : rbigint-fromstr-subquadratic - - - - - 902a801b by Carl Friedrich Bolz-Tereick at 2022-09-13T20:55:03+02:00 fix rounding, thanks bjorn martinsson --HG-- branch : rbigint-fromstr-subquadratic - - - - - e10e338f by Carl Friedrich Bolz-Tereick at 2022-09-13T22:27:38+02:00 test for previous commit --HG-- branch : rbigint-fromstr-subquadratic - - - - - 9dd7b25e by Carl Friedrich Bolz-Tereick at 2022-09-15T12:49:31+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - c431c200 by Carl Friedrich Bolz-Tereick at 2022-09-24T12:32:19+02:00 intermediate checkin: resurrect the lopsided karatsuba multiplication case which was wrongly removed it helps a lot for unbalanced huge multiplications. before this commit, unbalanced multiplications would fall back to using O(n**2) base case multiplication, no matter their size not quite sure yet which algorithm to use, CPython's or my own. both fix the complexity, my own seems unexpectedly faster. --HG-- branch : rbigint-fromstr-subquadratic - - - - - dde396a4 by Carl Friedrich Bolz-Tereick at 2022-09-24T12:35:57+02:00 oops --HG-- branch : rbigint-fromstr-subquadratic - - - - - fc674e42 by Carl Friedrich Bolz-Tereick at 2022-09-24T13:22:17+02:00 save a useless multiplication by 0 in the base case --HG-- branch : rbigint-fromstr-subquadratic - - - - - 50615b01 by Carl Friedrich Bolz-Tereick at 2022-09-24T21:04:27+02:00 introduce accessors for size and sign --HG-- branch : rbigint-fromstr-subquadratic - - - - - 8e82e35e by Carl Friedrich Bolz-Tereick at 2022-10-06T15:28:13+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - 11a53919 by Carl Friedrich Bolz-Tereick at 2022-10-06T15:33:13+02:00 Backed out changeset e4c06197fb2d my ideas in that direction didn't help and it breaks other things --HG-- branch : rbigint-fromstr-subquadratic - - - - - 8731e5e2 by Carl Friedrich Bolz-Tereick at 2022-10-09T17:12:39+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - a0b25a34 by Carl Friedrich Bolz-Tereick at 2022-10-09T21:25:18+02:00 implement lopsided mul in the naive way, in my benchmarks it's consistently faster than CPython's approach --HG-- branch : rbigint-fromstr-subquadratic - - - - - 89fdef2c by Carl Friedrich Bolz-Tereick at 2022-10-09T21:25:50+02:00 some more hypothesis tests for string conversion --HG-- branch : rbigint-fromstr-subquadratic - - - - - 713f9727 by Carl Friedrich Bolz-Tereick at 2022-10-09T21:46:38+02:00 make rbigint.floordiv and rbigint.mod also use rbigint.divmod, to benefit from its better complexity for huge inputs --HG-- branch : rbigint-fromstr-subquadratic - - - - - b96d3c4f by Carl Friedrich Bolz-Tereick at 2023-05-18T14:39:43+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - babe43a0 by Carl Friedrich Bolz-Tereick at 2023-05-18T16:26:56+02:00 fix import - - - - - b88b532d by Carl Friedrich Bolz-Tereick at 2023-05-18T16:29:09+02:00 merge heads --HG-- branch : rbigint-fromstr-subquadratic - - - - - 4f8eb614 by Carl Friedrich Bolz-Tereick at 2023-05-18T17:35:28+02:00 some cleanups in the tests --HG-- branch : rbigint-fromstr-subquadratic - - - - - 193767c6 by Carl Friedrich Bolz-Tereick at 2023-05-18T22:04:12+02:00 some additional hypothesis tests that don't rely on the underlying long implementation --HG-- branch : rbigint-fromstr-subquadratic - - - - - 3e71db3d by Carl Friedrich Bolz-Tereick at 2023-05-19T09:10:42+02:00 fix wrong test - - - - - 46c30169 by Carl Friedrich Bolz-Tereick at 2023-05-19T09:22:10+02:00 - ouch, one of the tests was not actually checking anything - add a test to check that the big divmod path is actually used --HG-- branch : rbigint-fromstr-subquadratic - - - - - cca76a1f by Carl Friedrich Bolz-Tereick at 2023-05-20T12:00:19+02:00 some more tests for fromrarith_int --HG-- branch : rbigint-fromstr-subquadratic - - - - - b6b4fcdc by Carl Friedrich Bolz-Tereick at 2023-05-20T12:00:38+02:00 after some more testing: we can reduce the minimum size for when to use the new algorithm for rbigint.fromstr --HG-- branch : rbigint-fromstr-subquadratic - - - - - 001e4396 by Carl Friedrich Bolz-Tereick at 2023-05-20T12:13:53+02:00 use a string builder --HG-- branch : rbigint-fromstr-subquadratic - - - - - 5e853322 by Carl Friedrich Bolz-Tereick at 2023-05-20T20:18:31+02:00 reduce the runtime of this hypothesis test --HG-- branch : rbigint-fromstr-subquadratic - - - - - 4f7edf0c by Carl Friedrich Bolz-Tereick at 2023-05-23T08:49:18+02:00 merge rbigint-fromstr-subquadratic implement the base 10 string-to-int conversion using a divide an conquer algorithm with complexity O(n**1.58). The algorithm is due to Bjorn Martinsson. In the process, I discovered that the "lopsided" case of karatsuba multiplication was removed for no good reason at some point. I re-measured and reimplemented it. - - - - - 69d07ce7 by Matti Picus at 2023-05-24T13:44:23+03:00 update release note - - - - - 1954fe02 by Matti Picus at 2023-05-24T13:48:59+03:00 make note appear - - - - - e1698c85 by Matti Picus at 2023-05-24T13:58:12+03:00 typo - - - - - dd485269 by Matti Picus at 2023-05-24T21:00:36+03:00 Added tag release-pypy2.7-v7.3.12rc2 for changeset 4ac174a992a3 - - - - - 51a67f76 by Matti Picus at 2023-05-24T21:01:05+03:00 Added tag release-pypy3.9-v7.3.12rc2 for changeset a6c2a04c0d03 - - - - - 1b9d1d15 by Matti Picus at 2023-05-24T21:01:23+03:00 Added tag release-pypy3.10-v7.3.12rc2 for changeset 07561e2940ea - - - - - 009e2e91 by Matti Picus at 2023-05-29T00:05:35+03:00 update versions.json for the rc2 release - - - - - 99a7389e by Carl Friedrich Bolz-Tereick at 2023-05-30T14:17:11+02:00 try to get rid of the weird _cache mechanism in the History class --HG-- branch : jit-history-no-cache - - - - - 155a1b3d by Carl Friedrich Bolz-Tereick at 2023-05-30T14:37:10+02:00 fix the somewhat fiddly exception stuff --HG-- branch : jit-history-no-cache - - - - - c14ddc55 by Carl Friedrich Bolz-Tereick at 2023-05-30T14:53:51+02:00 fix test --HG-- branch : jit-history-no-cache - - - - - a28ccd5c by Carl Friedrich Bolz-Tereick at 2023-05-30T15:15:39+02:00 remove copy_value_from --HG-- branch : jit-history-no-cache - - - - - bd353a7b by Carl Friedrich Bolz-Tereick at 2023-05-30T15:34:13+02:00 fix --HG-- branch : jit-history-no-cache - - - - - c123e4e6 by Carl Friedrich Bolz-Tereick at 2023-05-30T16:17:34+02:00 add the value to the *FrontendOp constructors --HG-- branch : jit-history-no-cache - - - - - 68a32b71 by Carl Friedrich Bolz-Tereick at 2023-05-30T21:01:11+02:00 fix virtualizables maybe --HG-- branch : jit-history-no-cache - - - - - 83f640bb by Matti Picus at 2023-05-31T14:47:29+03:00 update openssl (1.1.1u, 3.0.9) and lzma (5.2.10) - - - - - b320d3c2 by Carl Friedrich Bolz-Tereick at 2023-05-31T18:01:30+02:00 a few fixes --HG-- branch : jit-history-no-cache - - - - - 5b2e7691 by Carl Friedrich Bolz-Tereick at 2023-05-31T21:17:31+02:00 fixes --HG-- branch : jit-history-no-cache - - - - - 18e44485 by Carl Friedrich Bolz-Tereick at 2023-05-31T21:18:11+02:00 merge jit-history-no-cache: small refactoring in the History class, it can now use the proper opencoder encoding of a trace immediately, not only after the inputargs are known. this is a small simplification only. - - - - - 15b62b11 by Carl Friedrich Bolz-Tereick at 2023-05-31T21:20:31+02:00 merge heads - - - - - 07841690 by Carl Friedrich Bolz-Tereick at 2023-05-31T21:36:43+02:00 d77a1ac14a7e leads to the two extra operations, which are a bit annoying but not that costly - - - - - 087d670b by Carl Friedrich Bolz-Tereick at 2023-05-31T22:17:05+02:00 merge default --HG-- branch : better-storesink-2 - - - - - 28 changed files: - .hgtags - lib_pypy/pypy_tools/build_cffi_imports.py - pypy/doc/release-v7.3.12.rst - pypy/module/pypyjit/test_pypy_c/test_misc.py - pypy/tool/release/check_versions.py - pypy/tool/release/repackage.sh - pypy/tool/release/versions.json - rpython/jit/backend/x86/runner.py - rpython/jit/metainterp/history.py - rpython/jit/metainterp/opencoder.py - rpython/jit/metainterp/optimizeopt/test/test_util.py - rpython/jit/metainterp/pyjitpl.py - rpython/jit/metainterp/resoperation.py - rpython/jit/metainterp/resume.py - rpython/jit/metainterp/test/test_compile.py - rpython/jit/metainterp/test/test_heapcache.py - rpython/jit/metainterp/test/test_history.py - rpython/jit/metainterp/test/test_opencoder.py - rpython/jit/metainterp/test/test_pyjitpl.py - rpython/jit/metainterp/test/test_resume.py - rpython/jit/metainterp/test/test_warmstate.py - rpython/jit/metainterp/virtualizable.py - rpython/jit/metainterp/warmstate.py - rpython/jit/tool/oparser.py - rpython/rlib/rbigint.py - rpython/rlib/rstring.py - rpython/rlib/test/test_rbigint.py - rpython/rlib/unicodedata/test/test_unicodedata.py View it on Heptapod: https://foss.heptapod.net/pypy/pypy/-/compare/9d40643bd860a4c8a7eb9459b1b16d4388d5832b...087d670b81af87d88917c40e34f149a5c642cb28 -- View it on Heptapod: https://foss.heptapod.net/pypy/pypy/-/compare/9d40643bd860a4c8a7eb9459b1b16d4388d5832b...087d670b81af87d88917c40e34f149a5c642cb28 You're receiving this email because of your account on foss.heptapod.net.
_______________________________________________ pypy-commit mailing list -- pypy-commit@python.org To unsubscribe send an email to pypy-commit-le...@python.org https://mail.python.org/mailman3/lists/pypy-commit.python.org/ Member address: arch...@mail-archive.com
