https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68303
Bug ID: 68303
Summary: performance: unordered_map&co. up to 7x speedup
Product: gcc
Version: 5.1.1
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: jan.kratochvil at redhat dot com
Target Milestone: ---
libstdc++ spends most of the time on:
div %rdi
computing modulo even when commonly the container is empty().
Moreover for small size()s it is more effective to iterate the container rather
than calculating the modulo.
-----------------------------------------------------------------
template<class From,class To> class unordered_map_find:public
unordered_map<From,To> {
private:
const size_t find_max_size=20;
public:
/***/ iterator find(const From &k) /***/ {
if (unordered_map<From,To>::size()>find_max_size) // too big?
return unordered_map<From,To>::find(k);
for (auto it=unordered_map<From,To>::begin();;++it) // small => iterate
if (it==unordered_map<From,To>::end()||it->first==k)
return it;
}
};
#define unordered_map unordered_map_find
-----------------------------------------------------------------
gcc-5.1.1-4.fc23.x86_64
g++ -o findbench findbench.C -Wall -g -std=c++11 -O3;sync;for i in `seq 0
30`;do ./findbench $i;done
orig wrapped
----------- -----------
0=1.094465 0=0.157921
1=1.119786 1=0.183768
2=1.169548 2=0.279629
3=1.347452 3=0.407056
4=1.479790 4=0.415102
5=1.301983 5=0.516378
6=1.326878 6=0.629252
7=1.467088 7=0.672654
8=1.681829 8=0.632880
9=1.755480 9=0.656492
10=1.712439 10=0.900121
11=1.515782 11=0.791073
12=1.351241 12=0.837695
13=1.434103 13=0.948055
14=1.671421 14=1.114046
15=1.683168 15=1.055906
16=1.521289 16=1.295058
17=1.537086 17=1.219568
18=1.766316 18=1.304961
19=1.807524 19=1.544631
20=1.848499 20=2.530600
21=1.895775 21=1.911767
22=1.792831 22=1.813895
23=1.562995 23=1.399753
24=1.560324 24=1.583886
25=1.419246 25=1.481225
26=1.609419 26=1.625853
27=1.482955 27=1.498665
28=1.483937 28=1.509582
29=1.506504 29=1.680078
30=1.522410 30=1.564460
