3 ms·
You 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.
by optimiz3 13y ago
You 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.