[llvm-bugs] [Bug 21275] Performance of unordered_multimap::insert much slower than GCC 4.8.2

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=21275

Eric Fiselier <eric at efcs.ca> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |DUPLICATE

--- Comment #12 from Eric Fiselier <eric at efcs.ca> ---

(In reply to comment #11)
> As explained at the top of this PR, the current implementation of libc++'s
> unordered_map and unordered_multimap is wildly uncompetitive with GCC with
> and without hints.

The problem you describe at the top of this PR is exactly the same as PR16747.
While you may not agree with the resolution this problem has been discussed and
decided on. 

ALso you ONLY describe a problem with std::unordered_multimap. I have yet to
see how libc++'s std::unordered_map is uncompetative with GCC's. I have spent
time benchmarking both implementations and I do not see the problem. Could you
explain further?

> One cannot possibly know
> the key distribution in advance, so the libc++ implementation of
> unordered_map and unordered_multimap is simply not usable in its present
> form on large data sets. 

While that is somewhat true for unordered_multimap PR16747 describes how to use
unordered_multimap to get the behavior and performance you desire.

You once again mention std::unordered_map but I don't know what your refering
too. The problem only exists in std::unordered_multimap.



> Surely libc++ can be adapted to do something similar to GCC libstdc++'s
> superior algorithm? All the has to be done is to keep a pointer to the end
> of the values in the hash bucket and check that value first instead of doing
> a pointless and inefficient sequential scan.

I've looked into making changes to add an "bucket end" pointer but it seems
quite complicated.

First you have to understand that a change like this is made harder by the fact
we can't introduce ABI breaking changes. That means I cant actually add any new
class data members to any data type in std::unordered_multimap. This makes the
change a lot harder then simply adding a new list of bucket pointers.

Second, std::unordered_multimap and std::unordered_map are implemented using
the same underlying container `__hash_table`. Any changes made to
`__hash_table` to support std::unordered_multimap MUST NOT introduce needless
overhead to std::unordered_map. I don't see how we can easily make the changes
you describe without affecting std::unordered_map.


While I don't agree with Howard Hinnants decision to make
std::unordered_multimap do insertions at the end I don't think I can change the
existing behavior. If any change is going to be made to fix the performance
problems it should be to do insertions at the front. 

I'm closing this bug as a duplicate of PR16747. If I missed a performance
problem in std::unordered_map please reopen this bug.

*** This bug has been marked as a duplicate of bug 16747 ***

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20150826/5c154f26/attachment.html>