# Possible dictionary optimization

This topic is 1136 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I was skimming through scriptdictionary.cpp today to see some implementation details, and I couldn't help but notice the quite wordy implementation of CScriptDictionary::operator[]. Let me quote:

CScriptDictValue *CScriptDictionary::operator[](const string &key)
{
// Return the existing value if it exists, else insert an empty value
map<string, CScriptDictValue>::iterator it;
it = dict.find(key);
if( it == dict.end() )
it = dict.insert(map<string, CScriptDictValue>::value_type(key, CScriptDictValue())).first;

return &it->second;
}


It came to my attention that this is essentially a lengthy rewording of the following code:

CScriptDictValue *CScriptDictionary::operator[](const string &key)
{
return &dict[key];
}


(see http://en.cppreference.com/w/cpp/container/map/operator_at or http://www.cplusplus.com/reference/map/map/operator[]/ for reference for std::map operator[]). I wanted to see if something escapes my attention so I tested performance of both of these implementations with the following script:

void test() {
array<string> keys;
for (uint i = 0; i < 100000; i++)
keys.insertLast(formatInt(i, "", 10));

uint insertionTime = 0, accessTime = 0;
for (uint i = 0; i < 100; i++) {
dictionary d;

uint time1 = GetSystemTime();

for (uint j = 0; j < 100000; j++)
d[keys[j]] = j;

uint time2 = GetSystemTime();

for (uint j = 0; j < 100000; j++)
if (uint(d[keys[j]]) != j)
return 0;

uint time3 = GetSystemTime();

insertionTime += time2 - time1;
accessTime += time3 - time2;
}
Print("Insertion time: " + insertionTime + " ms\nAccess time: " + accessTime + " ms\n");
} 

Using AngelScript compiled in MSVC 2013 I obtained the following results:

Current implementation:

In Release mode: Insertion time: 18334 ms; Access time: 11434 ms

In Debug mode: Insertion time: 846300 ms; Access time: 300030 ms

Proposed implementation:

In Release mode: Insertion time: 15181 ms; Access time: 12121 ms

In Debug mode: Insertion time: 577720 ms; Access time: 271790 ms

I.e., in all situations except for Release mode access the simpler implementation was faster. It may be a bit of a tradeoff but looks worth it. I don't know how other compilers would react though. Either way I thought you may be interested.

Edited by Sir Ementaler

##### Share on other sites

There is no specific reason for not using the shorter code that you propose. It is just that I never thought about using the operator[] on the std::map container. I never had a reason to look for a shorter implementation as the current one was good enough for me.

That's one of the things I love about C++. No matter how many years of experience you have, there is always something new to learn.

I'll make the changes. Not for the potential performance improvement, but for the sake of cleaner code.

BTW. It's quite useless to do performance comparisons in debug mode. Performance comparisons should always be done in release mode to get as close to the actual code you would use in a released project as possible. Comparing performance of two algorithms in debug mode can easily make you chose to worse of the two, especially when considering cache management, branch-prediction, and multicore features in current day CPUs. In debug mode many of these features are all but eliminated due to all the extra checks that the debug code executes to check the sanity of the code.

I've personally seen cases where algorithms that 'should' be faster due to doing less work, actually becomes a lot slower due to causing more cache-misses or incorrect branch-predictions.

What's worse is that different CPU families/brands behave differently. So never trust numbers you get from only a single machine.

##### Share on other sites

Yeah, you're right. My initial reason for testing in debug mode was actually from disbelief that the resulting gains were so minor, because calling both find and insert should perform twice as many binary searches as just operator[], so I wanted to see if I'm experiencing some magical compiler optimizations. Debug mode performance certainly doesn't make a difference, that is except for when you're debugging.

Thanks for using it, I also agree it looks much neater.

##### Share on other sites

While you're looking at the dictionary class, would it be possible to update it to use typedefs for the string key type?

The reason i'm asking is because our project uses a custom string class, but we still want to use the given dictionary class.

Having the key type be a typedef simplifies updating it.

##### Share on other sites

I second the typedef, I too use a custom string class. Although I'll still have to edit the internals, as I use reference counted strings not value type.

##### Share on other sites

I'll look into it.

Regards,

Andreas

##### Share on other sites

I've made the changes to use a typedef for the dictionary key type in revision 2208.

Regards,

Andreas

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 9
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632621
• Total Posts
3007498
• ### Who's Online (See full list)

There are no registered users currently online

×