Jump to content
  • Advertisement
Sign in to follow this  
Sir Ementaler

Possible dictionary optimization

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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. biggrin.png

 

 

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!