Quick sort at compilation time using C++11 variadic templates

Question

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.

Answer 1

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.

Answer 2

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.