{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/9947","repository_url":"https://api.github.com/repos/dotnet/corefx","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/9947/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/9947/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/9947/events","html_url":"https://github.com/dotnet/corefx/pull/9947","id":164716880,"number":9947,"title":"Avoid repeated virtual method calls in Stack.Contains","user":{"login":"jamesqo","id":9159214,"avatar_url":"https://avatars.githubusercontent.com/u/9159214?v=3","gravatar_id":"","url":"https://api.github.com/users/jamesqo","html_url":"https://github.com/jamesqo","followers_url":"https://api.github.com/users/jamesqo/followers","following_url":"https://api.github.com/users/jamesqo/following{/other_user}","gists_url":"https://api.github.com/users/jamesqo/gists{/gist_id}","starred_url":"https://api.github.com/users/jamesqo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jamesqo/subscriptions","organizations_url":"https://api.github.com/users/jamesqo/orgs","repos_url":"https://api.github.com/users/jamesqo/repos","events_url":"https://api.github.com/users/jamesqo/events{/privacy}","received_events_url":"https://api.github.com/users/jamesqo/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dotnet/corefx/labels/cla-already-signed","name":"cla-already-signed","color":"009800"},{"url":"https://api.github.com/repos/dotnet/corefx/labels/netfx-port-consider","name":"netfx-port-consider","color":"5319e7"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":14,"created_at":"2016-07-10T14:00:27Z","updated_at":"2016-09-29T03:09:29Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/dotnet/corefx/pulls/9947","html_url":"https://github.com/dotnet/corefx/pull/9947","diff_url":"https://github.com/dotnet/corefx/pull/9947.diff","patch_url":"https://github.com/dotnet/corefx/pull/9947.patch"},"body":"Currently the implementation of `Stack.Contains` calls `EqualityComparer.Default.Equals` in a loop, meaning that if a stack is N items in size, it will make N virtual method calls to `Equals`. A better way of doing this is to call `Array.LastIndexOf` on the stack's backing array. Internally `LastIndexOf` calls the internal virtual method [`EqualityComparer.LastIndexOf`](https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Array.cs#L1532), which is specialized for all the default comparer types so instead of making N virtual calls we only make 1 (to `LastIndexOf`).\r\n\r\n### Performance results\r\n\r\n[old](https://gist.github.com/jamesqo/fbc16cc00105c28a0fa8b63441575969) / [new](https://gist.github.com/jamesqo/77f09c16797d23f934d65b19aa114aca) / [test source code](https://gist.github.com/jamesqo/b4c5e471ff840ef82b9f2ec73c6957a6)\r\n\r\nThere is a slowdown if the element is found at the 1st or 2nd position in the stack, presumably due to the overhead of argument validation from `LastIndexOf` and the fact that we only save 0/1 virtual method calls at those positions. However, by the 3rd position the timings are about the same; by the 10th position there is about a 2x speedup, and in an extreme case (1000th position) the speedup is about 4x.\r\n\r\nTest coverage has already been added as part of #8876\r\n\r\ncc @ianhays @stephentoub @omariom "},"comment":{"url":"https://api.github.com/repos/dotnet/corefx/issues/comments/250359728","html_url":"https://github.com/dotnet/corefx/pull/9947#issuecomment-250359728","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/9947","id":250359728,"user":{"login":"jamesqo","id":9159214,"avatar_url":"https://avatars.githubusercontent.com/u/9159214?v=3","gravatar_id":"","url":"https://api.github.com/users/jamesqo","html_url":"https://github.com/jamesqo","followers_url":"https://api.github.com/users/jamesqo/followers","following_url":"https://api.github.com/users/jamesqo/following{/other_user}","gists_url":"https://api.github.com/users/jamesqo/gists{/gist_id}","starred_url":"https://api.github.com/users/jamesqo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jamesqo/subscriptions","organizations_url":"https://api.github.com/users/jamesqo/orgs","repos_url":"https://api.github.com/users/jamesqo/repos","events_url":"https://api.github.com/users/jamesqo/events{/privacy}","received_events_url":"https://api.github.com/users/jamesqo/received_events","type":"User","site_admin":false},"created_at":"2016-09-29T03:09:29Z","updated_at":"2016-09-29T03:09:29Z","body":"Test Innerloop CentOS7.1 Debug Build and Test"}}
{"actor":{"display_login":"jamesqo"}}