Ok, that's a good start. Now put timing data around that loop to see if the slow down is in the loop. In fact, just a cout before and after the outer while loop might do it. Remember, I'm thinking one potential problem is in the destruction of a large map, so commenting out the code that fills the large map would get rid of that slowdown as well.
Oh, i am sorry, i wasn´t clear:
Total time execution with insertion: 2.08s
Loop time with insertion: 2.06s
Total time execution without insertion: 0.41s
Loop time without insertion: 0.41s
What timing do you get if you just change that loop to this?:Originally Posted by Scarvenger
Then tell us how long it takes if you instead do this:Code:while (begin != end) { *begin++; }
That should tell us whether the slowness is mainly related to incrementing the sregex_token_iterator, or whether it is in fact the actual insertions.Code:std::map<std::string, int> iter = dictionary.begin(); while (iter != dictionary.end()) { dictionary[iter++]++; }
Last edited by iMalc; 12-01-2007 at 06:26 PM.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
0.951sCode:while (begin != end) { dictionary[(*begin++)]++; }
0.781sCode:while (begin != end) { *begin++; }
So, yes, now i suppose that the problem is in the sregex_token_iterator... Maybe i will think anything to replace it...
Okay, i have changed the whole code that used the boost::regex library to a pure std approach, the code is the following:
This seems to be a much faster aproach than the boost::regex since it gives me total execution time of ~1.39s while the boost::regex was giving me ~4.01s.Code:ifstream file(filename); char data[3000]; while (!file.eof()) { file.getline(data, 3000); string line(data); stringToLower(line); unsigned int position = 0; while ((position = line.find_first_of(delimiters, position)) != -1) { int endPosition = line.find_first_not_of(delimiters, position); string result = line.substr(position, endPosition - position); position = endPosition; dictionary[result]++; } } return true;
Now i would like to squeeze this program to get the last drop of performance from it... Suggestions?
[edit]
Readability and good practices sugestion are welcome too
[/edit]
Last edited by Scarvenger; 12-01-2007 at 10:20 PM.
>> Now i would like to squeeze this program to get the last drop of performance from it... Suggestions?
Just a guess: put line.substr(position, endPosition - position) into the dictionary[] call instead of result and remove result entirely. Also you'd have to move the assignment of position to after that call as well. A good optimizing compiler probably would already have done that itself, but it's worth a try.
By the way, are the timings on a release build with optimizations on? That makes a big difference. All timing tests should be done with release builds.
>> Readability and good practices sugestion are welcome too
I'd use string::npos instead of -1 and string::size_type instead of unsigned int.
Why are you using the C-string version of getline? Are you purposefully trying to cap the input at 3000 characters? If so, that's fine. If you made it 3000 because you want to make sure you get the entire line, then use the C++ string version of getline: getline(file, line).
Whichever version of getline you use, you should not use eof() to control the loop. You need to check to see if the reading function (getline in this case) succeeds before using it. The most common and easy way to do this is to move the reading function into the while control:Code:string line; while (getline(file, line)) { // ...
To get more performance you'd need a hash table instead of the balanced tree. See if your compiler provides std::tr1::unordered_map, or perhaps stdext::hash_map.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
I would prefer boost's unordered_map implementation before using stdext::hash_map. The standard hash_map has pretty much been set now, so it only makes sense to start using that instead of the older compiler specific variations.
Also remember what I mentioned earlier about knowing a good size estimate before you start reading. If you don't have one, then you might either waste a ton of memory or lose all the performance benefits of the hash map (or worse have significantly worse performance). A good size to use is 50% more than how many elements will be in the map. Making that number prime or with few factors might help as well.
Except that Boost doesn't have an unordered_map implementation in its TR1 emulation. The only hash map in Boost is a multi_index container with a hash index.
All the buzzt!
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Really? I could have sworn I'd used or at least read about their implementation before. I guess I confused that with something else.
That's too bad. It took long enough to get a standardized interface that it would be nice if there was a cross-platform implementation available that implements it.
Or there is talk about their implementation. In fact, there is an implementation - but it's in the Sandbox, not yet part of Boost proper. 1.34 doesn't have it, 1.35 won't have it either.
All the buzzt!
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
