{"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":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":54,"created_at":"2015-02-07T22:13:58Z","updated_at":"2015-06-01T14:44:48Z","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/107539803","html_url":"https://github.com/JuliaLang/julia/pull/10116#issuecomment-107539803","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10116","id":107539803,"user":{"login":"StefanKarpinski","id":153596,"avatar_url":"https://avatars.githubusercontent.com/u/153596?v=3","gravatar_id":"","url":"https://api.github.com/users/StefanKarpinski","html_url":"https://github.com/StefanKarpinski","followers_url":"https://api.github.com/users/StefanKarpinski/followers","following_url":"https://api.github.com/users/StefanKarpinski/following{/other_user}","gists_url":"https://api.github.com/users/StefanKarpinski/gists{/gist_id}","starred_url":"https://api.github.com/users/StefanKarpinski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/StefanKarpinski/subscriptions","organizations_url":"https://api.github.com/users/StefanKarpinski/orgs","repos_url":"https://api.github.com/users/StefanKarpinski/repos","events_url":"https://api.github.com/users/StefanKarpinski/events{/privacy}","received_events_url":"https://api.github.com/users/StefanKarpinski/received_events","type":"User","site_admin":false},"created_at":"2015-06-01T14:44:48Z","updated_at":"2015-06-01T14:44:48Z","body":"The reason the Set argument is compelling is that it is natural to construct Set from Dict, but it's pretty clear that one wants two Sets to be considered equal if and only if they contain the same elements.\r\n\r\nOn the other hand, maybe it's good to have Dict and Set provide more different basic pieces of functionality – it's a little suspicious when one thing in the standard library is a very thin wrapper around something else in the standard library."}}