1

The code below executes 4x faster, if near "REPLACING WITH .." line, the functor compare_swaps() will be replaced with direct reference to my_intcmp(). Apparently the indirect use is not being inlined. Why?

inline bool my_intcmp( const int & a, const int & b ) {
        return a < b;
}


template <class T, class compare>
void insertion_sort_3( T* first, T* last, compare compare_swaps ) {
    // Count is 1?
    if( 1 == (last - first) )
        return;

    for( T* it = first + 1; it != last; it ++ ) {
        T val = *it;
        T* jt;

        for( jt = it; jt != first; jt -- ) {
            // REPLACING WITH if( my_intcmp(val, *(jt - 1) ) gives 4x speedup, WHY?
            if( compare_swaps(val, *(jt - 1)) ) {
                *jt = *(jt - 1);
            } else {
                break;
            }
        }

        *jt = val;
    }
}

#define SIZE 100000
#define COUNT 4

int main() {
    int myarr[ SIZE ];

    srand( time(NULL) );

    int n = COUNT;
    while( n-- ) {
        for( int i = 0; i < SIZE; i ++ )
            myarr[ i ] = rand() % 20000;

        insertion_sort_3( myarr, myarr + SIZE, my_intcmp );
    }

    return 0;
}
4
  • BTW, if you want to have a fast sort algorithm, you'd want to use a more effective algorithm than insertion sort. Commented Oct 3, 2012 at 23:49
  • 1
    "why the functor is not inlined?" -- Because my_intcmp isn't a functor.
    – Robᵩ
    Commented Oct 4, 2012 at 0:08
  • 1
    GCC 4.2, -O3 option. Using true functor with inlined operator() helps.
    – AllCoder
    Commented Oct 4, 2012 at 0:33
  • @DietmarKühl: insertion sort is great for mostly sorted collection, e.g. after inserting/updating one element to/in already sorted container.
    – AllCoder
    Commented Oct 4, 2012 at 0:35

1 Answer 1

4

The compiler sees a function pointer which he can't really determine as not changing. I have seen this a couple of times before. The fix to the problem is to use a simple wrapper struct:

struct my_intcmp_wrapper
{
    bool operator()(int v0, int v1) const {
        return my_intcmp(v0, v1);
    }
};

Specifically for build-in types you probably want to pass the objects by value rather than by reference. For inlined functions it probably doesn't make much of a difference but if the function isn't inlined it generally makes the situation worse.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.