Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cttrie – Compile-time trie-based string matching for C++

smilingthax.github.io

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Cttrie – Compile-time trie-based string matching for C++

#11

Post by saagarjha »

acidx wrote: post #4

I like this trick that I use in C. It's limited, as it only matches string prefixes, but it works pretty well in the end: https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in... It allows you to write something like this: https://github.com/lpereira/lwan/blob/master/src/lib/lwan-ti... -- which is generated as a binary search by GCC.

You know, I don't quite understand the point the author is making there. They concede that the compiler is smart enough to elide memcpys, but not smart enough to vectorize their strlen function? What?

Re: Cttrie – Compile-time trie-based string matching for C++

#12

Post by joejoint »

Why not just hash the string using constexpr ?

====================

C preprocessor based compile time hash from lolengine:

http://lolengine.net/blog/2011/12/20/cpp-constant-string-has...

====================

#define H1(s,i,x)(x65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x))))

#define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x))))

#define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16(s,i+48,x))))

#define H256(s,i,x) H64(s,i,H64(s,i+64,H64(s,i+128,H64(s,i+192,x))))

#define HASH(s) ((uint32_t)(H256(s,0,0)^(H256(s,0,0)>>16)))

template constexpr uint32_t h(char const (&s)[N]) { return HASH(s); }

constexpr uint32_t h(const char s) { return HASH(s); }

uint32_t h(const std::string& s) { return h(s.c_str()); }

int main(int argc, const char argv) {

    auto s = "keep";
    std::string x = "simple";

    switch(h(x))
    {
        case h("keep")  : std::cout

Re: Cttrie – Compile-time trie-based string matching for C++

#13

Post by ur-whale »

joejoint wrote: post #12

Why not just hash the string using constexpr ? ==================== C preprocessor based compile time hash from lolengine: http://lolengine.net/blog/2011/12/20/cpp-constant-string-has... ==================== #define H1(s,i,x)(x 65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x)))) #define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x)))) #define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16…

The hash has to look at all the chars in the string.

Does the trie have to as well?

Re: Cttrie – Compile-time trie-based string matching for C++

#14

Post by slededit »

ur-whale wrote: post #13
joejoint wrote: post #12

Why not just hash the string using constexpr ? ==================== C preprocessor based compile time hash from lolengine: http://lolengine.net/blog/2011/12/20/cpp-constant-string-has... ==================== #define H1(s,i,x)(x 65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x)))) #define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x)))) #define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16…

The hash has to look at all the chars in the string. Does the trie have to as well?

If it’s possible for the string to not be in the set then you have to look at all chars.

Otherwise there are some cases you can skip characters. I generally don’t use this optimization when writing Tries because it’s tricky and rarely makes a difference.

Re: Cttrie – Compile-time trie-based string matching for C++

#15

Post by kllrnohj »

joejoint wrote: post #12

Why not just hash the string using constexpr ? ==================== C preprocessor based compile time hash from lolengine: http://lolengine.net/blog/2011/12/20/cpp-constant-string-has... ==================== #define H1(s,i,x)(x 65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x)))) #define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x)))) #define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16…

Hash collisions would be one obvious problem with this approach. You could likely always tweak the hash used in response to collisions on the set of constants, but that's not going to be fun the first time it happens.

Also with that approach since it can't be made into a jump table it's still going to compile into a bunch of if/else combinations. At least with the trie it can early-return if the input doesn't have any chance of matching anything.

Re: Cttrie – Compile-time trie-based string matching for C++

#16

Post by wmu »

chubot wrote: post #6

If you're OK with textual code generation, you can also use something like re2c: http://re2c.org/ And then you get the power of regexes too. re2c will match an arbitrary set of regexes (including constant strings) by walking through the string byte-by-byte, a single time. A trie is basically a special case of a DFA.

"A trie is basically a special case of a DFA." The best definition of trie I read.

Re: Cttrie – Compile-time trie-based string matching for C++

#18

Post by lasagnaphil »

Although I understand people want to do some crazy stuff with template metaprogramming, I’m more concerned with how it will affect build times (you’re basically running a tree-walk interpreter in a compiler that was not supposed to run a turing complete language... it’s going to be very slow.)

For more practical reasons, what about just using runtime interned strings? Each unique string is hashed and allocated in heap memory only once, and to compare the strings you just compare the hashed values (which is just uint_64 comparison). Then you can easily use switch statements to compare your strings... As for performance, interning has an initial runtime cost for each string, but it will probably be miniscule compared to the massive compile time cost induced by crazy constexpr stuff.

Example of a string interning library:

https://github.com/mattiasgustavsson/libs/blob/master/docs/s...

Re: Cttrie – Compile-time trie-based string matching for C++

#19

Post by beached_whale »

joejoint wrote: post #12

Why not just hash the string using constexpr ? ==================== C preprocessor based compile time hash from lolengine: http://lolengine.net/blog/2011/12/20/cpp-constant-string-has... ==================== #define H1(s,i,x)(x 65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x)))) #define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x)))) #define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16…

This is what I have done. However, you still have the risk of collisions. Depending on the context, like i did a small test and permuted all letters a-z and numbers and there are no collisions. However, changing a-z to A-Z resulted in many(may need to check code). However, this allows for a 5 character command switch.

Re: Cttrie – Compile-time trie-based string matching for C++

#20

Post by beached_whale »

ur-whale wrote: post #13
joejoint wrote: post #12

Why not just hash the string using constexpr ? ==================== C preprocessor based compile time hash from lolengine: http://lolengine.net/blog/2011/12/20/cpp-constant-string-has... ==================== #define H1(s,i,x)(x 65599u+(uint8_t)s[(i) #define H4(s,i,x) H1(s,i,H1(s,i+1,H1(s,i+2,H1(s,i+3,x)))) #define H16(s,i,x) H4(s,i,H4(s,i+4,H4(s,i+8,H4(s,i+12,x)))) #define H64(s,i,x) H16(s,i,H16(s,i+16,H16(s,i+32,H16…

The hash has to look at all the chars in the string. Does the trie have to as well?

The string compare has a lot of branching and looks at both strings. The hash method one checks the hash of the test string(size_t) with the size_t of the other string. The hash itself, say fnv1a, can be very quick(a xor and a multiply I think per character) I think I remember testing this and it was quicker. ill try to find the test, but it is easily done. Either way, it's the only way to use a switch statement this way
Post reply on HN