Printable View
Hi, i am using std::map for many elements almost 20.000. But the insertion of those elements seems to be a litlle bit slow... Is there anything like std::string::reserve method on map? I already looked the references but havenīt found any hint. Ideas?
maps are implemented as binary trees, so you can't really reserve memory like you can for something implemented with an array. The reason reserve is used for strings and vectors is to avoid copying of the data over and over as it is being appended. There isn't any copying with a map because the existing elements never have to be moved when a new element is added.
If you think the slowdown is caused by fragmented memory (which has happened to me with a map), then you can adjust the allocator the map uses to allocate it's memory. I've used the Pool allocator from boost for this in the past. However, the slowdown we noticed was in deletion of the map, not insertion.
What makes you think the insertion is the source of the slowdown?
the insertion speed for a map depends on the number of elements which are already in the map so it's always slow compared to a list for example. thats the price to get the elements sorted. the only way to avoid this is using another type of container which allows insertion in constant time. If you describe the purpose of your map and the operations you run on it (what and how often) maybe a better alternative can be suggested.
But 20000 elements is nothing. That's at worst 15 comparisons. So unless your comparison function is really slow (what are you storing?), it shouldn't be noticeably slow.
I haven´t defined a comparison function... Ok, the purpose of the map is to store a indefined number of words 20.000 ~ 500.000 and count the times that that word appears on a text. So i was using map to store words like: mymap["the"]++;. And i noticed the slowdown on my routine of getting the words from the text since i have added the insertion routine to my map...
May-be you could post the code / insertion routine?
Sure, it have some code that uses boost too:
...Code:std::map<std::string, int> dictionary;
boost::regex expression("([a-z]+)", regex::perl|regex::icase);
Code:ifstream file(filename);
cmatch result;
char data[10000];
while (!file.eof())
{
file.getline(data, 10000);
string line(data);
sregex_token_iterator begin(line.begin(), line.end(), expression, 1);
sregex_token_iterator end;
while (begin != end)
{
dictionary[(*begin++)]++;
}
}
I'v never used boost::regexp but
end seems to be uninitialized.Code:sregex_token_iterator begin(line.begin(), line.end(), expression, 1);
sregex_token_iterator end;
while (begin != end)
Kurt
Oh, that´s the way it should be used ;P
So you're saying that if you take out the dictionary[(*begin++)]++; line it works much faster? How much faster?
Perhaps you can use a profiler to see exactly where the slowdown is. A decent one should show you the call even if it comes from the map class. There are free profilers available if you don't want to spend money.
Or you can add timers to the code to make sure the problem is there and not somewhere else. For example, if you're entire program just takes longer when you add that line, it still might be a memory fragmentation problem that occurs when the map is destroyed, rather than exactly at that line of code. The memory fragmentation issue has a solution.
BTW, because you're potentially mixing inserts and lookups, I don't think any another container makes sense over a map. If you don't need these things sorted then perhaps a hash based map would be better (use unordered_map from std::tr1 or boost). The catch with that is that you need a pretty reasonable estimate of how many entries you'll have before you start or a maximum size that you can use every time.
Can you indicate any win32 profiler? I am unable to use my gprof right now...
I honestly don't know any off the top of my head without doing a full search myself.
there is a free version of VTune from intel
Which doesn't work on AMD processors, but AMD has a similar tool called CodeAnalyst [in fact, the latter can do a lot more, because you also get a instruction simulator that can analyze EXACTLY what happens in any piece of your code - it just takes about 10-100x more time to run the code, but you only do that once you have figured out which bits are really you bottleneck, and you only do it enough to find the answer to why it's slow (unless you already know by the time you get to that piece of code!)].Quote:
Originally Posted by pheres
--
Mats
okay, with this piece of code:
The routine took 2.05 seconds, and without it (commenting it) i get 0.42 seconds...Code:while (begin != end)
{
dictionary[(*begin++)]++;
}
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?:Quote:
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++]++;
}
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]
>> 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.
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.
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.