{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/33392","repository_url":"https://api.github.com/repos/dotnet/corefx","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/33392/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/33392/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/33392/events","html_url":"https://github.com/dotnet/corefx/issues/33392","id":379442828,"node_id":"MDU6SXNzdWUzNzk0NDI4Mjg=","number":33392,"title":"Backport improvements from DictionarySlim to Dictionary","user":{"login":"danmosemsft","id":6385855,"node_id":"MDQ6VXNlcjYzODU4NTU=","avatar_url":"https://avatars3.githubusercontent.com/u/6385855?v=4","gravatar_id":"","url":"https://api.github.com/users/danmosemsft","html_url":"https://github.com/danmosemsft","followers_url":"https://api.github.com/users/danmosemsft/followers","following_url":"https://api.github.com/users/danmosemsft/following{/other_user}","gists_url":"https://api.github.com/users/danmosemsft/gists{/gist_id}","starred_url":"https://api.github.com/users/danmosemsft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danmosemsft/subscriptions","organizations_url":"https://api.github.com/users/danmosemsft/orgs","repos_url":"https://api.github.com/users/danmosemsft/repos","events_url":"https://api.github.com/users/danmosemsft/events{/privacy}","received_events_url":"https://api.github.com/users/danmosemsft/received_events","type":"User","site_admin":false},"labels":[{"id":154923328,"node_id":"MDU6TGFiZWwxNTQ5MjMzMjg=","url":"https://api.github.com/repos/dotnet/corefx/labels/area-System.Collections","name":"area-System.Collections","color":"d4c5f9","default":false},{"id":145399957,"node_id":"MDU6TGFiZWwxNDUzOTk5NTc=","url":"https://api.github.com/repos/dotnet/corefx/labels/enhancement","name":"enhancement","color":"207de5","default":true},{"id":153500238,"node_id":"MDU6TGFiZWwxNTM1MDAyMzg=","url":"https://api.github.com/repos/dotnet/corefx/labels/tenet-performance","name":"tenet-performance","color":"c2e0c6","default":false}],"state":"open","locked":false,"assignee":{"login":"MarcoRossignoli","id":7894084,"node_id":"MDQ6VXNlcjc4OTQwODQ=","avatar_url":"https://avatars0.githubusercontent.com/u/7894084?v=4","gravatar_id":"","url":"https://api.github.com/users/MarcoRossignoli","html_url":"https://github.com/MarcoRossignoli","followers_url":"https://api.github.com/users/MarcoRossignoli/followers","following_url":"https://api.github.com/users/MarcoRossignoli/following{/other_user}","gists_url":"https://api.github.com/users/MarcoRossignoli/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcoRossignoli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcoRossignoli/subscriptions","organizations_url":"https://api.github.com/users/MarcoRossignoli/orgs","repos_url":"https://api.github.com/users/MarcoRossignoli/repos","events_url":"https://api.github.com/users/MarcoRossignoli/events{/privacy}","received_events_url":"https://api.github.com/users/MarcoRossignoli/received_events","type":"User","site_admin":false},"assignees":[{"login":"MarcoRossignoli","id":7894084,"node_id":"MDQ6VXNlcjc4OTQwODQ=","avatar_url":"https://avatars0.githubusercontent.com/u/7894084?v=4","gravatar_id":"","url":"https://api.github.com/users/MarcoRossignoli","html_url":"https://github.com/MarcoRossignoli","followers_url":"https://api.github.com/users/MarcoRossignoli/followers","following_url":"https://api.github.com/users/MarcoRossignoli/following{/other_user}","gists_url":"https://api.github.com/users/MarcoRossignoli/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcoRossignoli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcoRossignoli/subscriptions","organizations_url":"https://api.github.com/users/MarcoRossignoli/orgs","repos_url":"https://api.github.com/users/MarcoRossignoli/repos","events_url":"https://api.github.com/users/MarcoRossignoli/events{/privacy}","received_events_url":"https://api.github.com/users/MarcoRossignoli/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/dotnet/corefx/milestones/5","html_url":"https://github.com/dotnet/corefx/milestone/5","labels_url":"https://api.github.com/repos/dotnet/corefx/milestones/5/labels","id":1328080,"node_id":"MDk6TWlsZXN0b25lMTMyODA4MA==","number":5,"title":"Future","description":"Milestone tracking issues not triaged to a planned release. Work in this milestone may happen, or may not: it is not committed.","creator":{"login":"joshfree","id":1302850,"node_id":"MDQ6VXNlcjEzMDI4NTA=","avatar_url":"https://avatars1.githubusercontent.com/u/1302850?v=4","gravatar_id":"","url":"https://api.github.com/users/joshfree","html_url":"https://github.com/joshfree","followers_url":"https://api.github.com/users/joshfree/followers","following_url":"https://api.github.com/users/joshfree/following{/other_user}","gists_url":"https://api.github.com/users/joshfree/gists{/gist_id}","starred_url":"https://api.github.com/users/joshfree/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joshfree/subscriptions","organizations_url":"https://api.github.com/users/joshfree/orgs","repos_url":"https://api.github.com/users/joshfree/repos","events_url":"https://api.github.com/users/joshfree/events{/privacy}","received_events_url":"https://api.github.com/users/joshfree/received_events","type":"User","site_admin":false},"open_issues":1966,"closed_issues":415,"state":"open","created_at":"2015-09-29T00:25:45Z","updated_at":"2019-03-26T22:53:09Z","due_on":null,"closed_at":null},"comments":17,"created_at":"2018-11-10T17:36:52Z","updated_at":"2019-03-27T01:49:08Z","closed_at":null,"author_association":"MEMBER","body":"Keeping a list of changes made in [DictionarySlim](https://github.com/dotnet/corefxlab/pull/2458) that could benefit Dictionary\r\n* Instead of ` & 0x7FFFFFFF;` to remove the sign bit on the hash code, use `(uint)` cast and store a uint hashcode, retaining more entropy. To store 'empty' instead of hashcode of -1 use this scheme: \r\n```c#\r\n            // 0-based index of next entry in chain: -1 means end of chain\r\n            // also encodes whether this entry _itself_ is part of the free list by changing sign and subtracting 3,\r\n            // so -2 means end of free list, -3 means index 0 but on free list, -4 means index 1 but on free list, etc.\r\n            public int next;\r\n```\r\n* Eliminate the `_freeCount` field and use `_freeList == -1` as a sentinel instead\r\n* ~~Eliminate `_buckets == null` check on every access, use a dummy 1-element array instead, on which reads fail and adds cause a resize into a real array~~\r\n\r\nSome of these apply to `HashSet<T>` also.\r\n\r\n@AnthonyLloyd @Zhentar"},"comment":{"url":"https://api.github.com/repos/dotnet/corefx/issues/comments/476929961","html_url":"https://github.com/dotnet/corefx/issues/33392#issuecomment-476929961","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/33392","id":476929961,"node_id":"MDEyOklzc3VlQ29tbWVudDQ3NjkyOTk2MQ==","user":{"login":"danmosemsft","id":6385855,"node_id":"MDQ6VXNlcjYzODU4NTU=","avatar_url":"https://avatars3.githubusercontent.com/u/6385855?v=4","gravatar_id":"","url":"https://api.github.com/users/danmosemsft","html_url":"https://github.com/danmosemsft","followers_url":"https://api.github.com/users/danmosemsft/followers","following_url":"https://api.github.com/users/danmosemsft/following{/other_user}","gists_url":"https://api.github.com/users/danmosemsft/gists{/gist_id}","starred_url":"https://api.github.com/users/danmosemsft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danmosemsft/subscriptions","organizations_url":"https://api.github.com/users/danmosemsft/orgs","repos_url":"https://api.github.com/users/danmosemsft/repos","events_url":"https://api.github.com/users/danmosemsft/events{/privacy}","received_events_url":"https://api.github.com/users/danmosemsft/received_events","type":"User","site_admin":false},"created_at":"2019-03-27T01:49:08Z","updated_at":"2019-03-27T01:49:08Z","author_association":"MEMBER","body":"From the PR, which is now just for entropy part, you said:\r\n\r\n>> Eliminate the _freeCount field and use _freeList == -1 as a sentinel instead`\r\n\r\n>and the result are not so great, we remove the local var freeCount but after that we use count as a \"real item count\" and it's no more aligned with entries count. This lead to change every piece of code that iterate throught entries using a local count = _count (to decrement after every \"valid item\" found, next > -1) . Another issue is that DictionarySlim doesn't support \"versioning\" so I had to change also every enumerator to support current dictionary behaviour(support remove during enumeration). We need also to change code for features like Trim(), EnsureCapacity() that slim one doesn't have.\r\n\r\nI spent a little time to absorb this. Resummarizing the problem for myself -- \r\n\r\nPreviously: _count was the “high water mark” in the backing array. Actual count is “_count - _freeCount”. If there are no free (ie _freeCount is 0), adds are inserted after \"_count\". When iterating, walk the array no further than “_count” to avoid wasted time.\r\n\r\nAfter: _count is the actual count of items in the backing array. Actual count is “_count”. If there are no free (ie _freeList == -1), adds are inserted after “_count”. When iterating, keep count of free entries encountered, and walk no further than “_count + free entries encountered. The problem being the added cost of doing this sum.\r\n\r\nFor CopyTo (much the same as enumeration), the code was\r\n```c#\r\n                int count = _dictionary._count;\r\n                for (int i = 0; i < count; i++)\r\n                {\r\n                    if (entries[i].hashCode >= 0) array[index++] = entries[i].key;\r\n                 }\r\n```\r\n\r\nAfter, it was\r\n```c#\r\n                int count = _dictionary._count;\r\n                for (int i = 0; count > 0 && i < entries.Length; i++)\r\n                {\r\n                    // entries < -1 are in freelist\r\n                    if (entries[i].next >= -1)\r\n                    {\r\n                        array[index++] = entries[i].key;\r\n                        count--;\r\n                    }\r\n                }\r\n```\r\nYou had to include the ` && i < entries.Length` even though you could not normally reach the end unless count is 0, because a remove could happen during iteration, which would mean count could be reduced. Although it could be written this way safely, it's still more work:\r\n```c#\r\n                int count = 0;\r\n                for (int i = 0; count < _dictionary._count; i++)\r\n                {\r\n                    // entries < -1 are in freelist\r\n                    if (entries[i].next >= -1)\r\n                    {\r\n                        array[index++] = entries[i].key;\r\n                        count++;\r\n                    }\r\n                }\r\n```\r\nAnother approach could be to follow the free list chain first, to get the free count, then the loop is back to the simple comparison with no counter required. But that traversal cost could be arbitrarily large.\r\n\r\nI may think some more about this but it does seem you are right that this will always be less efficient for enumeation.  That is worse than saving a field. Thanks for looking.\r\n"}}
{"actor":{"display_login":"danmosemsft"}}