31

I just implemented the quick sort algorithm by using C++11 variadic templates to evaluate it at compilation time. However, I encounter a performance issue when the data set is too large.

#include <iostream>

using namespace std;

template<int... vs>
struct Seq
{}; 
template<int v1, int...vs>
struct Seq<v1, vs...>{
};


template<typename newT, typename srcT>
struct PushFront{
};
template<int vadded, int...vs>
struct PushFront<Seq<vadded>, Seq<vs...>>{
  typedef Seq<vadded, vs...> ResultType;
};

template<typename T>
struct PopFront{
};
template<int v1, int...vs>
struct PopFront<Seq<v1, vs...>>{
  typedef Seq<vs...> RemaindType;
  typedef Seq<v1>    ResultType;
};

template<typename T1, typename T2>
struct CatSeq{};
template<int...v, int...us>
struct CatSeq<Seq<v...>, Seq<us...>>{
  typedef Seq< v..., us... >  ResultType;
};


template<bool c, typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify{
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<true, NewT, TrueClsT, FalseClsT>{
  typedef typename PushFront<NewT, TrueClsT>::ResultType NewTrueClsT;
  typedef FalseClsT  NewFalseClsT;
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<false, NewT, TrueClsT, FalseClsT>{
  typedef TrueClsT  NewTrueClsT;
  typedef typename PushFront<NewT, FalseClsT>::ResultType NewFalseClsT;
};

template<typename T1, typename T2>
struct Compare{};
template<int v1, int v2>
struct Compare<Seq<v1>, Seq<v2>>{
  static const bool result=(v1>=v2); 
};


template<typename AnchorT, typename SeqT, typename GESet, typename LSet>
struct PartitionImpl{};
template<typename GESet, typename LSet, int anchorv, int v1>
struct PartitionImpl<Seq<anchorv>, Seq<v1>, GESet, LSet>{
  static const bool isge=Compare<typename PopFront<Seq<v1>>::ResultType, Seq<anchorv>>::result;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewTrueClsT  RstGESet;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewFalseClsT  RstLSet;  
};
template<typename GESet, typename LSet, int anchorv, int v1, int...vs>
struct PartitionImpl<Seq<anchorv>, Seq<v1, vs...>, GESet, LSet>{
  static const bool isge=Compare<typename PopFront<Seq<v1, vs...>>::ResultType, Seq<anchorv>>::result;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewTrueClsT  TmpRstGESet;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewFalseClsT  TmpRstLSet;

  typedef typename PartitionImpl<Seq<anchorv>, Seq<vs...>, TmpRstGESet, TmpRstLSet>::RstGESet RstGESet;
  typedef typename PartitionImpl<Seq<anchorv>, Seq<vs...>, TmpRstGESet, TmpRstLSet>::RstLSet  RstLSet;
};


template<typename T>
struct Partition{
};
template<int v1, int v2, int...vs>
struct Partition<Seq<v1, v2, vs...>>{
  typedef Seq<v1> AnchorType;
  typedef Seq<> GESet;
  typedef Seq<> LSet;
  typedef typename PartitionImpl<AnchorType, Seq<v1, v2, vs...>, GESet, LSet>::RstGESet  RstGESet;
  typedef typename PartitionImpl<AnchorType, Seq<v1, v2, vs...>, GESet, LSet>::RstLSet   RstLSet;
};

//why introduce this? refer to Sort
template<typename SrcT, typename GESet, typename LSet, template<typename > class SortOp>
struct SortSub{  
  typedef typename SortOp<GESet>::ResultType  TmpGESet2;
  typedef typename SortOp<LSet>::ResultType   TmpLSet2;
};
template<typename SrcT, typename LSet, template<typename> class SortOp>
struct SortSub<SrcT, SrcT, LSet, SortOp>{
  typedef SrcT  TmpGESet2;
  typedef typename SortOp<LSet>::ResultType   TmpLSet2;
};
template<typename SrcT, typename GESet, template<typename> class SortOp>
struct SortSub<SrcT, GESet, SrcT, SortOp>{
  typedef typename SortOp<GESet>::ResultType  TmpGESet2;
  typedef SrcT   TmpLSet2;
};

template<typename T>
struct Sort;
template<>
struct Sort<Seq<>>{
  typedef Seq<> ResultType;
};
template<int v>
struct Sort< Seq<v> >{
  typedef Seq<v> ResultType;
};
template<int v1, int...vs>
struct Sort< Seq<v1, vs...> >{
  typedef Seq<v1, vs...> SrcType;
  typedef typename Partition< Seq<v1, vs...> >::RstGESet TmpGESet;
  typedef typename Partition< Seq<v1, vs...> >::RstLSet TmpLSet;

  //to by pass the case SrcType <==> TmpGESet or  SrcType <==> TmpLSet
  typedef typename SortSub<SrcType, TmpGESet, TmpLSet, Sort>::TmpGESet2  TmpGESet2;
  typedef typename SortSub<SrcType, TmpGESet, TmpLSet, Sort>::TmpLSet2   TmpLSet2;

  typedef typename CatSeq<TmpGESet2, TmpLSet2>::ResultType ResultType;
};


void dumpSeqTypeImpl(Seq<> ){
}
template<int v1>
void dumpSeqTypeImpl(Seq<v1> ){
  cout<<v1<<" ";
}
template<int v1, int...vs>
void dumpSeqTypeImpl(Seq<v1, vs...> ){
  cout<<v1<<" ";
  dumpSeqTypeImpl( Seq<vs...>() );
}
template<int...vs>
void dumpSeqType(Seq<vs...> ){
  cout<<"Seq type < ";
  dumpSeqTypeImpl( Seq<vs...>() );
  cout<<" >"<<endl;
}

    //test data
#include "qsort_input.txt"

int main(){
  //Seq<>  s0;// aggregate ‘Seq<> s0’ has incomplete type and cannot be defined
  Seq<1> s1;
  Seq<1, 2> s2;

  typedef Seq<5, 5, 5> TestType_SAME;
  TestType_SAME same;
  dumpSeqType( same );
  typename Partition< TestType_SAME >::RstGESet _ts1;
  typename Partition< TestType_SAME >::RstLSet _ts2;
  dumpSeqType( _ts1 );
  dumpSeqType( _ts2 );

#if 1
  typedef Seq<4, 7, 3, 9, 1, 2, 5, 5, 19, 5> TestType;
  TestType s3;
  dumpSeqType( s3 );
  typename Partition< TestType >::RstGESet ts1;
  typename Partition< TestType >::RstLSet ts2;
  dumpSeqType( ts1 );
  dumpSeqType( ts2 );

  typename Sort<TestType>::ResultType so1;
  dumpSeqType( so1 );
#endif 

#if 1
  typedef Seq<TEST_DATA_100> TAdvanceType;
  typename Sort<TAdvanceType>::ResultType soadvance;
  dumpSeqType(soadvance);
#endif

  return 0;
}

When the data set is TEST_DATA_100, it takes 1.7s to compile.
When the data set is TEST_DATA_1000, the compiler seems to halt....

I'm using gcc 4.6.0.

NmdMystery
  • 2,778
  • 3
  • 32
  • 60
Yuncy
  • 761
  • 1
  • 9
  • 20

2 Answers2

10

Have you also looked at its memory consumption? Note that quicksort itself is worse than linear, with a quite bad worse case runtime. This multiplies with the worse than linear runtime behaviour of certain steps of template compilation and instantiation (sometimes those are exponentional). You should maybe graph your compiletime for various datasets to observe the real complexity class for your code. Usually template metaprogramming with such large datasets is not feasible.

Edit: Out of curiosity I tried the code out and found that up until ~500 it follows roughly the formula pow(N*log(N),1.47)*0.0004+0.6 but then starts to get incredibly much slower, with 155 seconds for 700 items. Also at around that it starts eating very much ram (3GiB for 600) which leads me to the conclusion that for 1000 elements it will need more ram than most people have and will take hours to compile.

Further note that the code does not work when not every element is unique.

PlasmaHH
  • 15,673
  • 5
  • 44
  • 57
  • 4
    http://gcc.gnu.org/gcc-4.5/changes.html: `Compilation time for code that uses templates should now scale linearly with the number of instantiations rather than quadratically, as template instantiations are now looked up using hash tables.` – Sebastian Mach Aug 25 '11 at 10:42
  • Sounds like they have a fixed size for the hashtable and don't grow it, adn things degenerate after 500 elements here (which of course cause a much bigger amount of instantiations) – PlasmaHH Aug 25 '11 at 10:44
  • I took 4.6, since the OP used it too. – PlasmaHH Aug 25 '11 at 11:11
  • All I can say is: Interesting. I share your assumption about the hash table, then. – Sebastian Mach Aug 25 '11 at 11:26
  • Great found. About the "the code does not work when not every element is unique." I'll fix tomorrow. And since i run linux in Virtual Box, i didn't trace the performance. – Yuncy Aug 25 '11 at 15:56
  • Hi,PlasmaHH. I just fixed the bug "when not every element is unique". Thank you very much. – Yuncy Aug 26 '11 at 03:48
5

You are using recursive metafunctions to build your quicksort. What exactly did you expect to happen when you tried to shove 1000 recursive instantiations at the compiler?

Just because a function can theoretically take arbitrary numbers of arguments does not mean that the compiler actually can handle arbitrary numbers of arguments. Compilers have limits.

Besides: what's the point of compile-time sorting? You could do that off-line and copy the data into the .cpp file. Or just run std::sort one time when the program starts.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • 2
    Compile-time sort *could* be useful if it were types you were sorting. – R. Martinho Fernandes Aug 25 '11 at 10:12
  • 3
    The point of such code is usually that the code documents exactly what it's doing. You present the data the way it seems "natural" in the application domain and is easiest to maintain. Then you force it through a `Sort` meta function in order to get the data in a form needed for your algorithms. Things like this might save you half a page of comments on what the data is, where it comes from, and how it was put into whatever form you had to embed it. I prefer code that is clear at first look over code that needs extensive comments. – sbi Aug 25 '11 at 10:14
  • 11
    Of course, all this doesn't rule out that the OP might have done this just for fun. `:)` – sbi Aug 25 '11 at 10:14
  • 6
    Yeah, I do it just for fun. I have been wanting to implement quick sort in compilation time long time ago (when the C++11 was just C++0x). Now the C++0x is C++11. i can implement it by using variadic template. Funny. – Yuncy Aug 25 '11 at 10:30
  • If the OP asks for a compile time solution it is not an answer to say it can be done in runtime. To sort things can be done also on paper or given as external task for an external company somewhere :-) – Klaus Jun 08 '13 at 08:02
  • @Klaus: It is an answer to say that the compiler simply can't do it at compile-time. Since that's clearly true; it blows past the limitations that this compiler imposes. – Nicol Bolas Jun 08 '13 at 10:51
  • @R.MartinhoFernandes: I know of no way to automatically derive an ordering of types at compile time. It can be added manually by associating each type with an integer. It could be a nice C++17 feature. ;-) – Cheers and hth. - Alf Dec 07 '15 at 01:29
  • @R.MartinhoFernandes Indeed. I'm working on a library feature that essentially determines the unbound argument types in their expected order for an `std::bind` return value, which are arbitrarily ordered by the user with `std::placeholder` values. I currently use a compile time type sort to achieve this. – Barrett Adair Feb 24 '16 at 18:05
  • @Cheersandhth.-Alf A standard-compliant C++ compiler could have done this in 1998 - the C++ type system is Turing-complete. There is no need for a new language feature, because several already exist for this. See Boost.MPL, Boost.Fusion and Boost.Hana for examples. It can be done using the same techniques in OP's example, using `` or equivalent instead of actual value parameters (a very minor difference). Especially now with C++14 and beyond, there are [many ways](http://ldionne.com/2015/11/29/efficient-parameter-pack-indexing/) to skin this cat. – Barrett Adair Feb 24 '16 at 18:18
  • @BarrettAdair: I was talking of (compile time) "ordering of types", in response to the good robot. AFAIK that's still not possible, and could/would be very useful. You're talking about indexing into a parameter pack, which is trivial. Generally it's a good idea to be clear about what you're talking about. Avoid references to generic "this". – Cheers and hth. - Alf Feb 24 '16 at 18:54
  • @Cheersandhth.-Alf I threw together a quick-and-dirty live example of type sorting [here](http://melpon.org/wandbox/permlink/16mHHE8i9OCHtplf). This is not an ideal implementation (look to Boost for those), but it gives you an example of what I'm talking about. All the different ways of indexing a parameter pack are existing language features that can be used to sort types (although I don't use indexing in this example). Sorry for the confusion. The link was a half-hearted attempt to draw a connection between the two. – Barrett Adair Feb 24 '16 at 20:30
  • @BarrettAdair: Sorting on the size of types is not an ordering of types. Many types have the same size but are distinct. But thanks for the effort! :) (I believe in communication.) – Cheers and hth. - Alf Feb 24 '16 at 22:27
  • What is your definition of "ordering of types"? I think we are talking past each other at this point. Distinctness is not a sortable concept. I chose size arbitrarily, but you can sort by any trait (const-ness, reference-ness, a constexpr member value, copyable-ness, presence of a member, etc.) With a bit of pre-processor-aided reflection, you can even sort types lexically by name. Is that what you had in mind? – Barrett Adair Feb 24 '16 at 23:25
  • @Cheersandhth.-Alf I made some minor changes to the Boost.Hana type sorting algorithm to make it only use the standard library. [Here](http://melpon.org/wandbox/permlink/EcSVlpg7LeJ79MSl) is a standalone example. This one sorts on size again, since I don't know what else you had in mind, but you can pass any comparison functor you like (it just needs to return an std::integral_constant or equivalent). – Barrett Adair Mar 04 '16 at 01:09
  • @BarrettAdair: You can re-establish the now lost context simply by looking up in the commentary. :) This started with the R. Marthino's comment, the very first one, that sorting of types could be useful. I replied that “I know of no way to automatically derive an ordering of types at compile time. It can be added manually by associating each type with an integer.”. And yes, as you mention a compile time ordering can be added manually by associating each type with a (unique) name, but I think that's less useful than a Modern Design-like integer. Thanks anyway. :) – Cheers and hth. - Alf Mar 04 '16 at 02:42
  • Compile time sort can be useful, fact is that I'm actually trying to find an implementation like this at this very moment. Bad and subjective commend, -1. Oh, and your suggestion to manually sort and copy paste into the source? Yeah, very good solution for someone writing a library... eh not – aerkenemesis Dec 19 '16 at 19:37