mongodb/mongo-csharp-driver — pull request #113 by optimiz3 (2012-06-05 00:47:00+00:00)
Title: Improve deserialization performance by > 40% in the normal case and > 25% in the worst case.

Profiling showed that during deserialization, significant time was being spent in the following functions:
1. System.Type.IsAssignableFrom(class System.Type)	14.35%
2. MongoDB.Bson.IO.BsonBinaryReader.ReadBsonType() 11.46%
3. MongoDB.Bson.Serialization.BsonClassMap.GetMemberMapIndexForElement(string) 7.68%

This change addresses all 3 items:
1. Fixed by placing a quick type check before the hot path IsAssignableFrom calls. In most cases the types are equivalent which eliminates the call to IsAssignableFrom.
2/3. Most of the time in ReadBsonType is due to a call to ReadCString. All of the calls to GetMemberMapIndexForElement use the value returned by ReadCString. To improve this, I've implemented a trie (http://en.wikipedia.org/wiki/Trie) optimized for mapping input bytes sequences directly to result values specified by the caller. In the case of BsonClassMapSerializer, the trie directly maps the input binary UTF8 representation of element names to member map indexes. This completely eliminates all dictionary lookups, UTF8 string conversions, intermediary memory allocation, and does so in O(m) time where m is the length of the input string. Contrast this with the existing implementation where there are 5 (!!!) O(m) operations (1. Find the null byte, 2. Count the number of UTF8 characters, 3. Decode the UTF8 characters into a string, 4. Hash the string, 5. Compare the string the key in the hashtable bucket). Additionally, I’ve factored the trie so any deserializer can make use of one when decoding to immediately switch to the correct state when decoding.

Additionally I’ve also implemented two other minor improvements:
1. Replaced the lookup table based GetLeastSignificantBit implementation in BsonClassMapSerializer with a binary search based one. This is significantly faster on .Net because array accesses require an indirection and a managed bounds check. In my own side by side testing, the binary search based one is 40-50% faster.
2. Added the readonly attribute to _declaredMemberMaps in BsonClassMap and cleaned up the initialization of this value. Minor improvement but the field is now consistent with _allMemberMaps and fewer copies happen during construction.

Raw performance profiling data:

Run	Iterations	master	optimiz3	Improvement	master_multi	optimiz3_multi	Improvement
1	50000	15.1557587	11.1471546	26%	19.5359217	11.3929297	42%
2	50000	14.8104048	11.2266639	24%	19.579202	11.3677135	42%
3	50000	14.8222835	10.9488162	26%	19.5564535	11.6768085	40%
Average	50000	14.92948233	11.1075449	26%	19.5571924	11.47915057	41%

master/optimiz3 = runs with single character field names; master_multi/optimiz3_multi = runs with multi-character field names.