{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/25483","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/25483/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/25483/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/25483/events","html_url":"https://github.com/rust-lang/rust/issues/25483","id":76983234,"number":25483,"title":"`str::contains` is very slow for substring checks","user":{"login":"netvl","id":280456,"avatar_url":"https://avatars.githubusercontent.com/u/280456?v=3","gravatar_id":"","url":"https://api.github.com/users/netvl","html_url":"https://github.com/netvl","followers_url":"https://api.github.com/users/netvl/followers","following_url":"https://api.github.com/users/netvl/following{/other_user}","gists_url":"https://api.github.com/users/netvl/gists{/gist_id}","starred_url":"https://api.github.com/users/netvl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/netvl/subscriptions","organizations_url":"https://api.github.com/users/netvl/orgs","repos_url":"https://api.github.com/users/netvl/repos","events_url":"https://api.github.com/users/netvl/events{/privacy}","received_events_url":"https://api.github.com/users/netvl/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/rust-lang/rust/labels/I-slow","name":"I-slow","color":"e10c02"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-05-16T08:33:14Z","updated_at":"2015-05-16T13:22:42Z","closed_at":null,"body":"Originally found in [SO question](http://stackoverflow.com/questions/30272751/generate-strings-and-identify-substrings-in-rust).\r\n\r\nThis Rust code\r\n```rust\r\nfn main(){\r\n\r\n    let needle   = (0..100).map(|_| \"b\").collect::<String>();\r\n    let heystack = (0..100_000).map(|_| \"a\").collect::<String>();\r\n\r\n    println!(\"Data ready.\");\r\n\r\n    for _ in 0..1_000_000 {\r\n        if heystack.contains( &needle ) {\r\n            // Stuff...\r\n        }\r\n    }\r\n\r\n}\r\n```\r\nExecutes for up to three minutes on my machine (even with `-C opt-level=3`), while the equivalent Ruby or Python code:\r\n```ruby\r\nneedle   = 'b' * 100\r\nheystack = 'a' * 100_000\r\n\r\nputs 'Data ready.'\r\n\r\n1_000_000.times do\r\n    heystack.include? needle\r\nend\r\n```\r\nfinishes in several seconds. Java variant finishes almost instantly (but that seems to be due to JIT optimizations).\r\n\r\nIt looks like that pattern searching for substrings could be severely optimized."},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/102626497","html_url":"https://github.com/rust-lang/rust/issues/25483#issuecomment-102626497","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/25483","id":102626497,"user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"created_at":"2015-05-16T13:22:42Z","updated_at":"2015-05-16T13:22:42Z","body":"Oh wow, I thought that was something that we had already fixed."}}