Docs for SwissDict in wrong order, and questions about it

Hi @eulerkochy,

https://github.com/JuliaLang/julia/pull/38167/commits/3f5f9dbf65ed9ec27fe885a675261d5e7873832f

[I can fix that here too.]

When I realized SwissDict is actually ordered, I decided to use it! It seems like an awesome design, I watched the Google video.

Then when I saw the doc issue, it got me thinking, is it for sure an ordered container (not by accident, or is until it isn't for some reason...)? The docs here doesn't say, and for the C++ implementation, I've not tracked it down. I assume you just copy pasted some doc from Dict maybe and didn't change the order. And the C++ is also ordered, not something you added to the design, i.e. I assume you're trying to closely follow it?

I'm copying your implementation to Base, then I saw:

https://github.com/JuliaCollections/DataStructures.jl/pull/634

As of now, the benchmarks aren't favorable.

The little benchmarking I did, using your code, it seemed fast/er, so is that an outdated statement? And should the code at least work? What's your confidence level? At first I was getting OrderedDict into Base, as it's been used for a long time, but I actually found a bug (for recursive Dict, that seem ok for your SwissDict).

Mostly I do not care about the speed, unless it's awful, rather the ordered guarantee (and bug free...).

I did see for your other dict:
https://nextjournal.com/eulerkochy/ordered-dictionary-an-alternative-approach

To guarantee the maintenance of order, we have to compromise on time complexity of deletion.

Is that a statement only about that implementation? If I recall you can keep the same time-complexity for all operations going ordered. Maybe I misremember, or maybe there's a trade-off, and you do intentionally go for worse time-complexity for some less important/rarely used operations, to get performance on the more important ones? Do you know for SwissDict?

Start by reviewing the SwissDict documentation and the linked JuliaLang pull-request commit. Compare its ordering claims and implementation with the questions raised about DataStructures.jl pull request 634 and the linked ordered-dictionary article. Done would require a defined documentation change and resolved answers about ordering, performance, and complexity.