Mailman 3 March 2017 - Python-ideas

Multi threaded computation, thread local storage reducing false sharing, read only access to globals and a paused GIL to allow parallel scaling reads
by Josh Ring 20 Mar '17

20 Mar '17

Hi My name is Josh Ring, I am interested in raw compute performance from C modules called from python. Most of which are single threaded (eg Numpy, Scipy etc) Some things are sensible with many threads: 1. Read only global state can avoid locks entirely in multithreaded code, this is to avoid cache line invalidations killing scaling >2-4 threads. 2. Incr/decr can be paused when entering the parallel region to avoid invalidating caches of objects, readonly access makes this safe. 2. Locality of memory, so using thread local stack by default and heap allocations bound per thread this is essential to scale >4 threads and with NUMA server systems. 3. Leaving the GIL intact for single threaded code to do the "cleanup stage" of temporaries after parallel computation has finished. - I liked the approach of a "parallel region", where data does not need to be pickled, and can directly read-only access shared memory. - If global state is unchangeable from a threaded region we can avoid many gotchas and races, leaving the GIL alone, almost. - If reference counting can be "paused" during the parallel region we can avoid cache invalidation from multiple threads, due to incr/decr, which limits scaling with more threads, this is evident even with 2 threads. - Thread local storage is the default and only option, avoiding clunky "threading.local()" storage classes, "thread bound" heap allocations would also be a good thing to increase efficiency and reduce "false sharing". https://en.wikipedia.org/wiki/False_sharing - Implement the parallel region using a function with a decorator akin to openMP? The function then defines the scope for the local variables and the start and end of parallel region, when to return etc in a straightforward manner. - By default, the objects returned from the parallel region return into separate objects (avoiding GIL contention), these temporary objects are then merged into a list once control is returned to just a single thread. - Objects marked @thread_shared have their state merged from the thread local copies once execution from all the threads has finished. This could be made intelligent if some index is provided to put the entries in the right place in a list/dict etc. Thoughts? This proposal is borrowing several ideas from Pyparallel, but without the focus on windows only and IO. It is more focused on accelerating raw compute performance and is tailored for high performance computing for instance at CERN etc.

1 0

Additions to collections.Counter and a Counter derived class
by Marco Cognetta 16 Mar '17

16 Mar '17

Hi all, I have been using the Counter class recently and came across several things that I was hoping to get feedback on. (This is my first time mailing this list, so any advice is greatly appreciated) 1) Addition of a Counter.least_common method: This would add a method to Counter that is basically the opposite of the pre-existing Counter.most_common method. In this case, the least common elements are considered the elements in c with the lowest (non-zero) frequency. This was addressed in https://bugs.python.org/issue16994, but it was never resolved and is still open (since Jan. 2013). This is a small change, but I think that it is useful to include in the stdlib. I have written a patch for this, but have not submitted a PR yet. It can be found at https://github.com/mcognetta/cpython/tree/collections_counter_least_common 2) Undefined behavior when using Counter.most_common: Consider the case c = Counter([1, 1, 2, 2, 3, 3, 'a', 'a', 'b', 'b', 'c', 'c']), when calling c.most_common(3), there are more than 3 "most common" elements in c and c.most_common(3) will not always return the same list, since there is no defined total order on the elements in c. Should this be mentioned in the documentation? Additionally, perhaps there is room for a method that produces all of the elements with the n highest frequencies in order of their frequencies. For example, in the case of c = Counter([1, 1, 1, 2, 2, 3, 3, 4, 4, 5]) c.aforementioned_method(2) would return [(1, 3), (2, 2), (3, 2), (4, 2)] since the two highest frequencies are 3 and 2. 3) Addition of a collections.Frequency or collections.Proportion class derived from collections.Counter: This is sort of discussed in https://bugs.python.org/issue25478. The idea behind this would be a dictionary that, instead of returning the integer frequency of an element, would return it's proportional representation in the iterable. So, for example f = Frequency('aabbcc'), f would hold Frequency({'a': 0.3333333333333333, 'b': 0.3333333333333333, 'c': 0.3333333333333333}). To address >The pitfall I imagine here is that if you continue adding elements after normalize() is called, the >results will be nonsensical. from the issue, this would not be a problem because we could just build it entirely on top of a Counter, keep a count of the total number of elements in the Counter, and just divide by that every time we output or return the object or any of its elements. I think that this would be a pretty useful addition especially for code related to discrete probability distributions (which is what motivated this in the first place). Thanks in advance, -Marco

4 8

Optional parameters without default value
by Serhiy Storchaka 10 Mar '17

10 Mar '17

Function implemented in Python can have optional parameters with default value. It also can accept arbitrary number of positional and keyword arguments if use var-positional or var-keyword parameters (*args and **kwargs). But there is no way to declare an optional parameter that don't have default value. Currently you need to use the sentinel idiom for implementing this: _sentinel = object() def get(store, key, default=_sentinel): if store.exists(key): return store.retrieve(key) if default is _sentinel: raise LookupError else: return default There are drawback of this: * Module's namespace is polluted with sentinel's variables. * You need to check for the sentinel before passing it to other function by accident. * Possible name conflicts between sentinels for different functions of the same module. * Since the sentinel is accessible outside of the function, it possible to pass it to the function. * help() of the function shows reprs of default values. "foo(bar=<object object at 0xb713c698>)" looks ugly. I propose to add a new syntax for optional parameters. If the argument corresponding to the optional parameter without default value is not specified, the parameter takes no value. As well as the "*" prefix means "arbitrary number of positional parameters", the prefix "?" can mean "single optional parameter". Example: def get(store, key, ?default): if store.exists(key): return store.retrieve(key) try: return default except NameError: raise LookupError Alternative syntaxes: * "=" not followed by an expression: "def get(store, key, default=)". * The "del" keyword: "def get(store, key, del default)". This feature is orthogonal to supporting positional-only parameters. Optional parameters without default value can be positional-or-keyword, keyword-only or positional-only (if the latter is implemented).

20 41

Exploiting type-homogeneity in list.sort() (again!)
by Elliot Gorokhovsky 10 Mar '17

10 Mar '17

(Summary of results: my patch at https://bugs.python.org/issue28685 makes list.sort() 30-50% faster in common cases, and at most 1.5% slower in the uncommon worst case.) Hello all, You may remember seeing some messages on here about optimizing list.sort() by exploiting type-homogeneity: since comparing apples and oranges is uncommon (though possible, i.e. float to int), it pays off to check if the list is type-homogeneous (as well as homogeneous with respect to some other properties), and, if it is, to replace calls to PyObject_RichCompareBool with calls to ob_type->tp_richcompare (or, in common special cases, to optimized compare functions). The entire patch is less than 250 lines of code, most of which is pretty boilerplate (i.e. a lot of assertions in #ifdef Py_DEBUG blocks, etc). I originally wrote that patch back in November. I've learned a lot since then, both about CPython and about mailing list etiquette :). Previous discussion about this can be found at https://mail.python.org/pipermail/python-dev/2016-October/146648.html and https://mail.python.org/pipermail/python-ideas/2016-October/042807.html. Anyway, I recently redid the benchmarks much more rigorously (in preparation for presenting this project at my school's science fair), achieving a standard deviation of less than 0.5% of the mean for all measurements. The exact benchmark script used can be found at https://github.com/embg/python-fastsort-benchmark (it's just sorting random lists of/lists of tuples of [type]. While listsort.txt talks about benchmarking different kinds of structured lists, instead of just random lists, the results here would hold in those cases just as well, because this makes individual comparisons cheaper, instead of reducing the number of comparisons based on structure). I also made a poster describing the optimization and including a pretty graph displaying the benchmark data: https://github.com/embg/python-fastsort-benchmark/blob/master/poster.pdf. For those who would rather read the results here (though it is a *really* pretty graph): *** Percent improvement for sorting random lists of [type] (1-patched/unpatched): float: 48% bounded int (magnitude smaller than 2^32): 48.4% latin string (all characters in [0,255]): 32.7% general int (reasonably uncommon?): 17.2% general string (reasonably uncommon?): 9.2% tuples of float: 63.2% tuples of bounded int: 64.8% tuples of latin string: 55.8% tuples of general int: 50.3% tuples of general string: 44.1% tuples of heterogeneous: 41.5% heterogeneous (lots of float with an int at the end; worst-case): -1.5% *** Essentially, it's a gamble where the payoff is 20-30 times greater than the cost, and the odds of losing are very small. Sorting is perhaps not a bottleneck in most applications, but considering how much work has gone into Python's sort (Timsort, etc; half of listobject.c is sort code), I think it's interesting that list.sort() can be made essentially twice faster by a relatively simple optimization. I would also add that Python dictionaries already implement this optimization: they start out optimizing based on the assumption that they'll only be seeing string keys, checking to make sure that assumption holds as they go. If they see a non-string key, they permanently switch over to the general implementation. So it's really the same idea, except here it doesn't matter as much what type we're dealing with, which is important, because lists are commonly used with lots of different types, as opposed to dictionaries, which overwhelmingly commonly use string keys, especially internally. (Correct me if I'm wrong in any of the above). I got a lot of great feedback/input on this patch as I was writing it, but after submitting it, I didn't hear much from anybody. (The reason I took so long to post was because I wanted to wait until I had the chance to do the benchmarks *right*). What do you all think? Thanks, Elliot

17 63

For/in/as syntax
by Brice PARENT 09 Mar '17

09 Mar '17

Object: Creation of a ForLoopIterationObject object (name open to suggestions) using a "For/in/as" syntax. Disclaimer: I've read PEP-3136 which was refused. The present proposal includes a solution to what it tried to solve (multi-level breaking out of loops), but is a more general proposal and it offers many unrelated advantages and simplifications. It also gives another clean way of making a kind of for/except/else syntax of another active conversation. What it tries to solve: During the iteration process, we often need to create temporary variables (like counters or states) or tests that don't correspond to the logic of the algo, but are required to make it work. This proposal aims at removing these unnecessary and hard to understand parts and help write simpler, cleaner, more maintainable and more logical code. So, more PEP-8 compliant code. How does it solve it: By instanciating a new object when starting a loop, which contains some data about the iteration process and some methods to act on it. The list of available properties and methods are yet to be defined, but here are a subset of what could be really helpful. A word about compatibility and understandability before: "as" is already a keyword, so it is already reserved and easy to parse. It couldn't be taken for its other uses (context managers, import statements and exceptions) as they all start with a specific and different keyword. It would have a really similar meaning, so be easy to understand. It doesn't imply any incompatibility with previous code, as current syntax would of course still be supported, and it doesn't change anything anywhere else (no change in indentation levels for example, no deprecation). Syntax: for element in elements as elements_loop: assert type(elements_loop) is ForLoopIterationObject Properties and methods (non exhaustive list, really open to discussion and suggestions): for element in elements as elements_loop: elements_loop.length: int # len ? count ? elements_loop.counter: int # Add a counter0, as in Django? a counter1 ? elements_loop.completed: bool elements_loop.break() elements_loop.continue() elements_loop.skip(count=1) Examples of every presented element (I didn't execute the code, it's just to explain the proposal): ################################################## # forloop.counter and forloop.length for num, dog in enumerate(dogs): print(num, dog) print("That's a total of {} dogs !".format(len(dogs))) # would be equivalent to for dog in dogs as dogs_loop: print(dogs_loop.counter, dog) print("That's a total of {} dogs !".format(dogs_loop.length)) # -> cleaner, and probably faster as it won't have to call len() or enumerate() #(but I could easily be wrong on that) ################################################## # forloop.length when we broke out of the list small_and_medium_dogs_count = 0 for dog in generate_dogs_list_by_size(): if dog.size >= medium_dog_size: break small_and_medium_dogs_count += 1 print("That's a total of {} small to medium dogs !".format( small_and_medium_dogs_count)) # would be equivalent to for dog in generate_dogs_list_by_size() as dogs_loop: if dog.size >= medium_dog_size: break print("That's a total of {} small to medium dogs !".format( dogs_loop.length - 1)) # -> easier to read, less temporary variables ################################################## # forloop.break(), to break out of nested loops (or explicitly out of current #loop) - a little like pep-3136's first proposal has_dog_named_rex = False for owner in owners: for dog in dogs: if dog.name == "Rex": has_dog_named_rex = True break if has_dog_named_rex: break # would be equivalent to for owner in owners as owners_loop: for dog in dogs: # syntax without "as" is off course still supported if dog.name == "Rex": owners_loop.break() # -> way easier to read and understand, less temporary variables ################################################## # forloop.continue(), to call "continue" from any nested loops (or explicitly #in active loop) has_dog_named_rex = False for owner in owners: for dog in owner.dogs: if dog.name == "Rex": has_dog_named_rex = True break if has_dog_named_rex: continue # do something # would be equivalent to for owner in owners as owners_loop: for dog in owner.dogs: if dog.name == "Rex": owners_loop.continue() # do something # -> way easier to read and understand, less temporary variables ################################################## # forloop.completed, to know if the list was entirely consumed or "break" was #called (or exception caught) - might help with the for/except/elseproposal broken_out = False for dog in dogs: if dog.name == "Rex": broken_out = True break if broken_out: print("We didn't consume all the dogs list") # would be equivalent to for dog in dogs as dogs_loop: if dog.name == "Rex": break if not dogs_loop.completed: print("We didn't consume all the dogs list") # -> less temporary variables, every line of code is relevant, easy to #understand ################################################## # forloop.skip # In the example, we want to skip 2 elements starting from item #2 skip = 0 for num, dog in enumerate(dogs): if skip: skip -= 1 continue if num == 2: skip = 2 # would be equivalent to for dog in dogs as dogs_loop: if dogs_loop.counter == 2: dogs_loop.skip(2) # -> way easier to read and understand, less temporary variables # Notes : # - Does a call to forloop.skip() implies a forloop.continue() call or does # the code continue its execution until the end of the loop, which will # then be skipped? Implying the .continue() call seems less ambiguous to # me. Or the method should be called skip_next_iteration, or something # like that. # - Does a call to forloop.skip(2) adds 2 to forloop.length or not? # -> kwargs may be added to allow both behaviours for both questions. # We could allow the argument to be a function that accepts a single argument #and return a boolean, like dogs_loop.skip(lambda k: k % 3 == 0) # Execute the code on multiples of 3 only ################################################## Thoughts : - It would allow to pass forloop.break and forloop.continue as callback to other functions. Not sure yet if it's a good or a bad thing (readability against what it could offer). - I haven't yet used much the asynchronous functionalities, so I couldn't yet think about the implications of such a new syntax to this (and what about a lazy keyword in here?) - I suppose it's a huge work to create such a syntax. And I have no idea how complicated it could be to create methods (like break() and continue()) doing what keywords were doing until now. - I'm not sure if that would make sense in list comprehensions, despite being confusing. - Would enable to support callback events like forloop.on_break. But would there be a need for that? - Would this have a major impact on the loops execution times? - would a "while condition as condition_loop:" be of any use too? Sorry for the very long message, I hope it will get your interest. And I also hope my English was clear enough. Brice Parent

7 14

Smoothing transition: 'unicode' and 'basestring' as aliases for 'str'?
by Thomas Güttler 07 Mar '17

07 Mar '17

I found this in an old post: > Maybe too late now but there should have been 'unicode', > 'basestring' as aliases for 'str'. I guess it is too late to think about it again ... Regards, Thomas Güttler -- Thomas Guettler http://www.thomas-guettler.de/

4 5

Wrapper for ctypes
by George Fischhof 07 Mar '17

07 Mar '17

Hi Guys, right now I had to call functions from a dll, and I started using ctypes. I found this library too https://pypi.python.org/pypi/pywrap/0.1.0 which says (qutation): Replace this: prototype = ctypes.WINFUNCTYPE(wintypes.HANDLE, wintypes.UINT, wintypes.HANDLE)paramflags = (1, "uFormat"), (1, "hMem")SetClipboardData = prototype(("SetClipboardData", user32), paramflags)SetClipboardData.errcheck = null_errcheck With this: SetClipboardData = pywrap.wrap_winapi(name="SetClipboardData", library=user32, restype=wintypes.BOOL, params=[ Parameter("uFormat", wintypes.UINT), Parameter("hMem", wintypes.HANDLE) ], errcheck=null_errcheck) (end qutation) My idea: something like this library should be implemented in Python to make it more simple to use ctypes. BR, George

3 2

Re: [Python-ideas] Exploiting type-homogeneity in list.sort() (again!)
by Elliot Gorokhovsky 07 Mar '17

07 Mar '17

On Mon, Mar 6, 2017, 4:42 PM Jim J. Jewett <jimjjewett(a)gmail.com> wrote: (1) Good Job. Thanks! (3) Ideally, your graph would have the desired-to-be lines after the as-is lines; for English writing, that would mean putting your (short red) lines to the right of the (tall blue) lines. (4) I suspect colors other than red and blue would be helpful as well, but I am explicitly not a design wiz. My best suggestion (other than "ask someone who isn't me") would be to use blue for as-is and green for to-be. Ya, I know the colors are terrible, I just have no graphic design experience so I figured I'd make the graph the same colors as the diagram (5) I don't know that all-ASCII (or at least all-Latin1) is true for most applications, but it is certainly true for most datasets run in countries where latin1 is sufficient, which includes most places outside of Asia, Africa, and perhaps Eastern Europe. If anything, that strengthens your case, since you can win on plenty of datasets even for applications where it isn't always safe, and for those datasets that do require a wider charset, you're likely to discover this quickly. True. I think a much bigger part of the consideration is also that a lot of software (e.g. file systems) *don't* support unicode, at least by default, so if you're dealing with text you got from another program or from the OS, it's usually ASCII. And usually, our shell scripts our getting their text from other programs (e.g. file names). (6) When I saw the flowchart around f(v, w), at first I was thinking about the key function used in some sorting... I suppose that isn't relevant, since those sorts (If I Recall Correctly) already create a parallel array to avoid recomputing the keys, but ... it might be worth clarifying, if you can find a way to do it easily without adding too much complexity. Maybe just change "this f" to "the compare function f"? You are correct -- key sorts create a parallel array. In fact, *all* sorts create a parallel array, for safety: the only way to make sure the objects aren't getting mutated as you sort is to keep them safe! If the objects are getting mutated during the sort, something is clearly going horribly wrong, but at least you won't segfault. (This is not part of my patch -- it's part of the original implementation). (7) I hope you have put in a pull request to get this added to python 3.7. Thanks! I don't think I can make pull requests, but I am going to submit a fixed version to the bug tracker (Tim pointed out that my current code isn't thread-safe or adversary-safe because it stores compare_function in a global. I have to modify the code keep it in local scope and pass in to every function that needs it. This will make the diff hairier, but not increase code complexity. -jJ

1 0

get() method for list and tuples
by Michel Desmoulin 06 Mar '17

06 Mar '17

dict.get() is a very useful method, but for lists and tuples, we need to rely on try/except instead. Can we get list.get and tuple.get as well? Also, for list, a list.setdefault like the dict.setdefault would be logical.

18 69

for/except/else
by Wolfgang Maier 05 Mar '17

05 Mar '17

I know what the regulars among you will be thinking (time machine, high bar for language syntax changes, etc.) so let me start by assuring you that I'm well aware of all of this, that I did research the topic before posting and that this is not the same as a previous suggestion using almost the same subject line. Now here's the proposal: allow an except (or except break) clause to follow for/while loops that will be executed if the loop was terminated by a break statement. The idea is certainly not new. In fact, Nick Coghlan, in his blog post http://python-notes.curiousefficiency.org/en/latest/python_concepts/break_e…, uses it to provide a mental model for the meaning of the else following for/while, but, as far as I'm aware, he never suggested to make it legal Python syntax. Now while it's possible that Nick had a good reason not to do so, I think there would be three advantages to this: - as explained by Nick, the existence of "except break" would strengthen the analogy with try/except/else and help people understand what the existing else clause after a loop is good for. There has been much debate over the else clause in the past, most prominently, a long discussion on this list back in 2009 (I recommend interested people to start with Steven D'Aprano's Summary of it at https://mail.python.org/pipermail/python-ideas/2009-October/006155.html) that shows that for/else is misunderstood by/unknown to many Python programmers. - in some situations for/except/else would make code more readable by bringing logical alternatives closer together and to the same indentation level in the code. Consider a simple example (taken from the docs.python Tutorial: for n in range(2, 10): for x in range(2, n): if n % x == 0: print(n, 'equals', x, '*', n//x) break else: # loop fell through without finding a factor print(n, 'is a prime number') There are two logical outcomes of the inner for loop here - a given number can be either prime or not. However, the two code branches dealing with them end up at different levels of indentation and in different places, one inside and one outside the loop block. This second issue can become much more annoying in more complex code where the loop may contain additional code after the break statement. Now compare this to: for n in range(2, 10): for x in range(2, n): if n % x == 0: break except break: print(n, 'equals', x, '*', n//x) else: # loop fell through without finding a factor print(n, 'is a prime number') IMO, this reflects the logic better. - it could provide an elegant solution for the How to break out of two loops issue. This is another topic that comes up rather regularly (python-list, stackoverflow) and there is again a very good blog post about it, this time from Ned Batchelder at https://nedbatchelder.com/blog/201608/breaking_out_of_two_loops.html. Stealing his example, here's code (at least) a newcomer may come up with before realizing it can't work: s = "a string to examine" for i in range(len(s)): for j in range(i+1, len(s)): if s[i] == s[j]: answer = (i, j) break # How to break twice??? with for/except/else this could be written as: s = "a string to examine" for i in range(len(s)): for j in range(i+1, len(s)): if s[i] == s[j]: break except break: answer = (i, j) break So much for the pros. Of course there are cons, too. The classical one for any syntax change, of course, is: - burden on developers who have to implement and maintain the new syntax. Specifically, this proposal would make parsing/compiling of loops more complicated. Others include: - using except will make people think of exceptions and that may cause new confusion; while that's true, I would argue that, in fact, break and exceptions are rather similar features in that they are gotos in disguise, so except will still be used to catch an interruption in normal control flow. - the new syntax will not help people understand for/else if except is not used; importantly, I'm *not* proposing to disallow the use of for/else without except (if that would ever happen it would be in the *very* distant future) so that would indeed mean that people would encounter for/else, not only in legacy, but also in newly written code. However, I would expect that they would also start seeing for/except increasingly (not least because it solves the "break out of two loops" issue) so they would be nudged towards thinking of the else after for/while more like the else in try/except/else just as Nick proposes it. Interestingly, there has been another proposal on this list several years ago about allowing try/else without except, which I liked at the time and which would have made try/except/]else work exactly as my proposed for/except/else. Here it is: https://mail.python.org/pipermail/python-ideas/2011-November/012875.html - as a result of previous discussions about for/else a section was added to PEP3099 saying: "The else clause in while and for loops will not change semantics, or be removed." However, the proposal here is not to change the else clause semantics, but add an additional except clause. So that's it and while I'm well aware of the slim chances of this getting legal syntax, I would still be happy to get feedback from you :) Best, Wolfgang

11 17