Thread: std::map with many elements

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?

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

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

Code:

		sregex_token_iterator begin(line.begin(), line.end(), expression, 1);
		sregex_token_iterator end;

		while (begin != end)

end seems to be uninitialized.
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

okay, with this piece of code:

Code:

		while (begin != end)
		{
			dictionary[(*begin++)]++;
		}

The routine took 2.05 seconds, and without it (commenting it) i get 0.42 seconds...