| Author: | Wojciech Muła |
|---|---|
| Added on: | 2022-01-29 |
Contents
When we started to use boost::beast library at work, obviously I downloaded its source code. Can't say I am good at navigation across boost libraries, I was just opening random files waiting for compilation completion. My attention was caught by procedure string_to_verb, that translates a HTTP verb into a number, in fact an enum. The most common verbs are GET POST, PUT and DELETE, however in total there are 33 verbs, the longest ones have 12 characters.
Why the boost implementation seemed to me to be odd? It's basically a hardcoded Trie. There is the main switch statement that selects a subtree based on the first character. Then:
This looks like a lot of branches and we do know that branches might be a source of performance problems. A mispredicted branch penalty is several CPU cycles. I thought it would be good to check if other solutions would be better.
Experiment setup. We generate predefined number of random HTTP verbs. Verbs are either selected from the whole set of 33 verbs, or from subset GET/POST/PUT. Then a procedure is called given number of times and the total time is noted.
We tested five procedures:
Summary:
| procedure | input size | iterations | time [us] |
|---|---|---|---|
| boost::beast | 100 | 10000 | 2956 |
| SWAR64 | 100 | 10000 | 6922 |
| SWAR32 | 100 | 10000 | 7200 |
| SWAR32v2 | 100 | 10000 | 7024 |
| MPH | 100 | 10000 | 5464 |
| boost::beast | 1000 | 1000 | 9315 |
| SWAR64 | 1000 | 1000 | 7932 |
| SWAR32 | 1000 | 1000 | 8834 |
| SWAR32v2 | 1000 | 1000 | 9485 |
| MPH | 1000 | 1000 | 10352 |
| boost::beast | 10000 | 100 | 16457 |
| SWAR64 | 10000 | 100 | 21809 |
| SWAR32 | 10000 | 100 | 23204 |
| SWAR32 | 10000 | 100 | 21766 |
| MPH | 10000 | 100 | 11089 |
| procedure | input size | iterations | time [us] |
|---|---|---|---|
| boost::beast | 100 | 10000 | 3334 |
| SWAR64 | 100 | 10000 | 7321 |
| SWAR32 | 100 | 10000 | 6502 |
| SWAR32v2 | 100 | 10000 | 6421 |
| MPH | 100 | 10000 | 7891 |
| boost::beast | 1000 | 1000 | 5839 |
| SWAR64 | 1000 | 1000 | 8820 |
| SWAR32 | 1000 | 1000 | 8899 |
| SWAR32v2 | 1000 | 1000 | 10027 |
| MPH | 1000 | 1000 | 7531 |
| boost::beast | 10000 | 100 | 8339 |
| SWAR64 | 10000 | 100 | 14289 |
| SWAR32 | 10000 | 100 | 13722 |
| SWAR32v2 | 10000 | 100 | 12117 |
| MPH | 10000 | 100 | 7498 |
| procedure | input size | iterations | time [us] |
|---|---|---|---|
| boost::beast | 100 | 10000 | 9466 |
| SWAR64 | 100 | 10000 | 16286 |
| SWAR32 | 100 | 10000 | 9970 |
| SWAR32v2 | 100 | 10000 | 8432 |
| MPH | 100 | 10000 | 6956 |
| boost::beast | 1000 | 1000 | 24203 |
| SWAR64 | 1000 | 1000 | 13758 |
| SWAR32 | 1000 | 1000 | 17132 |
| SWAR32v2 | 1000 | 1000 | 11872 |
| MPH | 1000 | 1000 | 12606 |
| boost::beast | 10000 | 100 | 31449 |
| SWAR64 | 10000 | 100 | 25088 |
| SWAR32 | 10000 | 100 | 26211 |
| SWAR32v2 | 10000 | 100 | 25921 |
| MPH | 10000 | 100 | 13683 |
| procedure | input size | iterations | time [us] |
|---|---|---|---|
| boost::beast | 100 | 10000 | 3579 |
| SWAR64 | 100 | 10000 | 8458 |
| SWAR32 | 100 | 10000 | 7687 |
| SWAR32v2 | 100 | 10000 | 7713 |
| MPH | 100 | 10000 | 9542 |
| boost::beast | 1000 | 1000 | 6940 |
| SWAR64 | 1000 | 1000 | 12876 |
| SWAR32 | 1000 | 1000 | 11868 |
| SWAR32v2 | 1000 | 1000 | 11431 |
| MPH | 1000 | 1000 | 9194 |
| boost::beast | 10000 | 100 | 10500 |
| SWAR64 | 10000 | 100 | 16237 |
| SWAR32 | 10000 | 100 | 15809 |
| SWAR32v2 | 10000 | 100 | 14582 |
| MPH | 10000 | 100 | 9134 |
All implementations are available at github.
This is a verbose copy of boost::beast code.
verb string_to_verb(std::string_view v) { if(v.size() < 3) return verb::unknown; auto c = v[0]; v.remove_prefix(1); switch(c) { case 'A': if(v == "CL"_sv) return verb::acl; break; case 'B': if(v == "IND"_sv) return verb::bind; break; case 'C': c = v[0]; v.remove_prefix(1); switch(c) { case 'H': if(v == "ECKOUT"_sv) return verb::checkout; break; case 'O': if(v == "NNECT"_sv) return verb::connect; if(v == "PY"_sv) return verb::copy; ; default: break; } break; case 'D': if(v == "ELETE"_sv) return verb::delete_; break; case 'G': if(v == "ET"_sv) return verb::get; break; case 'H': if(v == "EAD"_sv) return verb::head; break; case 'L': if(v == "INK"_sv) return verb::link; if(v == "OCK"_sv) return verb::lock; break; case 'M': c = v[0]; v.remove_prefix(1); switch(c) { case '-': if(v == "SEARCH"_sv) return verb::msearch; break; case 'E': if(v == "RGE"_sv) return verb::merge; break; case 'K': if(v == "ACTIVITY"_sv) return verb::mkactivity; if(v[0] == 'C') { v.remove_prefix(1); if(v == "ALENDAR"_sv) return verb::mkcalendar; if(v == "OL"_sv) return verb::mkcol; break; } break; case 'O': if(v == "VE"_sv) return verb::move; ; default: break; } break; case 'N': if(v == "OTIFY"_sv) return verb::notify; break; case 'O': if(v == "PTIONS"_sv) return verb::options; break; case 'P': c = v[0]; v.remove_prefix(1); switch(c) { case 'A': if(v == "TCH"_sv) return verb::patch; break; case 'O': if(v == "ST"_sv) return verb::post; break; case 'R': if(v == "OPFIND"_sv) return verb::propfind; if(v == "OPPATCH"_sv) return verb::proppatch; break; case 'U': if(v == "RGE"_sv) return verb::purge; if(v == "T"_sv) return verb::put; ; default: break; } break; case 'R': if(v[0] != 'E') break; v.remove_prefix(1); if(v == "BIND"_sv) return verb::rebind; if(v == "PORT"_sv) return verb::report; break; case 'S': if(v == "EARCH"_sv) return verb::search; if(v == "UBSCRIBE"_sv) return verb::subscribe; break; case 'T': if(v == "RACE"_sv) return verb::trace; break; case 'U': if(v[0] != 'N') break; v.remove_prefix(1); if(v == "BIND"_sv) return verb::unbind; if(v == "LINK"_sv) return verb::unlink; if(v == "LOCK"_sv) return verb::unlock; if(v == "SUBSCRIBE"_sv) return verb::unsubscribe; break; default: break; } return verb::unknown; }
Below is a procedure that matches 8-byte prefixes.
#define STRING_CONST(s0, s1, s2, s3, s4, s5, s6, s7) \ ((uint64_t(uint8_t((s0))) << 0*8) | \ (uint64_t(uint8_t((s1))) << 1*8) | \ (uint64_t(uint8_t((s2))) << 2*8) | \ (uint64_t(uint8_t((s3))) << 3*8) | \ (uint64_t(uint8_t((s4))) << 4*8) | \ (uint64_t(uint8_t((s5))) << 5*8) | \ (uint64_t(uint8_t((s6))) << 6*8) | \ (uint64_t(uint8_t((s7))) << 7*8)) verb string_to_verb(std::string_view v) { if (v.size() < 3 or v.size() > 13) return verb::unknown; union { char buf[13]; uint64_t value; }; value = 0; memcpy(buf, v.data(), v.size()); switch (value) { case STRING_CONST('A', 'C', 'L', 0, 0, 0, 0, 0): return verb::acl; case STRING_CONST('B', 'I', 'N', 'D', 0, 0, 0, 0): return verb::bind; case STRING_CONST('C', 'H', 'E', 'C', 'K', 'O', 'U', 'T'): return verb::checkout; case STRING_CONST('C', 'O', 'N', 'N', 'E', 'C', 'T', 0): return verb::connect; case STRING_CONST('C', 'O', 'P', 'Y', 0, 0, 0, 0): return verb::copy; case STRING_CONST('D', 'E', 'L', 'E', 'T', 'E', 0, 0): return verb::delete_; case STRING_CONST('G', 'E', 'T', 0, 0, 0, 0, 0): return verb::get; case STRING_CONST('H', 'E', 'A', 'D', 0, 0, 0, 0): return verb::head; case STRING_CONST('L', 'I', 'N', 'K', 0, 0, 0, 0): return verb::link; case STRING_CONST('L', 'O', 'C', 'K', 0, 0, 0, 0): return verb::lock; case STRING_CONST('M', '-', 'S', 'E', 'A', 'R', 'C', 'H'): return verb::msearch; case STRING_CONST('M', 'E', 'R', 'G', 'E', 0, 0, 0): return verb::merge; case STRING_CONST('M', 'K', 'A', 'C', 'T', 'I', 'V', 'I'): if (v.size() == 10 and v.substr(8) == "TY"_sv) return verb::mkactivity; break; case STRING_CONST('M', 'K', 'C', 'A', 'L', 'E', 'N', 'D'): if (v.size() == 10 and v.substr(8) == "AR"_sv) return verb::mkcalendar; break; case STRING_CONST('M', 'K', 'C', 'O', 'L', 0, 0, 0): return verb::mkcol; case STRING_CONST('M', 'O', 'V', 'E', 0, 0, 0, 0): return verb::move; case STRING_CONST('N', 'O', 'T', 'I', 'F', 'Y', 0, 0): return verb::notify; case STRING_CONST('O', 'P', 'T', 'I', 'O', 'N', 'S', 0): return verb::options; case STRING_CONST('P', 'A', 'T', 'C', 'H', 0, 0, 0): return verb::patch; case STRING_CONST('P', 'O', 'S', 'T', 0, 0, 0, 0): return verb::post; case STRING_CONST('P', 'R', 'O', 'P', 'F', 'I', 'N', 'D'): return verb::propfind; case STRING_CONST('P', 'R', 'O', 'P', 'P', 'A', 'T', 'C'): if (v.size() == 9 and v[8] == 'H') return verb::proppatch; break; case STRING_CONST('P', 'U', 'R', 'G', 'E', 0, 0, 0): return verb::purge; case STRING_CONST('P', 'U', 'T', 0, 0, 0, 0, 0): return verb::put; case STRING_CONST('R', 'E', 'B', 'I', 'N', 'D', 0, 0): return verb::rebind; case STRING_CONST('R', 'E', 'P', 'O', 'R', 'T', 0, 0): return verb::report; case STRING_CONST('S', 'E', 'A', 'R', 'C', 'H', 0, 0): return verb::search; case STRING_CONST('S', 'U', 'B', 'S', 'C', 'R', 'I', 'B'): if (v.size() == 9 and v[8] == 'E') return verb::subscribe; break; case STRING_CONST('T', 'R', 'A', 'C', 'E', 0, 0, 0): return verb::trace; case STRING_CONST('U', 'N', 'B', 'I', 'N', 'D', 0, 0): return verb::unbind; case STRING_CONST('U', 'N', 'L', 'I', 'N', 'K', 0, 0): return verb::unlink; case STRING_CONST('U', 'N', 'L', 'O', 'C', 'K', 0, 0): return verb::unlock; case STRING_CONST('U', 'N', 'S', 'U', 'B', 'S', 'C', 'R'): if (v.size() == 11 and v.substr(8) == "IBE"_sv) return verb::unsubscribe; break; } return verb::unknown; }
Below is a procedure that matches 4-byte prefixes.
#define STRING_CONST(s0, s1, s2, s3) \ ((uint64_t(uint8_t((s0))) << 0*8) | \ (uint64_t(uint8_t((s1))) << 1*8) | \ (uint64_t(uint8_t((s2))) << 2*8) | \ (uint64_t(uint8_t((s3))) << 3*8)) verb string_to_verb(std::string_view v) { if (v.size() < 3 or v.size() > 13) return verb::unknown; union { char buf[13]; uint32_t word[2]; uint32_t value; }; value = 0; memcpy(buf, v.data(), v.size()); switch (value) { case STRING_CONST('A', 'C', 'L', 0): return verb::acl; case STRING_CONST('B', 'I', 'N', 'D'): return verb::bind; case STRING_CONST('C', 'H', 'E', 'C'): if (word[1] == STRING_CONST('K', 'O', 'U', 'T')) return verb::checkout; break; case STRING_CONST('C', 'O', 'N', 'N'): if (word[1] == STRING_CONST('E', 'C', 'T', 0)) return verb::connect; break; case STRING_CONST('C', 'O', 'P', 'Y'): return verb::copy; case STRING_CONST('D', 'E', 'L', 'E'): if (word[1] == STRING_CONST('T', 'E', 0, 0)) return verb::delete_; break; case STRING_CONST('G', 'E', 'T', 0): return verb::get; case STRING_CONST('H', 'E', 'A', 'D'): return verb::head; case STRING_CONST('L', 'I', 'N', 'K'): return verb::link; case STRING_CONST('L', 'O', 'C', 'K'): return verb::lock; case STRING_CONST('M', '-', 'S', 'E'): if (word[1] == STRING_CONST('A', 'R', 'C', 'H')) return verb::msearch; break; case STRING_CONST('M', 'E', 'R', 'G'): if (word[1] == STRING_CONST('E', 0, 0, 0)) return verb::merge; break; case STRING_CONST('M', 'K', 'A', 'C'): if (v.substr(4) == /*MKAC*/"TIVITY"_sv) return verb::mkactivity; break; case STRING_CONST('M', 'K', 'C', 'A'): if (v.substr(4) == /*MKCA*/"LENDAR"_sv) return verb::mkcalendar; break; case STRING_CONST('M', 'K', 'C', 'O'): if (word[1] == STRING_CONST('L', 0, 0, 0)) return verb::mkcol; break; case STRING_CONST('M', 'O', 'V', 'E'): return verb::move; case STRING_CONST('N', 'O', 'T', 'I'): if (word[1] == STRING_CONST('F', 'Y', 0, 0)) return verb::notify; break; case STRING_CONST('O', 'P', 'T', 'I'): if (word[1] == STRING_CONST('O', 'N', 'S', 0)) return verb::options; break; case STRING_CONST('P', 'A', 'T', 'C'): if (v[4] == 'H') return verb::patch; break; case STRING_CONST('P', 'O', 'S', 'T'): return verb::post; case STRING_CONST('P', 'R', 'O', 'P'): if (v.substr(4) == /*PROP*/"FIND"_sv) return verb::propfind; else if (v.substr(4) == /*PROP*/"PATCH"_sv) return verb::proppatch; break; case STRING_CONST('P', 'U', 'R', 'G'): if (v[4] == 'E') return verb::purge; break; case STRING_CONST('P', 'U', 'T', 0): return verb::put; case STRING_CONST('R', 'E', 'B', 'I'): if (word[1] == STRING_CONST('N', 'D', 0, 0)) return verb::rebind; break; case STRING_CONST('R', 'E', 'P', 'O'): if (word[1] == STRING_CONST('R', 'T', 0, 0)) return verb::report; break; case STRING_CONST('S', 'E', 'A', 'R'): if (word[1] == STRING_CONST('C', 'H', 0, 0)) return verb::search; break; case STRING_CONST('S', 'U', 'B', 'S'): if (v.substr(4) == /*SUBS*/"CRIBE"_sv) return verb::subscribe; break; case STRING_CONST('T', 'R', 'A', 'C'): if (v[4] == 'E') return verb::trace; break; case STRING_CONST('U', 'N', 'B', 'I'): if (word[1] == STRING_CONST('N', 'D', 0, 0)) return verb::unbind; break; case STRING_CONST('U', 'N', 'L', 'I'): if (word[1] == STRING_CONST('N', 'K', 0, 0)) return verb::unlink; break; case STRING_CONST('U', 'N', 'L', 'O'): if (word[1] == STRING_CONST('C', 'K', 0, 0)) return verb::unlock; break; case STRING_CONST('U', 'N', 'S', 'U'): if (v.substr(4) == /*UNSU*/"BSCRIBE"_sv) return verb::unsubscribe; break; } return verb::unknown; }
Another 32-bit variant
This is a slightly modified 32-bit procedure. It separately matches strings shorts string (0..4 bytes) and longer ones.
verb string_to_verb_v2(std::string_view v) { if (v.size() < 3 or v.size() > 13) return verb::unknown; union { char buf[13]; uint32_t word[2]; uint32_t value; }; value = 0; memcpy(buf, v.data(), v.size()); if (v.size() <= 4) { switch (value) { case STRING_CONST('G', 'E', 'T', 0): return verb::get; case STRING_CONST('H', 'E', 'A', 'D'): return verb::head; case STRING_CONST('P', 'O', 'S', 'T'): return verb::post; case STRING_CONST('P', 'U', 'T', 0): return verb::put; } switch (value) { case STRING_CONST('A', 'C', 'L', 0): return verb::acl; case STRING_CONST('B', 'I', 'N', 'D'): return verb::bind; case STRING_CONST('C', 'O', 'P', 'Y'): return verb::copy; case STRING_CONST('L', 'I', 'N', 'K'): return verb::link; case STRING_CONST('L', 'O', 'C', 'K'): return verb::lock; case STRING_CONST('M', 'O', 'V', 'E'): return verb::move; } } switch (value) { case STRING_CONST('C', 'H', 'E', 'C'): if (word[1] == STRING_CONST('K', 'O', 'U', 'T')) return verb::checkout; break; case STRING_CONST('C', 'O', 'N', 'N'): if (word[1] == STRING_CONST('E', 'C', 'T', 0)) return verb::connect; break; case STRING_CONST('D', 'E', 'L', 'E'): if (word[1] == STRING_CONST('T', 'E', 0, 0)) return verb::delete_; break; case STRING_CONST('M', '-', 'S', 'E'): if (word[1] == STRING_CONST('A', 'R', 'C', 'H')) return verb::msearch; break; case STRING_CONST('M', 'E', 'R', 'G'): if (word[1] == STRING_CONST('E', 0, 0, 0)) return verb::merge; break; case STRING_CONST('M', 'K', 'A', 'C'): if (v.substr(4) == /*MKAC*/"TIVITY"_sv) return verb::mkactivity; break; case STRING_CONST('M', 'K', 'C', 'A'): if (v.substr(4) == /*MKCA*/"LENDAR"_sv) return verb::mkcalendar; break; case STRING_CONST('M', 'K', 'C', 'O'): if (word[1] == STRING_CONST('L', 0, 0, 0)) return verb::mkcol; break; case STRING_CONST('N', 'O', 'T', 'I'): if (word[1] == STRING_CONST('F', 'Y', 0, 0)) return verb::notify; break; case STRING_CONST('O', 'P', 'T', 'I'): if (word[1] == STRING_CONST('O', 'N', 'S', 0)) return verb::options; break; case STRING_CONST('P', 'A', 'T', 'C'): if (v[4] == 'H') return verb::patch; break; case STRING_CONST('P', 'R', 'O', 'P'): if (v.substr(4) == /*PROP*/"FIND"_sv) return verb::propfind; else if (v.substr(4) == /*PROP*/"PATCH"_sv) return verb::proppatch; break; case STRING_CONST('P', 'U', 'R', 'G'): if (v[4] == 'E') return verb::purge; break; case STRING_CONST('R', 'E', 'B', 'I'): if (word[1] == STRING_CONST('N', 'D', 0, 0)) return verb::rebind; break; case STRING_CONST('R', 'E', 'P', 'O'): if (word[1] == STRING_CONST('R', 'T', 0, 0)) return verb::report; break; case STRING_CONST('S', 'E', 'A', 'R'): if (word[1] == STRING_CONST('C', 'H', 0, 0)) return verb::search; break; case STRING_CONST('S', 'U', 'B', 'S'): if (v.substr(4) == /*SUBS*/"CRIBE"_sv) return verb::subscribe; break; case STRING_CONST('T', 'R', 'A', 'C'): if (v[4] == 'E') return verb::trace; break; case STRING_CONST('U', 'N', 'B', 'I'): if (word[1] == STRING_CONST('N', 'D', 0, 0)) return verb::unbind; break; case STRING_CONST('U', 'N', 'L', 'I'): if (word[1] == STRING_CONST('N', 'K', 0, 0)) return verb::unlink; break; case STRING_CONST('U', 'N', 'L', 'O'): if (word[1] == STRING_CONST('C', 'K', 0, 0)) return verb::unlock; break; case STRING_CONST('U', 'N', 'S', 'U'): if (v.substr(4) == /*UNSU*/"BSCRIBE"_sv) return verb::unsubscribe; break; } return verb::unknown; }
Below is MPH implementation manually adjusted to return the value assigned to given key, not only the information whether key is valid or not.
inline unsigned int perfect_hash::hash(std::string_view str) { static const unsigned char asso_values[] = { 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 10, 5, 15, 0, 5, 25, 0, 10, 70, 15, 70, 0, 0, 20, 0, 5, 25, 20, 0, 0, 0, 40, 70, 70, 70, 20, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70 }; auto hval = str.size(); switch (hval) { default: hval += asso_values[static_cast<unsigned char>(str[3]+1)]; /*FALLTHROUGH*/ case 3: hval += asso_values[static_cast<unsigned char>(str[2])]; /*FALLTHROUGH*/ case 2: case 1: hval += asso_values[static_cast<unsigned char>(str[0])]; break; } return hval; } perfect_hash::verb perfect_hash::string_to_verb(std::string_view str) { enum { TOTAL_KEYWORDS = 33, MIN_WORD_LENGTH = 3, MAX_WORD_LENGTH = 11, MIN_HASH_VALUE = 3, MAX_HASH_VALUE = 69 }; static std::string_view wordlist[] = { "", "", "", "GET", "", "", "", "", "PUT", "POST", "PATCH", "UNLOCK", "", "ACL", "SUBSCRIBE", "TRACE", "SEARCH", "", "", "LOCK", "MKACTIVITY", "UNLINK", "OPTIONS", "", "LINK", "MKCOL", "UNBIND", "", "CHECKOUT", "HEAD", "MKCALENDAR", "DELETE", "", "M-SEARCH", "BIND", "MERGE", "REPORT", "", "PROPFIND", "PROPPATCH", "PURGE", "NOTIFY", "CONNECT", "", "COPY", "", "REBIND", "", "", "", "", "UNSUBSCRIBE", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "MOVE" }; static verb values[] = { verb::unknown, verb::unknown, verb::unknown, verb::get, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::put, verb::post, verb::patch, verb::unlock, verb::unknown, verb::acl, verb::subscribe, verb::trace, verb::search, verb::unknown, verb::unknown, verb::lock, verb::mkactivity, verb::unlink, verb::options, verb::unknown, verb::link, verb::mkcol, verb::unbind, verb::unknown, verb::checkout, verb::head, verb::mkcalendar, verb::delete_, verb::unknown, verb::msearch, verb::bind, verb::merge, verb::report, verb::unknown, verb::propfind, verb::proppatch, verb::purge, verb::notify, verb::connect, verb::unknown, verb::copy, verb::unknown, verb::rebind, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unsubscribe, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::unknown, verb::move }; if (str.size() <= MAX_WORD_LENGTH && str.size() >= MIN_WORD_LENGTH) { const unsigned int key = hash(str); if (key <= MAX_HASH_VALUE) { if (wordlist[key] == str) return values[key]; } } return verb::unknown; }