This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
Paolo Carlini wrote:
Joe Buck wrote:
There is wasted work because of the two lookups, but perhaps there's a way to further improve the situation by exposing the common part of find() and insert(), namely the hash computation. If there were a way to do the find(), and somehow reuse the hash computed by the find() to do the insert() more quickly, then I think Peter's approach would be an even bigger win.
Definitely. That is exactly my point.
... and the below is a preview of my implementation of your (Joe's and Peter's) very helpful suggestions. As you can see, in a nutshell the idea is implementing insert with hint and calling it from operator[] (as per our std::map). In this case the hint is "special", we are not passing a regular iterator, because we have to convey somehow the info that the element is not present yet and in which bucket it will be inserted (assuming no rehashing occurs).
As-is the patch (*) already passes regtesting and a few additional simple tests, it would be nice if Peter could benchmark it, while I refine it to its final (hoepfully cleaner) shape...
#include <tr1/unordered_map> #include <map> typedef std::tr1::unordered_map<int, int> map_type; typedef std::tr1::unordered_map<int, map_type> matrix_type; // typedef std::map<int, int> map_type; // typedef std::map<int, map_type> matrix_type; int main() { const int sz = 1000; matrix_type matrix; for (int iter=0; iter<100; ++iter) { for (int i=0; i<sz; ++i) { for (int j=0; j<sz; ++j) { map_type& row = matrix[i/4]; ++row[j/4]; } } } }
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |