Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign
patch : from std::map replace to hashmap
ollydbg:
@loaden, I have tested and find that there is nearly about 60% speed improvement, really cool!!!!
--- Code: ---stdMap 1 : 2203
stdMap 2 : 2188
stdMap 3 : 2203
stdMap 4 : 2203
stdMap 5 : 2203
stdMap Total Time: 11000
stdMap Average Time: 2200
------------------------------
hashMap 1 : 860
hashMap 2 : 875
hashMap 3 : 890
hashMap 4 : 875
hashMap 5 : 891
hashMap Total Time: 4391
hashMap Average Time: 878
------------------------------
(stdAverage - hashAverage) / stdAverage = 0.600909
Process returned 0 (0x0) execution time : 15.500 s
Press any key to continue.
--- End code ---
koso:
I have recently used unordered_map and it is very fast. There was only one problem .. it is available in newer comilators (VC2008 with installed Feature Pack ang gcc >4.3), so there must be some kind of fallback solution. In my case i used map, besace they both have compatible interfaces. So you will need only some "macro checks" for preprocessor.
And btw. Loaden, your hash function is quiet complicated for this purpose, especially when list of possible values is so small. Try this:
--- Code: ---namespace std
{
template<> struct hash< wxString >
{
size_t operator()( const wxString& x ) const
{
unsigned long __h = 0;
unsigned long len = __h = 128 ^ x.Len();
const wxChar* p = x.c_str();
for (long i = 1; i < len; i+=5)
__h = __h ^ p[i];
return size_t(__h);
}
};
}
--- End code ---
ollydbg:
--- Quote from: koso on March 22, 2010, 09:08:49 am ---I have recently used unordered_map and it is very fast. There was only one problem .. it is available in newer comilators (VC2008 with installed Feature Pack ang gcc >4.3), so there must be some kind of fallback solution. In my case i used map, besace they both have compatible interfaces. So you will need only some "macro checks" for preprocessor.
--- End quote ---
en, if we use unordered_map in the CodeCompletion plugin, then Codeblocks can only be built from gcc > 4.3. This means we abandon several old gcc version.
Loaden:
--- Quote from: koso on March 22, 2010, 09:08:49 am ---I have recently used unordered_map and it is very fast. There was only one problem .. it is available in newer comilators (VC2008 with installed Feature Pack ang gcc >4.3), so there must be some kind of fallback solution. In my case i used map, besace they both have compatible interfaces. So you will need only some "macro checks" for preprocessor.
And btw. Loaden, your hash function is quiet complicated for this purpose, especially when list of possible values is so small. Try this:
--- Code: ---namespace std
{
template<> struct hash< wxString >
{
size_t operator()( const wxString& x ) const
{
unsigned long __h = 0;
unsigned long len = __h = 128 ^ x.Len();
const wxChar* p = x.c_str();
for (long i = 1; i < len; i+=5)
__h = __h ^ p[i];
return size_t(__h);
}
};
}
--- End code ---
--- End quote ---
Thanks! What mean is unsigned long len = __h = 128 ^ x.Len();
This code will crash in my demo.
I changed to :
--- Code: ---namespace std
{
template<> struct hash<wxString>
{
size_t operator()(const wxString& x) const
{
size_t len = x.length();
unsigned long __h = 128 ^ len;
const wxChar* p = x.c_str();
for (size_t i = 0; i < len; i += 5)
__h = __h ^ p[i];
return size_t(__h);
}
};
}
--- End code ---
This is the lastest report:
--- Code: ---stdMap 1 : 1812
stdMap 2 : 1797
stdMap 3 : 1828
stdMap 4 : 1797
stdMap 5 : 1812
stdMap Total Time: 9046
stdMap Average Time: 1809
------------------------------
hashMap 1 : 469
hashMap 2 : 453
hashMap 3 : 469
hashMap 4 : 468
hashMap 5 : 454
hashMap Total Time: 2313
hashMap Average Time: 462
------------------------------
(stdAverage - hashAverage) / stdAverage = 0.74461
--- End code ---
koso:
Yes, there was typo :) Btw. it can be even better, but you should analyze, how it iss mostly used in code:
1. when you test this code with some string, which is "mapped", std::map will be slower. But once you try it with some random string, std::map can be faster (depends how well is writen hash function) - So you should find out, how often is it searching for known string, and how often for some other...
2. hash function should be faster, that string comparision used in std::map, so for example, when you try to search for string XXX, wxString comparator will soon find out, that there is no string beggining with XXX and will end -> hash function should use the same system (i.e. check, if first char is "_" and if not, then add to h some penalty value and imediately end hashing)
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version