{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10116","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10116/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10116/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10116/events","html_url":"https://github.com/JuliaLang/julia/pull/10116","id":56928269,"number":10116,"title":"WIP: try ordered Dict representation","user":{"login":"JeffBezanson","id":744556,"avatar_url":"https://avatars.githubusercontent.com/u/744556?v=3","gravatar_id":"","url":"https://api.github.com/users/JeffBezanson","html_url":"https://github.com/JeffBezanson","followers_url":"https://api.github.com/users/JeffBezanson/followers","following_url":"https://api.github.com/users/JeffBezanson/following{/other_user}","gists_url":"https://api.github.com/users/JeffBezanson/gists{/gist_id}","starred_url":"https://api.github.com/users/JeffBezanson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JeffBezanson/subscriptions","organizations_url":"https://api.github.com/users/JeffBezanson/orgs","repos_url":"https://api.github.com/users/JeffBezanson/repos","events_url":"https://api.github.com/users/JeffBezanson/events{/privacy}","received_events_url":"https://api.github.com/users/JeffBezanson/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/performance","name":"performance","color":"d7e102"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":107,"created_at":"2015-02-07T22:13:58Z","updated_at":"2016-01-02T09:58:15Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/10116","html_url":"https://github.com/JuliaLang/julia/pull/10116","diff_url":"https://github.com/JuliaLang/julia/pull/10116.diff","patch_url":"https://github.com/JuliaLang/julia/pull/10116.patch"},"body":"This implements the representation mentioned in #10092, storing keys and values in dense ordered arrays, with a sparse(r) index vector. There are a couple TODOs in the code. This is expected to be a bit slower for deletion-heavy workloads, but I haven't benchmarked that yet.\r\n\r\nMy benchmark code is at https://gist.github.com/JeffBezanson/ea224aa45e2242ca3ee9 .\r\nI took some benchmarks from past Dict performance issues, and added a couple more. The performance characteristics are interesting. Highlights:\r\n\r\n* Simply iterating over a Dict is 10x faster, as I decided to make `start` squeeze out deleted items first.\r\n* `rehash!` doesn't need to reallocate the keys and values arrays at all in theory, but we might need to in order to fix the problem of finalizers that remove keys during rehashing.\r\n* Seems to be faster for String keys, but unfortunately much slower for Int keys.\r\n\r\nProfiling indicates that a huge amount of insertion time is spent on the line\r\n\r\n```\r\n        elseif si > 0 && isequal(key, keys[si])\r\n```\r\n\r\nMy best guess is that this is because `keys[si]` is random access, where before we iterated through the slots and keys arrays in order. But if pointer indirection is involved anyway (e.g. String keys) we get a significant net speedup."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/168378009","html_url":"https://github.com/JuliaLang/julia/pull/10116#issuecomment-168378009","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10116","id":168378009,"user":{"login":"samoconnor","id":8266283,"avatar_url":"https://avatars.githubusercontent.com/u/8266283?v=3","gravatar_id":"","url":"https://api.github.com/users/samoconnor","html_url":"https://github.com/samoconnor","followers_url":"https://api.github.com/users/samoconnor/followers","following_url":"https://api.github.com/users/samoconnor/following{/other_user}","gists_url":"https://api.github.com/users/samoconnor/gists{/gist_id}","starred_url":"https://api.github.com/users/samoconnor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/samoconnor/subscriptions","organizations_url":"https://api.github.com/users/samoconnor/orgs","repos_url":"https://api.github.com/users/samoconnor/repos","events_url":"https://api.github.com/users/samoconnor/events{/privacy}","received_events_url":"https://api.github.com/users/samoconnor/received_events","type":"User","site_admin":false},"created_at":"2016-01-02T09:58:15Z","updated_at":"2016-01-02T09:58:15Z","body":"bump\r\n\r\nI'd very much like to see `Dict` be ordered by default.\r\n\r\nI don't buy any of the arguments along the lines of \"orderedness is not a dict-like property\".\r\n`Dict` is whatever the API manual says it is.\r\n\r\nPerformance problems can be fixed if they effect real world workloads.\r\n\r\nTcl [made dicts ordered by default in 2007](http://comments.gmane.org/gmane.comp.lang.tcl.core/8063) and it has been a great feature.\r\n\r\nThere are many use cases where insertion order preservation is useful.\r\n\r\nThere are few where it is a problem. Those can always use a `shuffle()` iterator."}}