{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/6212","repository_url":"https://api.github.com/repos/dotnet/coreclr","labels_url":"https://api.github.com/repos/dotnet/coreclr/issues/6212/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/coreclr/issues/6212/comments","events_url":"https://api.github.com/repos/dotnet/coreclr/issues/6212/events","html_url":"https://github.com/dotnet/coreclr/pull/6212","id":164739169,"number":6212,"title":"Avoid repeated virtual method calls in List.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/coreclr/labels/cla-already-signed","name":"cla-already-signed","color":"009800"}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":6,"created_at":"2016-07-10T23:13:37Z","updated_at":"2016-07-11T13:32:28Z","closed_at":"2016-07-11T12:30:13Z","pull_request":{"url":"https://api.github.com/repos/dotnet/coreclr/pulls/6212","html_url":"https://github.com/dotnet/coreclr/pull/6212","diff_url":"https://github.com/dotnet/coreclr/pull/6212.diff","patch_url":"https://github.com/dotnet/coreclr/pull/6212.patch"},"body":"Right now `List.Contains` calls `EqualityComparer.Default.Equals` in a loop to check if the list contains the item, which will result in N virtual method calls to `Equals` if there are N items in the list. A more efficient way to do this is to call `Array.IndexOf` and check if it's -1, since internally that calls `EqualityComparer.IndexOf`, which is an internal virtual method in `EqualityComparer` specialized for all the default comparers. This way, we only make 1 virtual call (to `EqualityComparer.IndexOf`) instead of N.\r\n\r\nSimilar to: dotnet/corefx#9947, which applies this optimization for Stack.\r\n\r\n### Performance results\r\n\r\n[old](https://gist.github.com/jamesqo/5583d7ccf1a70e254ec2e879f1fce75e) / [new](https://gist.github.com/jamesqo/f963ec77bd0b46dbe22f4b5ea9dd7d7b) / [test source code](https://gist.github.com/jamesqo/9857aaa8b1e03d7d7c5afa6adea142e2)\r\n\r\nAs with the other PR, if the element is found in the first item of the list the new implementation is slightly slower. If it's found at the 2nd or 3rd position the times are about the same, the new impl is about 1.5x faster for the 10th position, and in extreme cases (or not depending on how big 'typical lists' are) the new implementation can be more than 4x faster.\r\n\r\nI've pre-tested this with CoreFX and everything is passing in `System.Collections.Tests`.\r\n\r\n@jkotas @stephentoub PTAL\r\n\r\n**edit:** Note that this will not result in too big of a performance degradation for null items (e.g. if you do `list.Contains(null)` you won't be making virtual calls in a loop where you hadn't before), since each of the specialized implementations of `IndexOf` for each of the equality comparers [check for null / HasValue](https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs#L154) and still do plain `if (array[i] == null)` if the parameter is null, as opposed to calling `Equals`."},"comment":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/comments/231734895","html_url":"https://github.com/dotnet/coreclr/pull/6212#issuecomment-231734895","issue_url":"https://api.github.com/repos/dotnet/coreclr/issues/6212","id":231734895,"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-07-11T13:32:28Z","updated_at":"2016-07-11T13:32:28Z","body":"Thanks for merging this; I'll submit a pull request to CoreFX later as well to port the changes."}}
{"actor":{"display_login":"jamesqo"}}