Sorting should use inlineable comparison function

[thomasm]

TPIE has switched to using std::sort instead of qsort. However, the comparison function is still supplied through a pointer and it makes a huge difference since we have to make a indirect funtion call for each comparison. We should supply the comparison object in such a way that the function can be inline!

For more motivation, read this:  http://www.tilander.org/aurora/2007/12/comparing-stdsort-and-qsort.html

[thomasm]

The offending line is in source:/trunk/tpie/internal_sort.h@1858#L354

[adanner]

Replying to thomasm:

The offending line is in source:/trunk/tpie/internal_sort.h@1858#L354

I'm confused by this. I thought this is still possible given the existing code. There is Internal_Sorter_Op<T> in source:/trunk/tpie/internal_sort.h@1858#L253 that uses the comparison operator <. The Internal_Sorter_Obj can takes a class, not a function pointer. That class has compare() method (which can be inlined). The name compare() is a TPIE naming convention. The TPIE2STL_cmp wrapper in source:/trunk/tpie/comparator.h@1858 converts the compare() method to use the bool operator() which is the STL convention. This is inlined. We removed comparison functions and replaced them with comparison objects a while ago. Are you saying things are still messed up?

[thomasm]

Good point, I am still investigating, I'm not sure what happens. The problem is that we're supplying a pointer to a object (cmp_o) of the type CMPR, I want to make cmp_o an object copied by value instead. I'm not sure if the compiler inlines a function accessed through a pointer, even if it knows the type of the class - but I'm guessing it doesn't.

Also, I would love to somehow get rid of the TPIE2STL stuff since it adds another comparisons per method-invocation.

[adanner]

Replying to thomasm:

Good point, I am still investigating, I'm not sure what happens. The problem is that we're supplying a pointer to a object (cmp_o) of the type CMPR, I want to make cmp_o an object copied by value instead. I'm not sure if the compiler inlines a function accessed through a pointer, even if it knows the type of the class - but I'm guessing it doesn't. Also, I would love to somehow get rid of the TPIE2STL stuff since it adds another comparisons per method-invocation.

Right, TPIE2STL should go, but it breaks backwards compatibility. We would just need to document the new format, but changing it brings things more inline with STL. The pointer to an object business was probably due to historical reasons as well. The changes you propose sound good.

[thomasm]

Yup, we (you?) added TPIE2STL to maintain backwards compatibility and to keep the old way of supplying pointers to comparison functions/objects, and I maybe we should keeo this option around for a bit longer. However, after the huge changes last year (namespaces, std::string and more) backwards compatibility shouldn't really be a concern right now :).

[thomasm]

Some preliminary testing seems to indicate that at least GCC does in fact inline the comparison through the pointer sometimes. Surprisingly I could not detect an overhead from the TPIE2STL conversion either.