[LLVMbugs] [Bug 19708] New: libc++'s std::find is about 50% slower than the libstdc++'s

[bugzilla-daemon at llvm.org]

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

            Bug ID: 19708
           Summary: libc++'s std::find is about 50% slower than the
                    libstdc++'s
           Product: libc++
           Version: unspecified
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: cfy1990 at gmail.com
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

the function find is copied from libstdc++, and the function is copied from
libc++
$ cat main.cpp 
#include <celero/Celero.h>
#include <array>
#include <iostream>

#include <random>
template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
find(_RandomAccessIterator __first, _RandomAccessIterator __last,
     const _Tp& __val)
{
    int __trip_count = (__last - __first) >> 2;

    for ( ; __trip_count > 0 ; --__trip_count)
    {
        if (*__first == __val)
            return __first;
        ++__first;

        if (*__first == __val)
            return __first;
        ++__first;

        if (*__first == __val)
            return __first;
        ++__first;

        if (*__first == __val)
            return __first;
        ++__first;
    }

    switch (__last - __first)
    {
    case 3:
        if (*__first == __val)
            return __first;
        ++__first;
    case 2:
        if (*__first == __val)
            return __first;
        ++__first;
    case 1:
        if (*__first == __val)
            return __first;
        ++__first;
    case 0:
    default:
        return __last;
    }
}
template <class _InputIterator, class _Tp>
_InputIterator
find2(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
    for (; __first != __last; ++__first)
        if (*__first == __value_)
            break;
    return __first;
}


std::random_device rd;
std::uniform_int_distribution<int> dist(0, 1024000);
const int size=100000;
std::array<int,size> arr;
int value;
int main(int argc, char** argv) {
    std::cout << arr[0] << "\n";
    for(int &a :arr){
        a = dist(rd);
    }
    value = arr.at(size-1);
    celero::Run(argc, argv); return 0; }

BASELINE(Find, find_in_libstdcxx, 10, 10000)
{
    celero::DoNotOptimizeAway(find(arr.begin(), arr.end(), value));
}

BENCHMARK(Find, find_in_libcxx, 10, 10000)
{
    celero::DoNotOptimizeAway(find2(arr.begin(), arr.end(), value));
}

./find-performance-test 
0
[==========] 
[  CELERO  ]
[==========] 
[ STATUS   ] Timer resolution: 1000000.000000 us
[==========] 
[ STAGE    ] Baselining
[==========] 
[ RUN      ] find_in_libstdcxx [10 samples of 10000 calls each.]
[     DONE ] Find.find_in_libstdcxx 5.142554 sec. [4.752050e-05 us/call]
[2104.354963 calls/sec]
[ BASELINE ] Find.find_in_libstdcxx 1.000000 [SD: 63003.231701, V:
3969407204.711111, K: 3.506430]
[==========] 
[ STAGE    ] Benchmarking
[==========] 
[ RUN      ] find_in_libcxx [10 samples of 10000 calls each.]
[     DONE ] Find.find_in_libcxx 7.757648 sec. [7.598750e-05 us/call]
[1316.005922 calls/sec]
[ BASELINE ] Find.find_in_libcxx 1.599047 [SD: 13314.115398, V:
177265668.844445, K: -0.839739]
[==========] 
[ STAGE    ] 
[==========]

-- 
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/20140511/5a347342/attachment.html>