https://lemire.me/blog/2022/12/30/quickly-checking-that-a-string-belongs-to-a-small-set/ Skip to content Daniel Lemire's blog Daniel Lemire is a computer science professor at the University of Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering. He is a techno-optimist and a free-speech advocate. Menu and widgets * My home page * My papers * My software Subscribe Join 12,500 subscribers: Email Address [ ] [ ] [Subscribe by email] You can also follow this blog on telegram. You can find me on twitter as @lemire. Search for: [ ] [Search] Support my work! I do not accept any advertisement. However, you can you can sponsor my open-source work on GitHub. Recent Posts * Quickly checking that a string belongs to a small set * Science and Technology links (December 25 2022) * Fast base16 encoding * The size of things in bytes * Implementing 'strlen' using SVE Recent Comments * Daniel Lemire on Quickly checking that a string belongs to a small set * Daniel Lemire on Quickly checking that a string belongs to a small set * JY on Quickly checking that a string belongs to a small set * hexgrid on Quickly checking that a string belongs to a small set * Daniel Lemire on Quickly checking that a string belongs to a small set Pages * A short history of technology * About me * Book recommendations * Cognitive biases * Interviews and talks * My bets * My favorite articles * My favorite quotes * My readers * My sayings * Predictions * Recommended video games * Terms of use * Write good papers Archives Archives [Select Month ] Boring stuff * Log in * Entries feed * Comments feed * WordPress.org Quickly checking that a string belongs to a small set Suppose that I give you a set of reference strings ("ftp", "file", "http", "https", "ws", "wss"). Given a new string, you want to quickly tell whether it is part of this set. You might use a regular expression but it is unlikely to be fast: const std::regex txt_regex("(https)|(http)|(ftp)|(file)|(ws)|(wss)"); // later... bool match = std::regex_match(v.begin(), v.end(), txt_regex); A sensible solution might be to create a set and then to ask whether the string is in the set. In C++, a default set type is the unordered_set thus your code might look as follows: static const std::unordered_set special_set = { "ftp", "file", "http", "https", "ws", "wss"}; bool hash_is_special(std::string_view input) { return special_set.find(input) != special_set.end(); } You might also be more direct about it, and just do several comparisons: bool direct_is_special(std::string_view input) { return (input == "https") || (input == "http") || (input == "ftp") || (input == "file") || (input == "ws") || (input == "wss"); } If you look at how the code gets compiled, you may notice that the compiler is forced to do comparisons and jumps, because it is not allowed to read in the provided string beyond its reported size. You might be able to do slightly better if you can tell your compiler that the string you receive is 'padded' so that you can read eight bytes safely from it. I could not find a very elegant way to do it, but the following code works: static inline uint64_t string_to_uint64(std::string_view view) { uint64_t val; std::memcpy(&val, view.data(), sizeof(uint64_t)); return val; } uint32_t string_to_uint32(const char *data) { uint32_t val; std::memcpy(&val, data, sizeof(uint32_t)); return val; } bool fast_is_special(std::string_view input) { uint64_t inputu = string_to_uint64(input); if ((inputu & 0xffffffffff) == string_to_uint64("https\0\0\0")) { return input.size() == 5; } if ((inputu & 0xffffffff) == string_to_uint64("http\0\0\0\0")) { return input.size() == 4; } if (uint32_t(inputu) == string_to_uint32("file")) { return input.size() == 4; } if ((inputu & 0xffffff) == string_to_uint32("ftp\0")) { return input.size() == 3; } if ((inputu & 0xffffff) == string_to_uint32("wss\0")) { return input.size() == 3; } if ((inputu & 0xffff) == string_to_uint32("ws\0\0")) { return input.size() == 2; } return false; } Though I did not do it, you can extend the comparison so that it is case-insensitive (simply AND the input with the bytes 0xdf instead of the bytes 0xff). You can use a faster approach if you can assume that the input string has been padded with zeros: uint64_t inputu = string_to_uint64(input); uint64_t https = string_to_uint64("https\0\0\0"); uint64_t http = string_to_uint64("http\0\0\0\0"); uint64_t file = string_to_uint64("file\0\0\0\0"); uint64_t ftp = string_to_uint64("ftp\0\0\0\0\0"); uint64_t wss = string_to_uint64("wss\0\0\0\0\0"); uint64_t ws = string_to_uint64("ws\0\0\0\0\0\0"); if((inputu == https) | (inputu == http)) { return true; } return ((inputu == file) | (inputu == ftp) | (inputu == wss) | (inputu == ws)); Observe how I have selected what I believe are the two most common cases (among URL protocols). I am sure that there are faster and more clever alternatives! In any case, how fast are my alternatives? Using GCC 11 on an Intel Ice Lake server, I get the following results: regex 360 ns/string std::unordered_map 19 ns/string direct 16 ns/string fast 2.6 ns/string faster 1.9 ns/string On an Apple M2 with LLVM 12, I get similar (but better) results: regex 450 ns/string std::unordered_map 15 ns/string direct 7 ns/string fast 1.1 ns/string faster 0.8 ns/string Care is needed when optimizing such small functions: whether and how the function gets inlined can be critical to the good performance. The results will depend also on the data source and on the compiler. My source code is available. Published by [2ca999] Daniel Lemire A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire Posted on December 30, 2022December 30, 2022Author Daniel Lemire Categories 16 thoughts on "Quickly checking that a string belongs to a small set" 1. [c20381] Volker Simonis says: December 30, 2022 at 9:02 am Just out of interest, have you tried to measure a regex-based solution as well? Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 5:59 pm In my tests, regex is 100x slower. Of course, results will vary based on the underlying implementation. Reply 2. [335f48] Nathan Myers says: December 30, 2022 at 6:23 pm Seems like a good place for a bloom filter. Presumably the overwhelming majority of words seen don't match, so you would win by rejecting non-matches quickly. Reply 1. [edbd5f] Jens Alfke says: December 30, 2022 at 6:59 pm A Bloom filter will require hashing the string six or seven times with different hash functions. And it has false positives, so you still have to do a real set-membership test if the filter returns true. I didn't see anything in the post stating that matches will be rare, and in the benchmark code 60% of the strings match, so this doesn't seem like a good trade-off. Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 7:07 pm A conventional Bloom filter would be overkill here, but a hashing based technique could work. Reply 2. [d6f827] Wouter Bijlsma says: December 30, 2022 at 12:32 pm The 'direct' example uses bitwise | instead of logical ||, so no short-circuit evaluation? I guess that will affect the timing to 0.5x what you have now (amortised, if the needle is uniformly distributed) Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 7:09 pm The code has both functions. Results are sensitive to the compiler. Reply 3. [d69554] JRL says: December 30, 2022 at 4:19 pm It is a bit unfair to expect the input strings to be padded to 8 or 4 bytes. In practice, the parameter to memcpy should be input.size() instead of sizeof(uint..), but that seems to tank the performance. I played a bit with the example (on godbolt: zd9c9YM8b), and the "fast" implementation was the most stable (similar duration over multiple runs). The branchless implementation is consistently the fastest, and the hash version is the sweet spot between clarity and performance. I also tried a lame implementation of a letter graph, and it seems to be somewhere in between "branchless" and "fast". Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 7:10 pm It is a bit unfair to expect the input strings to be padded to 8 or 4 bytes. For a general-purpose function, I agree, but if it is part of your own system where you control where the strings come from, then I disagree. Requiring padding to your strings is quite doable if you have fine control over your data structures. Reply 4. [096004] Mark Hahn says: December 30, 2022 at 4:41 pm I wonder when perfect hashing becomes the winner. Reply 5. [129147] Xoranth says: December 30, 2022 at 5:02 pm Wojciech Mula has written a note about a similar problem in the past. He found that using a perfect hash function was the fastest way, and that switching character by character was faster than SWAR techniques like the one you mention in this post. I.e. see http://0x80.pl/notesen/2022-01-29-http-verb-parse.html Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 7:11 pm Damn it. Wojciech is always one step ahead of me. (For people reading this, Wojciech is a collaborator of mine.) Reply 6. [f83572] hexgrid says: December 30, 2022 at 7:27 pm This seems like exactly the sort of thing a critbit trie is for. https://github.com/agl/critbit Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 10:37 pm Did you run a benchmark? Reply 7. [b516af] JY says: December 30, 2022 at 8:13 pm > You might be able to do slightly better if you can tell your compiler that the string you receive is 'padded' so that you can read eight bytes safely from it. I could not find a very elegant way to do it There's std::assume in C++23 (https://en.cppreference.com/w/cpp/ language/attributes/assume) but currently the only way is to use the compiler builtin functions, e.g.: https://godbolt.org/z/ xxK939vca I've also taken some liberties at rewriting your approach, but the generate assembly should be similar Reply 1. [2ca999] Daniel Lemire says: December 30, 2022 at 10:42 pm Transcribing your interesting code: #include #include #include #include #include static constexpr std::array protocols = { "https", "http", "file", "ftp", "wss", "ws" }; static constexpr auto string_to_uint64 = [](std::string_view s) constexpr { using CharT = decltype(s)::value_type; static_assert(sizeof(CharT) == 1); std::array bytes{}; const auto copy_size = std::min(s.size(), 8ul); std::copy_n(s.cbegin(), copy_size, bytes.begin()); return std::bit_cast(bytes); }; static constexpr auto protocol_set = [] { std::array ps{}; std::ranges::transform(protocols, ps.begin(), string_to_uint64); return ps; }(); bool is_special(std::string_view s) { __builtin_assume(s.size() == 8ul); const auto as_uint64{ string_to_uint64(s) }; return std::ranges::count(protocol_set, as_uint64); } Reply Leave a Reply Cancel reply Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com. [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment * [ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. Receive Email Notifications? [no, do not subscribe ] [instantly ] Or, you can subscribe without commenting. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] You may subscribe to this blog by email. Post navigation Previous Previous post: Science and Technology links (December 25 2022) Terms of use Proudly powered by WordPress