SERVER-7639 fast StringMap class, no std::string copies

1 files changed, 139 insertions, 0 deletions

diff --git a/src/mongo/util/string_map_test.cpp b/src/mongo/util/string_map_test.cpp
new file mode 100644
index 00000000000..20fa9e67ec3
--- /dev/null
+++ b/src/mongo/util/string_map_test.cpp
@@ -0,0 +1,139 @@
+// string_map_test.cpp
+
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/platform/random.h"
+#include "mongo/platform/unordered_map.h"
+#include "mongo/util/string_map.h"
+#include "mongo/util/log.h"
+#include "mongo/util/timer.h"
+
+namespace {
+    using namespace mongo;
+
+    TEST(StringMapTest, Hash1) {
+        StringMapDefaultHash h;
+        ASSERT_EQUALS( h(""), h("") );
+        ASSERT_EQUALS( h("a"), h("a") );
+        ASSERT_EQUALS( h("abc"), h("abc") );
+
+        ASSERT_NOT_EQUALS( h(""), h("a") );
+        ASSERT_NOT_EQUALS( h("a"), h("ab") );
+
+        ASSERT_NOT_EQUALS( h("foo28"), h("foo35") );
+    }
+
+#define equalsBothWays(a,b) \
+    ASSERT_TRUE( e( (a), (b) ) );  \
+    ASSERT_TRUE( e( (b), (a) ) );
+
+#define notEqualsBothWays(a,b) \
+    ASSERT_FALSE( e( (a), (b) ) );  \
+    ASSERT_FALSE( e( (b), (a) ) );
+
+    TEST(StringMapTest, Equals1 ){
+        StringMapDefaultEqual e;
+
+        equalsBothWays( "", "" );
+        equalsBothWays( "a", "a" );
+        equalsBothWays( "bbbbb", "bbbbb" );
+
+        notEqualsBothWays( "", "a" );
+        notEqualsBothWays( "a", "b" );
+        notEqualsBothWays( "abc", "def" );
+        notEqualsBothWays( "abc", "defasdasd" );
+    }
+
+    TEST(StringMapTest, Basic1) {
+        StringMap<int> m;
+        ASSERT_EQUALS( 0U, m.size() );
+        m["eliot"] = 5;
+        ASSERT_EQUALS( 5, m["eliot"] );
+        ASSERT_EQUALS( 1U, m.size() );
+    }
+
+    TEST(StringMapTest, Big1) {
+        StringMap<int> m;
+        char buf[64];
+
+        for ( int i=0; i<10000; i++ ) {
+            sprintf( buf, "foo%d", i );
+            m[buf] = i;
+        }
+
+        for ( int i=0; i<10000; i++ ) {
+            sprintf( buf, "foo%d", i );
+            ASSERT_EQUALS( m[buf], i );
+        }
+    }
+
+    TEST(StringMapTest, find1 ) {
+        StringMap<int> m;
+
+        ASSERT_TRUE( m.end() == m.find( "foo" ) );
+
+        m["foo"] = 5;
+        StringMap<int>::const_iterator i = m.find( "foo" );
+        ASSERT_TRUE( i != m.end() );
+        ASSERT_EQUALS( 5, i->second );
+        ASSERT_EQUALS( "foo", i->first );
+        i++;
+        ASSERT_TRUE( i == m.end() );
+    }
+
+
+    template<typename M>
+    unsigned long long test_perf( M& m ) {
+        Timer t;
+
+        PseudoRandom r(17);
+        char buf[64];
+        for ( int i = 0; i< 100000; i++ ) {
+            sprintf( buf, "%dfoo%d", r.nextInt32(), r.nextInt32() );
+            m[buf] = i;
+            ASSERT_EQUALS( i, m[buf] );
+        }
+
+        return t.micros();
+    }
+
+    TEST( StringMapTest, perf1 ) {
+        unsigned long long standard = 0;
+        unsigned long long unordered = 0;
+        unsigned long long custom = 0;
+        for ( int i = 0; i < 5; i++ ) {
+            {
+                std::map<string,int> m;
+                standard += test_perf( m );
+            }
+            {
+                unordered_map<string,int> m;
+                unordered += test_perf( m );
+            }
+            {
+                StringMap<int> m;
+                custom += test_perf( m );
+            }
+        }
+
+        log() << "std::map :\t" << standard << std::endl;
+        log() << "unordered:\t" << unordered << std::endl;
+        log() << "StringMap:\t" << custom << std::endl;
+        ASSERT_LESS_THAN( custom, standard );
+    }
+}