SortedContainers 2.0 broke compatibility with no warning

[ghost]

Hello,
You may not view this as a bug, but it was a big surprise for me! SortedDict() .keys() used to return sets that could do .intersect() operations. It must now be converted from SortedKeysView (or something?) to a set() and this uses tons of memory and time. The iloc method was also removed. I only got that far before I realized the build I was troubleshooting had a newer version than dev and was broken because of it. Please put a "breaking changes" section into the documentation when making these sorts of things! Or better yet, don't go fixing what isn't broken and also remove functionality :-D

[observerss]

same problem, big surprise
maybe should at least doc the change and reasoning and an upgrade guide?

Update: found doc in HISTORY.rst

[mrocklin]

Same problem. I and many users that I support depend on sortedcontainers. I'm happy to see things modernize but would appreciate a deprecation cycle so that downstream projects can respond sensibly. All of my users that are now installing things are getting failures without warning.

I would strongly appreciate the rapid removal of the offending package from PyPI and the upload of a new one that raised deprecation warnings.

[grantjenks]

Hello, all. Just woke up. Will look at this immediately. Sorry for the surprise breaks.

I have a busy day/week so the easiest current solution that I can see is to remove the V2 uploads from PyPI. Is there any way to leave them there and make v1.5.10 preferred?

[mrocklin]

Is there any way to leave them there and make v1.5.10 preferred?

I've seen people host pre-releases on PyPI so there must be a way to have newer-but-not-default packages around.

[grantjenks]

Is it just iloc that you need? I can push a quick fix for that.

sorted_dict.iloc = sorted_dict.keys()

[grantjenks]

@LipillaiDave Can you be more specific? The SortedKeysView inherits collections.KeysView which does implement a set-like interface.

Also breaking changes are documented in the release history at http://www.grantjenks.com/docs/sortedcontainers/history.html

Also upgrade guide at http://www.grantjenks.com/docs/sortedcontainers/introduction.html#migrating

[mrocklin]

Yes, iloc is specifically what has broken dask.distributed. However I'm more than happy to evolve towards a newer API that sortedcontainers devs think is cleaner long term. I just need some time to smooth over the transition.

In my ideal world iloc would continue to work for another version or two, but raise a warning the first time it was used (not every time, which would flood users' logs) warning people of the coming change and pointing them towards correct behavior. Probably some user would note this in downstream projects' issue trackers, which would then compel those projects to adapt to the change.

Of course, if you think that iloc is something that is useful to keep then I wouldn't mind that either.

[grantjenks]

I get what you're saying. It sounds nice. But it will take me a fair amount of time to learn how to do that. I can probably get there by the end of next week. For today, let's figure out the best way forward.

1. I think iloc should go away. The functionality is now in SortedKeysView which you can get with sorted_dict.keys(). There are V2 uploads on PyPI that I know folks have started using.
2. I can put iloc back in as a temporary measure to un-break things. But beware that other methods like .items() and .values() also changed (all return dict views now).
3. I can alternatively remove the V2 uploads from PyPI. I can't see a setting that marks them pre-release. Can you point to docs on that? This will make another group of users unhappy as they've moved to V2. Hopefully not many. I released V2 on Friday, May 18.
4. Is there a way to change the sortedcontainers version to "<2" temporarily in your code?

I numbered things above just for reference. Don't think of them sequentially.

[mrocklin]

1. I use iloc frequently within inner loops. Is there a performance hit here?

2. I'm not particularly concerned about changes that reflect python 2/3 changes. In my experience most packages are already robust to this. If there are differences beyond what is typical in dicts when moving from Python 2/3 then I'm not sure how best to handle this.

3. This might help? https://stackoverflow.com/questions/35131861/what-does-the-pre-option-in-pip-signify?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

   I'm unfortunately just as inexperienced here

4. Right, so my atlernative solution if you keep the package up is to upload a new package on my end that pins away from sortedcontainers as you suggest. I'm assuming that other projects also depend on sortedcontainers though and so it makes more sense to handle this upstream rather than in all of the downstream packages. This might not be the case though. Sortedcontainers seems like it was built to be an infrastructural library, so I've been treating it like one in the past.

[ghost]

Hi Grant,

Sorry if I seemed crabby. I'm extremely grateful for SortedCollections. It was just past 1AM and I was woke up from sleep troubleshooting remote customers.

I'm not opposed to it changing moving forward, although I'd like to present a case for keeping iloc. Is there any real reason to remove it? SortedContainers is a feature- and performance-plus package. It makes sense to emulate Python3 style, sure, but why remove what is working well and fast for those who use it for the right reasons?

In regards to your question about intersections, this line of code was getting the following error:

  File "thingy.py", line 558, in resample_query_sample_time_set
    times = ts.sampled_series_json.keys().intersection(set(xrange(time_start,time_end,60)))
AttributeError: 'SortedKeysView' object has no attribute 'intersection'

[grantjenks]

@LipillaiDave Thank you for the kind words. That was an unintended regression. Sorry! I will look into it today.

@mrocklin -- I can add .iloc back with no performance regression. I will try to do so this morning.

I am teaching class all day so I may be less responsive then I would like. I will update at 1pm today (lunch) and see what I can get done this morning.

I appreciate you all as users and your feedback!

[mrocklin]

Thanks for your responsiveness during a pressured time. If you're able to take down the errant packages that would probably reduce time pressure significantly. People are downloading these now and getting faulty installs.

…

On Mon, May 21, 2018 at 11:31 AM, Grant Jenks ***@***.***> wrote: @LipillaiDave <https://github.com/LipillaiDave> Thank you for the kind words. That was an unintended regression. Sorry! I will look into it today. @mrocklin <https://github.com/mrocklin> -- I can add .iloc back with no performance regression. I will try to do so this morning. I am teaching class all day so I may be less responsive then I would like. I will update at 1pm today (lunch) and see what I can get done this morning. I appreciate you all as users and your feedback! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#92 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AASszM_Q1geZ2C0c6SX5-j6OZ0FIbV03ks5t0t3ZgaJpZM4UGeC7> .

[grantjenks]

I added back the sorted_dict.iloc attribute. Committed at 0ac84ed and deployed at v2.0.2. @mrocklin Does that fix your problem?

@LipillaiDave The KeysView does implement the set operations but as operators rather than as methods. Can you change your ".intersect" code to use "val1 & val2"?

[grantjenks]

@LipillaiDave Looks like you're using Python 2 and executing https://github.com/grantjenks/python-sortedcontainers/blob/v1/sortedcontainers/sorteddict.py#L224 from v1. In v1 on Python 2, the sorted_dict.keys() methods returns a SortedSet which implements the intersect method. Given the source like:

times = ts.sampled_series_json.keys().intersection(set(xrange(time_start,time_end,60)))

I think you can rewrite it as:

times = ts.sampled_series_json.keys() & xrange(time_start, time_end, 60)

Now, the times variable will be a set object rather than SortedSet. Do you need a set or SortedSet? That can be easily changed. You can work around the bug by wrapping the result like:

times = SortedSet(ts.sampled_series_json.keys() & xrange(time_start, time_end, 60))

Now I'm just guessing but I think you might've implemented something like:

times = SortedSet(ts.sampled_series_json.keys()).intersection(xrange(time_start, time_end, 60))

That is indeed slow as iterating the SortedKeysView is currently an O(n*log(n)) operation. That should be made faster (sorry!) by defining an optimized iteration method instead of using Sequence.__iter__.

So I think the necessary changes are:

1. Set operations for SortedKeysView and SortedItemsView should return a SortedSet.
2. Iterating a SortedKeysView, SortedValuesView, or SortedItemsView should be as fast as possible.

Would that fix your issues?

[grantjenks]

I think (2, above) is already done. Iterating a KeysView iterates the mapping directly which iterates the sorted list which should be extremely fast.

For reference: https://github.com/python/cpython/blob/3.6/Lib/_collections_abc.py#L719

Could you say more about, "and this uses tons of memory and time," in your original report?

[mrocklin]

I added back the sorted_dict.iloc attribute. Committed at 0ac84ed and deployed at v2.0.2. @mrocklin Does that fix your problem?

Dask's test suite does pass again, yes.

[mrocklin]

Should we plan to deprecate iloc in the future?

[grantjenks]

@mrocklin Yes, consider SortedDict.iloc deprecated. I'm working on changes to emit the warning.

[grantjenks]

Deprecation warning emitted at 2a00449.

SortedKeysView and SortedItemsView set-operations returned sorted sets at 28e99c0.

I plan to release the changes in v2.0.3 this week.

[grantjenks]

Fixes deployed in v2.0.3 on PyPI.