Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(116536)

#16991: Add OrderedDict written in C

Can't Edit
Can't Publish+Mail
Start Review
Created:
6 years, 10 months ago by ericsnowcurrently
Modified:
4 years, 5 months ago
Reviewers:
jimjjewett, yselivanov, stefan
CC:
rhettinger, gregory.p.smith, Nick Coghlan, AntoinePitrou, scoder, eric.smith, christian.heimes, Benjamin Peterson, ned.deily, ezio.melotti, eric.araujo, mrabarnett, arfrever.fta_gmail.com, alex, asvetlov, skrah, flox, BreamoreBoy, Mark.Shannon, devnull_psf.upfronthosting.co.za, eric.snow, Jim.J.Jewett, storchaka, Yury Selivanov, wes.turner_gmail.com, rymg19_gmail.com, Josh.R, tonn81_gmail.com, introom
Visibility:
Public.

Patch Set 1 #

Patch Set 2 #

Patch Set 3 #

Patch Set 4 #

Patch Set 5 #

Patch Set 6 #

Total comments: 2

Patch Set 7 #

Patch Set 8 #

Total comments: 2

Patch Set 9 #

Total comments: 2

Patch Set 10 #

Total comments: 57

Patch Set 11 #

Patch Set 12 #

Patch Set 13 #

Total comments: 5

Patch Set 14 #

Total comments: 33
Unified diffs Side-by-side diffs Delta from patch set Stats Patch
Include/dictobject.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 4 chunks +12 lines, -3 lines 0 comments Download
Include/odictobject.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +42 lines, -0 lines 0 comments Download
Include/Python.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +1 line, -0 lines 0 comments Download
Lib/collections/__init__.py View 1 2 3 4 5 6 7 8 9 10 11 12 13 3 chunks +19 lines, -2 lines 0 comments Download
Lib/test/test_collections.py View 1 2 3 4 5 6 7 8 9 10 11 12 13 23 chunks +184 lines, -18 lines 2 comments Download
Makefile.pre.in View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +1 line, -0 lines 0 comments Download
Modules/_collectionsmodule.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +3 lines, -0 lines 0 comments Download
Objects/dict-common.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +22 lines, -0 lines 0 comments Download
Objects/dictobject.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 23 chunks +165 lines, -172 lines 0 comments Download
Objects/object.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +15 lines, -0 lines 0 comments Download
Objects/odictobject.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +2394 lines, -0 lines 31 comments Download

Messages

Total messages: 19
sasha
http://bugs.python.org/review/16991/diff/8309/Include/odictobject.h File Include/odictobject.h (right): http://bugs.python.org/review/16991/diff/8309/Include/odictobject.h#newcode32 Include/odictobject.h:32: PyAPI_FUNC(int) PyODict_DelItem(PyObject *od, PyObject *key); Is there a reason ...
6 years, 5 months ago #1
Yury.Selivanov
Just two super minor nit-picks from me. http://bugs.python.org/review/16991/diff/9637/Lib/collections/__init__.py File Lib/collections/__init__.py (right): http://bugs.python.org/review/16991/diff/9637/Lib/collections/__init__.py#newcode60 Lib/collections/__init__.py:60: # raise ...
5 years, 9 months ago #2
Yury Selivanov
Found one refleak. http://bugs.python.org/review/16991/diff/14384/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14384/Objects/odictobject.c#newcode1662 Objects/odictobject.c:1662: if (odict_update(self, args, kwds) == NULL) ...
4 years, 6 months ago #3
Jim.J.Jewett
I'm going to echo the previous comment that maybe trying to emulate the existing dict ...
4 years, 5 months ago #4
Yury Selivanov
http://bugs.python.org/review/16991/diff/14899/Include/opcode.h File Include/opcode.h (right): http://bugs.python.org/review/16991/diff/14899/Include/opcode.h#newcode10 Include/opcode.h:10: #define POP_TOP 1 Why do we have this diff ...
4 years, 5 months ago #5
Jim.J.Jewett
http://bugs.python.org/review/16991/diff/14942/Lib/collections/__init__.py File Lib/collections/__init__.py (right): http://bugs.python.org/review/16991/diff/14942/Lib/collections/__init__.py#newcode1131 Lib/collections/__init__.py:1131: def casefold(self): The UserString fixes are good. I would ...
4 years, 5 months ago #6
Yury Selivanov
http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c#newcode139 Objects/odictobject.c:139: Situation that Endangers Consistency Eric, so have you resolved ...
4 years, 5 months ago #7
eric.snow
http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c#newcode139 Objects/odictobject.c:139: Situation that Endangers Consistency On 2015/05/26 20:46:41, Yury.Selivanov wrote: ...
4 years, 5 months ago #8
skrah
http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c#newcode783 Objects/odictobject.c:783: return; I think there's a leak. Goto line 802 ...
4 years, 5 months ago #9
eric.snow
http://bugs.python.org/review/16991/diff/8309/Include/odictobject.h File Include/odictobject.h (right): http://bugs.python.org/review/16991/diff/8309/Include/odictobject.h#newcode32 Include/odictobject.h:32: PyAPI_FUNC(int) PyODict_DelItem(PyObject *od, PyObject *key); On 2013/06/10 17:19:54, sasha ...
4 years, 5 months ago #10
eric.snow
http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14942/Objects/odictobject.c#newcode783 Objects/odictobject.c:783: return; On 2015/05/29 15:08:49, skrah wrote: > I think ...
4 years, 5 months ago #11
eric.snow
http://bugs.python.org/review/16991/diff/14899/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14899/Objects/odictobject.c#newcode484 Objects/odictobject.c:484: struct _odictobject { On 2015/05/24 04:33:27, Jim.J.Jewett wrote: > ...
4 years, 5 months ago #12
skrah
I have a couple of more comments. Additionally, probably increasing code coverage would be a ...
4 years, 5 months ago #13
eric.snow
I believe I've addressed all the review comments. http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode969 Objects/odictobject.c:969: if ...
4 years, 5 months ago #14
skrah
Jim has raised these issues earlier: I still don't understand the resize()/get_index() mutual recursion story ...
4 years, 5 months ago #15
skrah
http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode554 Objects/odictobject.c:554: assert(node != NULL); 'node' is always != NULL here.
4 years, 5 months ago #16
Jim.J.Jewett
http://bugs.python.org/review/16991/diff/14899/Objects/odictobject.c File Objects/odictobject.c (right): http://bugs.python.org/review/16991/diff/14899/Objects/odictobject.c#newcode484 Objects/odictobject.c:484: struct _odictobject { On 2015/05/30 04:46:24, eric.snow wrote: > ...
4 years, 5 months ago #17
eric.snow
Thanks again for the great reviews. I'll address the remaining comments (about get_index/resize) separately. http://bugs.python.org/review/16991/diff/14899/Objects/odictobject.c ...
4 years, 5 months ago #18
eric.snow
4 years, 5 months ago #19
http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c
File Objects/odictobject.c (right):

http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode554
Objects/odictobject.c:554: assert(node != NULL);
On 2015/05/31 14:11:26, skrah wrote:
> 'node' is always != NULL here.

Done.

http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode555
Objects/odictobject.c:555: i = _odict_get_index(od, _odictnode_KEY(node));
On 2015/05/31 13:08:16, skrah wrote:
> Call odict_get_index(), which does not call resize() if the above equality
holds
> ...

Although it is highly unlikely, PyObject_Hash() (in _odict_get_index) can
trigger a resize.

I suppose we could cache the hash on the node like dict does for entries.  Then
there would be no need to call PyObject_Hash in this loop.

http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode563
Objects/odictobject.c:563: if (size != ((PyDictObject *)od)->ma_keys->dk_size) {
On 2015/05/31 13:08:16, skrah wrote:
> ... then how can this happen?
> 
> I think it can't.

There is exactly one place where a dict resize could be triggered, through a
key's __hash__ misbehaving by adding items to the odict.

http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode589
Objects/odictobject.c:589: if (resize_res < 0)
On 2015/05/31 13:08:16, skrah wrote:
> If resize() is called here, and resize() calls get_index() again, then
> keys->dk_size should equal od->od_size (or I'm fundamentally misunderstanding
> something).
> 
> So why is the do/while loop necessary? I also don't see why mutual recursion
is
> necessary.
> 
> 

The loop is not necessary.  It was originally a goto and originally based on the
approach taken in the dict implementation.  However, it isn't necessary.

The mutual recursion is something I'd like to remove.  It's a source of too much
confusion.  With the risk of resize during PyObject_Hash() call in mind, the
only solution I've come up with so far is to cache the key's hash on each node
in the linked list.  I'm open to other solutions. :)  I'm sure we can find
something that isn't so complicated as what's there now.

http://bugs.python.org/review/16991/diff/14987/Objects/odictobject.c#newcode594
Objects/odictobject.c:594: hash = PyObject_Hash(key);
On 2015/05/31 13:08:16, skrah wrote:
> Why is this call inside the loop?

Yeah, it doesn't belong in the loop.
Sign in to reply to this message.

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+