When is explicit projection support really needed?

[Morwenn]

Now that issue #36 is closed, sorters implementers don't need to manually handle projections: sorter_facade will aggregate a comparison and a projection function in a projection_compare class template. While this is great per se, it actually raises new interesting questions: is it better to manually handle projections or to let projection_compare handle them? A few numbers to take into account:

• When given std::greater<> and std::negate<> at once, merge_sorter was clearly faster when projection_compare handled the projection than when the projection was manually handled. It probably has to do with the fact that mergesort is recursive and a lot of comparison and projection objects are passed down the call stack. std::greater<> and std::negate<> are empty classes, so projection_compare<std::greater<>, std::negate<>> probably takes advantage of EBCO and we end up passing fewer objects around. Moreover, utility::as_function is only applied once. I would expect the compiler to optimize the transformation away but maybe it actually has a cost. Update: apparently it is not the case anymore.
• On the other hand, quick_sorter was globally faster when projections were handled manually (it's also a good sorter to perform such tests since it's recursive). It probably has to do with the fact that we only need to project a value only once before each partitioning operation when manually handling projections, while this very projection is done again and again when projection_compare handles it.
• Even though it needs to project each object only once, insertion_sorter didn't seem to be better with manual projection handling, but wasn't better with automagic projection handling either.

Now, before making a decision, several things need to be considered: we need to check how an algorithm performs when given nothing, a comparison, a projection, or both at once. If there is a clear winner, then go for it, otherwise we're probably fine letting projection_compare handle the projections.

---

However, there are other creatures lurking in the dark and even more questions: what to do when an algorithm that performs better with automagic projections needs to call another algorithm that performs better with manual handling? Can we get the best of both?

I have a few ideas, but more tests are needed before a clear answer: projection_compare only stores the transformed projection, but assuming that either the non-transformed or the transformed projection weights nothing (I believe it's often the case), then storing it too shouldn't cost anything more, and the non-transformed function could then be retrieved thanks to a getter. A good heuristic would be to create another class to pack the additional function, let's call it projection_compare_full and make make_projection_compare return a projection_compare_full instance instead of a projection_compare one if the additional information weights nothing.

Going further, we could then add overloads to sorter_facade::operator() that take a projection_compare_full instance and dispatch the comparison and the projection functions to the sorter implementation iff it manually handles projections (if it accepts a dedicated projection parameter). That way, we could call a sorter that performs better with a projection_compare object but that can still call a another sorter that performs better with manual projection handling, while still getting the best of both.

Also, that design can be considerably simpler if as_function(as_function(projection)) is always guaranteed to be equivalent to as_function(projection). In such a case, we could just store as_function(projection) in projection_compare, returning it when a projection is needed, and totally get rid of projection_compare_full.

It seems that as_function(as_function(projection)) always has the same type than as_function(projection), so we can just go ahead and already give accessors to projection_compare and drop a part of the overly complicated design.

[vendethiel]

more templates pls

[nabijaczleweli]

You must construct additional templates.

[Morwenn]

Haha, it could bring to 30+ the number of sorter_facade::operator() overloads. I'm trying to convince me it's not necessary but it would be soooo fun. And the purrformance gain when you use merge_sorter with both a comparison and a projection is totally worth it, right? :D

[vendethiel]

@nabijaczleweli y u steal me memes

@Morwenn doesn't look useful at first glance... But then I'm not a heavy sorter :p.

[nabijaczleweli]

@vendethiel Your me me was but an inspiration

[Morwenn]

I'm killing that one, I'll just trust the compilers to optimize everything away when passed both a comparison and a projection.