Add ODict to Base for OrderedDict

[PallHaraldsson]

"unordered Dict iteration is a bug waiting to happen. Your PR would fix that."

My answer: https://discourse.julialang.org/t/replacement-for-dict-is-anyone-using-isslotfilled/48810/16?u=palli

I started that thread, asking if people would like Dict changed to ordered, but I realize by now that it's probably better to add the non-default ODict, so people can choose that, easily. At some point, e.g. Julia 2.0 we could change Dict to refer to ODict.

I neglected to mention the PR #38145, and one of the answers were:

"Generally, if you want something changed in Base and you want concrete feedback, it is best to make a PR"

elsewhere, people called for discussion. My PR already adds OrderedDict, and it works, it's just test failing because I'm replacing Dict, and with rather adding it as ODict, all the problems would go away.

@andyferris, I DO have some concerns, I thought I could choose any of the implementations, of ordered (not sorted) dicts available, but there's also this one I haven't looked at too closely (would it be better/ready?):

andyferris/Dictionaries.jl#31 (comment)

Midway through that I realised ordered dictionaries were a massive usability improvement, so that got incorporated here also.

The concrete implementation of Base.Dict is almost orthogonal in a sense - so long as we can merge it in a non-breaking way, it could enter Base at a different time (and Julia 1.6 makes a lot of sense to me, also).

Python added ordered dict to its standard library (despite "existing Python ordered-dict implementations") in 2008, with in rationale "PHP and Ruby 1.9 guarantee a certain order on iteration":

https://www.python.org/dev/peps/pep-0372/

Code ported from other programming languages such as PHP often depends on an ordered dict. Having an implementation of an ordering-preserving dictionary in the standard library could ease the transition and improve the compatibility of different libraries. [..]
Comparing two ordered dictionaries implies that the test will be order-sensitive [..] When ordered dicts are compared with other Mappings, their order insensitive comparison is used. This allows ordered dictionaries to be substituted anywhere regular dictionaries are used. [..]
Keeping a sorted list of keys is fast for all operations except delitem() which becomes an O(n) exercise. This data structure leads to very simple code and little wasted space.

Then for Python 3.7, in 2017-2018 the default dict became ordered by default:
https://mail.python.org/pipermail/python-dev/2017-December/151283.html

• 50% less memory usage
• 15% faster creation
• 100% (2x) faster iteration
• 20% slower move_to_end
• 40% slower comparison

with changed implementation:

Remove doubly-linked list from C OrderedDict
https://bugs.python.org/issue31265#msg301942

[JeffBezanson]

better to add the non-default ODict, so people can choose that, easily

There is nothing difficult about using OrderedDict from a package.

[andyferris]

@PallHaraldsson I think the value would be in modifying the behaviour in Base to be better by default rather than in providing more functionality or exporting more types from Base (which despite being currently quite large is intended to be minimal).

So, one possible outcome would be to reverse the roles of Base.Dict/Base.Set with OrderedCollections.jl and instead have ordered containers in Julia Base and unordered ones in a new UnorderedCollections.jl package (if unordered ones are somehow desirable for certain applications). Anyway that’s how I see it.

[KristofferC]

Discussion about making the default dict ordered can be had in #34265. It's, however, not useful to just copy-paste a Dict implementation from a package into Base as a new date structure.