c++ - What is the use of GCC find/find_if overload for random access iterators? -

c++ - What is the use of GCC find/find_if overload for random access iterators? -

i've found snippet while looking @ <algorithm> implementations:

/** * @if maint * overload used find() rai case. * @endif */ template<typename _randomaccessiterator, typename _tp> _randomaccessiterator find(_randomaccessiterator __first, _randomaccessiterator __last, const _tp& __val, random_access_iterator_tag) { typename iterator_traits<_randomaccessiterator>::difference_type __trip_count = (__last - __first) >> 2; ( ; __trip_count > 0 ; --__trip_count) { if (*__first == __val) homecoming __first; ++__first; if (*__first == __val) homecoming __first; ++__first; if (*__first == __val) homecoming __first; ++__first; if (*__first == __val) homecoming __first; ++__first; } switch (__last - __first) { case 3: if (*__first == __val) homecoming __first; ++__first; case 2: if (*__first == __val) homecoming __first; ++__first; case 1: if (*__first == __val) homecoming __first; ++__first; case 0: default: homecoming __last; } }

for understanding "trick" here perform distance / 4 iterations 4 if(...) return; ++ , same remaining distance % 4 items within switch. expected, same number of comparisons , incrementation performed, , theoretical complexity same. how improve optimization trivial input iterator implementation? micro-optimization lower number of loop iterations or there smarter don't get?

this technique called loop unrolling avoid cost of checking status @ every iteration tradeoff against binary size (and space).

the speedup depends on architecture super-scalar cpu can take advantage on breaking potentially unsafe dependency-chains might stall cpu when cache missing.

although theoretical complexity same (if consider comparisons dominant operations), algorithm (on cpu described) can perform faster. far complexity constraints respected, stl library can implement own version though.

related answers: when, if ever, loop unrolling still useful?

c++ gcc