[Python-Dev] Re: (Adaptive) Shivers sort variant of Tim sort

[Laurent Lyaudet]

Hello,

Le sam. 28 août 2021 à 19:38, Tim Peters  a écrit :

> [Laurent Lyaudet ]
> > ...
> > My benchmarks could be improved but however I found that Shivers' sort
> > and adaptive Shivers' sort (aka Jugé's sort) performs better than
> > Tim's sort.
>
> Cool! Could you move this to the issue report already open on this?
>
> Replace list sorting merge_collapse()?
> https://bugs.python.org/issue34561
>
> Thanks for the fast and kind answer :)
I just did.
Sorry for not checking the bugs reports before posting.
I only checked that Shivers and Jugé did not appear in the archive of the
python-dev mailing list.
(If it does then the search here:
https://mail.python.org/archives/list/python-dev@python.org/
is broken.)

> Alas, that's been inactive for nearly 3 years, but we _were_ making
> some decent progress before everyone got distracted by "more
> important" stuff.
>
> You'll see there that Vincent Jugé contributed another version,
> designed to address that his sort did substantially worse than what we
> already have in some cases with very few runs. Which, for reasons
> explained there, is likely important.
>
> Before that, the best alternative known was - and by far - Munro &
> Wild's "powersort" merge strategy. That's deeply rooted in theory
> about fast approximations to optimal binary search trees.
>
> Where that left off, Vincent was going to try proving properties of
> his new variant, plus investigate other ideas. Alas, that's where it
> ended, as Vincent ran out of time too.
>
> In any case, yes, I'm entirely in favor of replacing timsort's merge
> strategy, by something with provably good properties even in worst
> cases. As explained in the issue report, the merge strategy I made up
> was merely the first thing I tried that didn't obviously suck ;-) -
> almost all the work went into making merging itself as zippy as
> reasonably possible..
>
I will try to provide a patch before the end of the week.
But first I will read
https://www.python.org/psf/contrib/
https://devguide.python.org/
I took 5 minutes to fork and do a PR on my fork with the code for merge
collapse :
https://github.com/LLyaudet/cpython/pull/1
As soon as I have something more polished I'll do a PR on python repo.
Any early feedback is welcome :)

Best regards,
Laurent
___
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at 
https://mail.python.org/archives/list/python-dev@python.org/message/O3U3DWBLMG67TS55UJ3F2D5CYQZMMRJT/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-Dev] Re: Discrepancy between what aiter() and `async for` requires on purpose?

[Serhiy Storchaka]

29.08.21 23:16, Brett Cannon пише:
> If you look at
> https://github.com/python/cpython/blob/b11a951f16f0603d98de24fee5c023df83ea552c/Python/ceval.c#L2409-L2451
> 
> you will see that `async for` requires that the iterator returned from
> `__aiter__` define `__anext__`. But if you look at aiter() which uses
> PyObject_GetAiter() from
> https://github.com/python/cpython/blob/f0a6fde8827d5d4f7a1c741ab1a8b206b66ffd57/Objects/abstract.c#L2741-L2759
> 
> and PyAiter_Check() from
> https://github.com/python/cpython/blob/f0a6fde8827d5d4f7a1c741ab1a8b206b66ffd57/Objects/abstract.c#L2769-L2778
> 
> you will notice that aiter() requires `__anext__` *and* `__aiter__` on
> the async iterator that gets returned from __aiter__.
> 
> Now the docs for aiter() at
> https://docs.python.org/3.10/library/functions.html#aiter
>  points out
> that the async iterator is expected to define both methods as does the
> glossary definition for "asynchronous iterator"
> (https://docs.python.org/3.8/glossary.html#term-asynchronous-iterator
> ).
> 
> So my question is whether the discrepancy between what `async for`
> expects and what `aiter()` expects on purpose?
> https://bugs.python.org/issue31861 
> was the issue for creating aiter() and I didn't notice a discussion of
> this difference. The key reason I'm asking is this does cause a
> deviation compared to the relationship between `for` and `iter()` (which
> does not require `__iter__` to be defined on the iterator, although
> collections.abc.Iterator does). It also makes the glossary definition
> being linked from
> https://docs.python.org/3.10/reference/compound_stmts.html#the-async-for-statement
> 
> incorrect.

PyIter_Check() only checks existence of __next__, not __iter__ (perhaps
for performance reasons).

I just ported changes from PyPy in SQLite tests
(https://github.com/python/cpython/pull/28021) because a test class with
__next__ but without __iter__ passed tests on CPython but failed on PyPy.

___
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at 
https://mail.python.org/archives/list/python-dev@python.org/message/VWZQPBE5SLKA5IDOGSOJYFWUDOQ7HJKS/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-Dev] Discrepancy between what aiter() and `async for` requires on purpose?

[Brett Cannon]

If you look at
https://github.com/python/cpython/blob/b11a951f16f0603d98de24fee5c023df83ea552c/Python/ceval.c#L2409-L2451
you will see that `async for` requires that the iterator returned from
`__aiter__` define `__anext__`. But if you look at aiter() which uses
PyObject_GetAiter() from
https://github.com/python/cpython/blob/f0a6fde8827d5d4f7a1c741ab1a8b206b66ffd57/Objects/abstract.c#L2741-L2759
and PyAiter_Check() from
https://github.com/python/cpython/blob/f0a6fde8827d5d4f7a1c741ab1a8b206b66ffd57/Objects/abstract.c#L2769-L2778
you will notice that aiter() requires `__anext__` *and* `__aiter__` on the
async iterator that gets returned from __aiter__.

Now the docs for aiter() at
https://docs.python.org/3.10/library/functions.html#aiter points out that
the async iterator is expected to define both methods as does the glossary
definition for "asynchronous iterator" (
https://docs.python.org/3.8/glossary.html#term-asynchronous-iterator).

So my question is whether the discrepancy between what `async for` expects
and what `aiter()` expects on purpose? https://bugs.python.org/issue31861
was the issue for creating aiter() and I didn't notice a discussion of this
difference. The key reason I'm asking is this does cause a deviation
compared to the relationship between `for` and `iter()` (which does not
require `__iter__` to be defined on the iterator, although
collections.abc.Iterator does). It also makes the glossary definition being
linked from
https://docs.python.org/3.10/reference/compound_stmts.html#the-async-for-statement
incorrect.
___
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at 
https://mail.python.org/archives/list/python-dev@python.org/message/ZADNVL7SGH24QXBNPKMN33ELFSXRI2VJ/
Code of Conduct: http://python.org/psf/codeofconduct/