Maps are sloooowwwww!

[ultifinitus]

Holy cow, so I was relying heavily on maps for my collision detection system in my game. I mean heavily. That was dumb. I just ran some tests, and here are some results:

093766 (sqrt(a))s / tick
324928 (a + a)s / tick
001237 (mapname[a] = "blank"; mapname.clear())s / tick
000792 (mapname[a] = "string";)s / tick
029226 (vecname.push_back(3); vecname.clear())s / tick
044171 (vecname.push_back(a))s / tick
320808 (tan(a))s / tick

notice how the average number of map assignemts / tick is around 35x slower than vector push_back()s!!

Here's the (quick and dirty) corresponding code:

int main(){

vector<int> avg;

for (int a = 0; a < 20; a++){
map<int, string> thetest;
vector<int> test;

int testnum = 5000000;


int start = GetTickCount();


for (int a = 0; a < testnum; a++){
 ///test goes here.
}

int end = GetTickCount();

int total = end - start;

cout << "\nTook : " << total << "t";
if (total > 0){
cout << "\nThat's : " << testnum / total << " runs/t";
avg.push_back(testnum / total);
}
cout << "\n\n";
}
uint64_t total = 0;
for (int a = 0; a < avg.size(); a++){
 total += avg[a];
}
cout << "\ntotal : " << total;
if (avg.size() > 0)
cout << "\navg   : " << total / avg.size();
}

So now I'm trying to figure out a way to avoid hard coding a map size and avoid maps...

[exiledAussie]

This should probably be in the general c++ section.

Maps are slow. It can often be that sorted vectors are a much better alternative. This is not always the case though, depending on the size of your containers and what you are doing with them, but when it is, it can make a huge difference.

[Albatross]

The LLVM Documenter wrote:

std::map has similar characteristics to std::set: it uses a single allocation per pair inserted into the map, it offers log(n) lookup with an extremely large constant factor, imposes a space penalty of 3 pointers per pair in the map, etc.

std::map is most useful when your keys or values are very large, if you need to iterate over the collection in sorted order, or if you need stable iterators into the map (i.e. they don't get invalidated if an insertion or deletion of another element takes place).

;)

-Albatross

[ultifinitus]

@exiledAussie: meh. I'm not looking for help, this was an observation- I see the general forum as a place to look for assistance, none of which is needed here.

@alby: hahah, I suppose I should read the documentation =]