[LLVMbugs] [Bug 21275] New: Performance of unordered_multimap::insert much slower than GCC 4.8.2

[bugzilla-daemon at llvm.org]

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

            Bug ID: 21275
           Summary: Performance of unordered_multimap::insert much slower
                    than GCC 4.8.2
           Product: libc++
           Version: 3.4
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: zaxxon2011 at gmail.com
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

The performance of unordered_multimap::insert is very slow in LLVM libc++ 
when used on large data sets that have degenerate non-uniform key distribution. 

// g++ -std=c++11 -O3 umm.cpp -o umm && time ./umm
// 13.5s for Apple LLVM version 6.0 (clang-600.0.51) (based on LLVM 3.5svn).
// 0.016s for GCC version 4.8.2.
#include <unordered_map>
int main() {
    std::unordered_multimap<int,int> m;
    for (int x = 0; x < 100000; ++x)
        m.insert(std::pair<int,int>(x%4, x));
    return 0;
}

I recognize that a another ticket was filed on this issue and marked as
WONTFIX. 
But even using max_load_factor() does not help LLVM libc++ get anywhere near 
the performance of GCC. 

One cannot always know in advance what the key distribution of the data set
will 
be - it can be uniform or degenerate. Data sets can be multi-gigabyte and would 
not be conducive to multiple passes to determine key distribution. As a 
workaround I used #ifdefs with an ordered std::multimap on Mac which is only 
twice as slow as GCC 4.8.2 libstdc++'s unordered_multimap for this scenario, 
which is not ideal.

-- 
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/20141014/6f783330/attachment.html>