[issue16991] Add OrderedDict written in C

Yury Selivanov added the comment: Eric, is there any chance this can land in 3.5? OrderedDict is a heavily used thing, everyone will benefit from a fast implementation. It's OK if we have an imperfect (but fully compatible with existing OrderedDict) implementation in 3.5. We can optimize it

[issue16991] Add OrderedDict written in C

Changes by Eric V. Smith : -- nosy: +eric.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.py

[issue16991] Add OrderedDict written in C

Changes by shiyao.ma : -- nosy: +introom ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.or

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Thanks for speaking up, Antoine. Keep in mind that a C implementation of OrderedDict has a strict compatibility requirement with the existing pure Python one. The Python implementation subclasses dict so the C implementation must as well. I agree that it would b

[issue16991] Add OrderedDict written in C

Antoine Pitrou added the comment: >From a cursory glance, I still think this is the wrong approach. There's a lot >of complication due to the simple fact that it is subclassing from dict (and >therefore trying to be ABI-compatible, kind of). The linked list scheme should >be much simpler (perh

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I expect Antoine is trying to limit the scope of the change, which makes sense. In this case, though, once (if?) the patch lands I plan on using it in the interpreter, so the C-API bits will be necessary. -- ___ Python

[issue16991] Add OrderedDict written in C

Stefan Behnel added the comment: > do not add a C-API what speaks against it? -- nosy: +scoder ___ Python tracker ___ ___ Python-bugs

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: s/argument client/Argument Clinic/ -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscrib

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I've opened a feature clone to better track the work (features/cordereddict). Here's the updated patch against default from that clone. I haven't added any argument client stuff. I also haven't addressed any of the feedback from Antoine. I'd rather leave Ordere

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Suggestions from Antoine on python-dev: * do not make cOrderedDict "builtin"; drop changes to: - Include/Python.h - Objects/object.c - Makefile.pre.in * do not add a C-API * include the linked list pointers in the hash entries? (may simplify things) * drop the

[issue16991] Add OrderedDict written in C

Wes Turner added the comment: * Macros could be useful. * Would this make it easy/faster to also have a DefaultOrderedDict (which can/could also be accomplished with .get(attr, []) and .setdefault(attr, [])? * There may be some value in looking at https://pypi.python.org/pypi/cyordereddict * (I

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I'm open to suggestions on how to help make the patch more reviewable. Currently at roughly +2500 lines of code it's a lot to ask someone to review. While probably not the only way to help reviewers, I expect the best thing I could do is to split the patch up int

[issue16991] Add OrderedDict written in C

Changes by Arfrever Frehtes Taifersar Arahesis : -- nosy: +Arfrever ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscri

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I haven't had time for a while to do much work on this. At the last posting this patch was basically done. I'm sure it no longer applies cleanly. The biggest obstacle to wrapping this issue up is the size of the patch. It's hard to get a thorough review because

[issue16991] Add OrderedDict written in C

Артём Скорецкий added the comment: Any progress? It was planned for 3.5 release -- nosy: +tonn81 ___ Python tracker ___ ___ Python-bug

[issue16991] Add OrderedDict written in C

Changes by Stefan Krah : -- nosy: -skrah ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.o

[issue16991] Add OrderedDict written in C

Changes by Josh Rosenberg : -- nosy: +josh.rosenberg ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://ma

[issue16991] Add OrderedDict written in C

Changes by Gregory P. Smith : -- nosy: +gregory.p.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https:/

[issue16991] Add OrderedDict written in C

Changes by Stefan Krah : -- nosy: +skrah ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.or

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: After pulling up to tip and sticking in the basic **kwargs change, the results on the benchmark suite imply a refleak somewhere. As soon as I sort that out I'll push up the updated patch. -- ___ Python tracker

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I agree with Antoine. It's first on my todo list for 3.5. My goal is that this and a couple of related features will land during the PyCon sprints. -- ___ Python tracker

[issue16991] Add OrderedDict written in C

Antoine Pitrou added the comment: It's much too late for such a disruptive change in 3.4. -- nosy: +pitrou ___ Python tracker ___ ___

[issue16991] Add OrderedDict written in C

Changes by Antoine Pitrou : -- versions: +Python 3.5 -Python 3.4 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue16991] Add OrderedDict written in C

Yury Selivanov added the comment: Can we still merge this in 3.4? -- nosy: +yselivanov ___ Python tracker ___ ___ Python-bugs-list mai

[issue16991] Add OrderedDict written in C

Changes by Ryan Gonzalez : -- nosy: +Ryan.Gonzalez ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail

[issue16991] Add OrderedDict written in C

Serhiy Storchaka added the comment: Rebase patch to tip. -- Added file: http://bugs.python.org/file32262/cOrderedDict-2.diff ___ Python tracker ___ __

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file30468/cOrderedDict.diff ___ Python tracker ___ ___ Python-bugs-list mailing li

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I figured out what I hope were the last memory-related issues. Apparently tp_traverse is not inherited if tp_flags is set. I had it set on all the view types and all the iterator types. So during GC it would blow up when it tried to call tp_traverse. Everything

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Here's what I feel is a nearly complete patch. The only outstanding issues that I feel need to be answered are 4 spots where calls into the interpreter may result in unexpected changes to the object or make the current function state out-of-date. 1. _odict_clear_

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file30462/cOrderedDict.diff ___ Python tracker ___ ___ Python-bugs-list mailing li

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file30467/cOrderedDict-iterators-by-key.diff ___ Python tracker ___ ___ Python-bu

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: The concern about reference cycles here lies in their existence in the linked-list. To see what I mean, check out the use of weakrefs in the pure Python implementation at Lib/collections/__init__.py. As the current implementation does not use PyObjects for the li

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Here's one solution to the deletion-during-iteration problem. It makes the iterators track the key rather than the node, at the expense of a sliver of speed on __iter__() and keys(). -- Added file: http://bugs.python.org/file30467/cOrderedDict-iterators-by

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Here's an updated patch that has fixes for recursive pickles and for a couple memory-related segfaults that I missed before. That leaves the following to be done: * handle the case where a node is deleted during iteration * check for any reference cycles (should b

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file30357/cOrderedDict.diff ___ Python tracker ___ ___ Python-bugs-list mailing li

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Without too many optimzations, the C implementation of OrderedDict is basically between 1x and 4x the performance of raw dict. This contrasts with the pure Python OrderedDict, which falls in roughly between 4x and 100x. I've attached an addition to pybench, not in

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file29078/odict.diff ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file29077/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-lis

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I finally had some time so here's an updated patch (including O(1) deletions). I've also added a bunch of notes at the top of odictobject.c. Some notable things left to do: * address two recently failing tests due to r83881 (issue 17900) * check for any reference

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Raymond, do you have any objections to splitting the OrderedDict-related tests into their own module. Doing so allows for testing all the those test classes at once, which is handy when working on OrderedDict. This is more relevant now with the extra PEP-399-moti

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: > I just looked at the test-collections patch and don't want it > committed. It is full of trivial edits that make it hard to > review and doesn't make the test suite better. Thanks for the feedback, Raymond. I agree that there are a number of trivial edits there

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: It's worth noting that issue10977 is pretty closely related to this isssue. -- ___ Python tracker ___ ___

[issue16991] Add OrderedDict written in C

Raymond Hettinger added the comment: I just looked at the test-collections patch and don't want it committed. It is full of trivial edits that make it hard to review and doesn't make the test suite better. It is okay to add some new tests, but I don't want to rearrange the existing code with

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: My current patch ends up with O(n) deletion, which won't fly, so I'm refactoring. While I'm at it I'm also planning on using the BSD queue.h doubly-linked list rather than the one that I rolled. I'm also going to pull the ordered dict implementation into it's own

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: I should clarify, odict.diff passes test_ordereddict. Regardless, it's pretty close. I'm going to figure out why the review link hates me on this issue, but until then any extra eyes here would be appreciated. The memory-related issues are pushing well past my e

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file29083/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-lis

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Added file: http://bugs.python.org/file29083/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-list

[issue16991] Add OrderedDict written in C

Changes by Éric Araujo : -- nosy: +eric.araujo ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyth

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: > Why did you copy test_collections.py instead of just creating > a new file? To preserve the history of changes to the bulk of the code in test_ordereddict.py. -- ___ Python tracker

[issue16991] Add OrderedDict written in C

Benjamin Peterson added the comment: Why did you copy test_collections.py instead of just creating a new file? -- ___ Python tracker ___ _

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file28956/odict.diff ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file28839/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-lis

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Incidently, I'm just about done with the OrdereDict patch. I'm attaching the current one. At present it passes the unit tests, but I have two memory-related issues and a number of open questions (that I don't think are critical). The patch has the unittest clean

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Are there any objections to this unittest cleanup patch? I'd like to commit it separately prior to anything that will go in for the C OrderedDict. -- Added file: http://bugs.python.org/file29077/cleanup-test-collections.diff ___

[issue16991] Add OrderedDict written in C

Changes by Florent Xicluna : -- nosy: +flox ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file28972/odict.diff ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file28971/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-lis

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Added file: http://bugs.python.org/file28972/odict.diff ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Added file: http://bugs.python.org/file28971/cleanup-test-collections.diff ___ Python tracker ___ ___ Python-bugs-list

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Looks like I didn't get the patch lined up to tip so the review link isn't showing up. I'll have to fix that tomorrow. -- ___ Python tracker ___ __

[issue16991] Add OrderedDict written in C

Changes by Eric Snow : Removed file: http://bugs.python.org/file28762/odict.diff ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Here's an updated patch. I still have some ref-counting issues, but the patch is much closer to what I expect will be the final version. At this point it passes all the main unit tests (segfaults in some of the supplemental Mapping tests). One key thing is that

[issue16991] Add OrderedDict written in C

Ezio Melotti added the comment: These are indeed good reasons. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: > What's the reason for moving the OrderedDict tests in a separate file? Following the precedent of collections.deque and collections.defaultdict: * a big chunk of code * the default implementation will be coming via _collections. -- __

[issue16991] Add OrderedDict written in C

Ezio Melotti added the comment: What's the reason for moving the OrderedDict tests in a separate file? -- ___ Python tracker ___ ___ P

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: Here's a cleanup of test.test_collections that helps keep the subsequent patch (still forthcoming) cleaner. -- Added file: http://bugs.python.org/file28839/cleanup-test-collections.diff ___ Python tracker

[issue16991] Add OrderedDict written in C

Changes by Andrew Svetlov : -- nosy: +asvetlov ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyth

[issue16991] Add OrderedDict written in C

Eric Snow added the comment: @Benjamin: Yeah, I've fixed that. @Ezio: Good point. I've touched that up. Once I have cleared up reference counting issues I'll put up a new patch. -- ___ Python tracker ___

[issue16991] Add OrderedDict written in C

Changes by Alex Gaynor : -- nosy: +alex ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/

[issue16991] Add OrderedDict written in C

Ezio Melotti added the comment: The tests should probably be updated to use the PEP 399 idiom in order to test both the implementations. -- nosy: +ezio.melotti ___ Python tracker __

[issue16991] Add OrderedDict written in C

Changes by Serhiy Storchaka : -- nosy: +serhiy.storchaka ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http:/

[issue16991] Add OrderedDict written in C

Benjamin Peterson added the comment: Nit: This really not be exposed through _collections rather than hacked into builtins. -- nosy: +benjamin.peterson ___ Python tracker ___ __

[issue16991] Add OrderedDict written in C

New submission from Eric Snow: Here's an initial stab at writing OrderedDict in C. Though, the implementation is not heavily optimized and isn't super subclass-friendly, my hope is that it's relatively close to the final version. I'm getting this up now to get some eyes on it. The spot in t

<    1   2