error with lambda function that results in endless loop

Colleagues,

While working with some c++11 features I have encountered a problem with std::sort;

From some reason it was stuck when I tried to sort more than 10 elements.

I simplified the code to use normal int, instead of my objects, and it gets stuck above 30 elements.

Here is the code, followed by the compilation command line, followed by the output, followed by more information:

12:30:06/auto> cat sortproblem.cpp

#include <iostream>
#include <vector>

void checkSort( std::vector<int>& v )
{
    std::sort( v.begin(), v.end(),
        [] (const int& a1, const int& a2) -> bool
        {
            return true;
        }
    );
}

int main()
{
    unsigned int MAX_ELEMENTS;

    MAX_ELEMENTS = 30;
    std::vector< int > v1;

    std::cout << "v1 created" << std::endl;

    for ( unsigned int i = 0; i < MAX_ELEMENTS; ++ i )
    {
        v1.push_back( i );
    }

    std::cout << "v1 filled" << std::endl;

    checkSort( v1 );

    std::cout << "v1 sorted" << std::endl;

    MAX_ELEMENTS = 31;
    std::vector< int > v2;

    std::cout << "v2 created" << std::endl;

    for ( unsigned int i = 0; i < MAX_ELEMENTS; ++ i )
    {
        v2.push_back( i );
    }

    std::cout << "v2 filled" << std::endl;

    checkSort( v2 );

    std::cout << "v2 sorted" << std::endl;
}

12:30:07/auto> ./build
------------------------------------ command line -----------------------------------------
/auto/tnd_cesr/users/rregev/c++11/clang/llvm/build/Debug+Asserts/bin/clang++
sortproblem.cpp
-o run
-std=c++11 -Wall -Wno-c++11-extensions -rpath /auto/tnd_cesr/users/rregev/c++11/clang/libcxx/build/lib -g -O0 -ferror-limit=3
-I ../../clang/libcxx/include/
-L/auto/tnd_cesr/users/rregev/c++11/clang/libcxx/build/lib
-lc++
------------------------------------ compilation starts here -------------------------------
------------------------------------ compilation ends here ---------------------------------
[sussita2]12:30:17/auto> ./run
v1 created
v1 filled
v1 sorted
v2 created
v2 filled

------------------ findings ------------------
A)
This is the line that loops-forever:
0x0000000000401ef6 in std::__1::__sort<<lambda at sortproblem.cpp:8:9> &, int *>(int *, int *, class {...} &) (__first=0x605160, __last=0x6051dc, __comp=...)
    at ../../clang/libcxx/include/algorithm:3616
3616 while (__comp(*__i, *__m))

B)
When changing the lambda function into something more meaningful than just returning true the problem was solved.
    std::sort( v.begin(), v.end(),
        [] (const int& a1, const int& a2) -> bool
        {
            return a1 < a2;
        }
    );
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?

Ran.

This e-mail message is intended for the recipient only and contains information which is CONFIDENTIAL and which may be proprietary to ECI Telecom. If you have received this transmission in error, please inform us by e-mail, phone or fax, and then delete the original and all copies thereof.

The standard requires that the comparator shall provide a strict weak
ordering on the values. Your comparator doesn't and thus invokes UB.

Forever looping past a particular cutoff point is very valid undefined
behaviour. Some standard libraries are friendly enough to test whether
your comparator is broken or not in debug mode with a nice assert. This
one apparently isn't.

As for the hard cutoff, it's not unusual that implementations choose
between several different sorts depending on the size, the phase and
possibly the nature of the data.

This has nothing to do with lambdas.

You already know what the problem is, I'm not sure what you expect to happen.

std::sort requires a strict weak ordering, always returning true does not fulfill that criteria.

Have a look here:
http://cpp-next.com/archive/2010/02/order-i-say/

Checked versions of Microsoft’s standard library attempt to catch this type of problem, you end up with an assert if I recall, but that's a QOI issue.

Technically running your ill-defined program is allowed to do anything, including getting stuck at 31 elements and appearing to work at 30.

Ben

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

According to the following presentation, libc++ is able to detect 8 different patterns when it sort a list:

http://llvm.org/devmtg/2010-11/Hinnant-libcxx.pdf

-- Jean-Daniel

Just fyi, there's not a set number of patterns that it looks for. At every partition it checks to see if it took zero swaps to do the partition, and in this case, it draws a tentative conclusion that if the sequence is already partitioned, it might also be already sorted, or nearly so. It will try an insertion sort on the sequence in this case since insertion sort on an ordered sequence takes only N comparisons. If the insertion sort has to do more than a small number of insertions (8 I think), the insertion sort is abandoned, and the quick sort algorithm resumes.

This checking and switching to insertion sort is done during every partition phase as the quick sort recurses to smaller and smaller sub-sequences. So as a subsequence becomes "more sorted", it becomes more likely to switch over to an insertion sort, and if successful, short circuits the remaining recursive quick sort decent for that sub-sequence.

This combination of algorithms will sort an ordered sequence with 2N comparisons and a reverse ordered sequence with 3N comparisons. The cost of the check is an integer increment with each swap, and a branch on that integer after each partition.

Howard

Interesting.
Thank you for this information :slight_smile:

Thank you all for the insights!
Learnt a lot.

Ran.