Remove doubly-linked list from C OrderedDict

@arigo

BPO	31265
Nosy	@arigo, @rhettinger, @vstinner, @mitsuhiko, @methane, @ericsnowcurrently, @serhiy-storchaka
PRs	bpo-31265: Compact OrderedDict (wip) #3193

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2017-12-15.16:15:09.204>
created_at = <Date 2017-08-23.10:24:19.037>
labels = ['interpreter-core', '3.7']
title = 'Remove doubly-linked list from C OrderedDict'
updated_at = <Date 2017-12-16.07:19:57.287>
user = 'https://github.com/methane'

bugs.python.org fields:

activity = <Date 2017-12-16.07:19:57.287>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2017-12-15.16:15:09.204>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2017-08-23.10:24:19.037>
creator = 'methane'
dependencies = []
files = []
hgrepos = []
issue_num = 31265
keywords = []
message_count = 29.0
messages = ['300748', '300749', '300752', '300753', '300756', '300757', '300758', '300759', '300760', '300902', '301238', '301291', '301836', '301837', '301839', '301841', '301843', '301844', '301857', '301859', '301863', '301933', '301941', '301942', '301958', '308438', '308439', '308440', '308457']
nosy_count = 7.0
nosy_names = ['arigo', 'rhettinger', 'vstinner', 'aronacher', 'methane', 'eric.snow', 'serhiy.storchaka']
pr_nums = ['3193']
priority = 'normal'
resolution = 'later'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue31265'
versions = ['Python 3.7']

Since dict preserves insertion order, doubly linked list in OrderedDict
can be removed.

There is small performance improvement for odict creation:

$ curl https://api.github.com/orgs/python/repos > repos.json
$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import OrderedDict as od; import json; data=open("repos.json").read()' -- 'json.loads(data, object_pairs_hook=od)'
py-default: ..................... 1.53 ms +- 0.01 ms
py-patched: ..................... 1.30 ms +- 0.01 ms

Mean +- std dev: [py-default] 1.53 ms +- 0.01 ms -> [py-patched] 1.30 ms +- 0.01 ms: 1.18x faster (-15%)

And more memory efficient:

$ ./py-default -c 'from collections import OrderedDict; import sys; print(sys.getsizeof(OrderedDict.fromkeys(range(1000))))'
85416

$ ./py-patched -c 'from collections import OrderedDict; import sys; print(sys.getsizeof(OrderedDict.fromkeys(range(1000))))'
36992

But most important benefit is smaller code. It make easy to maintain.

There are some failing tests remaining, and I want to discuss about
some of them here.

Traceback (most recent call last):
  File "/home/inada-n/work/python/nodebug/Lib/test/test_ordered_dict.py", line 261, in test_pop
    self.assertEqual(m.pop('a', default=6), 6)
TypeError: pop() takes no keyword arguments

dict.pop doesn't take keyword argument.
Since OrderedDict is pure Python at first, C implementation of
OrderedDict.pop() takes keyword too.
May I change dict.pop() to take keyword too. It reduce odict
specific method.

Some test expect KeyError in some edge cases.
But new implementation behaves differently.
For example,

    def test_dict_delitem(self):
        OrderedDict = self.OrderedDict
        od = OrderedDict()
        od['spam'] = 1
        od['ham'] = 2
        dict.__delitem__(od, 'spam')
        with self.assertRaises(KeyError):
            repr(od)

Since current implementation uses linked list, it raises KeyError.
But this is totally OK for new C implementation.

---

Personally speaking, I want to stop keeping compatibility with pure Python
implementation.
Is it possible to make "builtin _collections.OrderedDict" as requirement for
all Python 3.7 implementations and remove pure Python implementation stdlib?

I would be very careful going down this path. Regular dict ordering is not yet guaranteed and is subject to change. Its design was primarily about compaction and the ordering was a side-effect. In contrast, the data structure for collections.OrderedDict() was designed specifically for maintaining order. It is likely that there are some workloads where the regular dict would degrade significantly compared to ordered dicts.

I like the idea. Actually I wanted to write such patch myself, but this is very delicate thing and needs to be very careful. The largest benefit is not just memory saving and performance, but robustness. Currently it is easy to went OrderedDict in incorrect state by using pure dict API. This can cause crashes, hangs or invalid bahavior (see bpo-24726 and bpo-25410). The new implementation should pass all existing tests and also fix the above issues.

See also bpo-28239. lru_cache uses simplified version of ordered dict.

I think typical usage is: get, set (incl, creating), and iterate.

get: there is no difference
set: inserting new key is little faster since no updating linked list
iterate: in typical case, new odict is faster because current odict iterator do lookup for each key.

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default \
  -s 'from collections import OrderedDict as odict; od = odict.fromkeys(range(10000))' -- 'list(od)'

py-default: ..................... 223 us +- 10 us
py-patched: ..................... 93.7 us +- 3.3 us
Mean +- std dev: [py-default] 223 us +- 10 us -> [py-patched] 93.7 us +- 3.3 us: 2.38x faster (-58%)

On the other hand, there are some cases new odict is slower:

iterating sparse dict. (but same speed as normal dict)
comparing two odict, because new odict do list(od1) == list(od2) to compare keys.

For now, new odict uses dict's iterator (with adding reversed order support) and it's weak
against modify while iterating. That's why I used temporal list while comparing.
And there is one failing test for modify-while-iterate case.

So I'm thinking about implementing robust odict iterator which detect modify for now.

od.move_to_end() is slower too:

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import OrderedDict as odict; od = odict.fromkeys("abcdefghijklmnopqrstuvwxyz")' -- 'od.move_to_end("a"); od.move_to_end("b")'
py-default: ..................... 196 ns +- 4 ns
py-patched: ..................... 227 ns +- 3 ns

Mean +- std dev: [py-default] 196 ns +- 4 ns -> [py-patched] 227 ns +- 3 ns: 1.16x slower (+16%)

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import OrderedDict as odict; od = odict.fromkeys("abcdefghijklmnopqrstuvwxyz")' -- 'od.move_to_end("z")'
py-default: ..................... 74.7 ns +- 0.4 ns
py-patched: ..................... 91.1 ns +- 3.5 ns

Mean +- std dev: [py-default] 74.7 ns +- 0.4 ns -> [py-patched] 91.1 ns +- 3.5 ns: 1.22x slower (+22%)

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import OrderedDict as odict; od1 = odict.fromkeys(range(10000)); od2=odict.fromkeys(range(10000))' -- 'od1==od2'
py-default: ..................... 451 us +- 3 us
py-patched: ..................... 632 us +- 6 us

Mean +- std dev: [py-default] 451 us +- 3 us -> [py-patched] 632 us +- 6 us: 1.40x slower (+40%)

# pros

1000 less lines of code
50% less memory usage
15% faster creation
100% (2x) faster iteration

# cons

Some inconsistency against pure Python implementation
20% slower move_to_end
40% slower comparison

Another idea is making "dict preserves insertion order" as language spec.
There are still some difference between dict and odict: .move_to_end() and __eq__.

But most use cases of odict is just keep insertion order.
For example, parsing config file, json, or csv.
In such cases, people can get all benefits (less memory and faster creation, iteration and deallocation) of dict if it's guaranteed.

What about move_to_end(last=False)?

When no change happens:

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import Ordedict; od = odict.fromkeys("abcdefghijklmnopqrstuvwxyz")' -- 'od.move_to_end("a", 0)'                                                                          
py-default: ..................... 90.6 ns +- 1.0 ns
py-patched: ..................... 107 ns +- 1 ns

Mean +- std dev: [py-default] 90.6 ns +- 1.0 ns -> [py-patched] 107 ns +- 1 ns: 1.18x slower (+18%)

When change happens:

$ ./py-patched -m perf timeit --compare-to `pwd`/py-default -s 'from collections import OrderedDict as odict; od = odict.fromkeys("abcdefghijklmnopqrstuvwxyz")' -- 'od.move_to_end("y", 0); od.move_to_end("z", 0)'
py-default: ..................... 233 ns +- 4 ns
py-patched: ..................... 304 ns +- 2 ns

Mean +- std dev: [py-default] 233 ns +- 4 ns -> [py-patched] 304 ns +- 2 ns: 1.30x slower (+30%)

I'll bring this up at the language sprints. Last year, there was an explicit decision to not go down this path.

Here are a few thoughts for now: It is a big deal to change the API. We try hard not to do that (breaking code for no reason and making it more challenging for people to upgrade their python -- the standard library is intended to be standard rather than highly mutable). It is a big deal to rip-out the pure python version and impose obligations on other implementations. Over time, we've tried to move in the direction of more pure python code rather than less. The pure python code is easier to understand, easier to maintain, generally less buggy, and is more portable. People currently using OrderedDict are choosing it specifically because they want the ordering behavior. That is currently implemented in an algorithmically correct way that preserves the big-oh behavior in the face of deletions and updates. In contrast, the regular dict only happens to be ordered and internally is achieving order by maintaining a sequence of consecutive pointers. This doesn't have the same performance characteristics and would be a step backwards for some use cases. Lastly, if the ordering of regular dicts becomes guaranteed, then collections.OrderedDict() will mostly become irrelevant so there is no need to change it all.

For now, this proposal is on hold because 1) it isn't clear that it should be done, 2) it needs a lot of serious discussion before proceeding, 3) it may be premature while the status of the regular dict is still in flux.

For now, this proposal is on hold because

it isn't clear that it should be done,

it needs a lot of serious discussion before proceeding,

it may be premature while the status of the regular dict
is still in flux.

+1

When writing the C implementation my biggest constraint was compatibility with the Python implementation, including algorithmic complexity. I'm in favor of making use of dict's new ordering, but it's not urgent and Raymond's concerns should be addressed first (particularly since the collections module is his).

FYI, my approach is not original, but copied from PyPy.

https://bitbucket.org/pypy/pypy/src/3e52029e9a5a677f7de62ef49f36090465cfbf4c/rpython/rtyper/lltypesystem/rordereddict.py?at=default&fileviewer=file-view-default#rordereddict.py-1437:1551

ISTM that what is being proposed is an algorithmically flawed re-implementation of the ordered dictionary. I'm unclear about whether you understand and acknowledge why the doubly-linked list was chosen and what kind of workloads it supports (we didn't choose it because it was either convenient or fun, we chose it because it was an algorithmically correct way of supporting arbitrary deletion, move-to-front, move-to-back, pop-first, and pop-last operations all of which have legitimate use cases).

Side note: part of the goal of the collections module is to provide builtin datatypes alternatives which different performance characteristics. For example, deque() has a list-like API but is there to support efficient appends and pops from both ends while giving up efficient random access (another goal was obtaining more predictable performance by avoiding realloc()).

On a procedural note, it isn't a good practice to go "opinion shopping" as a way of trying to override the recommendations of the current maintainers of the code. That seems like uncomfortable political gamesmanship. Instead of throwing-out all the code, it would be a better to submit implementation improvements that preserve the core design (for example there are faster and more compact ways to store and update the links -- I can help get you started with this if you're interested).

I'm unclear about whether you understand and acknowledge why the doubly-linked list was chosen and what kind of workloads it supports (we didn't choose it because it was either convenient or fun, we chose it because it was an algorithmically correct way of supporting arbitrary deletion, move-to-front, move-to-back, pop-first, and pop-last operations all of which have legitimate use cases).

Arbitrary deletion: New and current implementation has same complexity, because current implementation relying on dict deletion. Only difference is current implementation need to remove item from link list, not only dict.

move-to-front, move-to-back: Current implementation is worst case O(1) and new implementation is amortized O(1), like insertion.

pop-first, pop-last: Current implementation is worst case O(1). New implementation is typical case (when dict is dense) O(1). When mixed with arbitrary deletion operation (dict is sparse), it's become amortized O(1).

Note that mixed insertion and deletion is worst-case O(n) in current implementation.

Original Raymond's design didn't preserve ordering during deletion. It had worst-case O(1) for mixed insertion and deletion. I didn't follow the numerous discussions about compact dict implementation, but at some point it became keeping holes and preserving ordering during deletion. This leads to the need of periodical O(n) reallocation for mixed insertion and deletion. Perhaps the technical reason of this was the couple relation between C implementation of OrderedDict and dict.

Original Raymond's design didn't preserve ordering during deletion.

Original Raymond's pure Python implementation rebuilds index table.
Without it, proving can be very long or infinite loop.
See L89-92 in http://code.activestate.com/recipes/578375/
Strictly speaking, it's worst case is O(n) too.

Raymond's compact dict allocates entry table and index table separately.
I want to allocate them at once, as one memory block.
It makes better cache hit ratio on small dict.

That's why I choose "preserve insertion order" over "compaction".
Since index table and entry table grow at same time, rebuilding
index table and entry table at once makes sense to me.

Anyway, "namespace is ordered" is Python's language spec now.

class C:
    a = 1
    b = 2
    c = 3
    del a

In this case, C's namespace should {"b": 2, "c": 3}, not {"c": 3, "b": 2}.

I would side with Inada in thinking they both give the same amortized complexity, but beyond that, benchmarks are the real answer. There is little value in keeping the current implementation of OrderedDict *if* benchmarks show that it is rarely faster.

On Sun, Sep 10, 2017 at 10:27 PM, Serhiy Storchaka
<report@bugs.python.org> wrote:

Note that mixed insertion and deletion is worst-case O(n) in current implementation.

Could you elaborate? Note that every operation of the current
implementation matches the complexity of the Python implementation.

Eric Snow added the comment:

On Sun, Sep 10, 2017 at 10:27 PM, Serhiy Storchaka
<report@bugs.python.org> wrote:
> Note that mixed insertion and deletion is worst-case O(n) in current implementation.

Could you elaborate? Note that every operation of the current
implementation matches the complexity of the Python implementation.

It means rebuilding hash table to clean up dummy entries.
So, even when dict size is not increasing, remove + insert loop has
worst case O(n), amortized O(1) complexity.

I would side with Inada in thinking they both give the same amortized complexity, but beyond that, benchmarks are the real answer. There is little value in keeping the current implementation of OrderedDict *if* benchmarks show that it is rarely faster.

As I wrote in here:
https://bugs.python.org/issue31265#msg300757

PyPy-like ODict implementation is:

1000 less lines of code
50% less memory usage
15% faster creation
100% (2x) faster iteration
20% slower move_to_end
40% slower comparison

Since current implementation is still draft, there are some
potential optimization.

Optimize over allocation ratio for move_to_end. I have not tried to adjust it for nice balance between speed and space.
I used temporary list to comparing keys safely. But it can be avoided like normal iteration.

I'll try them in this or next week.

It means rebuilding hash table to clean up dummy entries.
So, even when dict size is not increasing, remove + insert loop has
worst case O(n), amortized O(1) complexity.

Ah, so it matches the pure Python implementation then.

Dividing the memory consumption by two is quite impressive.

Raymond: Would you mind to explain why you close the issue?

Since normal dict preserves insertion order, OrderedDict usage
will be decreased. So I don't think 2x memory consumption is
big issue.

BTW, functools.lru_cache uses custom doubly-linked list which
is much memory inefficient.
Rewriting it to use OrderedDict will reduce memory usage significantly.

Writing code compatible with Python older than 3.5 (like Python 2.7) requires to use OrderedDict. I expect that very few users will use "dict if sys.version_info >= (3, 6) else OrderedDict" to get an ordered dict.

OrderedDict remains useful when you need the methods added by the OrderedDict type.

Raymond: Would you mind to explain why you close the issue?

On python-dev, Inada suggested he would drop this issue if Guido approved regular dicts having guaranteed order. That occurred and I closed this issue.

The other reasons were listed earlier in this thread and on my python-dev post. Roughly, the OP is making the wrong trade-offs, trying to optimize what regular dicts are already good at. The OrderedDict aspires to be good at other things and to serve as an alternative to regular dicts in situations that aren't favorable to regular dicts.

The OP seems to be infinitely persistent on this subject eventhough I've clearly stated that I do not approve of this going forward. No amount of talking seems to convince him of the merits of doubly linked list. In the LRU case, when the cache is large enough, there will be a high hit rate. With a doubly-linked list, all that is entailed is a single dict lookup for the link and a fast link update (all currently done in C with beautifully clean and efficient code). Without a doubly-linked list, we have to remove an element from the dictionary (leaving a hole), then re-add the element at the end and then periodically run and an O(n) compaction. The current design doesn't have any of that cost.

The current ordered dict could run move_to_end() a billion times in succession and never trigger an O(n) resize or compaction. The OP either doesn't get this or doesn't care about what ordered dicts were actually designed to be good at.

The current design was done on purpose. There were explicitly rejected alternatives. For example, we could have keep a regular dictionary augmented by a list, just appending and periodically compacting. This would have given faster iteration, less memory usage, and a simpler implementation; however, it was explicitly rejected because doubly-linked lists could gracefully handle frequent semi-random deletions, insertions, and moves-to-end points. For example, the compact dict would perform terribly for repeated move to front operations.

When I get time over the holidays, I will build some examples where the proposed patch causes performance to crater. In the mean time, I have other important things to work on (documenting and testing the new dict guarantees, features for 3.7 before the freeze, etc).

Navigation Menu

Repository navigation

Remove doubly-linked list from C OrderedDict #75448

4 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Remove doubly-linked list from C OrderedDict #75448

Description

Activity

methane commented on Aug 23, 2017

methane commented on Aug 23, 2017

rhettinger commented on Aug 23, 2017

serhiy-storchaka commented on Aug 23, 2017

methane commented on Aug 23, 2017

methane commented on Aug 23, 2017

methane commented on Aug 23, 2017

serhiy-storchaka commented on Aug 23, 2017

methane commented on Aug 23, 2017

rhettinger commented on Aug 26, 2017

ericsnowcurrently commented on Sep 4, 2017

methane commented on Sep 5, 2017

4 remaining items

rhettinger commented on Sep 11, 2017

methane commented on Sep 11, 2017

serhiy-storchaka commented on Sep 11, 2017

methane commented on Sep 11, 2017

arigo commented on Sep 11, 2017

ericsnowcurrently commented on Sep 12, 2017

methane commented on Sep 12, 2017

methane commented on Sep 12, 2017

ericsnowcurrently commented on Sep 12, 2017

vstinner commented on Dec 16, 2017

methane commented on Dec 16, 2017

vstinner commented on Dec 16, 2017

rhettinger commented on Dec 16, 2017

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions