Is Prefix of String in Table? a Journey into SIMD String Processing • Hacker News Board

Post by glangdale » Tue, May 15, 2018, 8:10 AM UTC

rurban wrote: post #31

trentnelson wrote: post #22

Earlier quoted context omitted.

Patches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths. Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assembl…

True. A gperf alike hash table (with special key indices) works only ok with compile-time known strings. But a simple CMP-alike perfect hash table with double indirection would be worthwhile to test against. I called it Hanov after http://stevehanov.ca/blog/index.php?id=119 Problem is there that you have to calc a hash for each string, which is only fast with __builtin_crc/_mm_crc32_u64

A hash alone isn't going to help much; he has both a 1-char string in the set and to top it off, most of the other strings begin with (a distinct from the 1-char string one) the same string. There are some tricks (overpopulate the hash table with short string) but hashing is tricky here.

Source: 11 years of string matching work. :-) We built a multiple hash table string matcher in the early days of Hyperscan (it's gone now).