Author Topic: patch : from std::map replace to hashmap (Read 49484 times)

Loaden · « **on:** March 21, 2010, 01:21:02 pm »

Hello everyone, I created a patch: it can enable CC faster.
Before, CC macro replaced rules use std::map<wxString, wxString>, Like this:

Code

static ConfigManagerContainer::StringToStringMap s_Replacements;

Now, I change it to :

Code

#include <wx/hashmap.h>
WX_DECLARE_STRING_HASH_MAP(wxString, wxStringHashMap);
...
static wxStringHashMap s_HashReplacements;

This is a test code, the compiler is VC10.

Code

#include <windows.h>
#include <winbase.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>

using namespace std;

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}

This is a test result：

Code

9 repl rules:

std::map<wxString, wxString> :
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.719 seconds).
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.625 seconds).
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.656 seconds).
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.609 seconds).
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.906 seconds).
Parsing stage done (165 total parsed files, 47380 tokens in 0 minute(s), 4.656 seconds).
Total Time: 28.171
Average: 4.70

wxStringHashMap :
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.609 seconds).
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.500 seconds).
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.500 seconds).
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.547 seconds).
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.500 seconds).
Parsing stage done (165 total parsed files, 47320 tokens in 0 minute(s), 4.516 seconds).
Total Time: 27.172
Average: 4.53
Rate: (4.70 - 4.53) / 4.70 = 3.6%


18 repl rules:

std::map<wxString, wxString> :
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.47 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.46 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.62 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.63 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.62 seconds).
Total Time: 22.8
Average: 4.53

wxStringHashMap :
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.922 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.938 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.937 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.938 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.953 seconds).
Total Time: 19.688
Average: 3.9376
Rate: (4.53 - 3.9376) / 4.53 = 13.1%

MODIFY：Rename static member variable s_HashReplacements TO s_Replacements

[attachment deleted by admin]

ollydbg · « **Reply #1 on:** March 21, 2010, 03:46:39 pm »

In fact, we have discussed this change from the stand-map to hash-map in this forum several months ago.
As far As I can remember, oBFusCATed has suggest using a hashmap.

Today, you have implement it, so I really appreciate your effort and contribution. I have downloaded and test it in my local, it did work fine.

I hope using the hashmap can boost the performance, as loaden said, it can improve about 13.1%.

Jenna · « **Reply #2 on:** March 21, 2010, 03:56:38 pm »

Here are some test on linux:

I tested it with C::B build with automake-system and inside C::B, I used Loaden's sample-code and the linux 2.6.29 kernel-sources to test.
There is a big difference between automake and C::B-build code, but not between std::map and wxHashmap, automake uses -O2 if I remember right (in fact in some cases the patched C::B was slower, but I think that is statistically noise).

Code

kernel:

build with automake (trunk)

Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 14.438 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 15.590 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 11.838 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 17.893 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 14.574 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 13.328 seconds).
                                                      average: 1 minute     14.610 seconds

build with automake (patched)

Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 13.465 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 13.550 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 16.289 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 16.961 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 14.989 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 1 minute(s), 18.696 seconds).
                                                      average: 1 minute     15.658 seconds

                                                     
build inside C::B (trunk)

Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 28.661 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 28.677 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 27.898 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 29.919 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 25.487 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 26.787 seconds).
                                                      average: 2 minutes    27.905 seconds
build inside C::B (patched)

Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 26.98 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 26.431 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 23.28 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 22.661 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 25.386 seconds).
Parsing stage done (22398 total parsed files, 905754 tokens in 2 minute(s), 22.730 seconds).
                                                      average: 2 minutes    24.578 seconds
	

sample-code:

build with automake (trunk)

Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.395 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.330 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.370 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.342 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.327 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.365 seconds).
                                                               average: 0.355 seconds

build with automake (patched)

Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.379 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.330 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.358 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.338 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.346 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 0.327 seconds).
                                                               average: 0.346 seconds

build inside C::B (trunk)

Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.195 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.135 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.135 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.153 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.153 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.133 seconds).
                                                               average: 1,151 seconds

build inside C::B (patched)

Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.117 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.75 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.51 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.73 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.74 seconds).
Parsing stage done (52 total parsed files, 27554 tokens in 0 minute(s), 1.71 seconds).
                                                               average: 1.593 seconds

ollydbg · « **Reply #3 on:** March 21, 2010, 04:05:32 pm »

@jens, here is Loaden's test result he send to me by email.

Code

18repl:

STD:
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.47 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.46 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.62 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.63 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 4.62 seconds).
Total: 22.8
AVG: 4.53

HASH:
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.922 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.938 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.937 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.938 seconds).
Parsing stage done (155 total parsed files, 41958 tokens in 0 minute(s), 3.953 seconds).
Total: 19.688
Avg: 3.9376
(4.53 - 3.9376) / 4.53 = 13.1%

He use 18 replacement rules.
I personally think that the more the replacement rules we use, the more benefit we can get by using hashmap.

You can compare with codelite's replacement rule:
Re: vector<int> is OK, but string or wstring no-work.
There are a lot of replacement rules.

Loaden · « **Reply #4 on:** March 21, 2010, 04:25:46 pm »

@ jens , Can you test this demo in linux?

Code

#include <map>
#include <wx/hashmap.h>
#include <wx/string.h>

WX_DECLARE_STRING_HASH_MAP(wxString, wxHashString);

int main()
{
    wxHashString 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("_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("_CXX_STD")] = _T("std");
    hashMap[_T("_CXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_CXX_BEGIN_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_CXX_END_NESTED_NAMESPACE")] = _T("}");
    hashMap[_T("_CXX_END_NAMESPACE")] = _T("}");
    hashMap[_T("_CXX_END_NAMESPACE_TR1")] = _T("}");
    hashMap[_T("_CXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    hashMap[_T("_CXX_STD2")] = _T("2std");
    hashMap[_T("_CXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_CXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_CXX_END_NESTED_NAMESPACE2")] = _T("2}");
    hashMap[_T("_CXX_END_NAMESPACE2")] = _T("2}");
    hashMap[_T("_CXX_END_NAMESPACE_TR12")] = _T("2}");
    hashMap[_T("_CXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");

    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("_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("_CXX_STD")] = _T("std");
    stdMap[_T("_CXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_CXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_CXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMap[_T("_CXX_END_NAMESPACE")] = _T("}");
    stdMap[_T("_CXX_END_NAMESPACE_TR1")] = _T("}");
    stdMap[_T("_CXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMap[_T("_CXX_STD2")] = _T("2std");
    stdMap[_T("_CXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_CXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_CXX_END_NESTED_NAMESPACE2")] = _T("2}");
    stdMap[_T("_CXX_END_NAMESPACE2")] = _T("2}");
    stdMap[_T("_CXX_END_NAMESPACE_TR12")] = _T("2}");
    stdMap[_T("_CXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");

    for (int i = 0; i < 20000000; ++i)
    {
        hashMap.find(_T("testfindkey")); // you can switch to stdMap for test
    }

    return 0;
}

Thanks!
The attachments is a demo on win32.

[attachment deleted by admin]

Jenna · « **Reply #5 on:** March 21, 2010, 08:18:43 pm »

Quote from: Loaden on March 21, 2010, 04:25:46 pm

@ jens , Can you test this demo in linux?

I changed the code a little bit to get some more output on the console:

Code

#include <iostream>
#include <map>
#include <wx/hashmap.h>
#include <wx/string.h>
#include <wx/stopwatch.h>

WX_DECLARE_STRING_HASH_MAP(wxString, wxHashString);

int main()
{
    wxHashString 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("_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("_CXX_STD")] = _T("std");
    hashMap[_T("_CXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_CXX_BEGIN_NAMESPACE")] = _T("+namespace");
    hashMap[_T("_CXX_END_NESTED_NAMESPACE")] = _T("}");
    hashMap[_T("_CXX_END_NAMESPACE")] = _T("}");
    hashMap[_T("_CXX_END_NAMESPACE_TR1")] = _T("}");
    hashMap[_T("_CXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    hashMap[_T("_CXX_STD2")] = _T("2std");
    hashMap[_T("_CXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_CXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    hashMap[_T("_CXX_END_NESTED_NAMESPACE2")] = _T("2}");
    hashMap[_T("_CXX_END_NAMESPACE2")] = _T("2}");
    hashMap[_T("_CXX_END_NAMESPACE_TR12")] = _T("2}");
    hashMap[_T("_CXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");

    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("_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("_CXX_STD")] = _T("std");
    stdMap[_T("_CXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_CXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMap[_T("_CXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMap[_T("_CXX_END_NAMESPACE")] = _T("}");
    stdMap[_T("_CXX_END_NAMESPACE_TR1")] = _T("}");
    stdMap[_T("_CXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMap[_T("_CXX_STD2")] = _T("2std");
    stdMap[_T("_CXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_CXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    stdMap[_T("_CXX_END_NESTED_NAMESPACE2")] = _T("2}");
    stdMap[_T("_CXX_END_NAMESPACE2")] = _T("2}");
    stdMap[_T("_CXX_END_NAMESPACE_TR12")] = _T("2}");
    stdMap[_T("_CXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");

    int stdMapTime=0;
    int hashMapTime=0;

    wxStopWatch sw;
    for(int j = 0; j < 10 ; j++)
    {
        sw.Start();
        for (int i = 0; i < 20000000; ++i)
        {
            stdMap.find(_T("testfindkey")); // you can switch to stdMap for test
        }
        stdMapTime+=sw.Time();
        std::cout << "stdMap took " << sw.Time() << " ms" << std::endl;

        sw.Start();
        for (int i = 0; i < 20000000; ++i)
        {
            hashMap.find(_T("testfindkey")); // you can switch to stdMap for test
        }

        hashMapTime+=sw.Time();
        std::cout << "hashMap took " << sw.Time() << " ms" << std::endl;
    }
    std::cout << "average (stdMap): " << stdMapTime / 10 << " ms" << std::endl;
    std::cout << "average (hashMap): " << hashMapTime / 10 << " ms" << std::endl;
    std::cout << "100 * (" << hashMapTime << "-" <<  stdMapTime << ") / " << hashMapTime <<  " = : " << 100 * (hashMapTime-stdMapTime) / hashMapTime << " %" << std::endl;

    return 0;
}

Here is the output from debug-version:

Code

stdMap took 6627 ms
hashMap took 5962 ms
stdMap took 6636 ms
hashMap took 5988 ms
stdMap took 6640 ms
hashMap took 6019 ms
stdMap took 6680 ms
hashMap took 6017 ms
stdMap took 6677 ms
hashMap took 6119 ms
stdMap took 6722 ms
hashMap took 6010 ms
stdMap took 6664 ms
hashMap took 6062 ms
stdMap took 6793 ms
hashMap took 6044 ms
stdMap took 6671 ms
hashMap took 6032 ms
stdMap took 6683 ms
hashMap took 6035 ms
average (stdMap): 6679 ms
average (hashMap): 6028 ms
100 * (60288-66793) / 60288 = : -10 %

Process returned 0 (0x0)   execution time : 127.129 s
Press ENTER to continue.

and here the output from the release-version with -O2 optimization:

Code

stdMap took 2599 ms
hashMap took 3312 ms
stdMap took 2624 ms
hashMap took 3320 ms
stdMap took 2590 ms
hashMap took 3315 ms
stdMap took 2585 ms
hashMap took 3318 ms
stdMap took 2580 ms
hashMap took 3310 ms
stdMap took 2577 ms
hashMap took 3297 ms
stdMap took 2614 ms
hashMap took 3298 ms
stdMap took 2577 ms
hashMap took 3302 ms
stdMap took 2573 ms
hashMap took 3304 ms
stdMap took 2568 ms
hashMap took 3303 ms
average (stdMap): 2588 ms
average (hashMap): 3307 ms
100 * (33079-25887) / 33079 = : 21 %

Process returned 0 (0x0)   execution time : 59.013 s
Press ENTER to continue.

It seems that the STL-map can be better optimized (at least on linux), maybe we should think about a real release-version of C::B (for windows), not just a stripped version.

MortenMacFly · « **Reply #6 on:** March 21, 2010, 08:30:03 pm »

Quote from: jens on March 21, 2010, 08:18:43 pm

It seems that the STL-map can be better optimized (at least on linux), maybe we should think about a real release-version of C::B (for windows), not just a stripped version.

What do you mean: compiling C::B with optimization flags enabled?

Jenna · « **Reply #7 on:** March 21, 2010, 08:58:47 pm »

Quote from: MortenMacFly on March 21, 2010, 08:30:03 pm

Quote from: jens on March 21, 2010, 08:18:43 pm
It seems that the STL-map can be better optimized (at least on linux), maybe we should think about a real release-version of C::B (for windows), not just a stripped version.
What do you mean: compiling C::B with optimization flags enabled?

Yes, if automake-system is used, C::B is compiled with -O2 and batch-parsing is significantly faster than without optimization.

You can see it in my first post in this thread (http://forums.codeblocks.org/index.php/topic,12235.msg83070.html#msg83070), batch-parsing of linux kernel-code is about 50 % faster, if C::B is build with automake-system, for Loadens sample code the speedup is nearly 70 %.

oBFusCATed · « **Reply #8 on:** March 21, 2010, 09:53:24 pm »

Hah, you don't use optimizations on windows! :shock:

Keep in mind that gcc can generate wrong code in optimization mode lower that -O2 ... I've seen reports for -O0

Loaden · « **Reply #9 on:** March 22, 2010, 01:30:30 am »

Yes, I don't use -O2, because Code-Completion plugin not use -O2 too. :lol:
Here is another demo, I wonder is: gnu's hash_map is so efficient, even when use -O2.

Code

#include <iostream>
#include <map>
#include <string>

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

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

namespace std
{
using namespace __gnu_cxx;
}

namespace __gnu_cxx
{
template<> struct hash< std::string >
{
    size_t operator()( const std::string& x ) const
    {
        return hash< const char* >()( x.c_str() );
    }
};
}

//namespace __gnu_cxx
//{
//template<> struct hash< wxString >
//{
//    size_t operator()( const wxString& x ) const
//    {
//        return hash< const wxChar* >()( x.c_str() );
//    }
//};
//}

WX_DECLARE_STRING_HASH_MAP(wxString, wxHashString);

int main()
{
    wxHashString 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("_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("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
    hashMap[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");

    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("_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("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
    stdMap[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");
    
    std::hash_map<std::string, std::string> hashMap2;
    hashMap2["_GLIBCXX_STD"] = "std";
    hashMap2["_GLIBCXX_BEGIN_NESTED_NAMESPACE"] = "+namespace";
    hashMap2["_GLIBCXX_BEGIN_NAMESPACE"] = "+namespace";
    hashMap2["_GLIBCXX_END_NESTED_NAMESPACE"] = "}";
    hashMap2["_GLIBCXX_END_NAMESPACE"] = "}";
    hashMap2["_GLIBCXX_END_NAMESPACE_TR1"] = "}";
    hashMap2["_GLIBCXX_BEGIN_NAMESPACE_TR1"] = "-namespace tr1 {";
    hashMap2["_GLIBCXX_STD2"] = "2std";
    hashMap2["_GLIBCXX_BEGIN_NESTED_NAMESPACE2"] = "2+namespace";
    hashMap2["_GLIBCXX_BEGIN_NAMESPACE2"] = "2+namespace";
    hashMap2["_GLIBCXX_END_NESTED_NAMESPACE2"] = "2}";
    hashMap2["_GLIBCXX_END_NAMESPACE2"] = "2}";
    hashMap2["_GLIBCXX_END_NAMESPACE_TR12"] = "2}";
    hashMap2["_GLIBCXX_BEGIN_NAMESPACE_TR12"] = "2-namespace tr1 {";
    hashMap2["_XXGLIBCXX_END_NAMESPACE_TR12"] = "X2}";
    hashMap2["_XXGLIBCXX_BEGIN_NAMESPACE_TR12"] = "X2-namespace tr1 {";
    
    std::map<std::string, std::string> stdMap2;
    stdMap2["_GLIBCXX_STD"] = "std";
    stdMap2["_GLIBCXX_BEGIN_NESTED_NAMESPACE"] = "+namespace";
    stdMap2["_GLIBCXX_BEGIN_NAMESPACE"] = "+namespace";
    stdMap2["_GLIBCXX_END_NESTED_NAMESPACE"] = "}";
    stdMap2["_GLIBCXX_END_NAMESPACE"] = "}";
    stdMap2["_GLIBCXX_END_NAMESPACE_TR1"] = "}";
    stdMap2["_GLIBCXX_BEGIN_NAMESPACE_TR1"] = "-namespace tr1 {";
    stdMap2["_GLIBCXX_STD2"] = "2std";
    stdMap2["_GLIBCXX_BEGIN_NESTED_NAMESPACE2"] = "2+namespace";
    stdMap2["_GLIBCXX_BEGIN_NAMESPACE2"] = "2+namespace";
    stdMap2["_GLIBCXX_END_NESTED_NAMESPACE2"] = "2}";
    stdMap2["_GLIBCXX_END_NAMESPACE2"] = "2}";
    stdMap2["_GLIBCXX_END_NAMESPACE_TR12"] = "2}";
    stdMap2["_GLIBCXX_BEGIN_NAMESPACE_TR12"] = "2-namespace tr1 {";
    stdMap2["_XXGLIBCXX_END_NAMESPACE_TR12"] = "X2}";
    stdMap2["_XXGLIBCXX_BEGIN_NAMESPACE_TR12"] = "X2-namespace tr1 {";

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdMap.find(_T("testfindkey"));
        std::cout << "stdMap " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) hashMap.find(_T("testfindkey"));
        std::cout << "hashMap " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }
    
    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdMap2.find("testfindkey");
        std::cout << "stdMap2 " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }
    
    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) hashMap2.find("testfindkey");
        std::cout << "hashMap2 " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    return 0;
}

Code

stdMap 1 : 2281
stdMap 2 : 2266
stdMap 3 : 2281
stdMap 4 : 2266
stdMap 5 : 2265

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

hashMap 1 : 2375
hashMap 2 : 2360
hashMap 3 : 2359
hashMap 4 : 2359
hashMap 5 : 2360

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

stdMap2 1 : 3578
stdMap2 2 : 3578
stdMap2 3 : 3594
stdMap2 4 : 3578
stdMap2 5 : 3594

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

hashMap2 1 : 2421
hashMap2 2 : 2422
hashMap2 3 : 2422
hashMap2 4 : 2422
hashMap2 5 : 2422

Process returned 0 (0x0)   execution time : 53.531 s
Press any key to continue.

However, I can NOT compiled std::hash_map<wxString, wxString>, who knows how to solution?
Thanks!

[attachment deleted by admin]

Loaden · « **Reply #10 on:** March 22, 2010, 01:55:27 am »

If use -O0 like Code-Completion plugins, here are some test data:

Code

stdMap 1 : 4282
stdMap 2 : 4265
stdMap 3 : 4281
stdMap 4 : 4266
stdMap 5 : 4281

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

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

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

stdMap2 1 : 5234
stdMap2 2 : 5234
stdMap2 3 : 5235
stdMap2 4 : 5234
stdMap2 5 : 5250

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

hashMap2 1 : 3266
hashMap2 2 : 3265
hashMap2 3 : 3266
hashMap2 4 : 3266
hashMap2 5 : 3265

Process returned 0 (0x0)   execution time : 78.906 s
Press any key to continue.

ollydbg · « **Reply #11 on:** March 22, 2010, 02:19:16 am »

Quote from: Loaden on March 22, 2010, 01:55:27 am

If use -O0 like Code-Completion plugins, here are some test data:

Code

stdMap 1 : 4282
stdMap 2 : 4265
stdMap 3 : 4281
stdMap 4 : 4266
stdMap 5 : 4281

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

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

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

stdMap2 1 : 5234
stdMap2 2 : 5234
stdMap2 3 : 5235
stdMap2 4 : 5234
stdMap2 5 : 5250

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

hashMap2 1 : 3266
hashMap2 2 : 3265
hashMap2 3 : 3266
hashMap2 4 : 3266
hashMap2 5 : 3265

Process returned 0 (0x0)   execution time : 78.906 s
Press any key to continue.

so, the xxx2 version is ANSI version(std::string) and the other is UNICODE version(wxString).

For std-map, UNICODE is better.
For hash-map, ANSI is better.

Oh, wait, I think you don't defined the UNICODE macros, so all the string type is ANSI.

Loaden · « **Reply #12 on:** March 22, 2010, 02:23:53 am »

If you use only seven replacement rules:
No Optimization (-O0)：

Code

stdMap 1 : 3671
stdMap 2 : 3657
stdMap 3 : 3672
stdMap 4 : 3671
stdMap 5 : 3657

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

hashMap 1 : 2953
hashMap 2 : 2953
hashMap 3 : 2953
hashMap 4 : 2953
hashMap 5 : 2938

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

stdMap2 1 : 4234
stdMap2 2 : 4234
stdMap2 3 : 4235
stdMap2 4 : 4234
stdMap2 5 : 4235

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

hashMap2 1 : 3156
hashMap2 2 : 3172
hashMap2 3 : 3172
hashMap2 4 : 3171
hashMap2 5 : 3157

Process returned 0 (0x0)   execution time : 70.281 s
Press any key to continue.

Optimization (-O2):

Code

stdMap 1 : 2156
stdMap 2 : 2156
stdMap 3 : 2156
stdMap 4 : 2156
stdMap 5 : 2157

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

hashMap 1 : 2296
hashMap 2 : 2297
hashMap 3 : 2297
hashMap 4 : 2281
hashMap 5 : 2297

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

stdMap2 1 : 3047
stdMap2 2 : 3047
stdMap2 3 : 3047
stdMap2 4 : 3031
stdMap2 5 : 3047

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

hashMap2 1 : 2391
hashMap2 2 : 2406
hashMap2 3 : 2406
hashMap2 4 : 2391
hashMap2 5 : 2406

Process returned 0 (0x0)   execution time : 49.734 s
Press any key to continue.

ollydbg · « **Reply #13 on:** March 22, 2010, 02:53:02 am »

I suggest changing the variable names. see the code below:

Code

#include <iostream>
#include <map>
#include <string>

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

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

namespace std
{
using namespace __gnu_cxx;
}

namespace __gnu_cxx
{
template<> struct hash< std::string >
{
    size_t operator()( const std::string& x ) const
    {
        return hash< const char* >()( x.c_str() );
    }
};
}

//namespace __gnu_cxx
//{
//template<> struct hash< wxString >
//{
//    size_t operator()( const wxString& x ) const
//    {
//        return hash< const wxChar* >()( x.c_str() );
//    }
//};
//}

WX_DECLARE_STRING_HASH_MAP(wxString, wxHashString);

int main()
{
    wxHashString wxHashMapwxString;
    wxHashMapwxString[_T("_GLIBCXX_STD")] = _T("std");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    wxHashMapwxString[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    wxHashMapwxString[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    wxHashMapwxString[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    wxHashMapwxString[_T("_GLIBCXX_STD2")] = _T("2std");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    wxHashMapwxString[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
    wxHashMapwxString[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
    wxHashMapwxString[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
    wxHashMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
    wxHashMapwxString[_T("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
    wxHashMapwxString[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");

    std::map<wxString, wxString> stdMapwxString;
    stdMapwxString[_T("_GLIBCXX_STD")] = _T("std");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
    stdMapwxString[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
    stdMapwxString[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
    stdMapwxString[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
    stdMapwxString[_T("_GLIBCXX_STD2")] = _T("2std");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
    stdMapwxString[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
    stdMapwxString[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
    stdMapwxString[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
    stdMapwxString[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
    stdMapwxString[_T("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
    stdMapwxString[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");

    std::hash_map<std::string, std::string> stdHashMapstdString;
    stdHashMapstdString["_GLIBCXX_STD"] = "std";
    stdHashMapstdString["_GLIBCXX_BEGIN_NESTED_NAMESPACE"] = "+namespace";
    stdHashMapstdString["_GLIBCXX_BEGIN_NAMESPACE"] = "+namespace";
    stdHashMapstdString["_GLIBCXX_END_NESTED_NAMESPACE"] = "}";
    stdHashMapstdString["_GLIBCXX_END_NAMESPACE"] = "}";
    stdHashMapstdString["_GLIBCXX_END_NAMESPACE_TR1"] = "}";
    stdHashMapstdString["_GLIBCXX_BEGIN_NAMESPACE_TR1"] = "-namespace tr1 {";
    stdHashMapstdString["_GLIBCXX_STD2"] = "2std";
    stdHashMapstdString["_GLIBCXX_BEGIN_NESTED_NAMESPACE2"] = "2+namespace";
    stdHashMapstdString["_GLIBCXX_BEGIN_NAMESPACE2"] = "2+namespace";
    stdHashMapstdString["_GLIBCXX_END_NESTED_NAMESPACE2"] = "2}";
    stdHashMapstdString["_GLIBCXX_END_NAMESPACE2"] = "2}";
    stdHashMapstdString["_GLIBCXX_END_NAMESPACE_TR12"] = "2}";
    stdHashMapstdString["_GLIBCXX_BEGIN_NAMESPACE_TR12"] = "2-namespace tr1 {";
    stdHashMapstdString["_XXGLIBCXX_END_NAMESPACE_TR12"] = "X2}";
    stdHashMapstdString["_XXGLIBCXX_BEGIN_NAMESPACE_TR12"] = "X2-namespace tr1 {";

    std::map<std::string, std::string> stdMapstdString;
    stdMapstdString["_GLIBCXX_STD"] = "std";
    stdMapstdString["_GLIBCXX_BEGIN_NESTED_NAMESPACE"] = "+namespace";
    stdMapstdString["_GLIBCXX_BEGIN_NAMESPACE"] = "+namespace";
    stdMapstdString["_GLIBCXX_END_NESTED_NAMESPACE"] = "}";
    stdMapstdString["_GLIBCXX_END_NAMESPACE"] = "}";
    stdMapstdString["_GLIBCXX_END_NAMESPACE_TR1"] = "}";
    stdMapstdString["_GLIBCXX_BEGIN_NAMESPACE_TR1"] = "-namespace tr1 {";
    stdMapstdString["_GLIBCXX_STD2"] = "2std";
    stdMapstdString["_GLIBCXX_BEGIN_NESTED_NAMESPACE2"] = "2+namespace";
    stdMapstdString["_GLIBCXX_BEGIN_NAMESPACE2"] = "2+namespace";
    stdMapstdString["_GLIBCXX_END_NESTED_NAMESPACE2"] = "2}";
    stdMapstdString["_GLIBCXX_END_NAMESPACE2"] = "2}";
    stdMapstdString["_GLIBCXX_END_NAMESPACE_TR12"] = "2}";
    stdMapstdString["_GLIBCXX_BEGIN_NAMESPACE_TR12"] = "2-namespace tr1 {";
    stdMapstdString["_XXGLIBCXX_END_NAMESPACE_TR12"] = "X2}";
    stdMapstdString["_XXGLIBCXX_BEGIN_NAMESPACE_TR12"] = "X2-namespace tr1 {";

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdMapwxString.find(_T("testfindkey"));
        std::cout << "stdMapwxString " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) wxHashMapwxString.find(_T("testfindkey"));
        std::cout << "wxHashMapwxString " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdMapstdString.find("testfindkey");
        std::cout << "stdMapstdString " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdHashMapstdString.find("testfindkey");
        std::cout << "stdHashMapstdString " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    return 0;
}

And the result is here, I built this project with -O2 :

Code

stdMapwxString 1 : 3094
stdMapwxString 2 : 3094
stdMapwxString 3 : 3094
stdMapwxString 4 : 3109
stdMapwxString 5 : 3110

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

wxHashMapwxString 1 : 3296
wxHashMapwxString 2 : 3313
wxHashMapwxString 3 : 3297
wxHashMapwxString 4 : 3312
wxHashMapwxString 5 : 3297

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

stdMapstdString 1 : 4719
stdMapstdString 2 : 4734
stdMapstdString 3 : 4766
stdMapstdString 4 : 4734
stdMapstdString 5 : 4735

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

stdHashMapstdString 1 : 3515
stdHashMapstdString 2 : 3500
stdHashMapstdString 3 : 3516
stdHashMapstdString 4 : 3516
stdHashMapstdString 5 : 3515

Process returned 0 (0x0)   execution time : 73.344 s
Press any key to continue.

So, you can see:

Quote

stdMapwxString 1 : 3094
stdMapwxString 2 : 3094
stdMapwxString 3 : 3094
stdMapwxString 4 : 3109
stdMapwxString 5 : 3110

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

wxHashMapwxString 1 : 3296
wxHashMapwxString 2 : 3313
wxHashMapwxString 3 : 3297
wxHashMapwxString 4 : 3312
wxHashMapwxString 5 : 3297

Optimized stdMap is better than wxHashMap.

Loaden · « **Reply #14 on:** March 22, 2010, 05:07:39 am »

Please look at GNU's hash_map test results. (-O2)

Code

#include <iostream>
#include <map>

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

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

namespace std
{
using namespace __gnu_cxx;
}

namespace __gnu_cxx
{
template<> struct hash< wxString >
{
    size_t operator()( const wxString& x ) const
    {
        unsigned long __h = 0;
        const wxChar* p = x.wx_str();
        size_t size = x.size();
        while (size) __h = 5 * __h + p[--size];
        return size_t(__h);
    }
};
}

WX_DECLARE_STRING_HASH_MAP(wxString, wxHashString);

int main()
{
    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("_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("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
//    hashMap[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");

    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("_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("_XXGLIBCXX_END_NAMESPACE_TR12")] = _T("X2}");
//    stdMap[_T("_XXGLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("X2-namespace tr1 {");

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) stdMap.find(_T("testfindkey"));
        std::cout << "stdMap " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    std::cout << "\n---------------\n" << std::endl;

    for (int i = 0; i < 5; ++i)
    {
        wxStartTimer();
        for (int j = 0; j < 10000000; ++j) hashMap.find(_T("testfindkey"));
        std::cout << "hashMap " << i + 1 << " : " << wxGetElapsedTime() << std::endl;
    }

    return 0;
}

Code

stdMap 1 : 2203
stdMap 2 : 2188
stdMap 3 : 2203
stdMap 4 : 2203
stdMap 5 : 2203

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

hashMap 1 : 2078
hashMap 2 : 2094
hashMap 3 : 2078
hashMap 4 : 2078
hashMap 5 : 2078

Process returned 0 (0x0)   execution time : 21.484 s
Press any key to continue.

If changed TO 16 replace rules ：

Code

stdMap 1 : 2250
stdMap 2 : 2250
stdMap 3 : 2250
stdMap 4 : 2250
stdMap 5 : 2265

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

hashMap 1 : 2031
hashMap 2 : 2047
hashMap 3 : 2047
hashMap 4 : 2031
hashMap 5 : 2032

Process returned 0 (0x0)   execution time : 21.672 s
Press any key to continue.

NO OPTI, 16 replacement: (-O0)

Code

stdMap 1 : 4281
stdMap 2 : 4282
stdMap 3 : 4281
stdMap 4 : 4281
stdMap 5 : 4297

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

hashMap 1 : 3203
hashMap 2 : 3203
hashMap 3 : 3219
hashMap 4 : 3203
hashMap 5 : 3203

Process returned 0 (0x0)   execution time : 37.609 s
Press any key to continue.

OPTI(-O2), 9 replacement:

Code

stdMap 1 : 2235
stdMap 2 : 2234
stdMap 3 : 2219
stdMap 4 : 2234
stdMap 5 : 2219

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

hashMap 1 : 2047
hashMap 2 : 2031
hashMap 3 : 2047
hashMap 4 : 2031
hashMap 5 : 2031

Process returned 0 (0x0)   execution time : 21.609 s
Press any key to continue.

Code::Blocks Forums

News:

Author Topic: patch : from std::map replace to hashmap (Read 49484 times)

Loaden

patch : from std::map replace to hashmap

ollydbg

Re: patch : from std::map replace to hashmap

Jenna

Re: patch : from std::map replace to hashmap

ollydbg

Re: patch : from std::map replace to hashmap

Loaden

Re: patch : from std::map replace to hashmap

Jenna

Re: patch : from std::map replace to hashmap

MortenMacFly

Re: patch : from std::map replace to hashmap

Jenna

Re: patch : from std::map replace to hashmap

oBFusCATed

Re: patch : from std::map replace to hashmap

Loaden

Re: patch : from std::map replace to hashmap

Loaden

Re: patch : from std::map replace to hashmap

ollydbg

Re: patch : from std::map replace to hashmap

Loaden

Re: patch : from std::map replace to hashmap

ollydbg

Re: patch : from std::map replace to hashmap

Loaden

Re: patch : from std::map replace to hashmap