Tại sao std :: find thực hiện theo cách này?

Question

Tôi tình cờ chạy vào nguồn của std::find và thấy nó gây nhầm lẫn cho tôi. Về cơ bản, nó chia số lượng mục cho 4 và thực hiện so sánh 4 trong mỗi vòng:

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; 

    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; 
} 
} 

Tôi không biết tại sao nó lại được thực hiện theo cách này. Hình như một số tối ưu hóa. Nhưng tôi không nghĩ rằng điều này sẽ tận dụng lợi thế của đa lõi dễ dàng. Đây là một chủ đề duy nhất anyway.

Bất kỳ ý tưởng nào?

Answer 1

Có vẻ như loop unwinding, còn được gọi là bỏ vòng lặp.

Answer 2

Đó là việc bỏ vòng lặp. Kết quả là như nhau, nhưng nó thân thiện hơn với bộ vi xử lý.

Sự phức tạp tiệm cận là như nhau.

Answer 3

Đó là Duff's device. Đó là một kỹ thuật tối ưu hóa cũ kết hợp trong khi và chuyển đổi câu lệnh theo cách đặc biệt. Nó sử dụng vòng lặp unroling. Trong assembler bạn sẽ nhảy ngay bên trong một vòng lặp chưa được kiểm soát.

Answer 4

Không hoàn toàn chắc chắn, tôi nghĩ đây là loại bỏ vòng lặp.

Xem tính năng hủy vòng lặp trong: http://www.codeproject.com/Articles/6154/Writing-Efficient-C-and-C-Code-Optimization