{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/7017","repository_url":"https://api.github.com/repos/dotnet/coreclr","labels_url":"https://api.github.com/repos/dotnet/coreclr/issues/7017/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/coreclr/issues/7017/comments","events_url":"https://api.github.com/repos/dotnet/coreclr/issues/7017/events","html_url":"https://github.com/dotnet/coreclr/issues/7017","id":174414385,"number":7017,"title":"Consider doing \"naive\" search in IndexOfAny if string's length is under a certain threshold","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":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2016-09-01T01:09:15Z","updated_at":"2016-12-01T01:21:15Z","closed_at":null,"body":"`IndexOfAny` currently uses a trick where it initializes a bitmap to represent if a character is probably in the array. This makes checking whether a character is represented by the bitmap O(1) since it's just a couple of bit operations, however initializing the map is quite expensive since it's O(n) and these bit operations have to be done for every character of the array. This means that in some cases, the \"naive\" approach where we make a pass through the array for every character can be faster for small strings (i.e. if `anyOf.Length == 2`, the threshold seems to be at about 9).\n\nWe should consider applying the following optimizations:\n- Checking if the string's length is below a certain threshold depending on the length of `anyOf`, and if so, use the \"naive\" approach.\n  - This could be implemented as a lookup table, i.e. `static int32_t thresholds[] = { 9, 7, ... }` for minimal overhead.\n- Checking if `anyOf.Length == 1` and if so `return IndexOf(anyOf[0])`\n- Checking if `this.Length == 1` and if so `return Array.IndexOf(anyOf, this[0])`\n- Additionally if `anyOf.Length == 2` and the difference between the two characters is a power of 2, we may be able to apply [this optimization](https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Char.cs#L233-L234) where instead of searching the array or initializing the bitmap, we simply OR each char with `anyOf[0] ^ anyOf[1]` (which will have exactly one bit set) and check if it's equal to `anyOf[0] | anyOf[1]` (which will be one of the 2 elements).\n  - The drawback of this, of course, is that it would only apply to arrays of length 2.\n\nRelated issues:\n- dotnet/corefx#11293\n- dotnet/corefx#11282\n"},"comment":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/comments/264050333","html_url":"https://github.com/dotnet/coreclr/issues/7017#issuecomment-264050333","issue_url":"https://api.github.com/repos/dotnet/coreclr/issues/7017","id":264050333,"user":{"login":"benaadams","id":1142958,"avatar_url":"https://avatars.githubusercontent.com/u/1142958?v=3","gravatar_id":"","url":"https://api.github.com/users/benaadams","html_url":"https://github.com/benaadams","followers_url":"https://api.github.com/users/benaadams/followers","following_url":"https://api.github.com/users/benaadams/following{/other_user}","gists_url":"https://api.github.com/users/benaadams/gists{/gist_id}","starred_url":"https://api.github.com/users/benaadams/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benaadams/subscriptions","organizations_url":"https://api.github.com/users/benaadams/orgs","repos_url":"https://api.github.com/users/benaadams/repos","events_url":"https://api.github.com/users/benaadams/events{/privacy}","received_events_url":"https://api.github.com/users/benaadams/received_events","type":"User","site_admin":false},"created_at":"2016-12-01T01:21:15Z","updated_at":"2016-12-01T01:21:15Z","body":"Another example, removed IndexOfAny from MVC as it was taking a significant portion of the runtime https://github.com/aspnet/Mvc/issues/5362"}}
{"actor":{"display_login":"benaadams"}}