12d8360727
```
Benchmark 97fa3e5936 a820f8f10736 Difference % Difference
------------------------------------------------------ -------------- -------------- ------------ --------------
std::equal(deque<int>)_(it,_it,_it)/1024 510.92 82.64 -428.27 -83.82%
std::equal(deque<int>)_(it,_it,_it)/1048576 518795.61 87141.29 -431654.32 -83.20%
std::equal(deque<int>)_(it,_it,_it)/50 29.24 6.77 -22.46 -76.84%
std::equal(deque<int>)_(it,_it,_it)/8 4.20 3.71 -0.49 -11.61%
std::equal(deque<int>)_(it,_it,_it)/8192 3972.84 643.83 -3329.01 -83.79%
std::equal(deque<int>)_(it,_it,_it,_it)/1024 417.45 81.52 -335.93 -80.47%
std::equal(deque<int>)_(it,_it,_it,_it)/1048576 539228.26 87480.92 -451747.34 -83.78%
std::equal(deque<int>)_(it,_it,_it,_it)/50 22.25 7.25 -15.00 -67.41%
std::equal(deque<int>)_(it,_it,_it,_it)/8 4.75 4.44 -0.31 -6.45%
std::equal(deque<int>)_(it,_it,_it,_it)/8192 3259.01 641.31 -2617.70 -80.32%
std::equal(deque<int>)_(it,_it,_it,_it,_pred)/1024 532.68 327.58 -205.10 -38.50%
std::equal(deque<int>)_(it,_it,_it,_it,_pred)/1048576 600755.28 402988.04 -197767.24 -32.92%
std::equal(deque<int>)_(it,_it,_it,_it,_pred)/50 27.26 25.29 -1.97 -7.22%
std::equal(deque<int>)_(it,_it,_it,_it,_pred)/8 5.20 5.58 0.38 7.31%
std::equal(deque<int>)_(it,_it,_it,_it,_pred)/8192 4204.16 2847.30 -1356.86 -32.27%
std::equal(deque<int>)_(it,_it,_it,_pred)/1024 531.32 329.03 -202.30 -38.07%
std::equal(deque<int>)_(it,_it,_it,_pred)/1048576 598948.55 403822.65 -195125.90 -32.58%
std::equal(deque<int>)_(it,_it,_it,_pred)/50 26.28 16.18 -10.10 -38.43%
std::equal(deque<int>)_(it,_it,_it,_pred)/8 4.44 3.70 -0.74 -16.67%
std::equal(deque<int>)_(it,_it,_it,_pred)/8192 4184.03 2902.98 -1281.05 -30.62%
std::equal(list<int>)_(it,_it,_it)/1024 1168.78 1168.51 -0.27 -0.02%
std::equal(list<int>)_(it,_it,_it)/1048576 1283003.12 1281885.44 -1117.69 -0.09%
std::equal(list<int>)_(it,_it,_it)/50 60.19 44.38 -15.81 -26.27%
std::equal(list<int>)_(it,_it,_it)/8 3.07 3.07 0.00 0.15%
std::equal(list<int>)_(it,_it,_it)/8192 10367.41 11075.24 707.83 6.83%
std::equal(list<int>)_(it,_it,_it,_it)/1024 728.32 734.18 5.86 0.80%
std::equal(list<int>)_(it,_it,_it,_it)/1048576 951276.58 953928.39 2651.81 0.28%
std::equal(list<int>)_(it,_it,_it,_it)/50 31.86 32.32 0.46 1.44%
std::equal(list<int>)_(it,_it,_it,_it)/8 3.11 3.10 -0.01 -0.34%
std::equal(list<int>)_(it,_it,_it,_it)/8192 14940.68 16058.91 1118.22 7.48%
std::equal(list<int>)_(it,_it,_it,_it,_pred)/1024 803.49 813.53 10.05 1.25%
std::equal(list<int>)_(it,_it,_it,_it,_pred)/1048576 1012708.15 1026207.55 13499.40 1.33%
std::equal(list<int>)_(it,_it,_it,_it,_pred)/50 38.68 39.24 0.56 1.46%
std::equal(list<int>)_(it,_it,_it,_it,_pred)/8 4.07 4.07 -0.00 -0.08%
std::equal(list<int>)_(it,_it,_it,_it,_pred)/8192 16632.08 18073.63 1441.55 8.67%
std::equal(list<int>)_(it,_it,_it,_pred)/1024 1162.99 1162.48 -0.51 -0.04%
std::equal(list<int>)_(it,_it,_it,_pred)/1048576 1291522.30 1303819.01 12296.72 0.95%
std::equal(list<int>)_(it,_it,_it,_pred)/50 45.73 46.32 0.59 1.29%
std::equal(list<int>)_(it,_it,_it,_pred)/8 4.35 4.40 0.04 1.03%
std::equal(list<int>)_(it,_it,_it,_pred)/8192 15035.93 14598.06 -437.87 -2.91%
std::equal(vector<bool>)_(aligned)/1024 0.22 0.22 0.00 0.04%
std::equal(vector<bool>)_(aligned)/1048576 0.22 0.22 0.00 0.12%
std::equal(vector<bool>)_(aligned)/50 0.22 0.22 0.00 0.02%
std::equal(vector<bool>)_(aligned)/8 0.22 0.22 0.00 0.03%
std::equal(vector<bool>)_(aligned)/8192 0.22 0.22 0.00 0.05%
std::equal(vector<bool>)_(unaligned)/1024 6.34 6.39 0.04 0.70%
std::equal(vector<bool>)_(unaligned)/1048576 6809.31 6833.52 24.21 0.36%
std::equal(vector<bool>)_(unaligned)/50 1.11 0.92 -0.19 -17.55%
std::equal(vector<bool>)_(unaligned)/8 1.11 1.05 -0.06 -5.29%
std::equal(vector<bool>)_(unaligned)/8192 59.27 59.92 0.65 1.10%
std::equal(vector<int>)_(it,_it,_it)/1024 80.39 80.59 0.20 0.25%
std::equal(vector<int>)_(it,_it,_it)/1048576 72546.36 73803.43 1257.07 1.73%
std::equal(vector<int>)_(it,_it,_it)/50 3.92 4.43 0.51 12.92%
std::equal(vector<int>)_(it,_it,_it)/8 1.46 1.47 0.01 0.75%
std::equal(vector<int>)_(it,_it,_it)/8192 553.63 559.59 5.95 1.07%
std::equal(vector<int>)_(it,_it,_it,_it)/1024 78.69 78.37 -0.32 -0.40%
std::equal(vector<int>)_(it,_it,_it,_it)/1048576 72238.51 73582.13 1343.62 1.86%
std::equal(vector<int>)_(it,_it,_it,_it)/50 4.18 4.62 0.44 10.52%
std::equal(vector<int>)_(it,_it,_it,_it)/8 1.68 1.66 -0.01 -0.87%
std::equal(vector<int>)_(it,_it,_it,_it)/8192 549.35 555.24 5.89 1.07%
std::equal(vector<int>)_(it,_it,_it,_it,_pred)/1024 361.08 363.32 2.24 0.62%
std::equal(vector<int>)_(it,_it,_it,_it,_pred)/1048576 391367.63 394209.88 2842.25 0.73%
std::equal(vector<int>)_(it,_it,_it,_it,_pred)/50 15.24 15.83 0.59 3.87%
std::equal(vector<int>)_(it,_it,_it,_it,_pred)/8 3.18 3.19 0.01 0.40%
std::equal(vector<int>)_(it,_it,_it,_it,_pred)/8192 2992.57 3026.90 34.32 1.15%
std::equal(vector<int>)_(it,_it,_it,_pred)/1024 362.45 365.46 3.01 0.83%
std::equal(vector<int>)_(it,_it,_it,_pred)/1048576 399898.16 402718.88 2820.72 0.71%
std::equal(vector<int>)_(it,_it,_it,_pred)/50 14.79 14.79 -0.01 -0.04%
std::equal(vector<int>)_(it,_it,_it,_pred)/8 2.45 2.52 0.06 2.64%
std::equal(vector<int>)_(it,_it,_it,_pred)/8192 3062.16 3088.11 25.95 0.85%
Geomean 253.49 200.79 -52.70 -20.79%
```
62 lines
2.4 KiB
C++
62 lines
2.4 KiB
C++
//===----------------------------------------------------------------------===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#ifndef _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
|
|
#define _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
|
|
|
|
#include <__config>
|
|
#include <__iterator/segmented_iterator.h>
|
|
|
|
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
|
|
# pragma GCC system_header
|
|
#endif
|
|
|
|
_LIBCPP_BEGIN_NAMESPACE_STD
|
|
|
|
// __find_segment_if is a utility function for optimizing iteration over segmented iterators linearly.
|
|
// [__first, __last) has to be a segmented range. __pred is expected to take a range of local iterators.
|
|
// It returns an iterator to the first element that satisfies the predicate, or a one-past-the-end iterator if there was
|
|
// no match.
|
|
|
|
template <class _SegmentedIterator, class _Pred>
|
|
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _SegmentedIterator
|
|
__find_segment_if(_SegmentedIterator __first, _SegmentedIterator __last, _Pred __pred) {
|
|
using _Traits = __segmented_iterator_traits<_SegmentedIterator>;
|
|
|
|
auto __sfirst = _Traits::__segment(__first);
|
|
auto __slast = _Traits::__segment(__last);
|
|
|
|
// We are in a single segment, so we might not be at the beginning or end
|
|
if (__sfirst == __slast)
|
|
return _Traits::__compose(__sfirst, __pred(_Traits::__local(__first), _Traits::__local(__last)));
|
|
|
|
{ // We have more than one segment. Iterate over the first segment, since we might not start at the beginning
|
|
auto __llast = _Traits::__end(__sfirst);
|
|
auto __liter = __pred(_Traits::__local(__first), __llast);
|
|
if (__liter != __llast)
|
|
return _Traits::__compose(__sfirst, __liter);
|
|
}
|
|
++__sfirst;
|
|
|
|
// Iterate over the segments which are guaranteed to be completely in the range
|
|
while (__sfirst != __slast) {
|
|
auto __llast = _Traits::__end(__sfirst);
|
|
auto __liter = __pred(_Traits::__begin(__sfirst), _Traits::__end(__sfirst));
|
|
if (__liter != __llast)
|
|
return _Traits::__compose(__sfirst, __liter);
|
|
++__sfirst;
|
|
}
|
|
|
|
// Iterate over the last segment
|
|
return _Traits::__compose(__sfirst, __pred(_Traits::__begin(__sfirst), _Traits::__local(__last)));
|
|
}
|
|
|
|
_LIBCPP_END_NAMESPACE_STD
|
|
|
|
#endif // _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
|