{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/14107","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/14107/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/14107/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/14107/events","html_url":"https://github.com/rust-lang/rust/issues/14107","id":33256652,"number":14107,"title":"String searching is slow","user":{"login":"huonw","id":1203825,"avatar_url":"https://avatars.githubusercontent.com/u/1203825?v=3","gravatar_id":"","url":"https://api.github.com/users/huonw","html_url":"https://github.com/huonw","followers_url":"https://api.github.com/users/huonw/followers","following_url":"https://api.github.com/users/huonw/following{/other_user}","gists_url":"https://api.github.com/users/huonw/gists{/gist_id}","starred_url":"https://api.github.com/users/huonw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/huonw/subscriptions","organizations_url":"https://api.github.com/users/huonw/orgs","repos_url":"https://api.github.com/users/huonw/repos","events_url":"https://api.github.com/users/huonw/events{/privacy}","received_events_url":"https://api.github.com/users/huonw/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/rust-lang/rust/labels/A-libs","name":"A-libs","color":"d7e102"},{"url":"https://api.github.com/repos/rust-lang/rust/labels/I-slow","name":"I-slow","color":"e10c02"}],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2014-05-11T07:10:51Z","updated_at":"2015-02-01T18:12:58Z","closed_at":"2014-05-16T23:26:27Z","body":"The current implement of functions like `StrSlice.contains` are naive string searches, not using a more intelligent algorithm like Boyer-Moore (with a comment referring one to https://github.com/mozilla/rust/pull/1932).\r\n\r\nUnfortunately that means we're trounced when performing operations like that. e.g.\r\n\r\n```rust\r\n// contains_string.rs\r\nextern crate test;\r\n\r\nfn main() {\r\n    let haystack = std::io::stdin().read_to_str().unwrap();\r\n\r\n    let needle = \"Anything whatsoever related to the Rust programming language: an open-source systems programming language from Mozilla, emphasizing safety, concurrency, and speed.\";\r\n\r\n    println!(\"{} {}\", haystack.len(), needle.len());\r\n    for _ in range(0, 1000) {\r\n        test::black_box(haystack.contains(needle))\r\n    }\r\n}\r\n```\r\n\r\n```c\r\n// contains_string.c\r\n#include<string.h>\r\n#include<stdio.h>\r\n#include<unistd.h>\r\n#include<stdlib.h>\r\n\r\n// 16MB\r\n#define N (1 << 24)\r\n\r\nint main() {\r\n    char * haystack = calloc(N, 1);\r\n\r\n    read(0, haystack, N - 1);\r\n\r\n    const char * needle = \"Anything whatsoever related to the Rust programming language: an open-source systems programming language from Mozilla, emphasizing safety, concurrency, and speed.\";\r\n\r\n    printf(\"%d %d\", strlen(haystack), strlen(needle));\r\n    int count = 0;\r\n    for (int i = 0; i < 1000; i ++) {\r\n        haystack[N - 1] = 0;\r\n        count += strstr(haystack, needle) == NULL;\r\n    }\r\n\r\n    return count;\r\n}\r\n```\r\n```python\r\n// contains_string.py\r\nimport sys\r\n\r\nhaystack = sys.stdin.read()\r\nneedle = \"Anything whatsoever related to the Rust programming language: an open-source systems programming language from Mozilla, emphasizing safety, concurrency, and speed.\"\r\n\r\nprint(len(haystack), len(needle))\r\nfor _ in range(0, 1000):\r\n    needle in haystack\r\n```\r\n\r\n```\r\n$ wget http://www.gutenberg.org/cache/epub/1342/pg1342.txt # pride and prejudice (700 kb)\r\n[...snip...]\r\n$ rustc -O contains_string.rs\r\n\r\n$ gcc -O contains_string.c -o contains_string_c -std=gnu11\r\n\r\n$ time ./contains_string < pg1342.txt \r\n717569 163\r\n\r\nreal    0m1.041s\r\nuser    0m1.036s\r\nsys     0m0.000s\r\n\r\n$ time ./contains_string_c < pg1342.txt \r\n717569 163\r\nreal    0m0.064s\r\nuser    0m0.056s\r\nsys     0m0.004s\r\n\r\n$ time python ./contains_string.py < pg1342.txt \r\n(717569, 163)\r\n\r\nreal    0m0.155s\r\nuser    0m0.152s\r\nsys     0m0.000s\r\n```\r\n\r\n### General notes:\r\n\r\n- glibc's `strstr`: [strstr.c](https://github.com/lattera/glibc/blob/master/string/strstr.c) and [str-two-way.h](https://github.com/lattera/glibc/blob/master/string/str-two-way.h)\r\n- A cursory search found [this article](http://volnitsky.com/project/str_search/) which might be interesting to experiment with.\r\n- [This](https://github.com/RaphaelJ/fast_strstr/) came up on [reddit (discussion)](http://www.reddit.com/r/programming/comments/257u0n/a_fast_and_simple_substring_search_algorithm/)"},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/72376068","html_url":"https://github.com/rust-lang/rust/issues/14107#issuecomment-72376068","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/14107","id":72376068,"user":{"login":"mahkoh","id":1882250,"avatar_url":"https://avatars.githubusercontent.com/u/1882250?v=3","gravatar_id":"","url":"https://api.github.com/users/mahkoh","html_url":"https://github.com/mahkoh","followers_url":"https://api.github.com/users/mahkoh/followers","following_url":"https://api.github.com/users/mahkoh/following{/other_user}","gists_url":"https://api.github.com/users/mahkoh/gists{/gist_id}","starred_url":"https://api.github.com/users/mahkoh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mahkoh/subscriptions","organizations_url":"https://api.github.com/users/mahkoh/orgs","repos_url":"https://api.github.com/users/mahkoh/repos","events_url":"https://api.github.com/users/mahkoh/events{/privacy}","received_events_url":"https://api.github.com/users/mahkoh/received_events","type":"User","site_admin":false},"created_at":"2015-02-01T18:12:58Z","updated_at":"2015-02-01T18:12:58Z","body":"```\r\n~/dragons/strstr$ /usr/bin/time -p ./rust < pg1342.txt\r\nreal 26.85\r\nuser 26.79\r\nsys 0.00\r\n~/dragons/strstr$ /usr/bin/time -p ./c < pg1342.txt    \r\nreal 0.83\r\nuser 0.83\r\nsys 0.00\r\n```\r\nThis is for the case where the needle is a single character. In the case above the rust version is as fast or faster than the C version.\r\n```c\r\n#include<string.h>\r\n#include<unistd.h>\r\n\r\nint main(void) {\r\n    static char haystack[1024 * 1024];\r\n    read(0, haystack, sizeof(haystack) - 1);\r\n\r\n    const char *needle = \"_\";\r\n\r\n    for (size_t i = 0; i < 10000000; i++) {\r\n        size_t j = (size_t)strstr(haystack, needle);\r\n\tasm volatile(\"\" : : \"r\"(j), \"r\"(&needle) : \"memory\");\r\n    }\r\n}\r\n```\r\n```rust\r\n#![feature(core, test, io)]\r\n\r\nextern crate test;\r\n\r\nfn main() {\r\n    let haystack = std::old_io::stdin().read_to_string().unwrap();\r\n\r\n    let mut needle = \"_\";\r\n\r\n    for _ in range(0, 10000000) {\r\n        test::black_box(&mut needle);\r\n        test::black_box(haystack.contains(needle));\r\n    }\r\n}\r\n```\r\nMaybe there is a bug in the case for short needles."}}