map hash_map unordered_map 性能测试

拼搏现实的明天。 2022-08-13 14:40 230阅读 0赞

测试条件：

gcc version 4.2.1 20070719  \[FreeBSD\]

FreeBSD  7.2-RELEASE \#0: Fri May  1 07:18:07 UTC 2009     root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  amd64  
Intel(R) Xeon(R) CPU           E5620  @ 2.40GHz 16核

测试程序说明：

先准备好n个字符串随机的MD5字符串做为key，然后分别对3个容器进行插入、遍历、查找、删除操作。

例如，n=100的时候，插入是指插入100个随机MD5 key；遍历是指对容器遍历一次；查找是指分别对这个100个随机的MD5 key做查找操作（即查找100次）；删除是指挨个删除这个100个随机MD5 key。

测试数据如下表：

<table style="word-wrap:break-word"> 
 <tbody style="word-wrap:break-word"> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">插入，单位us</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1M</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10M</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">241</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">2833</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">35888</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">381214</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4439088</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">62233380</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::ext/hash_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">97</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1667</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">16466</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">146025</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1788446</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">18512639</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::tr1::unordered_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">77</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">772</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">8052</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">53094</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">658312</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">7429297</td> 
  </tr> 
 </tbody> 
</table>

<table style="word-wrap:break-word"> 
 <tbody style="word-wrap:break-word"> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">遍历，单位us</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1M</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10M</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">11</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">76</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">842</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">11603</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">155700</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1771906</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::ext/hash_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">47</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">430</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4218</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">39880</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">470344</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4781575</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::tr1::unordered_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">2</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">2</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1</td> 
  </tr> 
 </tbody> 
</table>

<table style="word-wrap:break-word"> 
 <tbody style="word-wrap:break-word"> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">查找，单位us</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1M</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10M</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">156</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">2111</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">30456</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">258709</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4100260</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">59064394</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::ext/hash_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">77</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">774</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">8056</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">56974</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">660231</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">7705527</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::tr1::unordered_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">77</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">772</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">8051</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">54456</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">659537</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">7600263</td> 
  </tr> 
 </tbody> 
</table>

<table style="word-wrap:break-word"> 
 <tbody style="word-wrap:break-word"> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">删除，单位us</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">100K</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">1M</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10M</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px"><span style="word-wrap:break-word; border-collapse:separate; font-family:Tahoma; border-spacing:0px">291</span></td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">3641</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">49584</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">472414</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">6675897</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">92491113</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::ext/hash_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px"><span style="word-wrap:break-word; border-collapse:separate; font-family:Tahoma; border-spacing:0px">89</span></td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">869</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">9068</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">86524</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">964767</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">10372650</td> 
  </tr> 
  <tr style="word-wrap:break-word"> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">std::tr1::unordered_map</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px"><span style="word-wrap:break-word; border-collapse:separate; font-family:Tahoma; border-spacing:0px">49</span></td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">480</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4879</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">33087</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">395098</td> 
   <td style="word-wrap:break-word; margin:0px; padding:0px">4369617</td> 
  </tr> 
 </tbody> 
</table>

结论：

1. std::tr1::unordered\_map 与 std::ext/hash\_map

任何情况下，如果要在这两个容器之间选择的话， 我们毫不犹豫应该选择 unordered\_map。因为他的性能在上述4中操作中均优于 hash\_map，甚至可以说远远优于 hash\_map。

2.  std::tr1::unordered\_map 与 std::map

map的性能总体来说是最差的。但是， 当我们需要一个有序的关联容器的时候，我们必须选择std::map，因为 unordered\_map 内部元素不是有序的，这一点从名字都可以看出来。除此之外都应该选择 unordered\_map 。

3. 上述测试中，unordered\_map 的遍历性能几乎是常数级别的，与常识不太相符，需要再研究研究。

#include <iostream>
    #include <string>
    #include <sstream>
    #include <list>
    #include <map>
    #include <sys/time.h>
    #include <ext/hash_map>
    #include <tr1/unordered_map>
    
    namespace zl
    { //{
         {
         {
        struct equal_to
        {
            bool operator()(const char* s1, const char* s2) const
            {
                return strcmp(s1, s2) == 0;
            }
        };
     
        struct hash_string
            : public std::unary_function<std::string, std::size_t>
            {
                std::size_t
                    operator()(const std::string& __s) const
    #ifdef __linux__
                    { return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
    #else
                    { return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
    #endif
            };
    
        
        struct hash_charptr
            : public std::unary_function<const char*, std::size_t>
            {
                std::size_t
                    operator()(const char* __s) const
    #ifdef __linux__
                    { return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
    #else
                    { return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
    #endif
            };
    }//}}}
    
    typedef std::list<std::string> string_list;
    typedef std::map<std::string, int> string_map;
    typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
    typedef std::tr1::unordered_map<std::string, int> string_unordered_map;
    
    void fill_list(string_list& slist, size_t count);
    uint64_t current_usec();
    
    int main( int argc, char* argv[] )
    {
        if (argc != 2 && argc != 3)
        {
            fprintf(stderr, "Usage:%s test_count rehash\n", argv[0]);
            fprintf(stderr, "For example:%s 10000 rehash\n", argv[0]);
            return -1;
        }
    
        size_t count = atoi(argv[1]);
        bool rehash = false;
        if (argc == 3)
        {
            rehash = true;
        }
    
        string_map smap;
        string_hash_map shash_map;
        string_unordered_map sunordered_map;
    
        if (rehash)
        {
            sunordered_map.rehash(count);
        }
    
        string_list slist;
        fill_list(slist, count);
    
        uint64_t start = 0;
        uint64_t end = 0;
    
        uint64_t map_insert_us = 0;
        uint64_t hash_map_insert_us = 0;
        uint64_t unordered_map_insert_us = 0;
    
        uint64_t map_traverse_us = 0;
        uint64_t hash_map_traverse_us = 0;
        uint64_t unordered_map_traverse_us = 0;
    
        uint64_t map_find_us = 0;
        uint64_t hash_map_find_us = 0;
        uint64_t unordered_map_find_us = 0;
    
        uint64_t map_delete_us = 0;
        uint64_t hash_map_delete_us = 0;
        uint64_t unordered_map_delete_us = 0;
    
    
    
        // Insert test
        {//{
         {
         {
            string_list::iterator it(slist.begin());
            string_list::iterator ite(slist.end());
    
            //map insert
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                smap[*it] = i;
            }
            end = current_usec();
            map_insert_us = end - start;
    
            //hash_map insert
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map[*it] = i;
            }
            end = current_usec();
            hash_map_insert_us = end - start;
    
            //unordered_map insert
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map[*it] = i;
            }
            end = current_usec();
            unordered_map_insert_us = end - start;
        }//}}}
    
        // Traverse test
        {//{
         {
         {
            //map traverse 
            {
                string_map::iterator it(smap.begin());
                string_map::iterator ite(smap.end());
                start = current_usec();
                for (int i = 0; it != ite; ++it)
                {
                    i++;
                }
                end = current_usec();
                map_traverse_us = end - start;
            }
    
            //hash_map traverse 
            {
                string_hash_map::iterator it(shash_map.begin());
                string_hash_map::iterator ite(shash_map.end());
                start = current_usec();
                for (int i = 0; it != ite; ++it)
                {
                    i++;
                }
                end = current_usec();
                hash_map_traverse_us = end - start;
            }
    
            //unordered_map traverse 
            {
                string_unordered_map::iterator it(sunordered_map.begin());
                string_unordered_map::iterator ite(sunordered_map.end());
                start = current_usec();
                for (int i = 0; it != ite; ++it)
                {
                    i++;
                }
                end = current_usec();
                unordered_map_traverse_us = end - start;
            }
        }//}}}
    
        // Find test
        {//{
         {
         {
            string_list::iterator it(slist.begin());
            string_list::iterator ite(slist.end());
    
            //map find
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                smap[*it] = i;
            }
            end = current_usec();
            map_find_us = end - start;
    
            //hash_map find
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map[*it] = i;
            }
            end = current_usec();
            hash_map_find_us = end - start;
    
            //unordered_map find
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map[*it] = i;
            }
            end = current_usec();
            unordered_map_find_us = end - start;
        }//}}}
    
        // Delete test
        {//{
         {
         {
            string_list::iterator it(slist.begin());
            string_list::iterator ite(slist.end());
    
            //map delete
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                smap.erase(*it);
            }
            end = current_usec();
            map_delete_us = end - start;
    
            //hash_map delete
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map.erase(*it);
            }
            end = current_usec();
            hash_map_delete_us = end - start;
    
            //unordered_map delete
            it = slist.begin();
            start = current_usec();
            for (int i = 0; it != ite; ++it, ++i)
            {
                shash_map.erase(*it);
            }
            end = current_usec();
            unordered_map_delete_us = end - start;
        }//}}}
    
        //stat output
        std::cout << " insert, count " << count << std::endl;
        std::cout << " std::map " << map_insert_us << " us\n";
        std::cout << " std::ext/hash_map " << hash_map_insert_us << " us\n";
        std::cout << "std::tr1::unordered_map " << unordered_map_insert_us << " us\n";
    
        std::cout << "\n";
        std::cout << " traverse, count " << count << std::endl;
        std::cout << " std::map " << map_traverse_us << " us\n";
        std::cout << " std::ext/hash_map " << hash_map_traverse_us << " us\n";
        std::cout << "std::tr1::unordered_map " << unordered_map_traverse_us << " us\n";
    
        std::cout << "\n";
        std::cout << " find, count " << count << std::endl;
        std::cout << " std::map " << map_find_us << " us\n";
        std::cout << " std::ext/hash_map " << hash_map_find_us << " us\n";
        std::cout << "std::tr1::unordered_map " << unordered_map_find_us << " us\n";
    
        std::cout << "\n";
        std::cout << " delete, count " << count << std::endl;
        std::cout << " std::map " << map_delete_us << " us\n";
        std::cout << " std::ext/hash_map " << hash_map_delete_us << " us\n";
        std::cout << "std::tr1::unordered_map " << unordered_map_delete_us << " us\n";
    
         
        return 0;
    }
    
    void fill_list(string_list& slist, size_t count)
    {
        for (size_t i = 0; i < count; ++i)
        {
            std::ostringstream oss;
            oss << i;
            //slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
            slist.push_back(oss.str());
        }
    }
    
    
    uint64_t current_usec()
    {
        struct timeval tv;
        gettimeofday( &tv, NULL );
        return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
    }