{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/6434","repository_url":"https://api.github.com/repos/dotnet/coreclr","labels_url":"https://api.github.com/repos/dotnet/coreclr/issues/6434/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/coreclr/issues/6434/comments","events_url":"https://api.github.com/repos/dotnet/coreclr/issues/6434/events","html_url":"https://github.com/dotnet/coreclr/pull/6434","id":167196042,"number":6434,"title":"Improve performance of string.IndexOf for large strings on 64-bit","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":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2016-07-23T18:10:35Z","updated_at":"2016-07-25T01:49:07Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/dotnet/coreclr/pulls/6434","html_url":"https://github.com/dotnet/coreclr/pull/6434","diff_url":"https://github.com/dotnet/coreclr/pull/6434.diff","patch_url":"https://github.com/dotnet/coreclr/pull/6434.patch"},"body":"## Summary\r\n\r\nThis pull request improves the performance of the char-based `string.IndexOf` by about 30% for large strings.\r\n\r\n## Description\r\n\r\nRight now, the current implementation of `IndexOf` checks each char in the string individually for `value`. While its performance isn't too bad since it's loop unrolled and (I'm asumming) the branch predictor helps out for larger strings, it could be improved.\r\n\r\nOn 64-bit, I've changed the function to use an approach where instead it reads in one word at a time from the string, and uses a trick to determine if any of the individual 4 chars in it are likely to contain value. If it does, it checks each individual char for value; otherwise, it continues the loop.\r\n\r\n### How it works\r\n\r\n1. We first align the pointer on an 8-byte boundary by calculating the number of bytes left until the next aligned address, aka `alignment`. We then divide this by 2, since we're counting by chars and not bytes (and `char*` obtained from strings will always have an even address, so the number of bytes to the next aligned address should be even, too).\r\n\r\n  - Before aligning, we calculate whether `count` is enough for aligning the pointer + at least one iteration of the loop. If not, we jump straight to the fallback loop where we check one char at a time.\r\n\r\n  - We then align the pointer, checking each char at a time for value until we do; since we know that `pAlign` is less than `pEnd` due to the earlier calculation, we don't need to check `pCh < pEnd`.\r\n\r\n2. We then go into the main loop, where we process 12 chars at a time. What we do here is create a mask out of value repeated 4x into a word; for example if someone passes in `\\u1234` then we want to create `0x1234123412341234`.\r\n\r\n  - We then read a word at a time from the target string and xor it with this mask, which is basically equivalent to xoring every individual char in the word with `0x1234`. If there is a `0x1234` in the string, it will be zeroed out.\r\n\r\n  - Then, the same trick as #6125 is used to check if a zero is present in the xored string, by adding 0x7fff to each of the chars and checking if any of the high bits are unset. If one of them is, we check each individual char in the word for value. If we find it, we return the index.\r\n\r\n    - It's possible for this algorithm to misfire if there's a char >= 0x8000 in the string (besides value | 0x8000, which will yield 0x8000 when xored); in that case, we simply skip the word we just processed and continue the loop if there's enough space left.\r\n\r\n3. When the number of chars left goes below the number of chars we can process in the loop (12 in this case), we leave the loop and fallback to processing individual chars.\r\n\r\nIt's also helpful to read the comments, as I've explained everything there as well.\r\n\r\n### Notes\r\n\r\n  - If the char we need to find is >= 0x8000, this new algorithm won't work very nicely; assuming a string of ASCII chars, xoring with value would yield something with its high bit set, and adding 0x7fff (unless it's value & ~0x8000) would yield something with its high bit *not* set, and then we would be jumping to `MaybeReturn` for basically *every iteration* of the loop. This is more of a concern than if the string itself contains chars >= 0x8000, since that would only cause a hiccup for one iteration of the loop. (Also, people might use it to check if a string contains invalid chars, e.g. `IndexOf('\\uffff') != -1`.) So I fell back to the old algorithm if the char has its high bit set.\r\n\r\n  - I had to keep the old implementation for x86 as well; using `uint` instead of `ulong` and even unrolling turned out to have much slower results than the old implementation on 32-bit.\r\n\r\n  - I initially loop-unrolled by 8 chars (`Chunk = 8`) due to code size concerns (each check does a xor/add/or/cmp/jne and some other stuff), but unrolling more aggressively to 12 chars at-a-time seemed to yield better performance results (by about 1/16 for larger strings), so I went with that.\r\n\r\n    - There appears to be two unnecessary `mov r11, 0x7FFF7FFF7FFF7FFF` in the generated assembly (see below) which are taking up quite a bit of code space inside the loop (probably hurting performance). I don't know if there's a way to tell the JIT to remove them, or I should just wait for the JIT to become better and eliminate these.\r\n\r\n  - I also saved on writes to `count` by pre-adding it to `pCh` and comparing `pCh` to that per-iteration of the loop, rather than checking how large `count` was. This saves 1 write per iteration of the loop, which adds an additional 1/15 speedup for larger strings. (I also applied this for the fallback loop.)\r\n\r\n### Performance results\r\n\r\nPerformance results are in [this Gist](https://gist.github.com/jamesqo/df6ab15c3e23d6c3e2bbd68c8f9ce278), including the asm/test source code and results.\r\n\r\n  - There is a negligible slowdown for strings of lengths 3/7.\r\n\r\n  - There are significant slowdowns for lengths 8-16, especially with length 14 (where the old loop runs thrice and then falls back, and the new loop runs once). However, I'm assuming this is OK since larger strings are more likely to be the bottleneck in an app (otherwise we should just replace all of the code in `String` with naive loops that check one char at a time, since that performs better for smaller strings, right?)\r\n\r\n  - The slowdown gets smaller by length 32- it's around 8%.\r\n\r\n  - By the 64th position, the new loop is starting to beat the old one by about 7%.\r\n\r\n  - **At the 128th and above positions, the new loop is running in about 65-75% the time of the old one.**\r\n\r\n  - When 0x8000 is passed in, where we fall back to the old implementation, the new results are still slightly faster; this is presumably due to cfd49d7 so we only make one write per iteration of the loop.\r\n\r\n  - When the string itself has lots of 0x8000s, the new loop is of course much slower than the old one (since we have to do constant jumping around and end up with a lot of misfires).\r\n\r\nEverything passes the CoreFX test suite; more tests are coming soon to cover the codepaths introduced in this PR. (will post here once that's merged)\r\n\r\nPlease let me know if there's anyway the performance could be improved. I did some fine tuning for the assembly in some of the commits, but there may still be more opportunities for optimization.\r\n\r\ncc: @jkotas @bbowyersmyth @GSPP @stephentoub @omariom"},"comment":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/comments/234819301","html_url":"https://github.com/dotnet/coreclr/pull/6434#issuecomment-234819301","issue_url":"https://api.github.com/repos/dotnet/coreclr/issues/6434","id":234819301,"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-25T01:49:06Z","updated_at":"2016-07-25T01:49:06Z","body":"@mikedn You're probably right. I'm considering doing some kind of thing where we use the regular (unrolled) loop written by @bbowyersmyth for X characters, and if we don't find it by then (and there's still enough room for 3 iterations of the optimized loop) then the optimization kicks in. That way the overhead of aligning everything/calculating the mask/etc. will be limited to larger strings, and only if we don't find it first using the smaller loop (at which point the overhead will be negligible)."}}
{"actor":{"display_login":"jamesqo"}}