Tim Peters added the comment:
About:
TableSize = 101
limits = bytearray(TableSize)
for n in range(0, TableSize):
for k in range(0, n+1):
if comb(n, k) != comb_small(n, k):
(and regardless of whether the last line is replaced with the later correction):
Did
Tim Peters added the comment:
All cool. Since I doubt these new rounding modes will get much use anyway, it's
not worth arguing about. If I were to do this for myself, the rounding argument
would be one of the three values {-1, 0, +1}, which are already more than good
enough as mnemonics
Tim Peters added the comment:
FYI, I had a simpler derivation in mind. Say
sqrt(n) = r + f
where r = isqrt(n) and 0 <= f < 1. Then
sqrt(4n) = 2 * sqrt(n) = 2*(r + f) = 2r + 2f, with 0 <= 2f < 2.
If f < 0.5, 2f < 1, so isqrt(4n) = 2r, and we shouldn't round r up either.
Tim Peters added the comment:
>> can we use the decimal module's names for the supported
>> rounding modes?
> I'm not sure those make sense because we never get to
> exactly half. There is only floor, ceil, and round,
> not half_up, half_even, etc.
So use de
Tim Peters added the comment:
A timing confounder: I see that CPython's _Py_popcount32() only tries to use
the relevant blazing fast hardware instruction if defined(__clang__) ||
defined(__GNUC__). On Windows, it's a long-winded bit-fiddling dance.
So which of xor-popcount and add-up-up
Tim Peters added the comment:
Raymond, using the count of trailing zeroes instead is exactly what I suggested
before, here:
https://bugs.python.org/issue37295#msg409000
So Mark & I already batted that around. For whatever reasons he had, though, he
stuck with the xor-popcount appr
Tim Peters added the comment:
[Mark]
> def risqrt(n):
>return (isqrt(n<<2) + 1) >> 1
Sweet! New one on me - did you invent this? It's slick :-)
I'd be happy to see recipes added to the docs for rounded and ceiling flavors
of isqrt, but am dubious about the valu
Tim Peters added the comment:
If people are keen to speed comb() for larger arguments, the approach in
Stefan's "comb_with_primes.py" is very much worth looking at. I've played with
that idea before, and it runs circles around any other approach I've seen.
The only divisio
Tim Peters added the comment:
Please don't use "long long". It usually introduces platform dependence where
none is intended, or helpful. PEP 7 requires that the compiler in use supply
the fixed-width integer types defined by C99's stdint.h[1]. These are:
int8_t
int16_t
int32
Tim Peters added the comment:
No problem, Mark! I just prefer the shallowest approaches that are "good
enough". If it's materially faster to use xors and a popcount instead, fine by
me, just provided a comment points to a clue about why that works.
BTW, the later xor version w
Tim Peters added the comment:
I see no use of 128-bit ints in the CPython core. Advice: forget it.
int64_t and uint64_t are required by C99, and are used many places in the core.
Advice: use freely.
Note that if tables of "odd part mod 2**64" and "number of trailing zeroe
Tim Peters added the comment:
Clever, Mark! Very nice.
The justification for the shift count isn't self-evident, and appears to me to
be an instance of the generalization of Kummer's theorem to multinomial
coefficients. I think it would be clearer at first sight to rely instead on
that 2
Tim Peters added the comment:
Just curious about why the focus on the newer exp2 and log2? Logs are logs, and
the "natural" `exp()` and `log()` should work just as well. On Windows, exp2()
is particularly poor for now (I've seen dozens of cases of errors over 2 ulp,
with exp2(x)
Tim Peters added the comment:
Across millions of tries, same thing: Windows exp2 is off by at least 1 ulp
over a third of the time, and by over 2 ulp about 3 times per million. Still
haven't seen pow(2, x) off by as much as 0.52 ulp.
>From its behavior, it appears Windows implements exp
Tim Peters added the comment:
Bad news: on Windows, exp2(x) is way worse then pow(2, x). Here I changed the
loop of Mark's little driver like so:
differ = really_bad = 0
worst = 0.0
for n in range(100_000):
x = random.uniform(-1000.0, 999.0) + random.random
Tim Peters added the comment:
I agree with closing this - I don't know of real use cases either.
Serhiy, essentially all LSD radix sorts are stable, and rely on that for their
own correctness. MSD radix sorts vary.
--
___
Python tracker
<ht
Tim Peters added the comment:
I'll add that the rounding mode is intended to ease emulating fixed-point
arithmetic. The decimal spec claimed that was a goal, but there really isn't
any direct support for saying, e.g., "I want two digits after the decimal
point". Only for specif
Tim Peters added the comment:
Not a good idea in general - this rounding mode is _mostly_ "to zero", and
isn't intended for chains of operations. I don't believe I've ever seen it used
in a real program, so the current "no example at all" is a fair represent
Tim Peters added the comment:
But I would like to leave it alone. Extended precision simply is not an issue
on any current platform I'm aware of ("not even Windows"), and I would, e.g.,
hate trying to explain to users why
1 / 2731 != 1.0 / 2731.0
(assuming we're not also
Tim Peters added the comment:
> Objects/longobject.c::long_true_divide() uses ldexp() internally.
> Will it suffer the same issues with subnormals on Windows?
Doesn't look like it will. In context, looks like it's ensuring that ldexp can
only lose trailing 0 bits, so that _whatever_
Tim Peters added the comment:
Mark, ya, MS's Visual Studio's ldexp() has, far as I know, always worked this
way. The code I showed was run under the 2019 edition, which we use to build
the Windows CPython.
Raymond,
x = float(i)
is screamingly obvious at first glance.
x = i/1
Tim Peters added the comment:
Note that, on Windows, ldexp() in the presence of denorms can truncate.
Division rounds, so
assert x / 2**i == ldexp(x, -i)
can fail.
>>> import math
>>> d = math.nextafter(0.0, 1.0)
>>> d
5e-324
>>> d3 = 7 * d # .
Tim Peters added the comment:
Changed stage back to "needs patch", since Raymond appears to have closed his
PR. Raymond, what's up with that?
--
stage: patch review -> needs patch
___
Python tracker
<https://bugs.pytho
Tim Peters added the comment:
Serhiy, we haven't documented such stuff, and, indeed, I've been burned by it
but much more often in the case of multiprocessing.Process. But note that I'm
SWAPPING the order of your last two lines. In the original, you mutated the
argument _before_ starting
Change by Tim Peters :
--
title: Promise that the long-time truth that `args=list` works -> Promise the
long-time truth that `args=list` works
___
Python tracker
<https://bugs.python.org/issu
New submission from Tim Peters :
A number of contexts allow specifying a tuple of arguments to be passed later
to a function. The Thread constructor is a fine example, and happened to come
up (again! for me) here today:
https://stackoverflow.com/questions/69858950/why-do-we-have-to-add-comma
Change by Tim Peters :
--
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python.or
Tim Peters added the comment:
New changeset 51ed2c56a1852cd6b09c85ba81312dc9782772ce by Tim Peters in branch
'main':
bpo-45530: speed listobject.c's unsafe_tuple_compare() (GH-29076)
https://github.com/python/cpython/commit/51ed2c56a1852cd6b09c85ba81312dc9782772ce
Tim Peters added the comment:
To be concrete, here's an implementation of a full-blown, stable lexicographic
sort based on "bucket refinement". `xs` is a list of sequences to be sorted in
lexicographic order. The types of the sequences don't matter (lists, tuples,
strings, ..
Tim Peters added the comment:
Stefan, thanks - I think I understand what you're driving at now.
You're (re)discovering that sorting by lexicographic ordering rules is
_inherently_ suboptimal if list elements can only be compared "starting at
index 0" each time. Not just tuples
Tim Peters added the comment:
+1 "in theory". But I too don't know whether any platforms would be adversely
affected, or how to find out :-(
--
nosy: +tim.peters
___
Python tracker
<https://bugs.python.o
Tim Peters added the comment:
> I see you mentioned that PyObject_RichCompareBool(..., Py_EQ) might be
> faster for example because it checks identity.
For example, in tupsort.py replace
xs = [random() for _ in range(length)]
with
xs = ['z' * 100 for _ in range(
Tim Peters added the comment:
I think Dennis's example is fatal: from section 6.10 ("Comparisons"):
"""
Comparisons can be chained arbitrarily, e.g., `x < y <= z` is equivalent to `x
< y and y <= z`, except that y is evaluated only once (but in both ca
Tim Peters added the comment:
It's rare that an optimization is a _pure_ win. Some cases win, others lose.
There's almost never "a proof" of net gain ending with "QED".
Of course it's dead easy to construct examples where "many duplicates in the
first tuple posit
Tim Peters added the comment:
> Elliot shortly after retrated from the approach, saying he
> rewrote unsafe_tuple_compare to move the less-than after
> the equality testing, to make sure it's 100% consistent".
I remember at the time having no idea what he meant by that comment
Tim Peters added the comment:
Stefan, I looked at that old PR and can't find anywhere I suggested that he
change the unsafe_tuple_compare() logic. I just _asked_ him "I'm curious about
what the patched Python prints for this program:".
And, in fact, that program showed th
Tim Peters added the comment:
Stefan, I have scant memory of ever caring, but, if I did, I got over it ;-)
>>> math.nan == math.nan
False
>>> {math.nan : 5}[math.nan]
5
That is, PyObject_RichCompareBool() takes object identity as overriding __eq__;
that's why the
Change by Tim Peters :
--
assignee: -> tim.peters
___
Python tracker
<https://bugs.python.org/issue45530>
___
___
Python-bugs-list mailing list
Unsubscrib
Change by Tim Peters :
--
keywords: +patch
pull_requests: +27345
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/29076
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
The attached tupsort.py gives a simple. focused example. Typical output on my
box:
float 3.10
(float,) 11.75
[float]25.68
It's sorting a large list of floats. In the first line the list contains plain
floats. In the second line, each float
Tim Peters added the comment:
FYI, this is fallout from a StackOverflow mystery:
https://stackoverflow.com/questions/69468552/efficiency-of-sorting-by-multiple-keys-in-python/69610671#
--
___
Python tracker
<https://bugs.python.org/issue45
New submission from Tim Peters :
The code could typically be faster if it did what its comments imply it does:
skip the expense of PyObject_RichCompareBool() entirely for the first pair of
tuple elements. It actually always calls PyObject_RichCompareBool() on the
first pair, and only
Tim Peters added the comment:
CPython's log() builds on the platform C's libm facilities, and C simply
doesn't define primitives capable of producing a worst-case < 1 ulp error
2-argument log in reasonable time. Instead we have to build it out of two
separate log operations, and a divis
Tim Peters added the comment:
Please stop re-opening this. The issue tracker is not a "help desk", and your
confusions aren't necessarily Python bugs ;-) If you post something that looks
like an actual bug, I'll re-open the report.
SequenceMatcher works on sequences.
Html
Tim Peters added the comment:
I have no idea why you think the result should be 0.2. 0.5630188679245283 looks
correct to me with autojunk disabled:
sm = SequenceMatcher(None, a, b, autojunk=False)
total = 0
for m in sm.get_matching_blocks():
print(m, repr(a[m.a : m.a + m.size
Tim Peters added the comment:
Unfortunately, you're getting hurt by the "autojunk" feature (see the docs). If
you turn it off, you'll get a result much more to your liking:
>>> print(SequenceMatcher(None, a, b).ratio())
0.3431803896920176
>>> print(SequenceMatche
Change by Tim Peters :
--
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python.or
Tim Peters added the comment:
New changeset 5cb4c672d855033592f0e05162f887def236c00a by Tim Peters in branch
'main':
bpo-34561: Switch to Munro & Wild "powersort" merge strategy. (#28108)
https://github.com/python/cpython/commit/5cb4c672d855033592f0e05162
Tim Peters added the comment:
I created a PR that implements the powersort merge strategy:
https://github.com/python/cpython/pull/28108
Across all the time this issue report has been open, that strategy continues to
be the top contender. Enough already ;-) It's indeed a more difficult
Change by Tim Peters :
--
keywords: +patch
pull_requests: +26550
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/28108
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
New runstack.py mostly adds comments about a surprise: the idea that
length-adaptive ShiversSort eeks out better results than powersort appears
nearly unique to the specific "0.80" cutoff used in the random-case generation
code to pick between t
Tim Peters added the comment:
And another runstack.py adds `shivers4()`, which reworks `shivers3()`
(length-adaptive ShiversSort) so that division, log2(), and floor() aren't used
anymore. It does need a loop, though, which needs to go around a number of
times `k` such that k
Change by Tim Peters :
Removed file: https://bugs.python.org/file50242/runstack.py
___
Python tracker
<https://bugs.python.org/issue45045>
___
___
Python-bugs-list mailin
Change by Tim Peters :
--
Removed message: https://bugs.python.org/msg400568
___
Python tracker
<https://bugs.python.org/issue45045>
___
___
Python-bugs-list m
Tim Peters added the comment:
And another runstack.py adds `shivers4()`, which reworks `shivers3()`
(length-adaptive ShiversSort) so that division, log2(), and floor() aren't used
anymore. It does need a loop, though, which needs to go around a number of
times `k` such that k
Tim Peters added the comment:
Added new runstack.py.
New `shivers2()` adds the implementation of adaptive ShiversSort from Vincent's
later paper. While the code is simpler, it appears to behave identically.
New `shivers3()` adds, from the same paper, the new "length-adaptive
Shiver
Tim Peters added the comment:
The merge order was mentioned on python-dev today, and a quick web searched
turned up a revision of Vincent Jugé's "Adaptive Shivers Sort: An Alternative
Sorting Algorithm" paper I hadn't seen before:
https://arxiv.org/pdf/1809.08411.pdf
Its "
Tim Peters added the comment:
The CPython Windows installer has a "thank you" box at the end:
"""
Special Windows thanks to Mark Hammond, without whose years of freely shared
Windows expertise, Python for Windows would still be Python for DOS.
""
Tim Peters added the comment:
Sorry, I'm just going to close this. For values of all numeric types now,
`bool(x)` returns the same as `x != type(x)(0)`. Besides being
backward-incompatible, making an exception for NaN would be jarringly
inconsistent.
Note that you don't need numpy
Tim Peters added the comment:
The binary power operator (`**`) has higher precedence than the unary negation
operator (`-`).
That is, -x**y groups as -(x**y).
Not a bug - that's how it was designed and how it's documented.
Note that this isn't novel, either. For example, to give just one
Tim Peters added the comment:
If you want to pursue changing what utcnow() does, python-ideas or python-dev
would probably need to be involved. Backward-incompatible changes are very hard
sells.
As Paul Ganssle noted here,
https://blog.ganssle.io/articles/2019/11/utcnow.html
in Python 2
Tim Peters added the comment:
> It looks like the difference one would expect from (fast) human input)
Nope, the timestamps in the original report are about 3 hours apart (10808+
seconds).
Reports like these are often much clearer if they state the timezone of the
system they're runn
Tim Peters added the comment:
Dan, the Microsoft URL in your message gives a 404 for me. Did you perhaps mean
to end it with "cng-portal" (instead of "cng-por")?
--
nosy: +tim.peters
___
Python tracker
<https://bug
Tim Peters added the comment:
That said, if you really do want those semantics, it's easy to build on top of
Raymond's API:
def takewhile_plus_one_more_if_any(pred, iterable):
from itertools import islice, chain
before, after = before_and_after(pred, iterable)
return chain(before
Tim Peters added the comment:
If you don't use the 'after` iterator, then of course you'll never see the
values (if any) it would have yielded.
How could it possibly be otherwise? By design and construction, the `before`
iterator ends before yielding the first (if any) transitional element
Tim Peters added the comment:
I agree Raymond's `before_and_after()` looks like an elegant, efficient, and
usable approach to this.
One minor nit: there's no need for the `iter()` call in:
yield from iter(transition)
Indeed, it confused me at first, because `yield from x` does its
Tim Peters added the comment:
Closing this now because the pull request did, I believe, all that can be done
at the function level. Exponents of 1 and 2 are well within a factor of 2 of
repeated multiplication now, and it's essentially a tie at exponent 3 now.
Above that, pow() wins now
Tim Peters added the comment:
New changeset 9d8dd8f08aae4ad6e73a9322a4e9dee965afebbc by Tim Peters in branch
'main':
bpo-44376 - reduce pow() overhead for small exponents (GH-26662)
https://github.com/python/cpython/commit/9d8dd8f08aae4ad6e73a9322a4e9dee965afebbc
Tim Peters added the comment:
This is a stab at reducing overhead for small exponents, along the lines I
sketched:
https://github.com/python/cpython/pull/26662
Unfortunately, I've been unable to convince BPO and GitHub to recognize that
the PR is related to this report. Did something basic
Change by Tim Peters :
--
keywords: +patch
pull_requests: +25248
stage: -> patch review
pull_request: https://github.com/python/cpython/pull/26662
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
Under the released 3.9.5 for 64-bit Win10, raising to the power 2 is clearly
much slower than multiplying directly:
C:\Windows\System32>py -3 -m timeit -s "x=151" "x*x"
1000 loops, best of 5: 30 nsec per loop
C:\Windows\System32>
Tim Peters added the comment:
+1. Although, to be fair, I'd personally be happy if (+-0)**inf returned, say,
1.375 instead ;-)
--
nosy: +tim.peters
___
Python tracker
<https://bugs.python.org/issue44
Change by Tim Peters :
--
nosy: +rhettinger
___
Python tracker
<https://bugs.python.org/issue44197>
___
___
Python-bugs-list mailing list
Unsubscribe:
Tim Peters added the comment:
Dennis, combinations("aaabbbcccddd") isn't a valid call - the function requires
a "how many?" argument too. If, e.g., we were asking for groups of 4, then
combinations("aaabbbcccddd", 4) generates the 4-tuple ('a', 'b', 'c', 'd')
Tim Peters added the comment:
Oh yes - please do. It's not just pickle size - going through str() makes
(un)pickling quadratic time in both directions if components are large. Pickle
the component ints instead, and the more recent pickle protocol(s) can do both
directions in linear time
Tim Peters added the comment:
[Stefan]
> I found it surprising that a comparison uses a different
> method of conversion than the (obvious) user-side
> conversion, with a different outcome. This seems to be
> implementation details leaking into the user side.
It's "spirit of
Tim Peters added the comment:
Please study the docs first:
https://docs.python.org/3/tutorial/floatingpoint.html
That will give you the background to understand why `int()` has nothing to do
with this.
>>> 1.
2.0
That is, `int()` was passed 2.0 to begin with
Tim Peters added the comment:
Yes, test_compileall can still fail for this reason on Windows. From a run just
now with -j0 (same as -j10 on this box, which has 8 logical cores: a -j value
<= 0 is treated the same as "2 + number of logical cores"):
"""
Comp
Tim Peters added the comment:
A "good" solution would be one that runs the test in such a way that it doesn't
fail only on Windows ;-)
There are presumably many ways that could be accomplished, including ugly ones.
For example, if test_compileall is in the collection of tests
Tim Peters added the comment:
@Sheyvan, whether it's possible to delete (rename, etc) an open file is a
property not of Python, but of the operating system. Windows doesn't allow it;
Linux (for example) does.
It's generally considered to be "a bug" in CPython's implementatio
Tim Peters added the comment:
Shreyan Avigyan:
> And the "(Pdb) continue (...) actually is manually entered by me.
Victor Stinner:
Do you mean that you modified the Python source code?
Me:
Doubt it. For me, with more words: the "(Pdb) " prompt appears all by itself,
by m
Tim Peters added the comment:
I expect parallelism is a red herring: early in the test output attached to
this report:
0:00:04 Run tests sequentially
and there's no other evidence in the output that multiple tests are running
simultaneously.
Also on Win10, the 4 failing tests here pass
Tim Peters added the comment:
I agree hashing a NaN acting like the generic object hash (return rotated
address) is a fine workaround, although I'm not convinced it addresses a
real-world problem ;-) But why not? It might.
But that's for CPython. I'm loathe to guarantee anything about
Tim Peters added the comment:
Terry, your suggested replacement statement looks like an improvement to me.
Perhaps the longer explanation could be placed in a footnote.
Note that I'm old ;-) I grew up on plain old ASCII, decades & decades ago, and
tabs are in fact the only "charact
Tim Peters added the comment:
I think it's time to change what address_in_range() tries to answer. It
currently gives a precise answer to "is this byte address in a region obmalloc
owns?". But that's stronger than what it needs to do its job: the real question
is "is
Tim Peters added the comment:
BTW, your cache WIP
https://github.com/python/cpython/pull/25130/files
partly moves to tracking pool (instead of byte) addresses, but any such attempt
faces a subtlety: it's not necessarily the case that a pool is entirely
"owned" by obmalloc or by
Tim Peters added the comment:
Can't really know without a system to try it on, but my best guess is that
these asserts are the only thing that will fail with tagging enabled. The
obvious "fix" is indeed just to skip them on a platform with tagging enabled.
They're meant as a sa
Tim Peters added the comment:
Lines beginning with "?" are entirely synthetic: they were not present in
either input. So that's what that part means.
I'm not clear on what else could be materially clearer without greatly bloating
the text. For example,
>>> d = difflib
Tim Peters added the comment:
"""
My philosophy here (which I learned from Tim Peters in the early 2000s) is that
even though each individual improvement has no measurable effect on a general
benchmark (as shown in the same comment), the combined effect of a number of
tiny i
Tim Peters added the comment:
I'm skeptical ;-) If MTE is actually being used, system software assigns
"random" values to 4 of the higher-order bits. When obmalloc punts to the
system malloc, presumably those bits will be randomized in the addresses
returned by malloc. Then
Tim Peters added the comment:
Are you sure it's "a list"? At least print out `type(questions_element)`.
`random.shuffle()` doesn't contain any code _capable_ of changing a list's
length. It only does indexed accessing of the list:
...
for i in reversed(range(1, len(x))):
Tim Peters added the comment:
This report is closed. Please open a different report.
We've already demonstrated that, as predicted, nothing can be said here without
it being taken as invitation to open-ended discussion. So it goes, but it
doesn't belong on _this_ report anymore
Tim Peters added the comment:
If experience is any guide, nothing about anything here will go smoothly ;-)
For example, setting up a module global `_gcd` name for `math.gcd` is a very
standard, widespread kind of micro-optimization. But - if that's thought to be
valuable (who knows? maybe
Tim Peters added the comment:
Thanks, all! This has been merged now. If someone wants to continue pursuing
things left hanging, I'd suggest opening a different BPO report.
--
resolution: -> fixed
stage: patch review -> resolved
status: open -&g
Tim Peters added the comment:
New changeset 690aca781152a498f5117682524d2cd9aa4d7657 by Sergey B Kirpichev in
branch 'master':
bpo-43420: Simple optimizations for Fraction's arithmetics (GH-24779)
https://github.com/python/cpython/commit/690aca781152a498f5117682524d2cd9aa4d7657
Tim Peters added the comment:
Terry, we could do that, but the opposition here isn't strong, and is pretty
baffling anyway ;-) : the suggested changes are utterly ordinary for
implementations of rationals, require very little code, are not delicate, and
are actually straightforward to see
Tim Peters added the comment:
Issue 21922 lists several concerns, and best I know they all still apply. As a
practical matter, I expect the vast bulk of core Python developers would reject
a change that sped large int basic arithmetic by a factor of a billion if it
slowed down basic
Tim Peters added the comment:
I agree with everyone ;-) That is, my _experience_ matches Mark's: as a
more-or-less "numeric expert", I use Fraction in cases where it's already fast
enough. Python isn't a CAS, and, e.g., in pure Python I'm not doing things like
computing or compo
Tim Peters added the comment:
This won't go anywhere without code (preferably minimal) we can run to
reproduce the complaint. If there were a "general principle" at work here,
someone else would surely have reported it over the last few decades ;-)
To the contrary, the common
Tim Peters added the comment:
New changeset 73a85c4e1da42db28e3de57c868d24a089b8d277 by Dennis Sweeney in
branch 'master':
bpo-41972: Use the two-way algorithm for string searching (GH-22904)
https://github.com/python/cpython/commit/73a85c4e1da42db28e3de57c868d24a089b8d277
101 - 200 of 1325 matches
Mail list logo