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

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.

Thanks for letting me know about this.

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.

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.

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.

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.

I'll look into it.

Regards,

Andreas

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

Regards,

Andreas