{"action":"created","issue":{"url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/576","repository_url":"https://api.github.com/repos/aspnet/HttpAbstractions","labels_url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/576/labels{/name}","comments_url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/576/comments","events_url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/576/events","html_url":"https://github.com/aspnet/HttpAbstractions/pull/576","id":137713372,"number":576,"title":"Faster SubMatch implementation","user":{"login":"DavidObando","id":950290,"avatar_url":"https://avatars.githubusercontent.com/u/950290?v=3","gravatar_id":"","url":"https://api.github.com/users/DavidObando","html_url":"https://github.com/DavidObando","followers_url":"https://api.github.com/users/DavidObando/followers","following_url":"https://api.github.com/users/DavidObando/following{/other_user}","gists_url":"https://api.github.com/users/DavidObando/gists{/gist_id}","starred_url":"https://api.github.com/users/DavidObando/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DavidObando/subscriptions","organizations_url":"https://api.github.com/users/DavidObando/orgs","repos_url":"https://api.github.com/users/DavidObando/repos","events_url":"https://api.github.com/users/DavidObando/events{/privacy}","received_events_url":"https://api.github.com/users/DavidObando/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/aspnet/HttpAbstractions/labels/cla-already-signed","name":"cla-already-signed","color":"009800"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2016-03-01T23:00:10Z","updated_at":"2016-03-03T08:01:57Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/aspnet/HttpAbstractions/pulls/576","html_url":"https://github.com/aspnet/HttpAbstractions/pull/576","diff_url":"https://github.com/aspnet/HttpAbstractions/pull/576.diff","patch_url":"https://github.com/aspnet/HttpAbstractions/pull/576.patch"},"body":"SubMatch has been sped up by implementing a modified Boyer–Moore–Horspool algorithm with an average-case complexity of O(N) on random text. Worst case, it behaves similarly to the previous implementation O(MN), where M is the length of the boundary and N is the length of the buffer to operate on.\r\n\r\nMethod SubMatch looks for two things:\r\n\r\n  1. Whether the byte array segment fully contains the boundary, or\r\n  2. Whether the byte array ends with the start of the boundary.\r\n\r\nCase 1 is now a lot faster than the previous implementation. Case 2 remains using the same code as before. The method will do Case 1 until the matchOffset is equal to N-M. It then switches to Case 2, unless a match is found.\r\n\r\nThe code can be further sped up with a full Boyer–Moore implementation, or something more sophisticated. This however can be evaluated in the case that this implementation is insufficiently performant for our main scenarios.\r\n\r\nThis commit resolves issue #575.\r\n\r\nUsing test [MultipartPOST](https://github.com/aspnet/Performance/tree/dev/testapp/MultipartPOST) the work percentage (inclusive %) for method SubMatch under the profiler was:\r\n  * Before this change: 53.4%\r\n  * After this change: 7.6%\r\n\r\n@SajayAntony @Tratcher @pranavkm @davidfowl "},"comment":{"url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/comments/191643358","html_url":"https://github.com/aspnet/HttpAbstractions/pull/576#issuecomment-191643358","issue_url":"https://api.github.com/repos/aspnet/HttpAbstractions/issues/576","id":191643358,"user":{"login":"davidfowl","id":95136,"avatar_url":"https://avatars.githubusercontent.com/u/95136?v=3","gravatar_id":"","url":"https://api.github.com/users/davidfowl","html_url":"https://github.com/davidfowl","followers_url":"https://api.github.com/users/davidfowl/followers","following_url":"https://api.github.com/users/davidfowl/following{/other_user}","gists_url":"https://api.github.com/users/davidfowl/gists{/gist_id}","starred_url":"https://api.github.com/users/davidfowl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidfowl/subscriptions","organizations_url":"https://api.github.com/users/davidfowl/orgs","repos_url":"https://api.github.com/users/davidfowl/repos","events_url":"https://api.github.com/users/davidfowl/events{/privacy}","received_events_url":"https://api.github.com/users/davidfowl/received_events","type":"User","site_admin":false},"created_at":"2016-03-03T08:01:57Z","updated_at":"2016-03-03T08:01:57Z","body":"@DavidObando test cases for each of the cases called out in the algorithm.\r\n\r\n"}}