Python-ideas October 2016

python-ideas@python.org

109 participants
65 discussions

Optimizing list.sort() by checking type in advance

by Elliot Gorokhovsky

Thanks for looking at this! That's why I spent months of my life (overall) devising a sequence of sorting algorithms for Python that reduced the number of comparisons needed. Yes, that's why I think this is so cool: for a couple dozen lines of code, we can get (at least for some cases, according to my questionable benchmarks) the kinds of massive improvements you had to use actual computer science to achieve (as opposed to mere hackery). Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types. The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap). Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying). Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal. This wouldn't work for strings (unicode is scary), and probably not for ints (one would have to check that all the ints are within C long bounds). Though on the other hand perhaps this would be too expensive? I had considered something "like this" for Python 2, but didn't pursue it because comparison was defined between virtually any two types (34 < [1], etc), and people were careless about that (both by design and by accident). In Python 3, comparison "blows up" for absurdly mixed types, so specializing for homogeneously-typed lists is a more promising idea on the face of it. The comparisons needed to determine _whether_ a list's objects have a common type is just len(list)-1 C-level pointer comparisons, and so goes fast. So I expect that, when it applies, this would speed even sorting an already-ordered list with at least 2 elements. That's what my crude benchmarks indicate... when I applied my sort to a list of 1e7 ints with a float tacked on the end, my sort actually ended up being a bit faster over several trials (which I attribute to PyObject_RichCompare == Py_True being faster than PyObject_RichCompareBool == 1, apologies for any typos in that code). For a mixed-type list with at least 2 elements, it will always be pure loss. But (a) I expect such lists are uncommon (and especially uncommon in Python 3); and (b) a one-time scan doing C-level pointer comparisons until finding a mismatched type is bound to be a relatively tiny cost compared to the expense of all the "rich comparisons" that follow. So +1 from me on pursuing this. Elliot, please: - Keep this on python-ideas. python-dev is for current issues in Python development, not for speculating about changes. - Open an issue on the tracker: https://bugs.python.org/ OK - At least browse the info for developers: https://docs.python.org/devguide/ Ya, I'm working on setting this up as a patch in the hg repo as opposed to an extension module to make benchmarking cleaner/more sane. - Don't overlook Lib/test/sortperf.py. As is, it should be a good test of what your approach so far _doesn't_ help, since it sorts only lists of floats (& I don't think you're special-casing them). If the timing results it reports aren't significantly hurt (and I expect they won't be), then add specialization for floats too and gloat about the speedup :-) Ya, I mean they aren't special-cased, but homogenous lists of floats still fit in the tp->rich_compare case, which still bypasses the expensive PyObject_RichCompare. I'll guess I'll see when I implement this as a patch and can run it on sortperf.py. - I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples). I'm not sure what you mean here... I'm looking at the types of lo.keys, not of saved_ob_item (I think I said that earlier in this thread by mistake actually). So if someone is passing tuples and using itemgetter to extract ints or strings or whatever, the current code will work fine; lo.keys will be scalar types. Unless I misunderstand you here. I mean, when would lo.keys actually be tuples? Nice start! :-) Thanks!

4 years, 4 months

Add sorted (ordered) containers

by Марк Коренберг

I mean mutable containers that are always sorted when iterating over them. See http://bugs.python.org/issue28433 for example: * SortedSet (sorted unique elements, implemented using (rb?)tree instead of hash) * SortedList (sorted elements, the same as SortedSet, but without uniquiness constraint) - actually a (rb?)tree, not a list (i.e. not an array) * SortedDict (sorted by key when interating) - like C++'s ordered_map There are many implementations in the net, like: https://bitbucket.org/bcsaller/rbtree http://newcenturycomputers.net/projects/rbtree.html https://sourceforge.net/projects/pyavl http://www.grantjenks.com/docs/sortedcontainers https://github.com/tailhook/sortedsets https://pypi.python.org/pypi/skiplist and also in pip: pip3 search sorted | grep -Ei '[^a-z]sorted' I think it should be one standardized implementation of such containers in CPython. For example, C++ has both ordered_map and unorderd_map. Instead of trees, implementation may use SkipList structure, but this is just implementation details. Such structres imply fast insertion and deletion, ability to iterate, and also memory efficiency.

4 years, 4 months

PEP 505 -- None-aware operators

by Gustavo Carneiro

Sorry if I missed the boat, but only just now saw this PEP. Glancing through the PEP, I don't see mentioned anywhere the SQL alternative of having a coalesce() function: https://www.postgresql.org/docs/9.6/static/functions-conditional.html#FUNCT… In Python, something like this: def coalesce(*args): for arg in args: if arg is not None: return arg return None Just drop it into builtins, and voila. No need for lengthy discussions about which operator to use because IMHO it needs no operator. Sure, it's not as sexy as a fancy new operator, nor as headline grabbing, but it is pretty useful. Just my 2p. -- Gustavo J. A. M. Carneiro Gambit Research "The universe is always one step beyond logic." -- Frank Herbert

4 years, 4 months

Re: [Python-ideas] PEP 505 -- None-aware operators

by Franklin? Lee

On Oct 14, 2016 9:14 AM, "Gustavo Carneiro" <gjcarneiro(a)gmail.com> wrote: > > Sorry if I missed the boat, but only just now saw this PEP. > > Glancing through the PEP, I don't see mentioned anywhere the SQL alternative of having a coalesce() function: https://www.postgresql.org/docs/9.6/static/functions-conditional.html#FUNCT… > > In Python, something like this: > > def coalesce(*args): > for arg in args: > if arg is not None: > return arg > return None > > Just drop it into builtins, and voila. No need for lengthy discussions about which operator to use because IMHO it needs no operator. > > Sure, it's not as sexy as a fancy new operator, nor as headline grabbing, but it is pretty useful. That function is for a different purpose. It selects the first non-null value from a flat collection. The coalesce operators are for traveling down a reference tree, and shortcutting out without an exception if the path ends. For example: return x?.a?.b?.c instead of: if x is None: return None if x.a is None: return None if x.a.b is None: return None return x.a.b.c You can use try-catch, but you might catch an irrelevant exception. try: return x.a.b.c except AttributeError: return None If `x` is an int, `x.a` will throw an AttributeError even though `x` is not None. A function for the above case is: def coalesce(obj, *names): for name in names: if obj is None: return None obj = getattr(obj, name) return obj return coalesce(x, 'a', 'b', 'c') See this section for some examples: https://www.python.org/dev/peps/pep-0505/#behavior-in-other-languages (The PEP might need more simple examples. The Motivating Examples are full chunks of code from real libraries, so they're full of distractions.)

4 years, 4 months

Fwd: Add sorted (ordered) containers

by Grant Jenks

On Thu, Oct 13, 2016 at 1:36 PM, Марк Коренберг <socketpair(a)gmail.com> wrote: > > I mean mutable containers that are always sorted when iterating over them. > > See http://bugs.python.org/issue28433 > > for example: > > * SortedSet (sorted unique elements, implemented using (rb?)tree instead of hash) > * SortedList (sorted elements, the same as SortedSet, but without uniquiness constraint) - actually a (rb?)tree, not a list (i.e. not an array) > * SortedDict (sorted by key when interating) - like C++'s ordered_map Can you share more about your use cases for these containers? What are you making? Nick Coghlan gave an answer to this question on StackOverflow at http://stackoverflow.com/a/5958960/232571 The answer kind of boils down to "there should be one obvious way to do it" and existing Python features like lists, sorted, bisect, and heapq cover many use cases. I wrote the answer that is now the second highest rated for that question. I've noticed that the upvotes have been accumulating at a slightly higher rate than Nick's answer. I think that reflects an increase in interest and maybe gradual tide change of opinion. > There are many implementations in the net, like: > > http://www.grantjenks.com/docs/sortedcontainers That's my project. I am the primary developer of the SortedContainers project. You may also be interested in the [SortedCollections](http://www.grantjenks.com/docs/sortedcollections/) module which builds atop SortedContainers with data types like ValueSortedDict and ItemSortedDict. Because it's pure-Python, SortedContainers offers a lot of opportunity for extension/customization. That's also made it easier for the API to adapt/expand over time. > I think it should be one standardized implementation of such containers in CPython. > > Instead of trees, implementation may use SkipList structure, but this is just implementation details. > > Such structres imply fast insertion and deletion, ability to iterate, and also memory efficiency. I gave a talk at PyCon 2016 about Python Sorted Collections[1] that's worth watching. The first third discusses about six different implementations with different strengths and weaknesses. The choice of data type is more than implementation details. One of the biggest issues is the various tradeoffs of data types like blists, rbtrees, etc. I have been meaning to discuss sorted collections further with Raymond Hettinger (author of the Python collections module). We spoke after the PyCon talk and wanted to continue the conversation. But I had a busy summer and just a few weeks ago welcomed my first son into the world. So realistically that conversation won't happen until 2017. [1]: http://www.grantjenks.com/docs/sortedcontainers/pycon-2016-talk.html > I recommend to read thorough review articles written by Andrew Barnert: > > http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.… > > http://stupidpythonideas.blogspot.com/2014/04/sortedcontainers.html One of Andrew Barnert's conclusions is that SortedContainers could not scale. I did a pretty rigorous performance analysis and benchmarking at http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html Short answer: I scaled SortedContainers up through ten billion elements, well past the memory limits of most machines.

4 years, 4 months

Suggestion: Deprecate metaclasses that are not instances of type

by Neil Girdhar

Background: I asked a stackoverflow question here <http://stackoverflow.com/questions/40029807/why-does-the-class-definitions-…> . The Python documentation <https://docs.python.org/3.6/reference/datamodel.html#determining-the-approp…> is very confusing to me. It says that: if an explicit metaclass is given and it is not an instance of type, then it is used directly as the metaclass This seems to suggest that in this case, the "explicit metaclass" does not need to be "subtype of all of these candidate metaclasses" as it would in the third case. (This is not true.) Also, providing a callable as a metaclass doesn't seem to be any more flexible, readable, or powerful than providing an instance of type. Therefore, I suggest that we deprecate the second case and replace the entire section (3.3.3.2) of the documentation to say: "The metaclass of a class definition is selected from the explicitly specified metaclass (if any) and the metaclasses (i.e. type(cls)) of all specified base classes. The most derived metaclass is one which is a subtype of all of these candidate metaclasses. If none of the candidate metaclasses meets that criterion, then the class definition will fail with TypeError. If provided, the explicit metaclass must be an instance of type()."

4 years, 4 months

Re: [Python-ideas] INSANE FLOAT PERFORMANCE!!!

by Chris Angelico

On Thu, Oct 13, 2016 at 5:17 PM, Stephen J. Turnbull <turnbull.stephen.fw(a)u.tsukuba.ac.jp> wrote: > Chris Angelico writes: > > > I'm not sure what you mean by "strcmp-able"; do you mean that the > > lexical ordering of two Unicode strings is guaranteed to be the same > > as the byte-wise ordering of their UTF-8 encodings? > > This is definitely not true for the Han characters. In Japanese, the > most commonly used lexical ordering is based on the pronunciation, > meaning that there are few characters (perhaps none) in common use > that has a unique place in lexical ordering (most individual > characters have multiple pronunciations, and even many whole personal > names do). Yeah, and even just with Latin-1 characters, you have (a) non-ASCII characters that sort between ASCII characters, and (b) characters that have different meanings in different languages, and should be sorted differently. So lexicographical ordering is impossible in a generic string sort. ChrisA

4 years, 4 months

Re: [Python-ideas] INSANE FLOAT PERFORMANCE!!!

by Elliot Gorokhovsky

To answer your question: I special-case unicode (strings), ints, and floats. I am working on special-casing tuples (can even be different types, just need homogeneity column-wise). The best speedups will be tuples of floats: it'll bypass three layers of useless checks. If I run it without special-casing floats (just using tp->rich_compare) I only get like a 5-10% speedup. I'm working on rigorous benchmarks for all this stuff, will post a pdf along with the patch once it's all done. But it's certainly <10%. However, part of this is because my special case is really low-level; for strings I've actually found the opposite, using tp->richcompare gives me almost the same results as my special case compare, since it still has to PyUnicode_READY the strings (or whatever it's called). Regarding generalization: the general technique for special-casing is you just substitute all type checks with 1 or 0 by applying the type assumption you're making. That's the only way to guarantee it's safe and compliant. Elliot On Tue, Oct 11, 2016, 5:19 PM Jim J. Jewett <jimjjewett(a)gmail.com> wrote: > Excellent. > I'm surprised cache didn't save more, but less surprised than I was ... I > hadn't realized that you were skipping the verifications in > PyFloat_RichCompare as well. Does that generalize to other element types > without exposing too much of the per-type internals to list.sort? > > Oh ... and I appreciate your not quoting private email as a general > courtesy, but I hereby give you permission if it was mine that was private. > [Though I think your summary was better than a quote anyhow.] > > -jJ > > On Oct 11, 2016 4:58 PM, "Elliot Gorokhovsky" < > elliot.gorokhovsky(a)gmail.com> wrote: > > So I got excited here. And the reason why is that I got those numbers *on > Tim's benchmark*. When I got these kinds of numbers on my benchmarks, I > figured there was probably a problem with they way I was timing, and > certainly the gains couldn't be as extreme as they suggested. But this is > on a benchmark that's already in the codebase! > > > Here is a detailed explanation of how to reproduce my results, and the > circumstances that would lead them to be invalid: > > ****************************************** > > To reproduce, just activate a virtualenv, and then clone > https://github.com/embg/python-fast-listsort.git. Then python setup.py > install and python sortperf.py. > > > Now let's look at what sortperf.py does and how it relates to Tim's > benchmark at Lib/test/sortperf.py. If you diff the two, you'll find I made > three changes: > > > 1. I added an import, "import fastlist". This obviously would not make > sorting twice faster. > > > 2. I changed the way it formats the output: I changed "fmt = ("%2s %7s" + > " %7s"*len(cases))" to "fmt = ("%2s %7s" + " %6s"*len(cases))". Again > irrelevant. > > > 3. I changed the timing function > > #from this > > > def doit_fast(L): > t0 = time.perf_counter() > L.fastsort() > t1 = time.perf_counter() > print("%6.2f" % (t1-t0), end=' ') > flush() > > > > #to this > > > def doit(L): > F = FastList(L) > f0 = time.perf_counter() > F.fastsort() > f1 = time.perf_counter() > F = FastList(L) > t0 = time.perf_counter() > F.sort() > t1 = time.perf_counter() > print("%6.2f%%" % (100*(1-(f1-f0)/(t1-t0))), end=' ') > flush() > > > ******************************************* > > So what we've shown is that (1) if you trust the existing sorting > benchmark and (2) if my modification to doit() doesn't mess anything up (I > leave this up to you to judge), then the measurements are as valid. Which > is a pretty big deal (50% !!!!!!!), hence my overexcitement. > > **************************************** > > > Now I'd like to respond to responses (the one I'm thinking of was off-list > so I don't want to quote it) I've gotten questioning how it could be > possible for such a small optimization, bypassing the typechecks, to > possibly have such a large effect, even in theory. Here's my answer: > > Let's ignore branch prediction and cache for now and just look at a high > level. The cost of sorting is related to the cost of a single comparison, > because the vast majority of our time (let's say certainly at least 90%, > depending on the list) is spent in comparisons. So let's look at the cost > of a comparison. > > Without my optimization, comparisons for floats (that's what this > benchmark looks at) go roughly like this: > > 1. Test type of left and right for PyObject_RichCompare (which costs two > pointer dereferences) and compare them. "3 ops" (quotes because counting > ops like this is pretty hand-wavy). "2 memory accesses". > > 2. Get the address of the float compare method from > PyFloat_Type->tp_richcompare. "1 op". "1 memory access". > > 3. Call the function whose address we just got. "1 op". "Basically 0 > memory accesses because we count the stack stuff in that 1 op". > > 4. Test type of left and right again in PyFloat_RichCompare and compare > both of them to PyFloat_Type. "4 ops". "2 memory accesses". > > 5. Get floats from the PyObject* by calling PyFloat_AS_DOUBLE or whatever. > "2 ops". "2 memory accesses". > > 6. Compare the floats and return. "2 ops". > > Now let's tally the "cost" (sorry for use of quotes here, just trying to > emphasize this is an intuitive, theoretical explanation for the numbers > which doesn't take into account the hardware): > "13 ops, 7 memory accesses". > > Here's what it looks like in my code: > > 1. Call PyFloat_AS_DOUBLE on left and right. "2 ops". "2 memory acceses". > > 2. Compare the floats and return. "2 ops". > > Tally: "4 ops, 2 memory accesses". > > Now you can argue branch prediction alleviates a lot of this cost, since > we're taking the same branches every time. But note that, branch prediction > or not, we still have to do all of those memory acceses, and since they're > pointers to places all over memory, they miss the cache basically every > time (correct me if I'm wrong). So memory-wise, we really are doing > something like a 7:2 ratio, and op-wise, perhaps not as bad because of > branch prediction, but still, 13:4 is probably bad no matter what's going > on in the hardware. > > Now consider that something like 90% of our time is spent in those steps. > Are my numbers really that unbelievable? > > Thanks for everything, looking forward to writing this up as a nice latex > doc with graphs and perf benchmarks and all the other rigorous goodies, as > well as a special case cmp func for homogeneous tuples and a simple patch > file, > > Elliot > >

4 years, 4 months

Re: [Python-ideas] [Python-Dev] Optimizing list.sort() by checking type in advance

by Tim Peters

[please restrict follow-ups to python-ideas] Let's not get hung up on meta-discussion here - I always thought "massive clusterf**k" was a precise technical term anyway ;-) While timing certainly needs to be done more carefully, it's obvious to me that this approach _should_ pay off significantly when it applies. Comparisons are extraordinarily expensive in Python, precisely because of the maze of test-and-branch code it requires just to figure out which bottom-level comparison function to invoke each time. That's why I spent months of my life (overall) devising a sequence of sorting algorithms for Python that reduced the number of comparisons needed. Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types. The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap). Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying). I had considered something "like this" for Python 2, but didn't pursue it because comparison was defined between virtually any two types (34 < [1], etc), and people were careless about that (both by design and by accident). In Python 3, comparison "blows up" for absurdly mixed types, so specializing for homogeneously-typed lists is a more promising idea on the face of it. The comparisons needed to determine _whether_ a list's objects have a common type is just len(list)-1 C-level pointer comparisons, and so goes fast. So I expect that, when it applies, this would speed even sorting an already-ordered list with at least 2 elements. For a mixed-type list with at least 2 elements, it will always be pure loss. But (a) I expect such lists are uncommon (and especially uncommon in Python 3); and (b) a one-time scan doing C-level pointer comparisons until finding a mismatched type is bound to be a relatively tiny cost compared to the expense of all the "rich comparisons" that follow. So +1 from me on pursuing this. Elliot, please: - Keep this on python-ideas. python-dev is for current issues in Python development, not for speculating about changes. - Open an issue on the tracker: https://bugs.python.org/ - At least browse the info for developers: https://docs.python.org/devguide/ - Don't overlook Lib/test/sortperf.py. As is, it should be a good test of what your approach so far _doesn't_ help, since it sorts only lists of floats (& I don't think you're special-casing them). If the timing results it reports aren't significantly hurt (and I expect they won't be), then add specialization for floats too and gloat about the speedup :-) - I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples). Nice start! :-)

4 years, 4 months

Expose condition._waiters

by Ram Rachum

Hi guys, I'm writing some code that uses `threading.Condition` and I found that I want to access condition._waiters. I want to do it in two different parts of my code for two different reasons: 1. When shutting down the thread that manages the condition, I want to be sure that there are no waiters on the condition, so I check whether `condition._waiters` is empty before exiting, otherwise I'll let them finish and only then exit. 2. When I do notify_all, I actually want to do as many notify actions as needed until there's a full round of notify_all in which none of the conditions for any of the waiters have been met. Only then do I want my code to continue. (It's because these waiters are waiting for resources that I'm giving them, each wanting a different number of resources, and I want to be sure that all of them are starved before I get more resources for them.) Do you think it'll be a good idea to add non-private functionality like that to threading.Condition? Thanks, Ram.

4 years, 4 months

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

Python-ideas October 2016