[cfe-dev] error with lambda function that results in endless loop

[Florian Pflug]

On May3, 2012, at 11:53 , Ran Regev wrote:
> Surly returning true regardless of the value of the elements has no real meaning and can results in nonsense like a1<a2==true && a2<a1==true
> And surly this is a bad idea to write code like this, but still - why it passes 30 and not 31?

Optimized sort implementations usually choose which algorithm to use based on the input length. This is done because the setup overhead of more sophisticated algorithms are often large enough to cause a net loss in performance for small inputs. In other words, a O(n*log(n)) algorithm may turn out to be slower than a O(n*n) algorithm if the former has a larger setup cost then the latter, and n is small.

And indeed, according to http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm libcxx's std::sort contains the code fragment

    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
    ...
    if (__len <= __limit) {
        _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
        return;
    }
    ...

So the reason for the behaviour you're observing is that __insertion_sort_3() doesn't loop endlessly for bogus comparison functions, whereas the more sophisticated (and generally faster) algorithm used for larger inputs does.

best regards,
Florian Pflug