[issue16991] Add OrderedDict written in C
Stefan Krah added the comment: It's fine to open other issues, but I'm not happy with the resize()/get_index() situation. Currently I can't come up even with an informal proof that it'll always work (and see #24361). I think these functions really *need* 100% code coverage. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Addressing the concerns with resize()/get_index() is next on my list. I had meant to open up an issue on it last night but it was getting pretty late for me and it slipped my mind. I've opened issue24362 to track that work. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Stefan Krah ste...@bytereef.org: Added file: http://bugs.python.org/file39582/crash-2.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Stefan Krah added the comment: crash-1.py is due to an unchecked return value from _odictnode_VALUE(). We should probably use PyDict_GetItemWithError(), also in other places. I normally try to steer clear of stylistic remarks, but the _odictnode* macros are hiding too many things. As of now, they were hiding that an assert() is always true and that a return value was unchecked. Also, they're very inconvenient in a debugger. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Stefan Krah ste...@bytereef.org: Added file: http://bugs.python.org/file39581/crash-1.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Stefan Krah added the comment: crash-2.py is due to the fact that _PyDict_Pop() deletes a reference to 'key' in _odict_popkey(). The INCREF(key) in popitem should take place before calling _odict_popkey(). Again, I don't see the point of INCREF/DECREF *inside* of _odict_popkey(). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've opened the following issues to address the 3 last comments: issue24347 issue24348 issue24349 I'll be opening a separate issue for outstanding review comments. -- status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Christian Heimes added the comment: Coverity has found an issue in odict, too: *** CID 1302699: Null pointer dereferences (NULL_RETURNS) /Objects/odictobject.c: 1316 in odict_copy() 1310 od_copy = PyObject_CallFunctionObjArgs((PyObject *)Py_TYPE(od), NULL); 1311 if (od_copy == NULL) 1312 return NULL; 1313 1314 if (PyODict_CheckExact(od)) { 1315 _odict_FOREACH(od, node) { CID 1302699: Null pointer dereferences (NULL_RETURNS) Dereferencing a pointer that might be null PyDict_GetItem((PyObject *)(PyObject *)od, node-key) when calling PyODict_SetItem. 1316 int res = PyODict_SetItem((PyObject *)od_copy, 1317 _odictnode_KEY(node), 1318 _odictnode_VALUE(node, od)); 1319 if (res != 0) 1320 goto fail; 1321 } -- nosy: +christian.heimes ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @Jim and Stefan, Thanks for thorough reviews! @Stefan, I'll take a look at those crashers and other suggestions ASAP. I really appreciate you taking the time. Now that the patch has been landed, would you mind opening new issues for each problem you find? That will help keep individual problems from getting lost. Thanks! -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Steve Dower steve.do...@microsoft.com: -- nosy: -steve.dower ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Stefan Krah added the comment: Opening again. I have too many questions. :) -- nosy: +skrah status: pending - open ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: If it's just a matter of adding the definitions then here's a patch. Does that look correct? -- Added file: http://bugs.python.org/file39567/odict-windows.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset aea27164d207 by Eric Snow in branch '3.5': Issue #16991: Add odictobject.h on Windows. https://hg.python.org/cpython/rev/aea27164d207 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset c9404fba02ba by Eric Snow in branch '3.5': Issue #16991: Properly handle return values in several places. https://hg.python.org/cpython/rev/c9404fba02ba New changeset 951a3ef82180 by Eric Snow in branch '3.5': Issue #16991: Do not return None from OrderedDict.__reversed__. https://hg.python.org/cpython/rev/951a3ef82180 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset fbe74badb0c6 by Eric Snow in branch 'default': Issue #16991: Ensure that the proper OrderedDict is used in tests. https://hg.python.org/cpython/rev/fbe74badb0c6 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset 030205f1e716 by Eric Snow in branch '3.5': Issue #16991: Fix a few leaks and other memory-related concerns in OrderedDict. https://hg.python.org/cpython/rev/030205f1e716 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset 3ba1fa925f17 by Eric Snow in branch 'default': Issue #16991: Use the correct version for master. https://hg.python.org/cpython/rev/3ba1fa925f17 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: -- status: open - pending ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Well, that last one has everything compiling again. I expect it should be okay now. I'll watch the results. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I'm checking a fix for Windows against a buildbot (http://buildbot.python.org/all/builders/AMD64%20Windows8%203.x). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: You already added public name Py_ODict_GetItemId. It uses private _Py_Identifier API and shouldn't be public. Ah. I'll remove it. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset 7117e9b0f595 by Eric Snow in branch '3.5': Issue #16991: Drop Py_ODict_GetItemId. https://hg.python.org/cpython/rev/7117e9b0f595 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: That last message is about building on Windows. -- nosy: +steve.dower ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset 1d851112922f by Eric Snow in branch '3.5': Issue #16991: Add PyODict* to Windows builds. https://hg.python.org/cpython/rev/1d851112922f -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Serhiy Storchaka added the comment: I agree with all Stephan's comments on Rietveld. See also issue24115 that fixed bugs similar to found in C implementation of OrderedDict. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset 0a7380984e37 by Eric Snow in branch '3.5': Issue #16991: Use PyObject_TypeCheck instead of PyObject_IsInstance. https://hg.python.org/cpython/rev/0a7380984e37 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Mark Lawrence added the comment: I'm getting the following linker errors on Windows 8.1 for 32 and 64 bit debug and release builds. unresolved external symbol _PyODict_Type in C:\cpython\PCbuild\_collectionsmodule.obj, and _PyODictIter_Type, _PyODictValues_Type, _PyODictKeys_Type,_PyODictItems_Type in C:\cpython\PCbuild\object.obj -- nosy: +BreamoreBoy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: PyObject_TypeCheck() should be used instead of PyObject_IsInstance() (see issue24257). Thanks for pointing this out. I've fixed both dictobject.h and odictobject.h. Perhaps Py_ODict_GetItemId() should be private API as relevant dict function. This isn't needed for 3.5, right? I'm not opposed to adding more functions to the C API for OrderedDict, but I wanted to start out as small as possible. My main motivation for the C implementation was for use in the interpreter and I hadn't given much thought to the direct use of C OrderedDict by extension modules. That can be addressed in 3.6 if it's important. I supposed you could double-check with Larry if you want to add more odict support to the C-API for 3.5. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: New changeset 0a7380984e37 by Eric Snow in branch '3.5': Issue #16991: Use PyObject_TypeCheck instead of PyObject_IsInstance. https://hg.python.org/cpython/rev/0a7380984e37 I've also merged this into default: changeset: 96384:10eabadba316b6f2034db4c076a60c63d25d8fc6 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I'm getting the following linker errors on Windows 8.1 for 32 and 64 bit debug and release builds. unresolved external symbol _PyODict_Type in C:\cpython\PCbuild\_collectionsmodule.obj, and _PyODictIter_Type, _PyODictValues_Type, _PyODictKeys_Type,_PyODictItems_Type in C:\cpython\PCbuild\object.obj Hmm. I'm not too familiar with how things work for Windows. I'm also not clear on where the leading underscore is coming from. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Serhiy Storchaka added the comment: This isn't needed for 3.5, right? I'm not opposed to adding more functions to the C API for OrderedDict, but I wanted to start out as small as possible. You already added public name Py_ODict_GetItemId. It uses private _Py_Identifier API and shouldn't be public. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Serhiy Storchaka added the comment: As for Windows issue, perhaps these names should be enumerated in PC/python3.def? See also issue23903. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: Added file: http://bugs.python.org/file39566/0813b1a88171.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @Jim, I believe I've addressed all the review comments that have indicate a risk. I've also answered basically all the rest. Thanks for the great review. Unless there are any objections, I'll likely commit the patch in the next hour or two. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset e7af362b78df by Eric Snow in branch 'default': Issue #16991: Add a C implementation of collections.OrderedDict. https://hg.python.org/cpython/rev/e7af362b78df -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Yep. :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Roundup Robot added the comment: New changeset b85028c9d4b9 by Eric Snow in branch '3.5': Issue #16991: Add a C implementation of collections.OrderedDict. https://hg.python.org/cpython/rev/b85028c9d4b9 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: @Eric: I think you also want to commit it to 3.5 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I'll keep an eye out for trouble on the buildbots. -- resolution: - fixed stage: patch review - resolved status: open - pending ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Serhiy Storchaka added the comment: PyObject_TypeCheck() should be used instead of PyObject_IsInstance() (see issue24257). Perhaps Py_ODict_GetItemId() should be private API as relevant dict function. -- status: pending - open ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Planning on committing today after I address some review comments. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Wes Turner added the comment: * Would this make it easy/faster to also have a DefaultOrderedDict (which can/could also be accomplished with .get(attr, []) and .setdefault ? On May 29, 2015 2:39 PM, Eric Snow rep...@bugs.python.org wrote: Eric Snow added the comment: Planning on committing today after I address some review comments. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: Can we merge this patch before new beta2? https://mail.python.org/pipermail/python-committers/2015-May/003410.html -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: * Would this make it easy/faster to also have a DefaultOrderedDict (which can/could also be accomplished with .get(attr, []) and .setdefault ? Not in 3.5. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Eric I realize that O (1) deletion is hard, and don't see a good way around it without changing the implementation ... I just think that the preserving the current C layout may be forcing an even more complicated solution than neccessary. I am nervous about pushing this to 3.5 because of the complexity. I agree that a simpler solution should (also?) wait for 3.6. Noted (and thanks for the feedback). I'm still comfortable with moving ahead for 3.5 with what we have. The code is documented and structured in such a way that it should be clear what's going on and relatively straightforward to adjust. There's a decent chance we will find a bug or two in corner cases, but nothing at a scale that would give me pause for a 3.5 release. Furthermore, the test suite for OrderedDict is pretty thorough so strict compatibility with the pure Python OrderedDict allows us to derive a lot of confidence about the C implementation. The question about dictheaher.h boils down to: if someone asks whether something is a dictview (not even using exact, though that isn't an option), an odictview will say false ... is that really what you want? Ah. I misunderstood your question to imply what should be added. Instead, you were just indicating what is already there. I don't think anything needs to be changed though. Those checks don't pass for the pure Python OrderedDict so I would not expect them to do so for the C implementation. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @Jim, You've got some good questions. I'll look into them today. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @mrab gah! I could swear I originally had the _odict_clear_node first and had switched them due to a segfault. It even crossed my mind on Friday but I didn't pursue it. I'm guessing I did put the _odict_clear_node call first at some point but lost that fix along the way. :( That's the benefit of having a patch languish for so long; you end up working on it from multiple hosts and sometimes lose bits and pieces. Unfortunately only recently did I think to create a feature repo on which to track the on-going work. Anyway, thanks for helping with the investigation. The patch should be just about ready to commit at this point. :) I'm going to give it a once over, check for any lingering ref leaks, and double-check with Raymond. So I'm hopeful we can land this in the next few days. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I'm going to echo the previous comment that maybe trying to emulate the existing dict implementation too carefully just adds complexity. The whole dance with _odict_get_index and _odict_resize is due to the requirement that OrderedDict maintain O(1) operation for deletion operations. Due to using a linked list, we needed a secondary mechanism for efficiently indexing into the list. There is a note at the top of the file explaining the alternatives I considered and the rationale for mirroring dict's hash table. The split-keys implementation shows that there is at least some flexibility to the implementation. Enough that the keys could map to an array offset, rather than directly to the values? What do you mean by this? If you are suggesting changes to dict or its accessory types then it is something I considered and rejected. Personally I don't want to change anything on dict itself for the sake of OrderedDict. If others would like to pursue that they're welcome to do so. :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Should dictobject.h get a bit more changes? In particular, should the following be expanded? #define PyDictKeys_Check(op) (Py_TYPE(op) == PyDictKeys_Type) #define PyDictItems_Check(op) (Py_TYPE(op) == PyDictItems_Type) #define PyDictValues_Check(op) (Py_TYPE(op) == PyDictValues_Type) /* This excludes Values, since they are not sets. */ # define PyDictViewSet_Check(op) \ (PyDictKeys_Check(op) || PyDictItems_Check(op)) I'm missing some context here. I'm not sure how this relates to OrderedDict. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @Mark, great idea. I wish we'd discussed it more at PyCon 2013 when I was working on preserving OrderedDict's O(1) deletion. :) TBH, I don't have any problems with improvements. In fact, I'd be quite happy if folks jumped in and improved what I've done or even replaced it entirely. But at the point (with the feature freeze exception Larry gave) we should land what I have in 3.5 and then target 3.6 for any improvements. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Mark Shannon added the comment: I realise that I am bit late to the party, but I would like to point out that a smaller, arguably simpler, and almost certainly faster alternative design exists. This design simply consists of an array of (prev, next, key) nodes attached to the base dict. The linked list is maintained using the prev next pointers of the nodes as normal. The mapping of keys to nodes is maintained by ensuring that the index of the node in the node array matches the index of the key in dict-key table. When the size of the array matches that of the keys table, this should be a very fast operation. When the dict is resized, the array will need to resized. (Possibly lazily if PyDict_* functions are used directly on the ordered dict.) Size analysis - For an an occupancy of X, Eric's design takes 7/X + 3 slots per key/value pair. The alternative design takes 6/X slots per key/value pair. For an occupancy of 50%, half way between the minimum of 1/3 and maximum of 2/3, on a 64bit machine: The design proposed in this issue takes 17 slots or 136 bytes per key/value pair. The alternative would take 12 slots or 96 bytes per pair, about 70% of the size. -- nosy: +Mark.Shannon ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: Added file: http://bugs.python.org/file39496/3b2a9026d48e.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: At present the only remaining issues with the patch are: * 10 leaked refs in test_collections * a failing test in test_enum === key: __members__ result: OrderedDict([('red', Color.red: 1), ('green', Color.green: 2), ('blue', Color.blue: 3)]) expected: OrderedDict([('red', Color.red: 1), ('green', Color.green: 2), ('blue', Color.blue: 3)]) === test test_enum failed -- Traceback (most recent call last): File /home/esnow/projects/cordereddict/Lib/test/test_enum.py, line 1668, in test_inspect_getmembers self.fail(result does not equal expected, see print above) AssertionError: result does not equal expected, see print above I'm not sure what to make of that test. By all appearances it should be passing. My guess is that there's some wackiness afoot over in Enum, but I'll take a closer look after I get the ref counts sorted out. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: The failing test is not passing so I don't see any further blockers to committing this. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: Added file: http://bugs.python.org/file39499/c3fab329aa7f.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: rather, it *is* passing now :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've cleaned up the patch. I still want to make one last pass to check re-entrancy concerns. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: Added file: http://bugs.python.org/file39500/ba1c6d40ca63.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've cleaned up all the ref leaks so now just the failing test_enum test remains to be resolved. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Jim Jewett added the comment: Eric I realize that O (1) deletion is hard, and don't see a good way around it without changing the implementation ... I just think that the preserving the current C layout may be forcing an even more complicated solution than neccessary. I am nervous about pushing this to 3.5 because of the complexity. I agree that a simpler solution should (also?) wait for 3.6. The question about dictheaher.h boils down to: if someone asks whether something is a dictview (not even using exact, though that isn't an option), an odictview will say false ... is that really what you want? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: rather, it *is* passing now :) Eric, thanks for working on this! Could you please go through your patch and replace // comments with /* .. */ ones? It would also be great if you can clean-up XXX comments. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Ah, good point. I'll take care of all those. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Matthew Barnett added the comment: First some background: when you put a new entry into a dict, it looks for an empty slot, the key's hash determining the initial choice, but if that slot's occupied, it picks another, etc, so the key might not be in the slot of first choice. In PyODict_DelItem, it deletes the key from the dict and then calls _odict_clear_node to delete the node. If the key that it's looking for wasn't in the slot of first choice, but that slot is empty, that'll be the one it'll return, ie, the wrong one. The solution, therefore, is to delete the node _before_ deleting the key from the dict. When I tried that, the test ran to completion. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Matthew Barnett added the comment: In odict_new, if _odict_initialize fails, will the dict pointed to by od_inst_dict be deallocated? In odictiter_new, there's Py_INCREF(od);. If di-di_result == NULL fails, od isn't DECREFed. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Good catch. I've fixed odictiter_new in the feature branch. However, I'm not sure there's anything to be fixed in odict_new. It follows the same pattern as dict_new (over in Objects/dictobject.c). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: -- hgrepos: +309 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Nick Coghlan added the comment: I'd suggest also taking a look into whether or not the PEP 412 keysharing might be causing problems. -- nosy: +ncoghlan ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Good point, Nick. I'd checked that earlier but did not see any relationship. At this point it's worth checking again. :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Jim Jewett added the comment: Eric, unless I'm misreading your debugging info, it is the other way around -- something is in the dict, but not in the list that you iterate over. And since the list that you iterate over looks right, I have to wonder if it was something internal-to-configparser (or its various converters and proxies). Perhaps the __root used by the collections.OrderedDict that it uses by default? Can you iterate over it as a dict, instead of as an ordered dict, to find the discrepancy? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Jim Jewett added the comment: (Just putting my review summary in the main ticket) I'm going to echo the previous comment that maybe trying to emulate the existing dict implementation too carefully just adds complexity. The split-keys implementation shows that there is at least some flexibility to the implementation. Enough that the keys could map to an array offset, rather than directly to the values? A simple array of key/value pairs (hashing only to ensure hashability, but ignoring it otherwise) should be faster for the really small dicts you care about, like keyword dicts. (Admittedly, those timing data are fairly out of date, but I would be surprised if it weren't still true.) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Jim Jewett added the comment: Should dictobject.h get a bit more changes? In particular, should the following be expanded? #define PyDictKeys_Check(op) (Py_TYPE(op) == PyDictKeys_Type) #define PyDictItems_Check(op) (Py_TYPE(op) == PyDictItems_Type) #define PyDictValues_Check(op) (Py_TYPE(op) == PyDictValues_Type) /* This excludes Values, since they are not sets. */ # define PyDictViewSet_Check(op) \ (PyDictKeys_Check(op) || PyDictItems_Check(op)) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Include/opcode.h shouldn't be in the change (and won't be when committed). I'm guessing it being there is related to one of the recent merges I did from default into the feature branch. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: If I still the following at Lib/test/test_configparser.py:328: print(len(cf._proxies), len(list(cf._proxies)), list(cf._proxies)) print(len(cf._sections), len(list(cf._sections)), list(cf._sections)) I get unexpected results that are a clear indication of a problem: 9 8 ['DEFAULT', 'Foo Bar', 'Spacey Bar', 'Spacey Bar From The Beginning', 'Commented Bar', 'Long Line', 'Section\\with$weird%characters[\t', 'Internationalized Stuff'] 8 7 ['Foo Bar', 'Spacey Bar', 'Spacey Bar From The Beginning', 'Commented Bar', 'Long Line', 'Section\\with$weird%characters[\t', 'Internationalized Stuff'] Note that OrderedDict.__len__ is just dict.__len__, so the first number (the actual length) should be the same as the second number (the number of keys). Also note that OrderedDict.keys() is working (even if not exactly correct). Between the two observations, this implies that for this one test the keys are not only off, but at least one of the keys in the linked list is not in the underlying dict. I'm sure this is consequence of resizing. At the last point that we resize this is the state of the cf._proxies and cf._sections (ignore the trailing NULL (?)): OrderedDict([('DEFAULT', Section: DEFAULT), ('Foo Bar', Section: Foo Bar), ('Spacey Bar', Section: Spacey Bar), ('Spacey Bar From The Beginning', Section: Spacey Bar From The Beginning), ('Commented Bar', Section: Commented Bar), NULL]) OrderedDict([('Foo Bar', OrderedDict([('foo', ['bar1'])])), ('Spacey Bar', OrderedDict([('foo', ['bar2'])])), ('Spacey Bar From The Beginning', OrderedDict([('foo', ['bar3']), ('baz', ['qwe'])])), ('Commented Bar', OrderedDict([('foo', ['bar4']), ('baz', ['qwe'])])), ('Long Line', OrderedDict([('foo', ['this line is much, much longer than my editor', 'likes it.'])])), NULL]) I haven't had time to analyze this but I'll be taking a closer look in later tonight. I'm not giving up on 3.5. :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Just to narrow things down a bit further, the failure happens specifically under ConfigParserTestCaseNoValue: PYTHONHASHSEED=7 ./python -m unittest test.test_configparser.ConfigParserTestCaseNoValue.test_basic -v -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Jim Jewett added the comment: Why does generated file Include/opcode.h show up as changed? It looks like pure whitespace, but I wonder if a similar whitespace change might be making something a space too long somewhere. -- nosy: +Jim.Jewett ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Ned Deily added the comment: FWIW, the random segfault seems to be triggered by hash randomization. If I disable randomization, it does not seem to fail: for i in `seq 1 20`; do PYTHONHASHSEED=1 ./python -m test.regrtest -m test_basic test_configparser ; done Presumably, the --forever option does not vary the hash seed value? Also, FWIW, clang issues a warning: ../../source/Objects/odictobject.c:550:15: warning: comparison of unsigned expression 0 is always false [-Wtautological-compare] if (i 0) { ~ ^ ~ for this: _odict_FOREACH(od, node) { size_t i = _odict_get_index(od, _odictnode_KEY(node)); if (i 0) { od-od_size = prev_size; PyMem_FREE(fast_nodes); return -1; } fast_nodes[i] = node; I can supply OS X crash tracebacks if they would be of help. -- nosy: +ned.deily ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Cool. The following gives consistent failures at certain seed values: for i in `seq 1 100`; do echo $i; PYTHONHASHSEED=$i ./python -m test.regrtest -m test_basic test_configparser ; done Through 100 I get segfaults with 7, 15, 35, 37, 39, 40, 42, 47, 50, 66, 67, 85, 87, 88, and 92. The distribution is probably essentially uniform across the full set of seeds, even if the exact pattern of failures isn't precisely uniform. I'll try to see why those hashes are significant here. If I can't figured it out quickly then I'll post about it on python-dev. My hunch is that the hash randomization impacts either dict/odict resizing or dict/odict lookup (or both). TBH, I've been pretty sure for a while that the segfault is coming out of one of those two. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Thanks for looking into this, Ned. I've changed that size_t to ssize_t which I expect will quiet that clang warning you saw. I'm glad you pointed it out because it means that that branch was never executing! Unfortunately fixing that does not solve all my problems. wink I'll look into the hash randomization connection. Thanks for pointing that out. Hopefully it doesn't complicate matters. My guess is that the segfaults only happen for certain seeds, so I'll check that first. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've spent a bit of time exploring the segfault. Here's some data that might help relative to the configparser test. I put the following at the beginning of _odict_resize: Py_ssize_t len = PyObject_Size((PyObject *)od); if (len == 0) PySys_FormatStdout(.); else { if (((PyDictObject *)od)-ma_keys-dk_size od-od_size) PySys_FormatStdout(-); if (len 10) PySys_FormatStdout(%d, len); else PySys_FormatStdout(+); } if (len = 10) PySys_FormatStdout(%d\n, len); If the current item count is 0 then it prints a dot. If the resize is shrinking then it prints a - (this did not happen). Otherwise the odict is growing and it prints the current item count. Multi-digit numbers are preceded by + and followed by a newline. I've included the results of different hash seeds (0/no randomization, 1, and 7). You'll notice how the results are subtly different. In the case of 7, it matches no randomization up to the point that it segfaults. I got the same results with 15. However, 35 fails right after the second +22. $ PYTHONHASHSEED=0 ./python -m test.regrtest -m test_basic test_configparser ...6+12 +22 6+12 +22 6.6+10 6.6+10 6.6+10 6.6+10 6.6+10 .+10 6.6+10 6.6+10 6.6+10 6.6...6..6+10 6.6.6.6.66.66.6.6.6.6.+12 6.+12 6.6.6.6.6.6.6.6.6.+22 6.+22 6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.+44 6.+44 6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.+86 6.+86 6.6.6.6.6.6.6.6.6.6.6.6.6.6.66.6+10 6.6+10 6.6+10 6.6+10 .6.. $ PYTHONHASHSEED=1 ./python -m test.regrtest -m test_basic test_configparser ...6+12 +22 6+12 +22 6.66.66.66.66.6.+11 6.66.66.66.6...6..66.6.6.6.66.66.6.6.6.6.+12 6.+12 6.6.6.6.6.6.6.6.6.+22 6.+22 6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.+44 6.+44 6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.+86 6.+86 6.6.6.6.6.6.6.6.6.6.6.6.6.6.66.66.66.66.6.6.. $ PYTHONHASHSEED=7 ./python -m test.regrtest -m test_basic test_configparser ...6+12 +22 6+12 +22 6.6+10 6.6+10 6.6+10 6.6+10 6.6+10 .+10 Fatal Python error: Segmentation fault -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Here are the last 10 frames from the backtrace (gdb): #0 0x005b15d0 in odictiter_iternext (di=optimized out) at Objects/odictobject.c:1888 #1 0x00453179 in PyIter_Next (iter=optimized out) at Objects/abstract.c:2760 #2 0x005881e7 in chain_next (lz=0x72b8d878) at ./Modules/itertoolsmodule.c:1866 #3 0x00537db6 in PyEval_EvalFrameEx (f=f@entry=0xcab188, throwflag=throwflag@entry=0) at Python/ceval.c:2975 #4 0x0053afee in fast_function (func=func@entry=0x72bc88f8, pp_stack=pp_stack@entry=0x7fff99f8, n=n@entry=1, na=na@entry=1, nk=nk@entry=0) at Python/ceval.c:4752 #5 0x0053b655 in call_function (pp_stack=pp_stack@entry=0x7fff99f8, oparg=oparg@entry=0) at Python/ceval.c:4679 #6 0x0053891d in PyEval_EvalFrameEx (f=f@entry=0xcbd588, throwflag=throwflag@entry=0) at Python/ceval.c:3198 #7 0x0053afee in fast_function (func=func@entry=0x72bc8840, pp_stack=pp_stack@entry=0x7fff9bd8, n=n@entry=3, na=na@entry=3, nk=nk@entry=0) at Python/ceval.c:4752 #8 0x0053b655 in call_function (pp_stack=pp_stack@entry=0x7fff9bd8, oparg=oparg@entry=2) at Python/ceval.c:4679 #9 0x0053891d in PyEval_EvalFrameEx (f=f@entry=0xc7d458, throwflag=throwflag@entry=0) at Python/ceval.c:3198 and from Python: Current thread 0x7f3ad9260740 (most recent call first): File /home/esnow/projects/cordereddict/Lib/configparser.py, line 1115 in _join_multiline_values File /home/esnow/projects/cordereddict/Lib/configparser.py, line 1109 in _read File /home/esnow/projects/cordereddict/Lib/configparser.py, line 716 in read_file File /home/esnow/projects/cordereddict/Lib/configparser.py, line 721 in read_string File /home/esnow/projects/cordereddict/Lib/test/test_configparser.py, line 354 in test_basic File /home/esnow/projects/cordereddict/Lib/unittest/case.py, line 597 in run -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: As far as I can tell there aren't any patterns that repeat across multiple seeds (which makes sense). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: The segfault happens at line 1888 of odictobject.c when it tries to Py_INCREF a NULL value. The problem is that the value that gets looked up for a presumably valid key is returned as NULL. So either the value is messed up, lookup is broken, or the wrong key is being used. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Matthew Barnett added the comment: FTR, in _odict_resize there's this: size_t i = _odict_get_index(od, _odictnode_KEY(node)); if (i 0) { Note that i is declared as unsigned and then tested whether it's negative. -- nosy: +mrabarnett ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Yeah, Ned pointed that one out. I fixed it but haven't pushed the change. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: These are the leaks I'm seeing in test_collections (14/24 tests): test_copying : 178 test_iterators : 40 test_update : 29 test_init: 22 test_move_to_end : 21 test_sorted_iterators: 20 test_setdefault : 16 test_clear : 5 test_setitem : 5 test_delitem : 4 test_repr_recursive : 4 test_repr: 3 test_override_update : 2 test_reinsert: 1 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've updated the cordereddict branch on the feature repo to fix the ref leak on None. I'm still seeing other leaks (regrtest -R 3:3), but I don't think that should block landing before the feature freeze. However, I'm concerned about a segfault I'm seeing roughly 3% of the time when running the following: ./python -m unittest test.test_configparser.ConfigParserTestCase.test_basic Presumably there is a dealloc bug there which manifests intermittently due to a GC race. I'm going work on tracking it down but help is appreciated. :) I'm also seeing consistent test failures in test_enum. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Antoine Pitrou added the comment: A patch shouldn't be integrated if there are known bugs with it (especially segfaults). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Agreed. I wanted to be clear about what is blocking landing the patch. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: I've fixed most of the leaks now. The only remaining ones are: test_clear : 5 test_repr_recursive : 3 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Regarding the segfault, the following does not fail: ./python -m test.regrtest --forever -m test_basic test_configparser but this does: for i in `seq 1 20`; do ./python -m test.regrtest -m test_basic test_configparser ; done -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: Eric, could you please upload your latest patch? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Here's a diff from the current cordereddict branch of the feature repo. -- Added file: http://bugs.python.org/file39445/cOrderedDict-4.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: Thanks for taking a look, Yury. I'll follow up on the ref leak soon. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: As for refleak -- I looked at it briefly: simple a = OrderedDict(); a = None code leaks, so it must be somewhere in tp_new/tp_dealloc. And I know what object is leaking - it's None. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: Raymond, is there any chance you can review the patch before beta1? Sorry, for bugging you with this, I just really hope we can have fast OrderedDict in 3.5. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: Started to look at the patch in more detail. Found one leak. There are more. Eric, maybe you can hunt them? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Yury Selivanov added the comment: I must have used a better example :) import sys; from collections import OrderedDict as OD sys.getrefcount(None) 2053 OD();OD();OD();OD(); OrderedDict() OrderedDict() OrderedDict() OrderedDict() sys.getrefcount(None) 2057 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[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 in 3.6. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Eric Snow added the comment: @Yury, I'm mostly just waiting for Raymond to give it at least a quick sanity-check. I know there is at least 1 ref leak, but that can be sorted out. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16991] Add OrderedDict written in C
Changes by Eric Snow ericsnowcurren...@gmail.com: -- priority: normal - release blocker ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16991 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com