Re: tr1::hashtable::operator[]

[Peter Doerfler <gcc at pdoerfler dot com>]

Paolo Carlini wrote:
> 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...

The performance of your patch is the same as with mine for my testcase 
(which I find surprising, I thought there would be a slight benefit from 
the insert with hint). I'm attaching a small artificial testcase that 
shows the effect. It's more drastic than my real use as the old 
implementation takes over a minute to complete against below 3 seconds 
for either patch.

Obviously, your analysis is correct that the overhead of my patch is 
much larger than in the case of map. I did look whether unordered_map 
had insert with hint or anything like lower_bound to get the hint, but 
stopped thinking there. Great job!

Looking forward to seeing your patch applied.

Thanks, Peter

#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];
      }
    }
  }
}