9 ms·

Quickly checking that a string belongs to a small set

93 points by ibobev 4y ago

rwmj 4y ago
gperf enters the chat https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ For C++ users, frozen is also a possibility: https://github.com/serge-sans-paille/frozen https://github.com/serge-sans-paille/frozen
- anonymoushn 4y ago
  But how many ns per query?
  - SloopJon 4y ago
    On my system (Windows 10, i7-10700K, Clang 11 with Visual C++ 2017 linker), frozen::unordered_set takes about 10ns. This is faster than std::unordered_set at 14ns, but slower than direct comparison at 6ns.
- mananaysiempre 4y ago
  While gperf (unlike, say, CMPH[1]) is also intended for small sets of short strings, I expect the difference here is in the definition of “small”: in the article, it’s six, whereas in gperf’s intended application, it’s more like six dozen (and CMPH’s “large” is thousands to millions). [1] https://cmph.sourceforge.net/gperf.html https://cmph.sourceforge.net/gperf.html
  - rurban 4y ago
    I've optimized gperf and nbperf to such small sets. I also add the padding, when it helps in the hash and comparison. cmph has an extremely large constant overhead. https://github.com/rurban/nbperf https://github.com/rurban/nbperf https://github.com/rurban/gperf https://github.com/rurban/gperf
- malkia 4y ago
  I worked on a game port (PS1->PC) and all (game object) strings were hashed using 16-bit hash and code directly checked their 16-bit values against them in the code, but unlike "gperf" there was no perect hash, just some standard routine (forgot what it was). So it made me wonder (initially) when some objects were named differently - like instead of chara, it was chara2 or chara5 (no 1, 3 or 4) - e.g. find a name where when hashed won't result in collision... then again it was super fast and just using 16-bits so win overall... Later in another studio we had some DB with collisions (32-bits) such that you don't introduce some string that would cause collision with existing.
  - malkia 4y ago
    Now obviously this won't work with external names, like http, https, etc. - but worked pretty good when all these names are under your control.
ape4 4y ago
Cool, but not optimized for future maintenance.
- sagarm 4y ago
  It's just a demonstration of the idea. If you wanted to deploy this in e.g. a query engine you'd want to generalize it to work with arbitrary input strings anyway.
tgv 4y ago
Probably even faster when the calls to string_to_uint64 are moved outside the function.
- adobrawy 4y ago
  It does not make difference. Just -O1 is enough to convert inline strings to static numbers: https://godbolt.org/z/cThn3dTrn https://godbolt.org/z/cThn3dTrn
  - Someone 4y ago
    I don’t think you should count on compilers doing that, especially not if it is easy to do better. The modern way to enforce that would be to write constexpr functions to do the conversions (or not? Are compilers required to evaluate constexpr expressions at compile time, where possible?)
    - twic 4y ago
      > Are compilers required to evaluate constexpr expressions at compile time, where possible? No. But C++20 adds consteval, which does carry that requirement: https://www.modernescpp.com/index.php/c-20-consteval-and-constinit https://www.modernescpp.com/index.php/c-20-consteval-and-con... Well, sort of. It has to produce a constant expression, and in practice the way to do that is to evaluate it at compile-time. But under the as-if rule, a compiler can do what it likes, up to and including producing a binary containing your source code and a copy of gcc, and compiling your entire program when you run it.
  - sparkie 4y ago
    Other reason to move them outside of the function: you might want to prepare them in memory in a way that could speed up the comparison further, which would only need to be done once, not each time the function is called. For example, using AVX_512: uint64_t protos[8] = { string_to_uint64("https\0\0\0"), string_to_uint64("http\0\0\0\0"), string_to_uint64("file\0\0\0\0"), string_to_uint64("ftp\0\0\0\0\0"), string_to_uint64("wss\0\0\0\0\0"), string_to_uint64("ws\0\0\0\0\0\0"), 0, 0 }; bool maybe_faster_is_special(std::string_view input, uint64_t protos[8]) { __m512i vprotos = __mm512_load_epi64(&protos[0]); __m512i vinput = __mm512_broadcastq_epi64(string_to_uint64(input)); __mmask8 comparisons = __mm512_cmpeq_epi64_mask(vinput, vprotos); return (bool)(!_cvtmask8_u32(comparisons)); }
pimlottc 4y ago
There's a related linear-time algorithm for checking a string against a list of targets for possible substring matches: Aho–Corasick algorithm [0] It's used by standard implementations of grep when matching against fixed strings (e.g. "grep -F" or "fgrep"). 0: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
- MattPalmer1086 4y ago
  You don't really need the full Aho Corasick algorithm to determine set membership of a string. A simple Trie structure made of the set of strings would suffice.
  - pimlottc 4y ago
    No, and it doesn't work for exactly this situation anyway, since you only want complete string matches here (e.g. "paws" shouldn't match), but I thought it was an interesting related problem.
    - recursive 4y ago
      As soon as you encounter the 'p', you fall out of the trie, and it's a miss.
      - pimlottc 4y ago
        Sorry, I was talking about Aho-Corasick
  - jeffrallen 4y ago
    There's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.
    - yakubin 4y ago
      Not just cache, but also the branch mispredictions while walking a trie.
ww520 4y ago
That’s a good experiment on doing batch comparison in 4 and 8 bytes. Should the input be padded too? To avoid reading beyond the end of the string. Also a trie could be faster for membership check.
benmmurphy 4y ago
Does the example only work for little endian machines? It converts ‘http\0\0\0\0’ to a u64. In LE machines the \0 padding becomes the MSB so it’s fine to use this 4 byte 0xffffffff mask. But for BE machines the padding becomes the LSB so the mask compares the padding.
im3w1l 4y ago
Seems cleaner and possibly faster to turn the checks inside out? if (input.size() == 5) { return memcmp(input.data(), "https", 5) == 0; } if (input.size() == 4) { return memcmp(input.data(), "http", 4) == 0 || memcmp(input.data(), "file", 4) == 0; } etc Edit: Nvm I see the issue with this, if you have a set like abcd1, abcd2, abcd3 then it has to try abcd first and then 1 and then abcd and then 2 and then abcd and then 3. You could do sort of manual trie of full 8 byte chunks followed by a 4 byte step followed by a 2 byte step followed by a 1 byte step. But yeah suddenly it's not so clean anymore. The example set doesn't have this issue though.
- jeffbee 4y ago
  Why do C programmers hate bcmp?
  - morelisp 4y ago
    It's deprecated since 2001 and not in the stdlib?
ripe 4y ago
"Static Search Structure" seems relevant [1]: A static search structure is an Abstract Data Type with certain fundamental operations, e.g., initialize, insert, and retrieve. Conceptually, all insertions occur before any retrievals. It is a useful data structure for representing static search sets. Static search sets occur frequently in software system applications. Typical static search sets include compiler reserved words, assembler instruction opcodes, and built-in shell interpreter commands. Search set members, called keywords, are inserted into the structure only once, usually during program initialization, and are not generally modified at run-time. Numerous static search structure implementations exist, e.g., arrays, linked lists, binary search trees, digital search tries, and hash tables. Different approaches offer trade-offs between space utilization and search time efficiency. For example, an n element sorted array is space efficient, though the average-case time complexity for retrieval operations using binary search is proportional to log n. Conversely, hash table implementations often locate a table entry in constant time, but typically impose additional memory overhead and exhibit poor worst case performance. Minimal perfect hash functions provide an optimal solution for a particular class of static search sets. A minimal perfect hash function is defined by two properties: * It allows keyword recognition in a static search set using at most one probe into the hash table. This represents the “perfect” property. * The actual memory allocated to store the keywords is precisely large enough for the keyword set, and no larger. This is the “minimal” property. For most applications it is far easier to generate perfect hash functions than minimal perfect hash functions. Moreover, non-minimal perfect hash functions frequently execute faster than minimal ones in practice. This phenomena occurs since searching a sparse keyword table increases the probability of locating a “null” entry, thereby reducing string comparisons. User @rwmj earlier posted a link to GNU gperf. That's an implementation. gperf's default behavior generates near-minimal perfect hash functions for keyword sets. However, gperf provides many options that permit user control over the degree of minimality and perfection. [1] https://www.gnu.org/software/gperf/manual/gperf.html https://www.gnu.org/software/gperf/manual/gperf.html
- DenisM 4y ago
  Very well written, thank you. Long enough to cover the subject, short enough to retain interest. If you have more of these on various subjects I would pay to read them. Perhaps make a book “Byte-size introductions to various CS topics” or some such.
DenisM 4y ago
That memcpy will read past the buffer boundary for small strings. Possibly a segfault or even information disclosure if string_to_uint64 is naively reused for another purpose. You’re probably “safe” wrt segfaults with default memory allocators since memory blocks will be padded to 8 bytes, but a more compact allocator will expose the flaw. On a related note, I vaguely recall that monkeying with allocator padding and alignment is a great way to suss out bugs like this. E.g. allocate all requested blocks of memory directly flush against the boundary of a decommitted page, forcing a segfault on even single-byte overruns. Wastes a lot of memory and forces slow unaligned memory access, but keeps you honest when justified.
- hermitdev 4y ago
  It seems to me there's a couple of other assumptions in there, too: 1) the string_view is null terminated (not required by string_view, not a safe assumption in general) and 2) that any padding is zero-initialized (don't think this is required, either).
  - benmmurphy 4y ago
    The padding doesn’t have to be 0 because the comparisons are masked off so the padding bytes are not included. Also, there is no null termination assumption. Though, I guess the last ‘fastest’ example does have the null terminator assumption but this should be assumed because it did assume zero padding. The only other assumption is that 8 bytes can be safely read and this is assumed in the original post. There might be an endian assumption.
- Dylan16807 4y ago
  > read past the buffer "if you can tell your compiler that the string you receive is ‘padded’ so that you can read eight bytes safely from it." But even if you can't make that guarantee, this still works pretty well as a performance comparison, you just need to make sure your final code has a runtime length check.
  - vlovich123 4y ago
ratboy666 4y ago
In old-school Pascal, type alfa is packed array [1..10] of char On the CDC 6600, word-size was 60 bits, and a character size of 6 bits -- so 10 characters in a 60 bit word. Then, compares become simple. The PDP-10 used 36 bit words and 6 bit encoding (ASCII space to underscore subtract 32, so space is 0, A is 33, _ is 63). Not so nice: "set of char" takes 64 bits -- and only 60 bits are available (using DEC SIXBIT encoding, or CDC DISPLAYCODE https://en-academic.com/dic.nsf/enwiki/11602432 https://en-academic.com/dic.nsf/enwiki/11602432). I guess we put that down to -- can't win them all. These days, I would consider 7 bit, 18 characters in 128 bits, and "set of char" in 128 bits. Back then, 36 bits would hold 6 characters... and that could be a filename. Compare in one instruction on the DEC-10. Thus 6.3 names (filename, extension, and 18 more bits in 2 words).
twic 4y ago
I thought you could make this clearer and possibly faster by using a switch, but initialising the switch constants is beyond me. You need a constexpr version of memcpy, and i couldn't find one that i could use. std::copy is constexpr, but i don't think you can whip up a char* pointing to the result uint64_t in a way that's constexpr. I could write a manual loop to do the copying, but surely that wouldn't reliably be as fast as memcpy. Anyway, this whole thing reminded me of FourCC codes, where you identify things with four-character ASCII strings, and freely reinterpret those as 32-bit integers whenever it's convenient: https://en.wikipedia.org/wiki/FourCC https://en.wikipedia.org/wiki/FourCC
- morelisp 4y ago
  nginx uses switch on a combination of length + specific known characters as part of a similar optimization. https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0ee5e40a84610fffb9/src/http/ngx_http_parse.c#L164 https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0e...
- gjye 4y ago
  std::bit_cast is constexpr. I'd defer the switch case generation to the compiler though: https://godbolt.org/z/oaWvGzWcn https://godbolt.org/z/oaWvGzWcn Seems to do the trick with the bunch of cmp/je in the generated asm.
pfdietz 4y ago
This reminds me of the Paul Khuong's string-case macro in Common Lisp. https://github.com/pkhuong/string-case/blob/master/string-case.lisp https://github.com/pkhuong/string-case/blob/master/string-ca...
moloch-hai 4y ago
Seems like a good place for a bloom filter. If the overwhelming majority of words seen don't match, you would win by rejecting non-matches quickly. If instead it almost always matches, you will need to look at all the bytes anyway to be certain of a match.
- Dylan1312 4y ago
  Bloom filters are a fantastic datastructure but more applicable when the search set is large (usually greater than can fit in-memory). If using a bloom filter with a small set, it's possible to obtain a low probability of false positives by using just one hash function and a small number of buckets. At that point you've effectively got a hashset like one of the solutions described in the blog post.
  - moloch-hai 4y ago
    The idea was that you maintain a running hash as bytes arrive, and drop out on the first that doesn't match. A separate hash table for what gets past would check for false positives, using the final hash value.
benmmurphy 4y ago
For swift and maybe other languages that have the small string optimisation the compiler is able to do comparisons using a similar mask and comparison. I’m surprised the default c++ benchmark didn’t benefit from this but maybe the standard library doesn’t use the small string optimisation.
- moloch-hai 4y ago
  It does, but these are not strings.
  - benmmurphy 4y ago
    I tried it using String instead of StringView and it didn't do the comparison optimisation either. For GCC it did inline one of the comparisons (https://godbolt.org/z/G3Ydfoxqc https://godbolt.org/z/G3Ydfoxqc). Probably, its not possible to do the optimisation with the standard library because the standard library doesn't guarantee that small strings will be in small string form so you always have to fallback on failure. Also, it doesn't work for swift because swift string comparison is based on some kind of normalisation. So there is a fast path check using the small string optimisation but if that fails it falls back to a slow check that tries to do normalisation. (https://swift.godbolt.org/z/fscsarGjb https://swift.godbolt.org/z/fscsarGjb)
rosebay 4y ago
Why isn’t a Trie considered the fastest solution?
kazinator 4y ago
In a comment, Lemire says: "In my tests, regex is 100x slower". Might he be including the regex compilation time? His snippet literally shows the regex construction and call being in the same scope, by indentation level: const std::regex txt_regex("(https)|(http)|(ftp)|(file)|(ws)|(wss)"); // later... bool match = std::regex_match(v.begin(), v.end(), txt_regex); The const won't help you here, what you want is static? Also, the parentheses aren't doing anything in that regex; and in many regex languages, parentheses are loaded with complicated semantics of group capture; I'd keep those out.
- yakubin 4y ago
  static would move the construction to before main(). In big projects that becomes an issue, when you have tons of little static objects defined here and there.
  - kazinator 4y ago
    It shouldn't be a problem for something entirely self-contained like a regex. If other static constructions try to use it before main() is called, then that could be a problem.
    - yakubin 4y ago
      I'm not talking about dependencies, but about the time spent before main(). It delays startup. Another thing is that local static variables often compile to fairly horrific long code with branches. Better just move it to a wider scope or a longer-lived struct/class member somewhere.
- gleenn 4y ago
  Also, they could compress the regular expressions for speedup by using a trie data structure and then walking the trie to match common-overlap. This is a Java example but you could easily port it or even just run it in Java and then export the regex after running with your fixed set of strings and paste into C++: https://github.com/gleenn/regex_compressor https://github.com/gleenn/regex_compressor
levodelellis 4y ago
In a project I did long ago (having nothing to do with a compiler) I was dealing with many text compares and two dozen keywords I heard of 'gperf' before but it wasn't giving me good results so I had to hand write my own solution. I quickly noticed many of the keywords start and end with the same few letters but the second and third last rarely matched up and when they did the word length was different I ended up writing `memcpy(&myint, (input_ptr+input_size-4), 4)` then adding size to myint. I then had a unique int so I used a switch and did a memcmp on each case. Memcmp was expensive because many words and keywords were the same length and 20+ letters. The function went from the slowest to fastest on that change. If I had to rewrite it today I would use SIMD and a 16bit compare
zX41ZdbW 4y ago
For a dynamic set of strings, I recommend checking the StringHashTable in ClickHouse. The basic idea is: to use a bunch of hash tables with fixed-size keys but split the strings into power-of-two size-classes. This basic idea originated in a chat and led to a PhD thesis by my friend: https://www.researchgate.net/publication/339879042_SAHA_A_String_Adaptive_Hash_Table_for_Analytical_Databases https://www.researchgate.net/publication/339879042_SAHA_A_St...
chris6f 4y ago
We took a similar approach in our JSON decoder. We needed to support sets (JSON object keys) that aren't necessarily known until runtime, and strings that are up to 16 bytes in length. We got better performance with a linear scan and SIMD matching than with a hash table or a perfect hashing scheme. See https://github.com/segmentio/asm/pull/57 https://github.com/segmentio/asm/pull/57 (AMD64) and https://github.com/segmentio/asm/pull/65 https://github.com/segmentio/asm/pull/65 (ARM64). Here's how it's used in the JSON decoder: https://github.com/segmentio/encoding/pull/101 https://github.com/segmentio/encoding/pull/101
- __turbobrew__ 4y ago
  This is immediately what I thought of. If your set is small enough you should be able to store them in a linear block of memory which can fit into L1 cache.
  - bigiain 4y ago
    I read an interesting blog post about doing a similar thing at AWS scale a while back: “ No parent will name a favorite among their children. But I do have one among my brainchildren, my software contributions over the decades: The event-streaming code I helped build at AWS. After rage-quitting I missed it so much that over the last few months, I wrote a library (in Go) called Quamina (GitHub) that does some of the same things. This is about that. Quamina offers an API to a construct called a “Matcher”. You add one or a hundred or a million “Patterns” to a Matcher then feed “Events” (data objects with possibly-nested fields and values) to it, and it will return you an array (possibly empty) of the Patterns each Event matches. Both Patterns and Events are represented by JSON objects (but it should be easy to support other Event encodings). Quamina (and here I beg pardon for a bit of chest-pounding) is really freaking fast. But what’s more interesting is that its speed doesn’t depend much on the number of Patterns that have been added. (Not strictly speaking O(1), but pretty close.) ” https://www.tbray.org/ongoing/When/202x/2022/05/12/Quamina https://www.tbray.org/ongoing/When/202x/2022/05/12/Quamina
JonChesterfield 4y ago
I really like the `switch(perfecthash(object))` dispatch model. Have been known to spend quite a lot of time seeking the hash function. Periodically I try to make a constraint solver find one but that is yet to work for me.

93 points by ibobev 4y ago

rwmj 4y ago

gperf enters the chat https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ For C++ users, frozen is also a possibility: https://github.com/serge-sans-paille/frozen https://github.com/serge-sans-paille/frozen

anonymoushn 4y ago
But how many ns per query?
- SloopJon 4y ago
  On my system (Windows 10, i7-10700K, Clang 11 with Visual C++ 2017 linker), frozen::unordered_set takes about 10ns. This is faster than std::unordered_set at 14ns, but slower than direct comparison at 6ns.
mananaysiempre 4y ago
While gperf (unlike, say, CMPH[1]) is also intended for small sets of short strings, I expect the difference here is in the definition of “small”: in the article, it’s six, whereas in gperf’s intended application, it’s more like six dozen (and CMPH’s “large” is thousands to millions). [1] https://cmph.sourceforge.net/gperf.html https://cmph.sourceforge.net/gperf.html
- rurban 4y ago
  I've optimized gperf and nbperf to such small sets. I also add the padding, when it helps in the hash and comparison. cmph has an extremely large constant overhead. https://github.com/rurban/nbperf https://github.com/rurban/nbperf https://github.com/rurban/gperf https://github.com/rurban/gperf
malkia 4y ago
I worked on a game port (PS1->PC) and all (game object) strings were hashed using 16-bit hash and code directly checked their 16-bit values against them in the code, but unlike "gperf" there was no perect hash, just some standard routine (forgot what it was). So it made me wonder (initially) when some objects were named differently - like instead of chara, it was chara2 or chara5 (no 1, 3 or 4) - e.g. find a name where when hashed won't result in collision... then again it was super fast and just using 16-bits so win overall... Later in another studio we had some DB with collisions (32-bits) such that you don't introduce some string that would cause collision with existing.
- malkia 4y ago
  Now obviously this won't work with external names, like http, https, etc. - but worked pretty good when all these names are under your control.

ape4 4y ago

Cool, but not optimized for future maintenance.

sagarm 4y ago
It's just a demonstration of the idea. If you wanted to deploy this in e.g. a query engine you'd want to generalize it to work with arbitrary input strings anyway.

tgv 4y ago

Probably even faster when the calls to string_to_uint64 are moved outside the function.

adobrawy 4y ago
It does not make difference. Just -O1 is enough to convert inline strings to static numbers: https://godbolt.org/z/cThn3dTrn https://godbolt.org/z/cThn3dTrn
- Someone 4y ago
  I don’t think you should count on compilers doing that, especially not if it is easy to do better. The modern way to enforce that would be to write constexpr functions to do the conversions (or not? Are compilers required to evaluate constexpr expressions at compile time, where possible?)
  - twic 4y ago
    > Are compilers required to evaluate constexpr expressions at compile time, where possible? No. But C++20 adds consteval, which does carry that requirement: https://www.modernescpp.com/index.php/c-20-consteval-and-constinit https://www.modernescpp.com/index.php/c-20-consteval-and-con... Well, sort of. It has to produce a constant expression, and in practice the way to do that is to evaluate it at compile-time. But under the as-if rule, a compiler can do what it likes, up to and including producing a binary containing your source code and a copy of gcc, and compiling your entire program when you run it.
- sparkie 4y ago
  Other reason to move them outside of the function: you might want to prepare them in memory in a way that could speed up the comparison further, which would only need to be done once, not each time the function is called. For example, using AVX_512: uint64_t protos[8] = { string_to_uint64("https\0\0\0"), string_to_uint64("http\0\0\0\0"), string_to_uint64("file\0\0\0\0"), string_to_uint64("ftp\0\0\0\0\0"), string_to_uint64("wss\0\0\0\0\0"), string_to_uint64("ws\0\0\0\0\0\0"), 0, 0 }; bool maybe_faster_is_special(std::string_view input, uint64_t protos[8]) { __m512i vprotos = __mm512_load_epi64(&protos[0]); __m512i vinput = __mm512_broadcastq_epi64(string_to_uint64(input)); __mmask8 comparisons = __mm512_cmpeq_epi64_mask(vinput, vprotos); return (bool)(!_cvtmask8_u32(comparisons)); }

pimlottc 4y ago

There's a related linear-time algorithm for checking a string against a list of targets for possible substring matches: Aho–Corasick algorithm [0] It's used by standard implementations of grep when matching against fixed strings (e.g. "grep -F" or "fgrep"). 0: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

MattPalmer1086 4y ago
You don't really need the full Aho Corasick algorithm to determine set membership of a string. A simple Trie structure made of the set of strings would suffice.
- pimlottc 4y ago
  No, and it doesn't work for exactly this situation anyway, since you only want complete string matches here (e.g. "paws" shouldn't match), but I thought it was an interesting related problem.
  - recursive 4y ago
    As soon as you encounter the 'p', you fall out of the trie, and it's a miss.
    - pimlottc 4y ago
      Sorry, I was talking about Aho-Corasick
- jeffrallen 4y ago
  There's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.
  - yakubin 4y ago
    Not just cache, but also the branch mispredictions while walking a trie.

ww520 4y ago

That’s a good experiment on doing batch comparison in 4 and 8 bytes. Should the input be padded too? To avoid reading beyond the end of the string. Also a trie could be faster for membership check.

benmmurphy 4y ago

Does the example only work for little endian machines? It converts ‘http\0\0\0\0’ to a u64. In LE machines the \0 padding becomes the MSB so it’s fine to use this 4 byte 0xffffffff mask. But for BE machines the padding becomes the LSB so the mask compares the padding.

im3w1l 4y ago

Seems cleaner and possibly faster to turn the checks inside out? if (input.size() == 5) { return memcmp(input.data(), "https", 5) == 0; } if (input.size() == 4) { return memcmp(input.data(), "http", 4) == 0 || memcmp(input.data(), "file", 4) == 0; } etc Edit: Nvm I see the issue with this, if you have a set like abcd1, abcd2, abcd3 then it has to try abcd first and then 1 and then abcd and then 2 and then abcd and then 3. You could do sort of manual trie of full 8 byte chunks followed by a 4 byte step followed by a 2 byte step followed by a 1 byte step. But yeah suddenly it's not so clean anymore. The example set doesn't have this issue though.

jeffbee 4y ago
Why do C programmers hate bcmp?
- morelisp 4y ago
  It's deprecated since 2001 and not in the stdlib?

ripe 4y ago

"Static Search Structure" seems relevant [1]: A static search structure is an Abstract Data Type with certain fundamental operations, e.g., initialize, insert, and retrieve. Conceptually, all insertions occur before any retrievals. It is a useful data structure for representing static search sets. Static search sets occur frequently in software system applications. Typical static search sets include compiler reserved words, assembler instruction opcodes, and built-in shell interpreter commands. Search set members, called keywords, are inserted into the structure only once, usually during program initialization, and are not generally modified at run-time. Numerous static search structure implementations exist, e.g., arrays, linked lists, binary search trees, digital search tries, and hash tables. Different approaches offer trade-offs between space utilization and search time efficiency. For example, an n element sorted array is space efficient, though the average-case time complexity for retrieval operations using binary search is proportional to log n. Conversely, hash table implementations often locate a table entry in constant time, but typically impose additional memory overhead and exhibit poor worst case performance. Minimal perfect hash functions provide an optimal solution for a particular class of static search sets. A minimal perfect hash function is defined by two properties: * It allows keyword recognition in a static search set using at most one probe into the hash table. This represents the “perfect” property. * The actual memory allocated to store the keywords is precisely large enough for the keyword set, and no larger. This is the “minimal” property. For most applications it is far easier to generate perfect hash functions than minimal perfect hash functions. Moreover, non-minimal perfect hash functions frequently execute faster than minimal ones in practice. This phenomena occurs since searching a sparse keyword table increases the probability of locating a “null” entry, thereby reducing string comparisons. User @rwmj earlier posted a link to GNU gperf. That's an implementation. gperf's default behavior generates near-minimal perfect hash functions for keyword sets. However, gperf provides many options that permit user control over the degree of minimality and perfection. [1] https://www.gnu.org/software/gperf/manual/gperf.html https://www.gnu.org/software/gperf/manual/gperf.html

DenisM 4y ago
Very well written, thank you. Long enough to cover the subject, short enough to retain interest. If you have more of these on various subjects I would pay to read them. Perhaps make a book “Byte-size introductions to various CS topics” or some such.

DenisM 4y ago

That memcpy will read past the buffer boundary for small strings. Possibly a segfault or even information disclosure if string_to_uint64 is naively reused for another purpose. You’re probably “safe” wrt segfaults with default memory allocators since memory blocks will be padded to 8 bytes, but a more compact allocator will expose the flaw. On a related note, I vaguely recall that monkeying with allocator padding and alignment is a great way to suss out bugs like this. E.g. allocate all requested blocks of memory directly flush against the boundary of a decommitted page, forcing a segfault on even single-byte overruns. Wastes a lot of memory and forces slow unaligned memory access, but keeps you honest when justified.

hermitdev 4y ago
It seems to me there's a couple of other assumptions in there, too: 1) the string_view is null terminated (not required by string_view, not a safe assumption in general) and 2) that any padding is zero-initialized (don't think this is required, either).
- benmmurphy 4y ago
  The padding doesn’t have to be 0 because the comparisons are masked off so the padding bytes are not included. Also, there is no null termination assumption. Though, I guess the last ‘fastest’ example does have the null terminator assumption but this should be assumed because it did assume zero padding. The only other assumption is that 8 bytes can be safely read and this is assumed in the original post. There might be an endian assumption.
Dylan16807 4y ago
> read past the buffer "if you can tell your compiler that the string you receive is ‘padded’ so that you can read eight bytes safely from it." But even if you can't make that guarantee, this still works pretty well as a performance comparison, you just need to make sure your final code has a runtime length check.
- vlovich123 4y ago

ratboy666 4y ago

In old-school Pascal, type alfa is packed array [1..10] of char On the CDC 6600, word-size was 60 bits, and a character size of 6 bits -- so 10 characters in a 60 bit word. Then, compares become simple. The PDP-10 used 36 bit words and 6 bit encoding (ASCII space to underscore subtract 32, so space is 0, A is 33, _ is 63). Not so nice: "set of char" takes 64 bits -- and only 60 bits are available (using DEC SIXBIT encoding, or CDC DISPLAYCODE https://en-academic.com/dic.nsf/enwiki/11602432 https://en-academic.com/dic.nsf/enwiki/11602432). I guess we put that down to -- can't win them all. These days, I would consider 7 bit, 18 characters in 128 bits, and "set of char" in 128 bits. Back then, 36 bits would hold 6 characters... and that could be a filename. Compare in one instruction on the DEC-10. Thus 6.3 names (filename, extension, and 18 more bits in 2 words).

twic 4y ago

I thought you could make this clearer and possibly faster by using a switch, but initialising the switch constants is beyond me. You need a constexpr version of memcpy, and i couldn't find one that i could use. std::copy is constexpr, but i don't think you can whip up a char* pointing to the result uint64_t in a way that's constexpr. I could write a manual loop to do the copying, but surely that wouldn't reliably be as fast as memcpy. Anyway, this whole thing reminded me of FourCC codes, where you identify things with four-character ASCII strings, and freely reinterpret those as 32-bit integers whenever it's convenient: https://en.wikipedia.org/wiki/FourCC https://en.wikipedia.org/wiki/FourCC

morelisp 4y ago
nginx uses switch on a combination of length + specific known characters as part of a similar optimization. https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0ee5e40a84610fffb9/src/http/ngx_http_parse.c#L164 https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0e...
gjye 4y ago
std::bit_cast is constexpr. I'd defer the switch case generation to the compiler though: https://godbolt.org/z/oaWvGzWcn https://godbolt.org/z/oaWvGzWcn Seems to do the trick with the bunch of cmp/je in the generated asm.

pfdietz 4y ago

This reminds me of the Paul Khuong's string-case macro in Common Lisp. https://github.com/pkhuong/string-case/blob/master/string-case.lisp https://github.com/pkhuong/string-case/blob/master/string-ca...

moloch-hai 4y ago

Seems like a good place for a bloom filter. If the overwhelming majority of words seen don't match, you would win by rejecting non-matches quickly. If instead it almost always matches, you will need to look at all the bytes anyway to be certain of a match.

Dylan1312 4y ago
Bloom filters are a fantastic datastructure but more applicable when the search set is large (usually greater than can fit in-memory). If using a bloom filter with a small set, it's possible to obtain a low probability of false positives by using just one hash function and a small number of buckets. At that point you've effectively got a hashset like one of the solutions described in the blog post.
- moloch-hai 4y ago
  The idea was that you maintain a running hash as bytes arrive, and drop out on the first that doesn't match. A separate hash table for what gets past would check for false positives, using the final hash value.

benmmurphy 4y ago

For swift and maybe other languages that have the small string optimisation the compiler is able to do comparisons using a similar mask and comparison. I’m surprised the default c++ benchmark didn’t benefit from this but maybe the standard library doesn’t use the small string optimisation.

moloch-hai 4y ago
It does, but these are not strings.
- benmmurphy 4y ago
  I tried it using String instead of StringView and it didn't do the comparison optimisation either. For GCC it did inline one of the comparisons (https://godbolt.org/z/G3Ydfoxqc https://godbolt.org/z/G3Ydfoxqc). Probably, its not possible to do the optimisation with the standard library because the standard library doesn't guarantee that small strings will be in small string form so you always have to fallback on failure. Also, it doesn't work for swift because swift string comparison is based on some kind of normalisation. So there is a fast path check using the small string optimisation but if that fails it falls back to a slow check that tries to do normalisation. (https://swift.godbolt.org/z/fscsarGjb https://swift.godbolt.org/z/fscsarGjb)

rosebay 4y ago

Why isn’t a Trie considered the fastest solution?

kazinator 4y ago

In a comment, Lemire says: "In my tests, regex is 100x slower". Might he be including the regex compilation time? His snippet literally shows the regex construction and call being in the same scope, by indentation level: const std::regex txt_regex("(https)|(http)|(ftp)|(file)|(ws)|(wss)"); // later... bool match = std::regex_match(v.begin(), v.end(), txt_regex); The const won't help you here, what you want is static? Also, the parentheses aren't doing anything in that regex; and in many regex languages, parentheses are loaded with complicated semantics of group capture; I'd keep those out.

yakubin 4y ago
static would move the construction to before main(). In big projects that becomes an issue, when you have tons of little static objects defined here and there.
- kazinator 4y ago
  It shouldn't be a problem for something entirely self-contained like a regex. If other static constructions try to use it before main() is called, then that could be a problem.
  - yakubin 4y ago
    I'm not talking about dependencies, but about the time spent before main(). It delays startup. Another thing is that local static variables often compile to fairly horrific long code with branches. Better just move it to a wider scope or a longer-lived struct/class member somewhere.
gleenn 4y ago
Also, they could compress the regular expressions for speedup by using a trie data structure and then walking the trie to match common-overlap. This is a Java example but you could easily port it or even just run it in Java and then export the regex after running with your fixed set of strings and paste into C++: https://github.com/gleenn/regex_compressor https://github.com/gleenn/regex_compressor

levodelellis 4y ago

In a project I did long ago (having nothing to do with a compiler) I was dealing with many text compares and two dozen keywords I heard of 'gperf' before but it wasn't giving me good results so I had to hand write my own solution. I quickly noticed many of the keywords start and end with the same few letters but the second and third last rarely matched up and when they did the word length was different I ended up writing `memcpy(&myint, (input_ptr+input_size-4), 4)` then adding size to myint. I then had a unique int so I used a switch and did a memcmp on each case. Memcmp was expensive because many words and keywords were the same length and 20+ letters. The function went from the slowest to fastest on that change. If I had to rewrite it today I would use SIMD and a 16bit compare

zX41ZdbW 4y ago

For a dynamic set of strings, I recommend checking the StringHashTable in ClickHouse. The basic idea is: to use a bunch of hash tables with fixed-size keys but split the strings into power-of-two size-classes. This basic idea originated in a chat and led to a PhD thesis by my friend: https://www.researchgate.net/publication/339879042_SAHA_A_String_Adaptive_Hash_Table_for_Analytical_Databases https://www.researchgate.net/publication/339879042_SAHA_A_St...

chris6f 4y ago

We took a similar approach in our JSON decoder. We needed to support sets (JSON object keys) that aren't necessarily known until runtime, and strings that are up to 16 bytes in length. We got better performance with a linear scan and SIMD matching than with a hash table or a perfect hashing scheme. See https://github.com/segmentio/asm/pull/57 https://github.com/segmentio/asm/pull/57 (AMD64) and https://github.com/segmentio/asm/pull/65 https://github.com/segmentio/asm/pull/65 (ARM64). Here's how it's used in the JSON decoder: https://github.com/segmentio/encoding/pull/101 https://github.com/segmentio/encoding/pull/101

__turbobrew__ 4y ago
This is immediately what I thought of. If your set is small enough you should be able to store them in a linear block of memory which can fit into L1 cache.
- bigiain 4y ago
  I read an interesting blog post about doing a similar thing at AWS scale a while back: “ No parent will name a favorite among their children. But I do have one among my brainchildren, my software contributions over the decades: The event-streaming code I helped build at AWS. After rage-quitting I missed it so much that over the last few months, I wrote a library (in Go) called Quamina (GitHub) that does some of the same things. This is about that. Quamina offers an API to a construct called a “Matcher”. You add one or a hundred or a million “Patterns” to a Matcher then feed “Events” (data objects with possibly-nested fields and values) to it, and it will return you an array (possibly empty) of the Patterns each Event matches. Both Patterns and Events are represented by JSON objects (but it should be easy to support other Event encodings). Quamina (and here I beg pardon for a bit of chest-pounding) is really freaking fast. But what’s more interesting is that its speed doesn’t depend much on the number of Patterns that have been added. (Not strictly speaking O(1), but pretty close.) ” https://www.tbray.org/ongoing/When/202x/2022/05/12/Quamina https://www.tbray.org/ongoing/When/202x/2022/05/12/Quamina

JonChesterfield 4y ago

I really like the `switch(perfecthash(object))` dispatch model. Have been known to spend quite a lot of time seeking the hash function. Periodically I try to make a constraint solver find one but that is yet to work for me.