Quickly checking that a string belongs to a small set | Hacker News Reader

Quickly checking that a string belongs to a small set

lemire.me

93 pointsibobev76 comments

gperf enters the chat

https://www.gnu.org/software/gperf/

For C++ users, frozen is also a possibility: https://github.com/serge-sans-paille/frozen

But how many ns per query?

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.

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

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/gperf

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.

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.

"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

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.

Thank you for the kind words! That was extracted from the link I provided, with minor rewording.

Since the pandemic, I have been writing short articles aimed at lay people (not readers like you on HN), called Robots In Plain English. Link in my profile.

A different thing from what you were asking, but might be interesting to you.

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.

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.

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.

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.

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

The NFA -> DFA subset construction will identify and squeeze out the overlaps.

Compressing regexes, I suspect, is a pointless excercise, except as a preprocessing pass before a pseudo-regex engine that does backtracking (e.g. Perl).

Some of these backtracking regex engines have problem semantics like if both a|abc can match a string, the left match will win, so only "a" gets matched. If you put some compressing pass before that, you have to be careful not to mess that up. Basically "abc" can be deleted in this example. then you compress.

This applies to non-backtracking non-DFAs too: https://github.com/rust-lang/regex/issues/787#issuecomment-1...

The GitHub issue comment is perhaps a bit high context. I wrote this reddit comment the other day that is lower context and probably more accessible: https://old.reddit.com/r/rust/comments/zsntov/pomsky_08_rele...

High level problem: general purpose regex engines that use finite state machines basically never build DFAs. Some of them will build lazy DFAs, but sometimes the lazy DFA can't or shouldn't be used. So you're stuck with an NFA simulation or bounded backtracking. And in those cases, getting rid of the alternation clog can be hugely beneficial (by orders of magnitude).

Do you know is Java's built-in regex engine builds a DFA? This is all news to me. I built that optimizer because we were doing something pretty naive at work I suppose: we were doing the string concatenation joining with | for a relatively large set of strings and got a notably large speedup so I'm going to assume Java doesn't. It was a very fun project none-the-less :)

I don't know much about Java's regex engine, but my understanding is that it's a backtracker. Indeed, such an optimization can make the regex go from intractably slow to quite fast.

We used my regex compressor and saw a very large speedup on a large production system so anecdotally it was very useful.

Yeah, my first thought was that this was a job for a trie. You can inspect your input character by character, and you can rule out most strings by the first byte since it must be h, f or w. If your set is small and static, you can hard-code the trie and it will be superfast, but a long as you can fail fast when checking each character (so don’t use the default hasher in Rust), you can check for matches quickly and easily.

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 (AMD64) and 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

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.

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

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

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.

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.

As soon as you encounter the 'p', you fall out of the trie, and it's a miss.

Sorry, I was talking about Aho-Corasick

There's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.

Not just cache, but also the branch mispredictions while walking a trie.

Since the trie is static it could be pregenerated and held in small static array that might fit in a cache line ... I think. I don't really know this stuff.

But still probably would be slower especially if there aren't many misses that could be quickly rejected by the trie.

Yes, for a small set of strings, which is the problem he is solving, you are almost certainly right.

I wonder what, if any, is the advantage of this algorithm compared to forming a regex disjunction of the strings and compiling to DFA.

They do totally different things. A regex will tell you if the haystack contained any needle (and if you want, give you one specific one which depends on the engine/compilation). AC tells you all needles the haystack contained.

The reply you already got is kind of correct, but only in the sense of what is typically exposed at an API level. Most Aho-Corasick implementations have a way to provide all possible matches, even overlapping ones. Yet, most regex engines do not provide any way to return all possible matches. However, FSM-based regex engines can do that, if they want to, using largely the same structure as Aho-Corasick: keep a list of matching patterns for each match state. With that said, this would require treating each literal pattern as a distinct regex instead of doing 'pat0|pat1|..|patN'. But this is mostly just API stuff.

Putting that aside, what I suspect to be the most essential difference is the construction algorithm itself. Building an Aho-Corasick NFA (or even DFA) is done in worst case linear time. But building a DFA through powerset construction takes worst case exponential time.

Whether I'm actually right about that or not depends on whether the worst case bound for powerset construction remains as such when you know your input is just an alternation of literals. But certainly, if you take a general regex construction implementation and feed it a bunch of literals, the Aho-Corasick implementation is almost certainly going to come out on top. The former is more general and has more infrastructure that costs time and space.

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.

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_St...

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). 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).

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

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

nginx uses switch on a combination of length + specific known characters as part of a similar optimization.

https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0e...

std::bit_cast is constexpr. I'd defer the switch case generation to the compiler though: https://godbolt.org/z/oaWvGzWcn Seems to do the trick with the bunch of cmp/je in the generated asm.

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.

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).

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.

> 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.

And that your allocation isn’t at the end of a page.

If you legitimately have the buffer length then it doesn't matter how the allocation is aligned. The extra time to read the next page with no errors doesn't need to be avoided, since it's rare and you're very likely to use that data anyway. The only thing you need is certainty that you have the buffer length.

You're assuming the next page is mapped. If it's pointing into unmapped memory, then you'll segfault.

I'm not assuming.

When I say "guarantee", I mean the code is designed so the first 8 bytes are always mapped.

When I say "runtime length check", I mean the code only runs if the first 8 bytes are in fact mapped.

No assumptions. No possible way to segfault. The read is valid.

If buffer[6] is not mapped, then you don't "legitimately have the buffer length".

Ok then I just misunderstood / some kind of language preciseness confusion. We’re on the same page now. AFAIK this is what the article is saying to do.

> AFAIK this is what the article is saying to do.

Yeah, that's why I quoted the article.

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.

Why do C programmers hate bcmp?

It's deprecated since 2001 and not in the stdlib?

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.

It does, but these are not strings.

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). 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)

This reminds me of the Paul Khuong's string-case macro in Common Lisp.

https://github.com/pkhuong/string-case/blob/master/string-ca...

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

It does not make difference. Just -O1 is enough to convert inline strings to static numbers: https://godbolt.org/z/cThn3dTrn

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?)

> 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-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.

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));
    }

Very nice, how’s the performance?

Not tested, but should be predictable. Each instrinsic maps to one instruction. Instruction latencies according to uops.info:

    vmovdqa64 zmm, m512      ; latency<=12
    vpbroadcastq zmm, r64    ; latency<=5
    vpcmpeqq k, zmm, zmm     ; latency=3
    kmovb r32, k             ; latency<=3

The code is branchless. It will take the same number of cycles regardless of input. This is why it is `maybe_faster`. The faster version from the article may be faster for http/https because of short-circuiting behavior, but it would be slower for other protocols due to multiple branching.

Aside from having greater throughput per instruction, being branchless means you will not have any branch prediction misses which negatively affect performance.

The vectorized version would be a significant improvement if there are many (more than 6) small strings to compare, but for this example the difference is probably minor.

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.

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.

Cool, but not optimized for future maintenance.

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.

Why isn’t a Trie considered the fastest solution?

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.

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.

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.

Reply on news.ycombinator.com