summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
...
* Added a test specifically to tickle Karatsuba; it costs no appreciableTim Peters2002-08-131-0/+26
| | | | runtime.
* Add a missing call to _strclass().Jeremy Hylton2002-08-131-1/+1
|
* Fixed error in new comment.Tim Peters2002-08-131-4/+3
|
* k_mul(): The fix for (ah+al)*(bh+bl) spilling 1 bit beyond the allocatedTim Peters2002-08-131-8/+44
| | | | | | | | | | space is no longer needed, so removed the code. It was only possible when a degenerate (ah->ob_size == 0) split happened, but after that fix went in I added k_lopsided_mul(), which saves the body of k_mul() from seeing a degenerate split. So this removes code, and adds a honking long comment block explaining why spilling out of bounds isn't possible anymore. Note: ff we end up spilling out of bounds anyway <wink>, an assert in v_iadd() is certain to trigger.
* Regress Guido's change of 2002/08/06 to check for the zlib versionBarry Warsaw2002-08-131-4/+13
| | | | | 1.1.4. Redhat hasn't upgraded but does provide a patched 1.1.3 package, so checking for 1.1.4 just makes life difficult.
* Allow docstrings to be removed during compilation for *SLOT macro and friendsNeal Norwitz2002-08-131-3/+5
|
* Add tests for including __dict__ and/or __weakref__ in __slots__.Guido van Rossum2002-08-131-1/+50
| | | | Add some more rigor to slotmultipleinheritance().
* SF bug #574235, convert_path fails with empty pathnameNeal Norwitz2002-08-131-2/+4
|
* Allow docstrings to be removed during compilationNeal Norwitz2002-08-131-3/+3
|
* Add test for SF bug # 575229, multiple inheritance w/ slots dumps coreNeal Norwitz2002-08-131-0/+11
| | | | Fix already checked in by Guido
* Remove ugly irregular spaces from in front of some comments.Fred Drake2002-08-131-3/+3
|
* Bug #556025: list(xrange(1e9)) --> seg faultJason Tishler2002-08-131-0/+5
| | | | | | | | | Close the bug report again -- this time for Cygwin due to a newlib bug. See the following for the details: http://sources.redhat.com/ml/newlib/2002/msg00369.html Note that this commit is only a documentation (i.e., comment) change.
* Add an improvement wrinkle to Neil Schemenauer's change to int_mulGuido van Rossum2002-08-131-2/+4
| | | | | | | (rev. 2.86). The other type is only disqualified from sq_repeat when it has the CHECKTYPES flag. This means that for extension types that only support "old-style" numeric ops, such as Zope 2's ExtensionClass, sq_repeat still trumps nb_multiply.
* test_division(): Added one larger digits value, to ensure that theTim Peters2002-08-131-1/+2
| | | | "lopsided Karatsuba" driver also gets some exercise.
* Machines-- and Python --are a lot faster in relevant ways since thisTim Peters2002-08-131-3/+5
| | | | | | test was written. So boosted the number of "digits" this generates, and also beefed up the "* / divmod" test to tickle numbers big enough to trigger the Karatsuba algorithm. It takes about 2 seconds now on my box.
* Fix comment for PyLong_AsUnsignedLong() to say that the return valueGuido van Rossum2002-08-131-1/+1
| | | | is an *unsigned* long.
* Fix wanrings about unsigned hex constants.Guido van Rossum2002-08-121-2/+2
|
* k_lopsided_mul(): This allocated more space for bslice than necessary.Tim Peters2002-08-121-1/+1
|
* The auto-reply text for the python-docs address. This is not automaticallyFred Drake2002-08-121-0/+171
| | | | updated when checkins are made, but I can get that updated when needed.
* Added new function k_lopsided_mul(), which is much more efficient thanTim Peters2002-08-122-13/+75
| | | | | | | | k_mul() when inputs have vastly different sizes, and a little more efficient when they're close to a factor of 2 out of whack. I consider this done now, although I'll set up some more correctness tests to run overnight.
* Don't use hex constants representing negative numbers.Guido van Rossum2002-08-121-1/+1
|
* Suppress warnings about test_grammar.py that can't be suppressed insideGuido van Rossum2002-08-121-0/+6
| | | | that file itself (because it's the parser that reports them).
* Use PyErr_WarnExplicit() to warn about hex/oct constants, so theGuido van Rossum2002-08-121-4/+9
| | | | correct filename and line number are reported.
* Updated for the current state of affairs.Jack Jansen2002-08-121-20/+27
|
* New names.Guido van Rossum2002-08-121-0/+2
|
* Make sure that *any* object whose id() is used as a memo key is keptGuido van Rossum2002-08-121-2/+1
| | | | alive in the memo. This fixes SF bug 592567.
* k_mul(): Moved an assert down. In a debug build, interrupting aTim Peters2002-08-121-2/+2
| | | | | multiply via Ctrl+C could cause a NULL-pointer dereference due to the assert.
* k_mul(): Heh -- I checked in two fixes for the last problem. Only keepTim Peters2002-08-121-2/+2
| | | | the good one <wink>. Also checked in a test-aid by mistake.
* k_mul(): White-box testing turned up that (ah+al)*(bh+bl) can, in rareTim Peters2002-08-121-3/+11
| | | | | | | | | cases, overflow the allocated result object by 1 bit. In such cases, it would have been brought back into range if we subtracted al*bl and ah*bh from it first, but I don't want to do that because it hurts cache behavior. Instead we just ignore the excess bit when it appears -- in effect, this is forcing unsigned mod BASE**(asize + bsize) arithmetic in a case where that doesn't happen all by itself.
* Fix MSVC warnings.Guido van Rossum2002-08-121-2/+2
|
* Refactor how __dict__ and __weakref__ interact with __slots__.Guido van Rossum2002-08-121-55/+147
| | | | | | | | | | | | | | | | | | | | | | | 1. You can now have __dict__ and/or __weakref__ in your __slots__ (before only __weakref__ was supported). This is treated differently than before: it merely sets a flag that the object should support the corresponding magic. 2. Dynamic types now always have descriptors __dict__ and __weakref__ thrust upon them. If the type in fact does not support one or the other, that descriptor's __get__ method will raise AttributeError. 3. (This is the reason for all this; it fixes SF bug 575229, reported by Cesar Douady.) Given this code: class A(object): __slots__ = [] class B(object): pass class C(A, B): __slots__ = [] the class object for C was broken; its size was less than that of B, and some descriptors on B could cause a segfault. C now correctly inherits __weakrefs__ and __dict__ from B, even though A is the "primary" base (C.__base__ is A). 4. Some code cleanup, and a few comments added.
* x_mul(): Made life easier for C optimizers in the "grade school"Tim Peters2002-08-121-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | algorithm. MSVC 6 wasn't impressed <wink>. Something odd: the x_mul algorithm appears to get substantially worse than quadratic time as the inputs grow larger: bits in each input x_mul time k_mul time ------------------ ---------- ---------- 15360 0.01 0.00 30720 0.04 0.01 61440 0.16 0.04 122880 0.64 0.14 245760 2.56 0.40 491520 10.76 1.23 983040 71.28 3.69 1966080 459.31 11.07 That is, x_mul is perfectly quadratic-time until a little burp at 2.56->10.76, and after that goes to hell in a hurry. Under Karatsuba, doubling the input size "should take" 3 times longer instead of 4, and that remains the case throughout this range. I conclude that my "be nice to the cache" reworkings of k_mul() are paying.
* k_mul() and long_mul(): I'm confident that the Karatsuba algorithm isTim Peters2002-08-122-12/+40
| | | | | | | | correct now, so added some final comments, did some cleanup, and enabled it for all long-int multiplies. The KARAT envar no longer matters, although I left some #if 0'ed code in there for my own use (temporary). k_mul() is still much slower than x_mul() if the inputs have very differenent sizes, and that still needs to be addressed.
* Portable way of producing unsigned 32-bit hex output to print theGuido van Rossum2002-08-121-2/+4
| | | | CRCs.
* Shut up warnings about hex()/oct() that can't be avoided.Guido van Rossum2002-08-122-0/+8
|
* Avoid warnings about <<. external_attr is now an unsigned long.Guido van Rossum2002-08-121-2/+2
|
* k_mul: Rearranged computation for better cache use. Ignored overflowTim Peters2002-08-121-60/+50
| | | | | | | | | (it's possible, but should be harmless -- this requires more thought, and allocating enough space in advance to prevent it requires exactly as much thought, to know exactly how much that is -- the end result certainly fits in the allocated space -- hmm, but that's really all the thought it needs! borrows/carries out of the high digits really are harmless).
* Correct PyAPI_FUNC to PyAPI_DATA - sorry Jack.Mark Hammond2002-08-121-2/+2
|
* Add name mangling for new PyUnicode_FromOrdinal() and fix declarationMarc-André Lemburg2002-08-121-1/+3
| | | | to use new extern macro.
* Excise DL_EXPORT from Include.Mark Hammond2002-08-1251-673/+669
| | | | Thanks to Skip Montanaro and Kalle Svensson for the patches.
* x_mul(): This failed to normalize its result.Tim Peters2002-08-121-6/+18
| | | | | | | | | | | | | | | | | | | | | | k_mul(): This didn't allocate enough result space when one input had more than twice as many bits as the other. This was partly hidden by that x_mul() didn't normalize its result. The Karatsuba recurrence is pretty much hosed if the inputs aren't roughly the same size. If one has at least twice as many bits as the other, we get a degenerate case where the "high half" of the smaller input is 0. Added a special case for that, for speed, but despite that it helped, this can still be much slower than the "grade school" method. It seems to take a really wild imbalance to trigger that; e.g., a 2**22-bit input times a 1000-bit input on my box runs about twice as slow under k_mul than under x_mul. This still needs to be addressed. I'm also not sure that allocating a->ob_size + b->ob_size digits is enough, given that this is computing k = (ah+al)*(bh+bl) instead of k = (ah-al)*(bl-bh); i.e., it's certainly enough for the final result, but it's vaguely possible that adding in the "artificially" large k may overflow that temporarily. If so, an assert will trigger in the debug build, but we'll probably compute the right result anyway(!).
* Introduced helper functions v_iadd and v_isub, for in-place digit-vectorTim Peters2002-08-121-29/+75
| | | | | | | addition and subtraction. Reworked the tail end of k_mul() to use them. This saves oodles of one-shot longobject allocations (this is a triply- recursive routine, so saving one allocation in the body saves 3**n allocations at depth n; we actually save 2 allocations in the body).
* New news about __class__ assignment restrictions and speed-up ofGuido van Rossum2002-08-121-43/+51
| | | | | | | new-style object creation/deallocation. Moved all news about type/class unification and new-stype classes to a separate section at the top.
* Revert what looks like a typo from the last checkinNeal Norwitz2002-08-121-1/+1
|
* k_mul(): Repaired another typo in another comment.Tim Peters2002-08-121-1/+1
|
* k_mul(): Repaired typo in comment.Tim Peters2002-08-121-1/+1
|
* Cautious introduction of a patch that started fromTim Peters2002-08-123-88/+272
| | | | | | | | SF 560379: Karatsuba multiplication. Lots of things were changed from that. This needs a lot more testing, for correctness and speed, the latter especially when bit lengths are unbalanced. For now, the Karatsuba code gets invoked if and only if envar KARAT exists.
* Fixed misspelling in comment.Tim Peters2002-08-111-1/+1
|
* int_lshift(): Simplified/sped overflow-checking.Tim Peters2002-08-111-4/+2
|
* Extend stripid() to handle strings ending in more than one '>'.Ka-Ping Yee2002-08-111-37/+36
| | | | | Add resolve() to handle looking up objects and names (fix SF bug 586931). Add a nicer error message when given a filename that doesn't exist.
generated by cgit v0.12 at 2025-08-10 06:10:43 (GMT)