Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign

patch : from std::map replace to hashmap

<< < (4/9) > >>

ollydbg:
Nice!
So, you have implemented a hash function for wxString when using gnu hash map?

Here is my test result, all the test was built in -O2 optimization.

Here is the result for 9 replacement rules:


--- Code: ---stdMap 1 : 2953
stdMap 2 : 2953
stdMap 3 : 2953
stdMap 4 : 2969
stdMap 5 : 2953

---------------

hashMap 1 : 3000
hashMap 2 : 2968
hashMap 3 : 2969
hashMap 4 : 2969
hashMap 5 : 2969

--- End code ---

with 16 map entries. the  result is listed below:

--- Code: ---stdMap 1 : 3079
stdMap 2 : 3062
stdMap 3 : 3078
stdMap 4 : 3078
stdMap 5 : 3063

---------------

hashMap 1 : 2953
hashMap 2 : 2953
hashMap 3 : 2969
hashMap 4 : 2953
hashMap 5 : 2984

--- End code ---

The conclusion is: We should use gnu hash wxString map.

Loaden:

--- Quote from: ollydbg on March 22, 2010, 05:36:29 am ---Nice!
So, you have implemented a hash function for wxString when using gnu hash map?

Here is my test result, all the test was built in -O2 optimization.

Here is the result for 9 replacement rules:

--- End quote ---
Try change the hash function TO:

--- Code: ---namespace __gnu_cxx
{
template<> struct hash< wxString >
{
    size_t operator()( const wxString& x ) const
    {
        unsigned long __h = 0;
        for (const wxChar* p = x.c_str(); *p; ++p)
            __h = 5 * __h + *p;
        return size_t(__h);
    }
};
}
--- End code ---

Loaden:
Please test this demo, -O2:

--- Code: ---#include <iostream>
#include <map>

#define _BACKWARD_BACKWARD_WARNING_H 0

#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif

#include <wx/string.h>
#include <wx/timer.h>

const size_t LOOPS = 5;
const size_t TIMES = 10000000;
const wxString FINDKEY = _T("_GLIBCXX_END_NAMESPACE_TR1");

namespace std
{
using namespace __gnu_cxx;
}

namespace __gnu_cxx
{
template<> struct hash< wxString >
{
    size_t operator()( const wxString& x ) const
    {
        unsigned long __h = 0;
        for (const wxChar* p = x.c_str(); *p; ++p)
            __h = 5 * __h + *p;
        return size_t(__h);
    }
};
}

int main()
{
    std::map<wxString, wxString> stdMap;
    stdMap[_T("_GLIBCXX_STD")] = _T("std");
    stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    stdMap[_T("_STD_END")] = _T("}");
   
    std::hash_map<wxString, wxString> hashMap;
    hashMap[_T("_GLIBCXX_STD")] = _T("std");
    hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    hashMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    hashMap[_T("_STD_END")] = _T("}");

    int stdTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) stdMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "stdMap " << i + 1 << " : " << time << std::endl;
        stdTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "stdMap Total Time: " << stdTotalTime << std::endl;
    double stdAverage = stdTotalTime / LOOPS;
    std::cout << "stdMap Average Time: " << stdAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;

    int hashTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) hashMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "hashMap " << i + 1 << " : " << time << std::endl;
        hashTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "hashMap Total Time: " << hashTotalTime << std::endl;
    double hashAverage = hashTotalTime / LOOPS;
    std::cout << "hashMap Average Time: " << hashAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;
   
    std::cout << "(stdAverage - hashAverage) / stdAverage = " << (stdAverage - hashAverage) / stdAverage;
    std::cout << std::endl;

    return 0;
}
--- End code ---

--- Code: ---stdMap 1 : 3375
stdMap 2 : 3407
stdMap 3 : 3390
stdMap 4 : 3375
stdMap 5 : 3407

stdMap Total Time: 16954
stdMap Average Time: 3390
------------------------------

hashMap 1 : 1625
hashMap 2 : 1625
hashMap 3 : 1625
hashMap 4 : 1625
hashMap 5 : 1625

hashMap Total Time: 8125
hashMap Average Time: 1625
------------------------------

(stdAverage - hashAverage) / stdAverage = 0.520649

Process returned 0 (0x0)   execution time : 25.219 s
Press any key to continue.
--- End code ---

18 replacement:

--- Code: ---#include <iostream>
#include <map>

#define _BACKWARD_BACKWARD_WARNING_H 0

#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif

#include <wx/string.h>
#include <wx/timer.h>

const size_t LOOPS = 5;
const size_t TIMES = 10000000;
const wxString FINDKEY = _T("_GLIBCXX_END_NAMESPACE_TR1");

namespace std
{
using namespace __gnu_cxx;
}

namespace __gnu_cxx
{
template<> struct hash< wxString >
{
    size_t operator()( const wxString& x ) const
    {
        unsigned long __h = 0;
        for (const wxChar* p = x.c_str(); *p; ++p)
            __h = 5 * __h + *p;
        return size_t(__h);
    }
};
}

int main()
{
    std::map<wxString, wxString> stdMap;
    stdMap[_T("_GLIBCXX_STD")] = _T("std");
    stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    stdMap[_T("_STD_END")] = _T("}");
    stdMap[_T("_GLIBCXX_STD2")] = _T("2std");
    stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
    stdMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
    stdMap[_T("_STD_END2")] = _T("2}");
   
    std::hash_map<wxString, wxString> hashMap;
    hashMap[_T("_GLIBCXX_STD")] = _T("std");
    hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    hashMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    hashMap[_T("_STD_END")] = _T("}");
    hashMap[_T("_GLIBCXX_STD2")] = _T("2std");
    hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
    hashMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
    hashMap[_T("_STD_END2")] = _T("2}");

    int stdTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) stdMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "stdMap " << i + 1 << " : " << time << std::endl;
        stdTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "stdMap Total Time: " << stdTotalTime << std::endl;
    double stdAverage = stdTotalTime / LOOPS;
    std::cout << "stdMap Average Time: " << stdAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;

    int hashTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) hashMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "hashMap " << i + 1 << " : " << time << std::endl;
        hashTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "hashMap Total Time: " << hashTotalTime << std::endl;
    double hashAverage = hashTotalTime / LOOPS;
    std::cout << "hashMap Average Time: " << hashAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;
   
    std::cout << "(stdAverage - hashAverage) / stdAverage = " << (stdAverage - hashAverage) / stdAverage;
    std::cout << std::endl;

    return 0;
}

--- End code ---

--- Code: ---stdMap 1 : 4265
stdMap 2 : 4266
stdMap 3 : 4265
stdMap 4 : 4297
stdMap 5 : 4266

stdMap Total Time: 21359
stdMap Average Time: 4271
------------------------------

hashMap 1 : 1625
hashMap 2 : 1625
hashMap 3 : 1625
hashMap 4 : 1625
hashMap 5 : 1625

hashMap Total Time: 8125
hashMap Average Time: 1625
------------------------------

(stdAverage - hashAverage) / stdAverage = 0.619527

Process returned 0 (0x0)   execution time : 29.609 s
Press any key to continue.
--- End code ---

Jenna:
I am (and was) aware of std::hash_map, but I did not use it, because it's declared as deprecated and just supressing the warnings is not a real option to me, because it might supress warnings about other deprecated headers too and what's more it might break build in newer versions of gcc.

Loaden:

--- Quote from: jens on March 22, 2010, 07:08:53 am ---I am (and was) aware of std::hash_map, but I did not use it, because it's declared as deprecated and just supressing the warnings is not a real option to me, because it might supress warnings about other deprecated headers too and what's more it might break build in newer versions of gcc.

--- End quote ---
OK, I think we can use unordered_map.

--- Code: ---This file includes at least one deprecated or antiquated header which \ may be removed without further notice at a future date. Please use a \ non-deprecated interface with equivalent functionality instead. For a \ listing of replacement headers and interfaces, consult the file \ backward_warning.h. To disable this warning use -Wno-deprecated.


/* A list of valid replacements is as follows:
Use: Instead of:
<sstream>, basic_stringbuf <strstream>, strstreambuf
<sstream>, basic_istringstream <strstream>, istrstream
<sstream>, basic_ostringstream <strstream>, ostrstream
<sstream>, basic_stringstream <strstream>, strstream
<unordered_set>, unordered_set <ext/hash_set>, hash_set
<unordered_set>, unordered_multiset <ext/hash_set>, hash_multiset
<unordered_map>, unordered_map <ext/hash_set>, hash_map
<unordered_map>, unordered_multimap <ext/hash_set>, hash_multimap
<functional>, bind <functional>, binder1st
<functional>, bind <functional>, binder2nd
<functional>, bind <functional>, bind1st
<functional>, bind <functional>, bind2nd
<memory>, unique_ptr <memory>, auto_ptr
*/

--- End code ---

Here is the demo, need -std=gnu++0x option

--- Code: ---#include <iostream>
#include <map>
#include <unordered_map>

#include <wx/string.h>
#include <wx/timer.h>

const size_t LOOPS = 5;
const size_t TIMES = 10000000;
const wxString FINDKEY = _T("_GLIBCXX_END_NAMESPACE_TR1");

namespace std
{
template<> struct hash< wxString >
{
    size_t operator()( const wxString& x ) const
    {
        unsigned long __h = 0;
        for (const wxChar* p = x.c_str(); *p; ++p)
            __h = 5 * __h + *p;
        return size_t(__h);
    }
};
}

int main()
{
    std::map<wxString, wxString> stdMap;
    stdMap[_T("_GLIBCXX_STD")] = _T("std");
    stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    stdMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    stdMap[_T("_STD_END")] = _T("}");
   
    std::unordered_map<wxString, wxString> hashMap;
    hashMap[_T("_GLIBCXX_STD")] = _T("std");
    hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    hashMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    hashMap[_T("_STD_BEGIN")] = _T("-namespace std {");
    hashMap[_T("_STD_END")] = _T("}");

    int stdTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) stdMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "stdMap " << i + 1 << " : " << time << std::endl;
        stdTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "stdMap Total Time: " << stdTotalTime << std::endl;
    double stdAverage = stdTotalTime / LOOPS;
    std::cout << "stdMap Average Time: " << stdAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;

    int hashTotalTime = 0;
    for (size_t i = 0; i < LOOPS; ++i)
    {
        wxStopWatch sw;
        for (size_t j = 0; j < TIMES; ++j) hashMap.find(FINDKEY);
        sw.Pause();
        int time = sw.Time();
        std::cout << "hashMap " << i + 1 << " : " << time << std::endl;
        hashTotalTime += time;
    }
    std::cout << std::endl;
    std::cout << "hashMap Total Time: " << hashTotalTime << std::endl;
    double hashAverage = hashTotalTime / LOOPS;
    std::cout << "hashMap Average Time: " << hashAverage << std::endl;
    std::cout << "------------------------------\n" << std::endl;
   
    std::cout << "(stdAverage - hashAverage) / stdAverage = " << (stdAverage - hashAverage) / stdAverage;
    std::cout << std::endl;

    return 0;
}
--- End code ---

--- Code: ---stdMap 1 : 1828
stdMap 2 : 1828
stdMap 3 : 1812
stdMap 4 : 1829
stdMap 5 : 1812

stdMap Total Time: 9109
stdMap Average Time: 1821
------------------------------

hashMap 1 : 703
hashMap 2 : 703
hashMap 3 : 703
hashMap 4 : 688
hashMap 5 : 703

hashMap Total Time: 3500
hashMap Average Time: 700
------------------------------

(stdAverage - hashAverage) / stdAverage = 0.615596

Process returned 0 (0x0)   execution time : 12.797 s
Press any key to continue.
--- End code ---

Navigation

[0] Message Index

[#] Next page

[*] Previous page