[HN Gopher] Quickly checking that a string belongs to a small set
___________________________________________________________________
Quickly checking that a string belongs to a small set
Author : ibobev
Score : 72 points
Date : 2022-12-30 13:03 UTC (9 hours ago)
(HTM) web link (lemire.me)
(TXT) w3m dump (lemire.me)
| ape4 wrote:
| Cool, but not optimized for future maintenance.
| sagarm wrote:
| 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.
| moloch-hai wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It does, but these are not strings.
| benmmurphy wrote:
| 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)
| im3w1l wrote:
| 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 wrote:
| Why do C programmers hate bcmp?
| morelisp wrote:
| It's deprecated since 2001 and not in the stdlib?
| tgv wrote:
| Probably even faster when the calls to string_to_uint64 are moved
| outside the function.
| adobrawy wrote:
| It does not make difference. Just -O1 is enough to convert
| inline strings to static numbers:
| https://godbolt.org/z/cThn3dTrn
| Someone wrote:
| 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 wrote:
| > 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.
| sparkie wrote:
| 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)); }
| hnav wrote:
| Very nice, how's the performance?
| kazinator wrote:
| 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.
| gleenn wrote:
| 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
| kazinator wrote:
| 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).
| kazinator wrote:
| 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.
| burntsushi wrote:
| 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.co
| m/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).
| yakubin wrote:
| _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 wrote:
| 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.
| zX41ZdbW wrote:
| 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...
| ratboy666 wrote:
| 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).
| pfdietz wrote:
| This reminds me of the Paul Khuong's string-case macro in Common
| Lisp.
|
| https://github.com/pkhuong/string-case/blob/master/string-ca...
| ww520 wrote:
| 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.
| ripe wrote:
| "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
| DenisM wrote:
| 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.
| ripe wrote:
| 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.
| DenisM wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| levodelellis wrote:
| 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
| rosebay wrote:
| [dead]
| twic wrote:
| 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
| gjye wrote:
| 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.
| morelisp wrote:
| nginx uses switch on a combination of length + specific known
| characters as part of a similar optimization.
|
| https://github.com/nginx/nginx/blob/9c7a2c7ce4ad02a36df1bb0e...
| rwmj wrote:
| _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
| mananaysiempre wrote:
| 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
| rurban wrote:
| 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
| anonymoushn wrote:
| But how many ns per query?
| SloopJon wrote:
| 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.
| pimlottc wrote:
| 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
| kazinator wrote:
| I wonder what, if any, is the advantage of this algorithm
| compared to forming a regex disjunction of the strings and
| compiling to DFA.
| burntsushi wrote:
| 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.
| morelisp wrote:
| 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.
| MattPalmer1086 wrote:
| 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 wrote:
| 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 wrote:
| As soon as you encounter the 'p', you fall out of the trie,
| and it's a miss.
| pimlottc wrote:
| Sorry, I was talking about Aho-Corasick
| jeffrallen wrote:
| There's no way the cache thrashing of walking a trie would
| cost less than the integer compares the author used.
| benmmurphy wrote:
| 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.
___________________________________________________________________
(page generated 2022-12-30 23:01 UTC)