tr1::hashtable::operator[]

[Peter Doerfler]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: testUnorderedMap.cpp
Type: text/x-c++src
Size: 487 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20060515/d7c1e658/attachment.bin>