That's not a reason why we shouldn't do it.  Python is the language where speed, correctness, and readability trump performance every time.  We should decide what semantics we want, then do that, period.  And anyway, it seems like some genius always figures out how to make it fast sooner or later ;-) I can believe that, given the current implementation, sets might give up some of their optimizations if they maintained insertion order.  But I don't understand what "flexibility" they would lose.  Apart from being slower, what would set objects give up if they maintained insertion order?  Are there operations on set objects that would no longer be possible? //arry/ On 12/15/19 6:58 PM, Tim Peters wrote:

[Larry Hastings <larry@hastings.org>]

...

As of 3.7, dict objects are guaranteed to maintain insertion order. But set objects make no such guarantee, and AFAIK in practice they don't maintain insertion order either. If they ever appear to, it's an accident you shouldn't rely on.

...

Should they? From Raymond, 22 Dec 2017:

https://twitter.com/raymondh/status/944454031870607360 """ Sets use a different algorithm that isn't as amendable to retaining insertion order. Set-to-set operations lose their flexibility and optimizations if order is required. Set mathematics are defined in terms of unordered sets. In short, set ordering isn't in the immediate future. """

Which is more an answer to "will they?" than "should they?" ;-)

On Mon, Dec 16, 2019 at 1:33 PM Guido van Rossum <guido@python.org> wrote:

Actually, for dicts the implementation came first.

I had tried to implement the Ordered Set. Here is the implementation. https://github.com/methane/cpython/pull/23 Regards,

On 2019-12-16 06:00, Larry Hastings wrote: [...]

These are all performance concerns.  As I mentioned previously in this thread, in my opinion we should figure out what semantics we want for the object, then implement those, and only after that should we worry about performance.  I think we should decide the question "should set objects maintain insertion order?" literally without any consideration about performance implications.

Then this thread is missing arguments saying *why* ordered dicts are actually better, semantics-wise. Originally, making dicts ordered was all about performance (or rather memory efficiency, which falls in the same bucket.) It wasn't added because it's better semantics-wise. Here's one (very simplified and maybe biased) view of the history of dicts: * 2.x: Dicts are unordered, please don't rely on the order. * 3.3: Dict iteration order is now randomized. We told you not to rely on it! * 3.6: We now use an optimized implementation of dict that saves memory! As a side effect it makes dicts ordered, but that's an implementation detail, please don't rely on it. * 3.7: Oops, people are now relying on dicts being ordered. Insisting on people not relying on it is battling windmills. Also, it's actually useful sometimes, and alternate implementations can support it pretty easily. Let's make it a language feature! (Later it turns out MicroPython can't support it easily. Tough luck.) By itself, "we already made dicts do it" is not a great argument in the set *semantics* debate. Of course, it may turn out ordering was a great idea semantics-wise as well, but if I'm reading correctly, so far this thread has one piece of anectodal evidence for that.

[Guido]

... the language should not disappoint them, optimization opportunities be damned.

I would like to distinguish between two kinds of "optimization opportunities": theoretical ones that may or may not be exploited some day, and those that CPython has _already_ exploited. That is, we don't have a blank slate here. As Raymond said, the set implementation already diverged from the dict implementation in fundamental ways for "go fast" reasons. How much are people willing to see set operations slow down to get this new feature? For me, "none" ;-) Really. I have no particular use for "ordered" sets, but have set-slinging code that benefits _today_ from the "go fast" work Raymond did for them. Analogy: it was always obvious that list.sort() is "better" stable than not, but I ended up crafting a non-stable samplesort variant that ran faster than any stable sort anyone tried to write. For years. So we stuck with that, to avoid slowing down sorting across releases. The stable "timsort" finally managed to be _as_ fast as the older samplesort in almost all cases, and was very much faster in many real-world cases. "Goes faster" was the thing that really sold it, and so much so that its increased memory use didn't count for much against it in comparison. Kinda similarly, "ordered dicts" were (as has already been pointed out) originally introduced as a memory optimization ("compact" dicts), where the "ordered" part fell out more-or-less for free. The same approach wouldn't save memory for sets (or so I'm told), so the original motivation for compact dicts doesn't carry over. So I'm +1 on ordered sets if and only if there's an implementation that's at least as fast as what we already have. If not now, then, like ordered dicts evolved, offer a slower OrderedSet type in the `collections` module for those who really want it, and wait for magic ;-) BTW, what should {1, 2} | {3, 4, 5, 6, 7} return as ordered sets? Beats me.; The imbalance between the operands' cardinalities can be arbitrarily large, and "first make a copy of the larger one, then loop over the smaller one" is the obvious way to implement union to minimize the number of lookups needed. The speed penalty for, e.g., considering "the left" operand's elements' insertion orders to precede all "the right" operand's elements' insertion orders can be arbitrarily large. The concept of "insertion order" just doesn't make well-defined sense to me for any operation the produces a set from multiple input sets, unless it means no more than "whatever order happens to be used internally to add elements to the result set". Dicts don't have anything like that, although dict.update comes close, but in that case the result is defined by mutating the dict via a one-at-a-time loop over the argument dict.

[Tim]

BTW, what should

{1, 2} | {3, 4, 5, 6, 7}

return as ordered sets? Beats me.;

[Larry]

The obvious answer is {1, 2, 3, 4, 5, 6, 7}.

Why? An obvious implementation that doesn't ignore performance entirely is: def union(smaller, larger): if len(larger) < len(smaller): smaller, larger = larger, smaller result = larger.copy() for x in smaller: result.add(x) In the example, that would first copy {3, 4, 5, 6, 7}, and then add 1 and 2 (in that order) to it, giving {3, 4, 5, 6, 7, 1, 2} as the result. If it's desired that "insertion order" be consistent across runs, platforms, and releases, then what "insertion order" _means_ needs to be rigorously defined & specified for all set operations. This was comparatively trivial for dicts, because there are, e.g., no commutative binary operators defined on dicts. If you want to insist that `a | b` first list all the elements of a, and then all the elements of b that weren't already in a, regardless of cost, then you create another kind of unintuitive surprise: in general the result of "a | b" will display differently than the result of "b | a" (although the results will compare equal), and despite that the _user_ didn't "insert" anything.

[Tim]

...

If it's desired that "insertion order" be consistent across runs, platforms, and releases, then what "insertion order" _means_ needs to be rigorously defined & specified for all set operations. This was comparatively trivial for dicts, because there are, e.g., no commutative binary operators defined on dicts.

[Larry]

My intuition is that figuring out sensible semantics here is maybe not trivial, but hardly impossible. If this proposal goes anywhere I'd be willing to contribute to figuring it out.

No, it _is_ easy. It's just tedious, adding piles of words to the docs, and every constraint also constrains possible implementations. You snipped my example of implementing union, which you should really think about instead ;-)

...

If you want to insist that `a | b` first list all the elements of a, and then all the elements of b that weren't already in a, regardless of cost, then you create another kind of unintuitive surprise: in general the result of "a | b" will display differently than the result of "b | a" (although the results will compare equal), and despite that the _user_ didn't "insert" anything.

Call me weird--and I won't disagree--but I find nothing unintuitive about that. After all, that's already the world we live in: there are any number of sets that compare as equal but display differently. In current Python:

...

...

...

a = {'a', 'b', 'c'} d = {'d', 'e', 'f'} a | d {'f', 'e', 'd', 'a', 'b', 'c'} d | a {'f', 'b', 'd', 'a', 'e', 'c'}

Yup, it happens But under the sample union implementation I gave, it would never happen when the sets had different cardinalities (the different sizes are used to force a "standard" order then). For mathematical sets, | is commutative (it makes no difference to the result if the arguments are swapped - but can make a _big_ difference to implementation performance unless the implementation is free to pick the better order).

... This is also true for dicts, in current Python, which of course do maintain insertion order. Dicts don't have the | operator, so I approximate the operation by duplicating the dict (which AFAIK preserves insertion order)

Ya, it does, but I don't believe that's documented (it should be).

and using update.

Too different to be interesting here - update() isn't commutative. For sets, union, intersection, and symmetric difference are commutative.

... Since dicts already behave in exactly that way, I don't think it would be too surprising if sets behaved that way too. In fact, I think it's a little surprising that they behave differently, which I suppose was my whole thesis from the beginning.

I appreciate that dicts and sets behave differently in visible ways now. It just doesn't bother me enough that I'm cool with slowing set operations to "fix that".

[Petr Viktorin <encukou@gmail.com>]

... Originally, making dicts ordered was all about performance (or rather memory efficiency, which falls in the same bucket.) It wasn't added because it's better semantics-wise.

As I tried to flesh out a bit in a recent message, the original "compact dict" idea got all the memory savings, but did _not_ maintain insertion order. Maintaining insertion order too complicated deletions (see recent message), but was deliberately done because people really did want "ordered dicts".

Here's one (very simplified and maybe biased) view of the history of dicts:

* 2.x: Dicts are unordered, please don't rely on the order. * 3.3: Dict iteration order is now randomized. We told you not to rely on it! * 3.6: We now use an optimized implementation of dict that saves memory! As a side effect it makes dicts ordered, but that's an implementation detail, please don't rely on it. * 3.7: Oops, people are now relying on dicts being ordered. Insisting on people not relying on it is battling windmills. Also, it's actually useful sometimes, and alternate implementations can support it pretty easily. Let's make it a language feature! (Later it turns out MicroPython can't support it easily. Tough luck.)

A very nice summary! My only quibble is as above: the "compact dict" implementation doesn't maintain insertion order naturally, _unless_ there are no deletions (which is, e.g., true of dicts constructed to pass keyword arguments). The code got hairier to maintain insertion order in the presence of mixing insertions and deletions.

[Larry]

Didn't some paths also get sliiiiightly slower as a result of maintaining insertion order when mixing insertions and deletions?

I paid no attention at the time. But in going from "compact dict" to "ordered dict", deletion all by itself got marginally cheaper. The downside was the need to rearrange the whole dict when too many "holes" built up. "Compact (but unordered) dict" doesn't need that.

My recollection is that that was part of the debate--not only "are we going to regret inflicting these semantics on posterity, and on other implementations?", but also "are these semantics worth the admittedly-small performance hit, in Python's most important and most-used data structure?".

There's a layer of indirection in compact dicts - lookups are distributed across two arrays. In non-compact unordered dicts, everything is in a single array. Cache effects may or may not make a measurable difference then, depending on all sorts of things.

Also, I don't recall anything about us resigning ourselves to explicitly maintain ordering on dicts because people were relying on it, "battling windmills", etc. Dict ordering had never been guaranteed, a lack of guarantee Python had always taken particularly seriously. Rather, we decided it was a desirable feature, and one worth pursuing even at the cost of a small loss of performance.

I'm not convinced there was a loss of performance. The delay between the implementation supplying ordered dicts, and the language guaranteeing it, was, I suspect, more a matter of getting extensive real-world experience about whether the possible new need to massively rearrange dict internals to remove "holes" would bite someone too savagely to live with. But, again, I wasn't paying attention at the time.

One prominent Python core developer** wanted this feature for years, and I recall them saying something like:

Guido says, "When a programmer iterates over a dictionary and they see the keys shift around when the dictionary changes, they learn something!" To that I say--"Yes! They learn that Python is unreliable and random!"

I never wanted ordered dicts, but never objected to them either. All in all, given that _I_ haven't seen a performance degradation, I like that they're more predictable, and love the memory savings. But as Raymond said (& I elaborated on), there's reason to believe that the implementation of ordered dicts is less suited to sets, where high rates of mixing adds and deletes is more common (thus triggering high rates of massive internal dict rearranging). Which is why I said much earlier that I'd be +1 on ordered sets only when there's an implementation that's as fast as what we have now. Backing up:

Python is the language where speed, correctness, and readability trump performance every time.

Speed trumping performance didn't make any sense ;-) So assuming you didn't intend to type "speed", I think you must have, say, Scheme or Haskell in mind there. "Practicality beats purity" is never seen on forums for those languages. Implementation speed & pain have played huge rules in many Python decisions. As someone who has wrestled with removing the GIL, you should know that better than anyone ;-)

... [Larry]

...

One prominent Python core developer** wanted this feature for years, and I recall them saying something like:

Guido says, "When a programmer iterates over a dictionary and they see the keys shift around when the dictionary changes, they learn something!" To that I say--"Yes! They learn that Python is unreliable and random!"

[Tim]

I never wanted ordered dicts, but never objected to them either. All in all, given that _I_ haven't seen a performance degradation, I like that they're more predictable, and love the memory savings.

That reads like I was correcting Larry for misquoting _me_. Sorry! He wasn't quoting me, and I didn't think he was. What he did quote was delightfully snarky enough that I didn't want to snip it, but not substantial enough to be worth the bother of addressing. So I just moved on to summarize what I said at the time (i.e., nothing).

On 12/17/19 2:02 AM, Steven D'Aprano wrote:

Without being facetious[1] if you don't care about performance, you don't need a set, you could use a list.

Lists don't enforce uniqueness.  Apart from that a list would probably work fine for my needs; in my admittedly-modest workloads I would probably never notice a performance difference.  My anecdote was merely a jumping-off point for the discussion. "I don't care about performance" is not because I'm aching for Python to run my code slowly.  It's because I'm 100% confident that the Python community will lovingly optimize the implementation.  So when I have my language designer hat on, I really don't concern myself with performance.  As I thought I said earlier in the thread, I think we should figure out the semantics we want /first,/ and /then/ we figure out how to make it fast. I'll also cop to "a foolish consistency is the hobgoblin of little minds".  I lack this strongly mathematical view of sets others have espoused; instead I view them more like "dicts without values".  I'm therefore disgruntled by this inconsistency between what are I see as closely related data structures, and it makes sense to me that they'd maintain their insertion order the same way that dictionaries now do. //arry/

On Tue, 17 Dec 2019 at 11:48, Paul Moore <p.f.moore@gmail.com> wrote:

On Tue, 17 Dec 2019 at 11:13, Larry Hastings <larry@hastings.org> wrote:

...

I lack this strongly mathematical view of sets others have espoused; instead I view them more like "dicts without values". I'm therefore disgruntled by this inconsistency between what are I see as closely related data structures, and it makes sense to me that they'd maintain their insertion order the same way that dictionaries now do.

I'll admit to a mathematical background, which probably influences my views. But I view sets as "collections" of values - values are "in" the set or not. I don't see them operationally, in the sense that you add and remove things from the set. Adding and removing are mechanisms for changing the set, but they aren't fundamentally what sets are about (which for me is membership). So insertion order on sets is largely meaningless for me (it doesn't matter *how* it got there, what matters is whether it's there now).

Having said that, I also see dictionaries as mappings from key to value, so insertion order is mostly not something I care about for dictionaries either. I can see the use cases for ordered dictionaries, and now we have insertion order, it's useful occasionally, but it's not something that was immediately obvious to me based on my intuition. Similarly, I don't see sets as *needing* insertion order, although I concede that there probably are use cases, similar to dictionaries. The question for me, as with dictionaries, is whether the cost (in terms of clear semantics, constraints on future implementation choices, and actual performance now) is justified by the additional capabilities (remembering that personally, I'd consider insertion order preservation as very much a niche requirement).

As a random data point, I often see the pattern where one needs to remove duplicates from the list while preserving the order of first appearance. This is for example needed to get stability in various type-checking situations (like union items, type variables in base classes, type queries etc.) One can write a four line helper to achieve this, but I can see that having order preserving set could be useful. So again, it is "nice to have but not really critical". -- Ivan

[Larry]

"I don't care about performance" is not because I'm aching for Python to run my code slowly. It's because I'm 100% confident that the Python community will lovingly optimize the implementation.

I'm not ;-)

So when I have my language designer hat on, I really don't concern myself with performance. As I thought I said earlier in the thread, I think we should figure out the semantics we want first, and then we figure out how to make it fast.

Pretty much the opposite of how Python started. The original lists and dicts were deliberately designed to have dirt simple implementations, in reaction against ABC's "theoretically optimal" data structures that were a nightmare to maintain, and had so much overhead to support "optimality" in all cases that they were, in fact, much slower in common cases. There isn't magic waiting to be uncovered here: if you want O(1) deletion at arbitrary positions in an ordered sequence, a doubly linked list is _the_ way to do it. That's why, e.g., Raymond said he still uses a doubly linked list, instead of an ordered dict, in the LRU cache implementation. If that isn't clear, a cache can be maintained in least-to-most recently accessed order with an ordered dict like so: if key in cache: cached_value = cache.pop(key) # remove key else: compute cached_value assert key not in cache cache[key] = cached_value # most recently used at the end now return cached_value and deleting the least recently used is just "del cache[next(iter(cache))]" (off topic, just noting this is a fine use for the "first()" function that's the subject of a different thread). We _could_ structure an ordered dict's hash+key+value records as a doubly linked list instead (and avoid the need for O(N) reorganizations). But then we piss away much of the memory savings (to store the new links) that was the _point_ of compact dicts to begin with. So there was a compromise. No links, deletion on its own is O(1), but can periodically require O(N) under-the-covers table reorganizations to squash out the holes. "Suitable enough" for ordered dicts, but _thought_ to be unsuitable for ordered sets (which appear to have higher rates of mixing deletions with insertions - the LRU cache example being an exception). But there are also other optimizations in the current set implementation, so "fine, add the doubly linked list to sets but not to dicts" is only part of it. Which may or may not be possible to match, let alone beat, in an ordered set implementation. A practical barrier now is that Python is too mature to bank on loving optimizations _after_ a change to a core feature is released. It's going to need a highly polished implementation first. I certainly don't object to anyone trying, but it won't be me ;-)

[Nick Coghlan <ncoghlan@gmail.com>]

Starting with "collections.OrderedSet" seems like a reasonable idea, though - that way "like a built-in set, but insertion order preserving" will have an obvious and readily available answer, and it should also make performance comparisons easier.

Ya, I suggested starting with collections.OrderedSet earlier, but gave up on it. The problem is that the "use case" here isn't really a matter of functionality, but of consistency: "it would be nice if", like dicts enjoy now, the iteration order of sets was defined in an implementation-independent way. That itch isn't scratched unless the builtin set type defines it.

On Fri., 20 Dec. 2019, 2:58 am Tim Peters, <tim.peters@gmail.com> wrote:

[Nick Coghlan <ncoghlan@gmail.com>]

...

Starting with "collections.OrderedSet" seems like a reasonable idea, though - that way "like a built-in set, but insertion order preserving" will have an obvious and readily available answer, and it should also make performance comparisons easier.

Ya, I suggested starting with collections.OrderedSet earlier, but gave up on it.

The problem is that the "use case" here isn't really a matter of functionality, but of consistency: "it would be nice if", like dicts enjoy now, the iteration order of sets was defined in an implementation-independent way. That itch isn't scratched unless the builtin set type defines it.

I took Larry's request a slightly different way: he has a use case where he wants order preservation (so built in sets aren't good), but combined with low cost duplicate identification and elimination and removal of arbitrary elements (so lists and collections.deque aren't good). Organising a work queue that way seems common enough to me to be worthy of a stdlib solution that doesn't force you to either separate a "job id" from the "job" object in an ordered dict, or else use an ordered dict with "None" values. So while it means answering "No" to the "Should builtin sets preserve order?" question (at least for now), adding collections.OrderedSet *would* address that "duplicate free pending task queue" use case. Cheers, Nick.

[David Mertz <mertz@gnosis.cx>]

It's not obvious to me that insertion order is even the most obvious or most commonly relevant sort order. I'm sure it is for Larry's program, but often a work queue might want some other order. Very often queues might instead, for example, have a priority number assigned to them.

Indeed, and it makes me more cautious that claims for the _usefulness_ (rather than just consistency) of an ordered set are missing an XY problem. The only "natural" value of insertion-order ordering for a dynamic ordered set is that it supports FIFO queues. Well, that's one thing that a deque already excels at, but much more obviously, flexibly, and space- and time- efficiently. For dicts the motivating use cases were much more "static", like preserving textual order of keyword argument specifications, and avoiding gratuitous changing of order when round-tripping key-value encodings like much of JSON. So what problem(s) would a dynamic ordered set really be aiming at? I don't know. Consistency & predictability I understand and appreciate, but little beyond that. Even FIFO ordering is somewhat a PITA, since `next(iter(set))` is an overly elaborate way to need to spell "get the first" if a FIFO queue _is_ a prime dynamic use case. And there's no efficient way at all to access the other end (although I suppose set.pop() would - like dict.popitem() - change to give a _destructive_ way to get at "the other end").

[Nick]

I must admit that I was assuming without stating that a full OrderedSet implementation would support the MutableSequence interface.

Efficient access via index position too would be an enormous new requirement, My bet: basic operations would need to change from O(1) to O(log(N)). BTW, in previous msgs there are links to various implementations calling themselves "ordered sets". One of them supplies O(1) indexing, but at the expense of making deletion O(N) (!): https://pypi.org/project/ordered-set/ If efficient indexing is really wanted, then the original "use case" Larry gave was definitely obscuring an XY problem ;-)

On Fri, Dec 20, 2019 at 4:15 PM Wes Turner <wes.turner@gmail.com> wrote:

How slow and space-inefficient would it be to just implement the set methods on top of dict?

Speed: Dict doesn't cache the position of the first item. Calling next(iter(D)) repeatedly is O(N) in worst case. Space: It waste 8bytes per member.

Do dicts lose insertion order when a key is deleted? AFAIU, OrderedDict do not lose insertion order on delete.

Dict keeps insertion order after deletion too.

Would this limit the utility of an ordered set as a queue? What set methods does a queue need to have?

I want O(1) D.popleft(). (The name is borrowed from deque. popfirst() would be better maybe). -- Inada Naoki <songofacandy@gmail.com>

[Wes Turner <wes.turner@gmail.com>]

...

How slow and space-inefficient would it be to just implement the set methods on top of dict?

[Inada Naoki <songofacandy@gmail.com>]

Speed: Dict doesn't cache the position of the first item. Calling next(iter(D)) repeatedly is O(N) in worst case. ...

See also Raymond's (only) message in this thread. We would also lose low-level speed optimizations specific to the current set implementation. And we would need to define what "insertion order" _means_ for operators (union, intersection, symmetric difference) that build a new set out of other sets without a user-level "insert" in sight. However that's defined, it may constrain possible implementations in ways that are inherently slower (for example, may require the implementation to iterate over the larger operand where they currently iterate over the smaller). And the current set implementation (like the older dict implementation) never needs to "rebuild the table from scratch" unless the cardinality of the set keeps growing. As Raymond telegraphically hinted, the current dict implementation can, at times, in the presence of deletions, require rebuilding the table from scratch even if the dict's maximum size remains bounded. That last can't be seen directly from Python code (rebuilding the table is invisible at the Python level). Here's a short example: d = dict.fromkeys(range(3)) while True: del d[0] d[0] = None Run that with a breakpoint set on dictobject.c's `dictresize()` function. You'll see that it rebuilds the table from scratch every 3rd time through the loop. In effect, for the purpose of deciding whether it needs to rebuild, the current dict implementation sees no difference between adding a new element and deleting an existing element Deleting leaves behind "holes" that periodically have to be squashed out of existence so that insertion order can be maintained in a dead simple way upon future additions.

[Inada Naoki <songofacandy@gmail.com>]

I just meant the performance of the next(iter(D)) is the most critical part when you implement orderdset on top of the current dict and use it as a queue.

Which is a good point. I added a lot more, though, because Wes didn't even mention queues in his question: [Wes Turner <wes.turner@gmail.com>]

...

...

...

How slow and space-inefficient would it be to just implement the set methods on top of dict?

I can't guess what he was _really_ asking about, so now he's got lots of answers ;-)

This code should be O(N), but it's O(N^2) if q is implemented on top of the dict.

while q: item = q.popleft()

Sorry for the confusion.

To flesh this out, the FIFO queue entries are all together in a contiguous vector, with no "holes" in the middle. Pushing a new item appends "to the right" (higher index in the vector), while popping an item leaves "a hole" at the left. But there are no holes "in the middle" in this case. So the first real entry is at a higher index with every pop, but iteration starts at index 0 every time. The more pops there are, the more holes iteration has to skip over, one at a time, to find the first real entry remaining. Until pushing a new item would fall off the right end of the vector. Then the table is rebuilt from scratch, moving all the real entries to form a contiguous block starting at index 0 again.

...

And the current set implementation (like the older dict implementation) never needs to "rebuild the table from scratch" unless the cardinality of the set keeps growing.

It is a bit misleading. If "the cardinality of the set" means len(S),

Yes.

set requires the rebuild in low frequency if the its items are random.

Anyway, it is a smaller problem than next(iter(D)) because of the amortized cost is O(1).

For the specific case of FIFO queues, sure. In general, though, "O(1) period". is more desirable than "amortized O(1)". This is especially true when sets get very large.

Current dict is not optimized for queue usage.

Nor should it be:-) That's what collections.deque is for, pushes and pops, at both ends, always time O(1) period. No holes, no internal rearrangements, and O(1) "wasted" space.

(mixing together messages in the thread, sorry threaded-view readers) On 12/19/19 3:15 PM, Tim Peters wrote:

[Nick]

...

I took Larry's request a slightly different way: [...] Only Larry can answer whether that would meet his perceived need. My _guess_ is that he wouldn't know OrderedSet existed, and, even if he did, he'd use a dict with None values anyway (because it's less hassle and does everything he wanted).

At last, something I can speak knowledgeably about: Larry's use case!  Regarding Larry, I'd say 1. his use case was small enough that almost anything maintaining order would have worked, even a list, 2. he often /does have/ a pretty good idea what goodies are salted away in the Python standard library, and 3. a hypothetical collections.OrderedSet would probably work just fine.  And he'd probably use it too, as that makes the code clearer / easier to read.  If you read code using an OrderedSet, you know what the intent was and what the semantics are.  If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve.  Let's hope those comments are accurate! Also, speaking personally, at least once (maybe twice?) in this thread folks have asked "would YOU, Mr Larry, really want ordered sets if it meant sets were slightly slower?" The first thing I'd say is, I'm not sure why people should care about what's best for me.  That's sweet of you!  But you really shouldn't. The second thing is, my needs are modest, so the speed hit we're talking about would likely be statistically insignificant, for me. And the third thing is, I don't really put the set() API through much of a workout anyway.  I build sets, I add and remove items, I iterate over them, I do the occasional union, and only very rarely do I use anything else.  Even then, when I write code where I reach for a fancy operation like intersection or symmetric_difference--what tends to happen is, I have a rethink and a refactor, and after I simplify my code I don't need the fancy operations anymore.  I can't remember the last time I used one of these fancy operations where the code really stuck around for a long time. So, personally?  Sure, I'd take that tradeoff.  As already established, I like that dict objects maintain their order, and I think it'd be swell if sets maintained their order too.  I suspect the performance hit wouldn't affect /me/ in any meaningful way, and I could benefit from the order-maintaining semantics.  I bet it'd have other benefits too, like making regression tests more stable.  And my (admittedly uninformed!) assumption is, the loss of performance would mostly be in these sophisticated operations that I never seem to use anyway. But I don't mistake my needs for the needs of the Python community at large.  I'd be mighty interested to read other folks coming forward and saying, for example, "please don't make set objects any slower!" and talking us through neat real-world use cases.  Bonus points if you include mind-boggling numbers and benchmarks! On 12/20/19 5:09 AM, Peter Wang wrote:

As Larry pointed out earlier, ordered dicts posed a problem for MicroPython.

Just a minor correction: that wasn't me, that was Petr Viktorin. Ten days left until we retire 2.7, //arry/

To begin with, please compare performance of dict-with-None-values to that of a set, for operations that can be expressed by both (e.g. both have update()). On Mon, Dec 23, 2019 at 18:08 Kyle Stanley <aeros167@gmail.com> wrote:

Larry Hastings wrote:

...

a hypothetical collections.OrderedSet would probably work just fine.

I'm also in agreement with adding a collections.OrderedSet. There certainly seems to be a practical use case for a Set that preserves insertion order, but with significant push back to modifying the existing Set implementation (primarily due to performance concerns).

If later down the road an improvement to OrderedSet is made that gives it equal or better average performance across the board compared to Set, we can consider changing the default implementation *if* there's significant demand for it.

Larry Hastings wrote:

...

And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

This is an excellent point. My first thought if someone were to be using a Dict with all values set to None would be: why not use a Set here? As Larry said, the need for preservation of insertion order would have to be explicitly described in the code comments. Realistically speaking, code comments are not something that can be consistently relied upon, especially if it's part of some boilerplate format that gets replicated or if the container is used in multiple locations. I'd much rather have a dedicated data structure that clearly describes what it does based on the name alone, IMO that's a million times better for readability purposes.

Also, this is mostly speculation since I haven't ran any benchmarks for an OrderedSet implementation, but I strongly suspect that OrderedSet will end up having better average performance for add, pop, and update than trying to use a dictionary with None values (assuming it's implemented in C or at least with a C accelerator).

Not to mention allowing the ability to update (for both addition and removal) based on intersections and unions across ordered sets, which currently isn't possible to do with dictionaries (at least not directly with |=, &=, -=. and ^=). I'm not sure how much of a practical use case this would have for ordered sets specifically, but it's a nice bonus.

On Sat, Dec 21, 2019 at 7:59 AM Larry Hastings <larry@hastings.org> wrote:

...

(mixing together messages in the thread, sorry threaded-view readers)

On 12/19/19 3:15 PM, Tim Peters wrote:

[Nick]

I took Larry's request a slightly different way:

[...]

Only Larry can answer whether that would meet his perceived need. My _guess_ is that he wouldn't know OrderedSet existed, and, even if he did, he'd use a dict with None values anyway (because it's less hassle and does everything he wanted).

At last, something I can speak knowledgeably about: Larry's use case! Regarding Larry, I'd say

1. his use case was small enough that almost anything maintaining order would have worked, even a list, 2. he often *does have* a pretty good idea what goodies are salted away in the Python standard library, and 3. a hypothetical collections.OrderedSet would probably work just fine. And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

Also, speaking personally, at least once (maybe twice?) in this thread folks have asked "would YOU, Mr Larry, really want ordered sets if it meant sets were slightly slower?"

The first thing I'd say is, I'm not sure why people should care about what's best for me. That's sweet of you! But you really shouldn't.

The second thing is, my needs are modest, so the speed hit we're talking about would likely be statistically insignificant, for me.

And the third thing is, I don't really put the set() API through much of a workout anyway. I build sets, I add and remove items, I iterate over them, I do the occasional union, and only very rarely do I use anything else. Even then, when I write code where I reach for a fancy operation like intersection or symmetric_difference--what tends to happen is, I have a rethink and a refactor, and after I simplify my code I don't need the fancy operations anymore. I can't remember the last time I used one of these fancy operations where the code really stuck around for a long time.

So, personally? Sure, I'd take that tradeoff. As already established, I like that dict objects maintain their order, and I think it'd be swell if sets maintained their order too. I suspect the performance hit wouldn't affect *me* in any meaningful way, and I could benefit from the order-maintaining semantics. I bet it'd have other benefits too, like making regression tests more stable. And my (admittedly uninformed!) assumption is, the loss of performance would mostly be in these sophisticated operations that I never seem to use anyway.

But I don't mistake my needs for the needs of the Python community at large. I'd be mighty interested to read other folks coming forward and saying, for example, "please don't make set objects any slower!" and talking us through neat real-world use cases. Bonus points if you include mind-boggling numbers and benchmarks!

On 12/20/19 5:09 AM, Peter Wang wrote:

As Larry pointed out earlier, ordered dicts posed a problem for MicroPython.

Just a minor correction: that wasn't me, that was Petr Viktorin.

Ten days left until we retire 2.7,

*/arry* _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/JYSJ55CW... Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/2KEAXZBQ... Code of Conduct: http://python.org/psf/codeofconduct/

-- --Guido (mobile)

On Tue, Dec 24, 2019 at 1:57 PM Kyle Stanley <aeros167@gmail.com> wrote:

Add (much faster for dicts):

...

...

...

timeit.timeit("s = set(); s.add(0)", number=100_000_000) 13.330938750001224 timeit.timeit("d = {}; d[0] = None", number=100_000_000) 5.788865385999088

I think this is an artifact of Python not having an empty set literal.

...

...

timeit.timeit("s = set(); s.add(0)", number=100_000_000) 13.275540543720126 timeit.timeit("d = dict(); d[0] = None", number=100_000_000) 13.044076398015022 timeit.timeit("d = {}; d[0] = None", number=100_000_000) 6.088695731014013 timeit.timeit("s = {1}; s.add(0)", number=100_000_000) 9.260965215042233 timeit.timeit("d = {1:2}; d[0] = None", number=100_000_000) 8.75433829985559

When both use the constructor call or both use a literal, the difference is far smaller. I'd call this one a wash. ChrisA

On 12/23/19 8:09 PM, Kyle Stanley wrote:

Chris Angelico wrote:

...

I think this is an artifact of Python not having an empty set literal. [snip] When both use the constructor call or both use a literal, the difference is far smaller. I'd call this one a wash.

Ah, good catch. I hadn't considered that it would make a substantial difference, but that makes sense. Here's an additional comparison between "{}"  and "dict()" to confirm it:

...

...

...

timeit.timeit("{}", number=100_000_000) 2.1038335599987477 timeit.timeit("dict()", number=100_000_000) 10.225583500003268

We could also go the other way with it, set / dict-map-to-dontcare with one element, because that way we /can/ have a set literal: >>> timeit.timeit("set()", number=100_000_000) 8.579900023061782 >>> timeit.timeit("dict()", number=100_000_000) 10.473437276901677 >>> timeit.timeit("{0}", number=100_000_000) 5.969995185965672 >>> timeit.timeit("{0:0}", number=100_000_000) 6.24465325800702 (ran all four of those just so you see a relative sense on my laptop, which I guess is only sliiiightly slower than Kyle's) Happy holidays, //arry/

On Mon, Dec 23, 2019 at 8:56 PM Kyle Stanley <aeros167@gmail.com> wrote:

...

To begin with, please compare performance of dict-with-None-values to that of a set, for operations that can be expressed by both (e.g. both have update()).

Good idea. It would be useful to have a baseline comparison. I emboldened the comparisons with a notable difference.

Tested on: Version: Python 3.8.0 OS: Linux kernel 5.4.5 CPU: Intel i5-4460

Initialization (about the same):

...

...

...

timeit.timeit("set(i for i in range(1000))", number=100_000) 4.878508095000143 timeit.timeit("{i: None for i in range(1000)}", number=100_000) 4.9192055170024105

Membership (about the same):

...

...

...

timeit.timeit("random.randint(0, 999) in s", setup="import random; s = set(i for i in range(1000))", number=10_000_000) 7.992674231001729 timeit.timeit("random.randint(0, 999) in d", setup="import random; d = {i: None for i in range(1000)}", number=10_000_000) 8.032404395999038

Add (much faster for dicts):

...

...

...

timeit.timeit("s = set(); s.add(0)", number=100_000_000) 13.330938750001224 timeit.timeit("d = {}; d[0] = None", number=100_000_000) 5.788865385999088

Update (much faster for updating sets):

...

...

...

timeit.timeit("s.update(other_s)", setup="s = set(); other_s = set(i for i in range(1000))", number=1_000_000) 6.2428832090008655 timeit.timeit("d.update(other_d)", setup="d = {}; other_d = {i: None for i in range(1000)}", number=1_000_000) 13.031371458000649

Create list from keys (faster for sets):

...

...

...

timeit.timeit("list(s)", setup="s = set(i for i in range(1000))", number=10_00_000) 5.24364303600305 timeit.timeit("list(d)", setup="d = {i: None for i in range(1000)}", number=10_00_000) 6.303017043999716

Removal isn't easily comparable, since s.pop(), s.discard(), d.pop(), and d.popitem() all behave quite differently. Also, I'm sure these benchmarks could be improved significantly, particularly with the "Add" ones. This should provide a decent general idea though.

On Mon, Dec 23, 2019 at 8:12 PM Guido van Rossum <guido@python.org> wrote:

...

To begin with, please compare performance of dict-with-None-values to that of a set, for operations that can be expressed by both (e.g. both have update()).

On Mon, Dec 23, 2019 at 18:08 Kyle Stanley <aeros167@gmail.com> wrote:

...

Larry Hastings wrote:

...

a hypothetical collections.OrderedSet would probably work just fine.

I'm also in agreement with adding a collections.OrderedSet. There certainly seems to be a practical use case for a Set that preserves insertion order, but with significant push back to modifying the existing Set implementation (primarily due to performance concerns).

If later down the road an improvement to OrderedSet is made that gives it equal or better average performance across the board compared to Set, we can consider changing the default implementation if there's significant demand for it.

Larry Hastings wrote:

...

And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

This is an excellent point. My first thought if someone were to be using a Dict with all values set to None would be: why not use a Set here? As Larry said, the need for preservation of insertion order would have to be explicitly described in the code comments. Realistically speaking, code comments are not something that can be consistently relied upon, especially if it's part of some boilerplate format that gets replicated or if the container is used in multiple locations. I'd much rather have a dedicated data structure that clearly describes what it does based on the name alone, IMO that's a million times better for readability purposes.

Also, this is mostly speculation since I haven't ran any benchmarks for an OrderedSet implementation, but I strongly suspect that OrderedSet will end up having better average performance for add, pop, and update than trying to use a dictionary with None values (assuming it's implemented in C or at least with a C accelerator).

Not to mention allowing the ability to update (for both addition and removal) based on intersections and unions across ordered sets, which currently isn't possible to do with dictionaries (at least not directly with |=, &=, -=. and ^=). I'm not sure how much of a practical use case this would have for ordered sets specifically, but it's a nice bonus.

On Sat, Dec 21, 2019 at 7:59 AM Larry Hastings <larry@hastings.org> wrote:

...

(mixing together messages in the thread, sorry threaded-view readers)

On 12/19/19 3:15 PM, Tim Peters wrote:

[Nick]

I took Larry's request a slightly different way:

[...]

Only Larry can answer whether that would meet his perceived need. My _guess_ is that he wouldn't know OrderedSet existed, and, even if he did, he'd use a dict with None values anyway (because it's less hassle and does everything he wanted).

At last, something I can speak knowledgeably about: Larry's use case! Regarding Larry, I'd say

his use case was small enough that almost anything maintaining order would have worked, even a list, he often does have a pretty good idea what goodies are salted away in the Python standard library, and a hypothetical collections.OrderedSet would probably work just fine. And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

Also, speaking personally, at least once (maybe twice?) in this thread folks have asked "would YOU, Mr Larry, really want ordered sets if it meant sets were slightly slower?"

The first thing I'd say is, I'm not sure why people should care about what's best for me. That's sweet of you! But you really shouldn't.

The second thing is, my needs are modest, so the speed hit we're talking about would likely be statistically insignificant, for me.

And the third thing is, I don't really put the set() API through much of a workout anyway. I build sets, I add and remove items, I iterate over them, I do the occasional union, and only very rarely do I use anything else. Even then, when I write code where I reach for a fancy operation like intersection or symmetric_difference--what tends to happen is, I have a rethink and a refactor, and after I simplify my code I don't need the fancy operations anymore. I can't remember the last time I used one of these fancy operations where the code really stuck around for a long time.

So, personally? Sure, I'd take that tradeoff. As already established, I like that dict objects maintain their order, and I think it'd be swell if sets maintained their order too. I suspect the performance hit wouldn't affect me in any meaningful way, and I could benefit from the order-maintaining semantics. I bet it'd have other benefits too, like making regression tests more stable. And my (admittedly uninformed!) assumption is, the loss of performance would mostly be in these sophisticated operations that I never seem to use anyway.

But I don't mistake my needs for the needs of the Python community at large. I'd be mighty interested to read other folks coming forward and saying, for example, "please don't make set objects any slower!" and talking us through neat real-world use cases. Bonus points if you include mind-boggling numbers and benchmarks!

On 12/20/19 5:09 AM, Peter Wang wrote:

As Larry pointed out earlier, ordered dicts posed a problem for MicroPython.

Just a minor correction: that wasn't me, that was Petr Viktorin.

Ten days left until we retire 2.7,

/arry

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/JYSJ55CW... Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/2KEAXZBQ... Code of Conduct: http://python.org/psf/codeofconduct/

-- --Guido (mobile)

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/A7KJQJBC... Code of Conduct: http://python.org/psf/codeofconduct/

Tim Peters wrote:

Sorry! A previous attempt to reply got sent before I typed anything :-(

No worries, I only saw the link in the footer to the PSF CoC, and I was mildly concerned for a moment. My first thought was "Oh no, what did I do?". Thanks for clearing that up (:

The collision resolution strategy for sets evolved to be fancier than for dicts, to reduce cache misses. This is important for sets because the _only_ interesting thing about an element wrt a set is whether or not the set contains it. Lookup speed is everything for sets.

Huh, that's quite interesting. For some reason, I had assumed in the back of my head (without giving it much thought) that the average collision rate would be the same for set items and dict keys. Thanks for the useful information.

If you use a contiguous range of "reasonable" integers for keys, the integer hash function is perfect: there's never a collision. So any such test misses all the work Raymond did to speed set lookups. String keys have sufficiently "random" hashes to reliably create collisions, though. Cache misses can, of course, have massive effects on timing.

Ah, I forgot to consider how the hash function actually works for continuous integers. A better comparison to demonstrate the collision differences would likely use random strings. Also, I believe that max "reasonable" integer range of no collision is (-2305843009213693951, 2305843009213693951), as defined in Include/pyhash.h ( https://github.com/python/cpython/blob/e42b705188271da108de42b55d9344642170a... ).

In the former case you're primarily measuring the time to look up the "add" method of sets (that's more expensive than adding 0 to the set). A better comparison would, e.g., move `add = s.add` to a setup line, and use plain "add(0)" in the loop.

Good point, there's also what Chris Angelico pointed out as well: dicts have a significant advantage in this case for having a literal for initialization. From my understanding, this ends up having a minimal performance impact in most realistic code (similar to method lookup time), but it makes a very substantial difference in this case since initialization of the containers takes up a significant portion of each iteration. I suspect my initialization comparison might also be flawed for similar reasons, but I'm glad that at least 3/5 of my comparisons were mostly reasonable. So far, the performance difference between set.update() and dict.update() were the most notable. I'll likely spend some more time experimenting in the next couple of weeks or so, and report back if I find any interesting results. In the meantime, anyone can certainly feel free to improve upon my existing comparisons. On Mon, Dec 23, 2019 at 11:03 PM Tim Peters <tim.peters@gmail.com> wrote:

Sorry! A previous attempt to reply got sent before I typed anything :-(

Very briefly:

...

...

...

...

timeit.timeit("set(i for i in range(1000))", number=100_000)

[and other examples using a range of integers]

The collision resolution strategy for sets evolved to be fancier than for dicts, to reduce cache misses. This is important for sets because the _only_ interesting thing about an element wrt a set is whether or not the set contains it. Lookup speed is everything for sets.

If you use a contiguous range of "reasonable" integers for keys, the integer hash function is perfect: there's never a collision. So any such test misses all the work Raymond did to speed set lookups. String keys have sufficiently "random" hashes to reliably create collisions, though. Cache misses can, of course, have massive effects on timing.

...

Add (much faster for dicts):

...

...

...

timeit.timeit("s = set(); s.add(0)", number=100_000_000) 13.330938750001224 timeit.timeit("d = {}; d[0] = None", number=100_000_000) 5.788865385999088

In the former case you're primarily measuring the time to look up the "add" method of sets (that's more expensive than adding 0 to the set). A better comparison would, e.g., move `add = s.add` to a setup line, and use plain "add(0)" in the loop.

That's it!

...

Also, I believe that max "reasonable" integer range of no collision is (-2305843009213693951, 2305843009213693951), ...

Any range that does _not_ contain both -2 and -1 (-1 is an annoying special case, with hash(-1) == hash(-2) == -2), and spans no more than sys.hash_info.modulus integers. Apart from that, the sign and magnitude of the start of the range don't matter; e.g.,

...

...

...

len(set(hash(i) for i in range(10**5000, 10**5000 + 1000000))) 1000000 len(set(hash(i) for i in range(-10**5000, -10**5000 + 1000000))) 1000000

Sorry again! That only shows that the hash codes are unique. Dicts and sets use only the last N bits to determine the start of the probe sequence, for some value of N >= 3 (depending on the table size). So for a table of size a million, the last 20 bits (1000000 ~= 2**20) are interesting. But same thing:

...

...

MASK = (1 << 20) - 1 len(set(hash(i) & MASK for i in range(-10**5000, -10**5000 + 1000000))) 1000000 len(set(hash(i) & MASK for i in range(-10**5000, -10**5000 + 1000000))) 1000000

26.12.19 00:56, Tim Peters пише:

- I don't have a theory for why dict build time is _so_ much higher than dict lookup time for the nasty keys.

1/2 of items were copied to a new hashtable when the dict grew up. 1/4 of items were copied twice. 1/8 of items were copied three times, etc. In average every item is copied 1 time, so the build time is twice the lookup time when the cost of lookup is dominated. But the lookup benchmarking includes the overhead of iterating Python loop, which is more significant for "good" keys, thus the lookup time is larger than the build time.

Even though I was the first person in this thread to suggest collections.OrderedSet, I'm "meh" about it now. As I read more and played with the sortedcollections package, it seemed to me that while I might want a set that iterated in a determinate and meaningful order moderately often, insertion order would make up a small share of those use cases. On Mon, Dec 23, 2019, 8:05 PM Kyle Stanley <aeros167@gmail.com> wrote:

Larry Hastings wrote:

...

a hypothetical collections.OrderedSet would probably work just fine.

I'm also in agreement with adding a collections.OrderedSet. There certainly seems to be a practical use case for a Set that preserves insertion order, but with significant push back to modifying the existing Set implementation (primarily due to performance concerns).

If later down the road an improvement to OrderedSet is made that gives it equal or better average performance across the board compared to Set, we can consider changing the default implementation *if* there's significant demand for it.

Larry Hastings wrote:

...

And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

This is an excellent point. My first thought if someone were to be using a Dict with all values set to None would be: why not use a Set here? As Larry said, the need for preservation of insertion order would have to be explicitly described in the code comments. Realistically speaking, code comments are not something that can be consistently relied upon, especially if it's part of some boilerplate format that gets replicated or if the container is used in multiple locations. I'd much rather have a dedicated data structure that clearly describes what it does based on the name alone, IMO that's a million times better for readability purposes.

Also, this is mostly speculation since I haven't ran any benchmarks for an OrderedSet implementation, but I strongly suspect that OrderedSet will end up having better average performance for add, pop, and update than trying to use a dictionary with None values (assuming it's implemented in C or at least with a C accelerator).

Not to mention allowing the ability to update (for both addition and removal) based on intersections and unions across ordered sets, which currently isn't possible to do with dictionaries (at least not directly with |=, &=, -=. and ^=). I'm not sure how much of a practical use case this would have for ordered sets specifically, but it's a nice bonus.

On Sat, Dec 21, 2019 at 7:59 AM Larry Hastings <larry@hastings.org> wrote:

...

(mixing together messages in the thread, sorry threaded-view readers)

On 12/19/19 3:15 PM, Tim Peters wrote:

[Nick]

I took Larry's request a slightly different way:

[...]

Only Larry can answer whether that would meet his perceived need. My _guess_ is that he wouldn't know OrderedSet existed, and, even if he did, he'd use a dict with None values anyway (because it's less hassle and does everything he wanted).

At last, something I can speak knowledgeably about: Larry's use case! Regarding Larry, I'd say

1. his use case was small enough that almost anything maintaining order would have worked, even a list, 2. he often *does have* a pretty good idea what goodies are salted away in the Python standard library, and 3. a hypothetical collections.OrderedSet would probably work just fine. And he'd probably use it too, as that makes the code clearer / easier to read. If you read code using an OrderedSet, you know what the intent was and what the semantics are. If you see code using a dict but setting the values to None, you think "that's crazy" and now you have a puzzle to solve. Let's hope those comments are accurate!

Also, speaking personally, at least once (maybe twice?) in this thread folks have asked "would YOU, Mr Larry, really want ordered sets if it meant sets were slightly slower?"

The first thing I'd say is, I'm not sure why people should care about what's best for me. That's sweet of you! But you really shouldn't.

The second thing is, my needs are modest, so the speed hit we're talking about would likely be statistically insignificant, for me.

And the third thing is, I don't really put the set() API through much of a workout anyway. I build sets, I add and remove items, I iterate over them, I do the occasional union, and only very rarely do I use anything else. Even then, when I write code where I reach for a fancy operation like intersection or symmetric_difference--what tends to happen is, I have a rethink and a refactor, and after I simplify my code I don't need the fancy operations anymore. I can't remember the last time I used one of these fancy operations where the code really stuck around for a long time.

So, personally? Sure, I'd take that tradeoff. As already established, I like that dict objects maintain their order, and I think it'd be swell if sets maintained their order too. I suspect the performance hit wouldn't affect *me* in any meaningful way, and I could benefit from the order-maintaining semantics. I bet it'd have other benefits too, like making regression tests more stable. And my (admittedly uninformed!) assumption is, the loss of performance would mostly be in these sophisticated operations that I never seem to use anyway.

But I don't mistake my needs for the needs of the Python community at large. I'd be mighty interested to read other folks coming forward and saying, for example, "please don't make set objects any slower!" and talking us through neat real-world use cases. Bonus points if you include mind-boggling numbers and benchmarks!

On 12/20/19 5:09 AM, Peter Wang wrote:

As Larry pointed out earlier, ordered dicts posed a problem for MicroPython.

Just a minor correction: that wasn't me, that was Petr Viktorin.

Ten days left until we retire 2.7,

*/arry* _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/JYSJ55CW... Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/2KEAXZBQ... Code of Conduct: http://python.org/psf/codeofconduct/

On Tue, 24 Dec 2019 12:08:33 +0900 "Stephen J. Turnbull" <turnbull.stephen.fw@u.tsukuba.ac.jp> wrote:

David Mertz writes:

...

Even though I was the first person in this thread to suggest collections.OrderedSet, I'm "meh" about it now. As I read more and played with the sortedcollections package, it seemed to me that while I might want a set that iterated in a determinate and meaningful order moderately often, insertion order would make up a small share of those use cases.

On the other hand, insertion order is one of the most prominent of the determinate meaningful orders where you would have to do ugly things to use "sorted" to get that order. Any application where you have an unreliable message bus feeding a queue (so that you might get duplicate objects but it's bad to process the same object twice) would be a potential application of insertion-ordered sets.

In that case you probably want a separate persistent "seen" set. Because your queue can have been drained by the time a duplicate object arrives. (which means you probably want something more efficient, such as a sequence number) Regards Antoine.

On Dec 27, 2019, at 19:48, Tim Peters <tim.peters@gmail.com> wrote:

So, ya, I've seen and implemented lots of work queues along these lines - but an OrderedSet would be an "attractive nuisance" (offhandedly appearing to solve a problem it doesn't actually address):

jobs = some_kind_of_queue() finished_jobs = set() ... while jobs: job = jobs.get() if job in finished_jobs: continue try: work on the job possibly adding (sub)jobs to the `jobs` queue except TransientExceptions: jobs.put(job) # try again later else: finished_jobs.add(job)

Well, if an OrderedSet were designed to gracefully handle resizes during iteration, something like this may make sense: jobs = OrderedSet(initial_jobs) for job in jobs: new_jobs = process(job) jobs |= new_jobs ... # jobs is now a set of every job processed A dictionary with None values comes close if you replace the union line with a jobs.update(new_jobs) call (and ignore resizing issues), but it breaks because repeated jobs are shuffled to the end of the sequence and would be processed again. Brandt

[Larry]

Here is the original description of my problem, from the original email in this thread. I considered this an adequate explanation of my problem at the time.

...

I do have a use case for this. In one project I maintain a "ready" list of jobs; I need to iterate over it, but I also want fast lookup because I soemtimes remove jobs when they're subsequently marked "not ready".

Which is a description not of "the problem", but of the operations you want to perform. It's the first time in my life I've heard of a "ready list of jobs" where the programmer sometimes decides later "oh, no - this one and that one aren't ready after all" ;-) Not that it matters much - you want the operations you want. The lack of "oh - of course - that's a problem we all face at times" motivation, though, works against it being _compelling_ on its own.

... In subsequent emails I've clarified that my workloads are small enough--and computers are fast enough--that almost any data structure would work fine for me here, e.g. a list.

I don't think my needs should drive the decision making process regardless. I only described my problem to get the conversation rolling.

Which it did :-) Others went on to, explicitly or implicitly, suggest that an ordered set must also, e.g., support the entire MutableSequence interface, and even define what happens if you mutate the ordered set _while_ iterating over it (lists define the results in such cases, but ordered dicts raise an exception).

I opine that anybody who iterates over set objects and has bugs in their code would appreciate set objects maintaining insertion order. I suspect it would make their debugging easier, because given identical inputs their set iteration would behave identically, thus making their bugs that much more stable. That's as much use case as I have for the feature.

That's much stronger to me than some weird FIFO-only queue supporting fast deletion of interior elements (which - sorry - I've never had a use for). And fine by me if such a thing is added. All else being equal, I'd prefer that the builtin set type be ordered, simply because it's less surprising. and dicts are ordered now (although, as Inada Naoki said, their current implementation isn't suitable for a FIFO queue, doe primarily to O(N) time needed to find "the first" key+value record). I believe we agree that adding _some_ flavor of OrderedSet to `collections` would be a fine start. I'm just not cool with replacing the builtin set before there's an implementation fast and memory-efficient enough that _current_ heavy set users won't feel betrayed by major slowdowns or memory bloat when the switch is made. Toward that end, my opinion - which I won't defend - is that OrderedSet should not promise better than O(N)-time indexing (if it supports indexing at all), and should - like current sets and dicts - try to raise an exception if it can detect that the container has been mutated during iteration.

[Larry]

It's a lightweight abstract dependency graph. Its nodes are opaque, only required to be hashable. And it doesn't require that you give it all the nodes in strict dependency order.

When you add a node, you can also optionally specify dependencies, and those dependencies aren't required to be nodes that the graph has previously seen. So you can add a node A that depends on B and C, without showing it B or C first. When that happens it creates placeholder nodes for B and C, and naturally these nodes have no dependencies. You can then later inform the graph that node B has dependencies on X Y and Z.

(My specific use case is a package manager. Packages are identified with unique strings. So the nodes I give the give the graph are simply those package names. It's pretty common for me to get a package with dependencies on packages I haven't seen yet. Designing the graph to create placeholders let me skip making two passes over the package list, pre-creating the package objects, etc etc. This made the code simpler and presumably faster.)

The graph API maintains an externally-visible "ready" iterable of nodes. And since B can go from ready to not-ready, it can get added to "ready" and subsequently removed.

Also, when a node is satisfied, you simply remove it from the graph. If A depends on B and C, and they all represent jobs, and B and C have no dependencies, they'll be in the "ready" iterable. You iterate over "ready", and execute those jobs, and assuming they are successful you then remove them from the graph. When A's dependencies are all satisfied, it'll get added to the "ready" iterable. And naturally when B and C were removed from the graph, they were removed from the "ready" iterable too.

OK! You're doing a topological sort. There are natural & simple ways to do that right now that scale efficiently to very large graphs (time & space linear in the sum of the number of nodes and the number of dependencies). Curiously, the difficulties are mostly driven by the quality of _error_ messages you want (in case of, e.g., cycles in the dependency graph). Lots of those implementations became deterministic "by magic" when ordered dicts were introduced. This is why: a bare bones implementation needs to associate two pieces of info with each node: a list of its immediate successors, and an integer count of the number of its immediate predecessors. A dict is the natural way to implement that association. When all the dependency info has been entered, then: - First all nodes are emitted whose predecessor count is 0. Iterating over the association dict once is the natural way to find them, and that order is defined now. - Then, as each emitted node N is marked done: for child in N.successors: assert child.predcount > 0 child.predcount -= 1 if child.predcount == 0: emit(child) That's about all there is to it. But there's no end to the cruft that _can_ be added to, e.g., verify that a node is marked done no more than once, or to compute & display strongly connected components if not all nodes are emitted, etc. Ordered sets could improve this "natural" implementation if the successor lists were successor sets instead, simply because then - like lists - their iteration order would be defined, which can in turn affect the order in which nodes are emitted in the loop just above. But lists are adequate to the task, are cheaper in both time and space, and can't _not_ be ordered ;-)

Thus it's this "ready" collection that I want to a) be iterable, b) be stable, and c) support fast removal. I add and remove nodes from that set a lot, which I realized would perturb the iteration order from run to run, etc etc etc, and here we are.

The sketch above (which is a bog-common way to implement topsorts) doesn't build a data structure recording the final order, and, in fact, never deletes anything. You might protest that the initial iteration step (scanning the association dict to find nodes with no predecessors) is an expense you skip because nodes with predecessors are deleted from your "ready" structure all along. But nodes with predecessors are _touched_ either way, and merely skipping over them is bound to be cheaper than deleting them. After that initial step, no search of any kind is needed again.

I grant you maybe it's a weird approach. But after two false starts, where I was starting to boil the oceans with ABCs and "node is satisfied" APis and separate iterator objects, I had a re-think and hit on this super lightweight design. I'm actually quite pleased with it--it's short, it has a minimal API, it's readable, it was easy to get right, and it solves my problem.

Whereas I would have started with a topsort and finished it while I was sleeping ;-) Seriously, I've written such a thing many times, but never reuse the code because it's so easy to redo from scratch. Every application has _some_ unique twist, which makes a general-purpose API so bloated it's harder to figure out how to use than to write custom code. In your application, I'm guessing (but don't know) that when a package name is emitted, it's possible you're not able to find the package, and so the process has to stop. That's why I inserted a "as each emitted node N is marked done" step to my description. That is, I'm picturing an API that adds a (say) topsorter.record_succeeded(node) method to say that - yes - the node was processed successfully. Else, by default, its successors (if any) must not be emitted. But if that isn't needed, the whole topsort order can be materialized into (say) a list in one gulp, or delivered by a generator.

Happy new year,

And to you too! :-)

A set was requested with preserved insertion order. Mathematically, such a structure relates more to an Oset (having order) than a Set. See relationships in the image below: [image: libo.png] Each of the mentioned structure types has a dedicated role. Python's sets work well and correlate with existing math principles. I would be more convinced to introduce a new collection to Python rather than alter existing sets. -1: preserving insertion-order in sets 0: adding `OrderedSet` (where `dict.fromkeys()` does not suffice, i.e. needing set operations) +1: implementing an analogous abstract collection, e.g. "`HashList`" -> Oset, just as `Counter` -> Mset On Sun, Dec 29, 2019 at 9:00 PM Wes Turner <wes.turner@gmail.com> wrote:

Due to version and platform constraints, a SAT solver is necessary for conda and (now) pip. Libsolv is one of the fastest around.

https://github.com/QuantStack/mamba is conda implemented with libsolv (and parallel downloading of *declarative* dependency metadata).

For general purpose graphs with implicit node instantation from edge declaration, NetworkX has implementations of many graph algorithms.

https://networkx.github.io/documentation/stable/reference/algorithms/generat...

CuGraph (a product of the RAPIDS.ai project) does graphs with CUDA (from Python) with a "NetworkX-like API" but doesn't yet have a topological sort (though it does have BFS) https://github.com/rapidsai/cugraph

"pip needs a dependency resolver" + End (Fn+Right) links to the latest work on the new pip code (that must require declarative dependency metadata) https://github.com/pypa/pip/issues/988

That said, this implementation of topo sort could have a deterministic output given an OrderedSet: https://rosettacode.org/wiki/Topological_sort#Python

A table including Big-O and memory usage for the necessary data structure and methods would be useful.

On Sun, Dec 29, 2019, 5:12 PM Tim Peters <tim.peters@gmail.com> wrote:

...

[Larry]

...

It's a lightweight abstract dependency graph. Its nodes are opaque, only required to be hashable. And it doesn't require that you give it all the nodes in strict dependency order.

When you add a node, you can also optionally specify dependencies, and those dependencies aren't required to be nodes that the graph has previously seen. So you can add a node A that depends on B and C, without showing it B or C first. When that happens it creates placeholder nodes for B and C, and naturally these nodes have no dependencies. You can then later inform the graph that node B has dependencies on X Y and Z.

(My specific use case is a package manager. Packages are identified with unique strings. So the nodes I give the give the graph are simply those package names. It's pretty common for me to get a package with dependencies on packages I haven't seen yet. Designing the graph to create placeholders let me skip making two passes over the package list, pre-creating the package objects, etc etc. This made the code simpler and presumably faster.)

The graph API maintains an externally-visible "ready" iterable of nodes. And since B can go from ready to not-ready, it can get added to "ready" and subsequently removed.

Also, when a node is satisfied, you simply remove it from the graph. If A depends on B and C, and they all represent jobs, and B and C have no dependencies, they'll be in the "ready" iterable. You iterate over "ready", and execute those jobs, and assuming they are successful you then remove them from the graph. When A's dependencies are all satisfied, it'll get added to the "ready" iterable. And naturally when B and C were removed from the graph, they were removed from the "ready" iterable too.

OK! You're doing a topological sort. There are natural & simple ways to do that right now that scale efficiently to very large graphs (time & space linear in the sum of the number of nodes and the number of dependencies). Curiously, the difficulties are mostly driven by the quality of _error_ messages you want (in case of, e.g., cycles in the dependency graph).

Lots of those implementations became deterministic "by magic" when ordered dicts were introduced. This is why: a bare bones implementation needs to associate two pieces of info with each node: a list of its immediate successors, and an integer count of the number of its immediate predecessors. A dict is the natural way to implement that association.

When all the dependency info has been entered, then:

- First all nodes are emitted whose predecessor count is 0. Iterating over the association dict once is the natural way to find them, and that order is defined now.

- Then, as each emitted node N is marked done: for child in N.successors: assert child.predcount > 0 child.predcount -= 1 if child.predcount == 0: emit(child)

That's about all there is to it. But there's no end to the cruft that _can_ be added to, e.g., verify that a node is marked done no more than once, or to compute & display strongly connected components if not all nodes are emitted, etc.

Ordered sets could improve this "natural" implementation if the successor lists were successor sets instead, simply because then - like lists - their iteration order would be defined, which can in turn affect the order in which nodes are emitted in the loop just above. But lists are adequate to the task, are cheaper in both time and space, and can't _not_ be ordered ;-)

...

Thus it's this "ready" collection that I want to a) be iterable, b) be stable, and c) support fast removal. I add and remove nodes from that set a lot, which I realized would perturb the iteration order from run to run, etc etc etc, and here we are.

The sketch above (which is a bog-common way to implement topsorts) doesn't build a data structure recording the final order, and, in fact, never deletes anything. You might protest that the initial iteration step (scanning the association dict to find nodes with no predecessors) is an expense you skip because nodes with predecessors are deleted from your "ready" structure all along. But nodes with predecessors are _touched_ either way, and merely skipping over them is bound to be cheaper than deleting them.

After that initial step, no search of any kind is needed again.

...

I grant you maybe it's a weird approach. But after two false starts, where I was starting to boil the oceans with ABCs and "node is satisfied" APis and separate iterator objects, I had a re-think and hit on this super lightweight design. I'm actually quite pleased with it--it's short, it has a minimal API, it's readable, it was easy to get right, and it solves my problem.

Whereas I would have started with a topsort and finished it while I was sleeping ;-) Seriously, I've written such a thing many times, but never reuse the code because it's so easy to redo from scratch. Every application has _some_ unique twist, which makes a general-purpose API so bloated it's harder to figure out how to use than to write custom code.

In your application, I'm guessing (but don't know) that when a package name is emitted, it's possible you're not able to find the package, and so the process has to stop. That's why I inserted a "as each emitted node N is marked done" step to my description. That is, I'm picturing an API that adds a (say)

topsorter.record_succeeded(node)

method to say that - yes - the node was processed successfully. Else, by default, its successors (if any) must not be emitted.

But if that isn't needed, the whole topsort order can be materialized into (say) a list in one gulp, or delivered by a generator.

...

Happy new year,

And to you too! :-) _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/HRKQPTPQ... Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/6UKXR63M... Code of Conduct: http://python.org/psf/codeofconduct/

[Nick]

I took Larry's request a slightly different way:

Sorry, I was unclear: by "use case" I had in mind what appeared to me to be the overwhelming thrust of the _entirety_ of this thread so far, not Larry's original request.

he has a use case where he wants order preservation (so built in sets aren't good), but combined with low cost duplicate identification and elimination and removal of arbitrary elements (so lists and collections.deque aren't good).

Sure.

Organising a work queue that way seems common enough to me to be worthy of a stdlib solution that doesn't force you to either separate a "job id" from the "job" object in an ordered dict, or else use an ordered dict with "None" values.

So while it means answering "No" to the "Should builtin sets preserve order?" question (at least for now), adding collections.OrderedSet *would* address that "duplicate free pending task queue" use case.

Only Larry can answer whether that would meet his perceived need. My _guess_ is that he wouldn't know OrderedSet existed, and, even if he did, he'd use a dict with None values anyway (because it's less hassle and does everything he wanted). But I have to add that I don't know enough about his original use case to be sure it wasn't "an XY problem": https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem """ The XY problem is asking about your attempted solution rather than your actual problem. That is, you are trying to solve problem X, and you think solution Y would work, but instead of asking about X when you run into trouble, you ask about Y. """ Because I've never had a "job queue" problem where an OrderedSet would have helped. Can't guess what's different about Larry's problem.

The only `OrderedSet` use I have seen in the wild is https://github.com/python-hyper/uritemplate/search?q=orderedset&unscoped_q=orderedset .

A more generalized Python code search across GitHub of "orderedset" returns ~500k results: https://github.com/search?l=Python&q=orderedset&type=Code . Of course, a general code search across GitHub is by no means a clear or reliable measure of actual usage, considering the number of duplicate results. But, it's still useful for rough estimations. On Thu, Jan 2, 2020 at 7:08 PM Brett Cannon <brett@python.org> wrote:

The only `OrderedSet` use I have seen in the wild is https://github.com/python-hyper/uritemplate/search?q=orderedset&unscoped_q=orderedset . _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@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/GYIOTCKM... Code of Conduct: http://python.org/psf/codeofconduct/

On Sun, Dec 15, 2019 at 11:28 PM Raymond Hettinger < raymond.hettinger@gmail.com> wrote:

* The corresponding mathematical concept is unordered and it would be weird to impose such as order.

I'm with Raymond in not wanting sets to maintain insertion (or any) order. Even though I don't doubt that Larry--and no doubt other folks, from time to time--have a use for an "ordered set," I feel like it is bad practice to encourage that way of thinking about sets and using them. Admittedly, I was only lukewarm about making an insertion-order guarantee for dictionaries too. But for sets I feel more strongly opposed. Although it seems unlikely now, if some improved implementation of sets had the accidental side effects of making them ordered, I would still not want that to become a semantic guarantee. That said, having OrderedSet in collections module would be fine by me. It might have different performance characteristics, but so what? It would be a different class that folks could use or not, depending on how they felt about its behavior and performance profile. -- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.

On Mon 12/16/19, 9:59 AM, "David Mertz" <mertz@gnosis.cx<mailto:mertz@gnosis.cx>> wrote: Admittedly, I was only lukewarm about making an insertion-order guarantee for dictionaries too. But for sets I feel more strongly opposed. Although it seems unlikely now, if some improved implementation of sets had the accidental side effects of making them ordered, I would still not want that to become a semantic guarantee. Eek… No accidental side effects whenever possible, please. People come to rely upon them (like that chemistry paper example[*]), and changing the assumptions results in a lot of breakage down the line. Changing the length of AWS identifiers (e.g. instances from i-1234abcd to i-0123456789abcdef) was a huge deal; even though the identifier length was never guaranteed, plenty of folks had created database schemata with VARCHAR(10) for instance ids, for example. Break assumptions from day 1. If some platforms happen to return sorted results, sort the other platforms or toss in a sorted(key=lambda el: random.randomint()) call on the sorting platform. If you’re creating custom identifiers, allocate twice as many bits as you think you’ll need to store it. Yes, this is bad user code, but I’m all for breaking bad user code in obvious ways sooner rather than subtle ways later, especially in a language like Python. [*] https://arstechnica.com/information-technology/2019/10/chemists-discover-cro...

[Raymond]

... * The ordering we have for dicts uses a hash table that indexes into a sequence. That works reasonably well for typical dict operations but is unsuitable for set operations where some common use cases make interspersed additions and deletions (that is why the LRU cache still uses a cheaply updated doubly-l linked list rather that deleting and reinserting dict entries).

I'm going to take a stab at fleshing that out a bit: ideally, an ordered dict stores hash+key+value records in a contiguous array with no "holes". That's ("no holes") where the memory savings comes from. The "holes" are in the hash table, which only hold indices _into_ the contiguous array (and the smallest width of C integer indices sufficient to get to every slot in the array). "The problem" is that deletions leave _two_ kinds of holes: one in the hash table, and another in the contiguous vector. The latter holes cannot be filled with subsequent new hash+key+value records because that would break insertion order. So in an app that mixes additions and deletions, the ordered dict needs to be massively rearranged at times to squash out the holes left behind by deletions, effectively moving all the holes to "the end", where they can again be used to reflect insertion order. Unordered dicts never had to be rearranged unless the total size changed "a lot", and that remains true of the set implementation. But in apps mixing adds and deletes, ordered dicts can need massive internal rearrangement at times even if the total size never changes by more than 1. Algorithms doing a lot of mixing of adds and deletes seem a lot more common for sets than for dicts, and so the ordered dict's basic implementation _approach_ is a lot less suitable for sets. Or, at least, that's my best attempt to flesh out Raymond's telegraphic thinking there. Note: the holes left by deletions _wouldn't_ be "a problem" _except_ for maintaining insertion order. If we were only after the memory savings, then on deletion "the last" record in the contiguous array could be moved into the hole at once, leaving the array hole-free again. But that also changes the order. IIRC, that's what the original "compact dict" _did_ do.