3 ms·
JSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member. Any scenario wher
by optimiz3 13y ago
JSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member.
Any scenario where you decode {k,v} pairs benefits from this.
- nly 13y agoWhy do you need prefixes for that? Sounds like the perfect usecase for a hash table or a precomputed perfect hash function.
- optimiz3 13y agoYou pay for computing a hash function over directly walking to the next node. EDIT: Here you go. Some work I contributed a while ago when we were using Mongo. Replace hash table with a TRIE, deserialization performance goes up 40%. Because you don't need to decode a string, hash it, and then hit a hash table. https://github.com/mongodb/mongo-csharp-driver/commit/0b78790af8f510d588a2b7d5478f75290a649bf7 https://github.com/mongodb/mongo-csharp-driver/commit/0b7879...
- nly 13y agoPerfect hash functions are ridiculously cheap. Completely different beasts to those designed to operate as good hashers for all inputs.
- optimiz3 13y agoHow so? Perfect hash functions only work when all possible inputs are known.
- sp332 13y agoSomething odd about that commit message... You know that O(m) is equivalent to 5 * O(m) right? Any constant multiplier will have the same big-O value.
- optimiz3 13y agoWhile it is true that asymptotically 5 * O(m) equals O(m), in practice 5 * O(m) is still 5x slower. EDIT (reply threshold): "That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way." Now you're just being pedantic.
- sp332 13y agoThat's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way.