Possible improvement in next_permutation implementation

[David GONZALEZ MALINE <David dot Gonzalez dot Maline at cern dot ch>]

Dear gcc developers,

I am currently doing some tests comparing the performance of some 
algorithms implemented in the standard library and the ones implemented 
in ROOT for sorting, searching, permutation generation, etc.

I have found that in most cases, the performance of the algorithms in 
the standard library are better in some degree, however, this is not 
true for the method std::next_permutation. I have compared the 
implementation in the standard library with those of ROOT (root.cern.ch) 
and the one in GSL (http://www.gnu.org/software/gsl/) and it happens 
that the former ones perform a lot better when compiled with full 
optimization.


In linux, I obtain the next times:

Number of elements        TMath::Permute  std::next_permutation 
gsl_permutation_next
5                                       1.40667e-05            
1.40667e-05                 9.799e-05
6                                       8.01086e-05            
6.60419e-05                 2.5034e-05
7                                       0.000221968           
0.00031209                  0.000128984
8                                       0.00271511             
0.00339818                  0.00129509
9                                       0.0165091               
0.0200059                    0.00875807
10                                     0.151734                 
0.200203                      0.0913639
11                                     1.67053                   
2.20031                        0.901346
12                                     20.0224                   
26.3941                        11.294


For the test that I am attaching to this email.

I wonder whether it would be possible to make an implementation of the 
standard library method closer to what the gsl algorithm does. The three 
algorithms are intrinsically the same one, but the way they have been 
implemented differ in the small details, and that is what makes the 
difference in time. I also wonder, what is the reason to have 
implemented the algorithm this way. There may be reasons I do not see 
because of my poor knowledge of the implementation of the library.

Cheers,
David

#include <iostream>
#include <ctime>
#include <algorithm>
#include <vector>

#include <gsl/gsl_permutation.h>

#include <TRandom2.h>
#include <TMath.h>
#include <TStopwatch.h>

#include <TApplication.h>
#include <TCanvas.h>
#include <TH2F.h>
#include <TGraph.h>
#include <TLegend.h>
#include <TAxis.h>

const int npass = 2;
const int minsize = 5;
const int maxsize = 12;
const int maxint = 5000;
const int arraysize = (maxsize-minsize) + 1;

using namespace std;

 ostream& operator <<(ostream& os, const vector<Int_t>& v)
{
   os << "[ ";
   for ( vector<Int_t>::const_iterator i = v.begin(); i != v.end() ; ++i) {
      os << *i << ' ';
   }
   os << ']';

   return os;
}

void initArray(Int_t n, vector<Int_t>& array)
{
   TRandom2 r( time( 0 ) );
   for ( Int_t i = 0; i < n; i++) {
      array[i] = r.Integer( maxint ); 
   }
   sort(array.begin(), array.end());
}

bool checkPermute()
{
   const Int_t n = minsize;

   vector<Int_t> original(n);
   vector<Int_t> vM(n);
   vector<Int_t> vS(n);

   bool equals = true;

   initArray(n, original);

   // TMATH
   copy(original.begin(), original.end(), vM.begin());
   copy(original.begin(), original.end(), vS.begin());
   //cout << original << vM << vS << endl;

   while ( TMath::Permute(n, &vM[0]) ) {
      std::next_permutation(&vS[0], &vS[n]);
      //cout << vM << vS << endl;
      equals &= equal(vM.begin(), vM.end(), vS.begin());
   }

   TMath::Permute(n, &vM[0]);
   std::next_permutation(vS.begin(), vS.end());
   //cout << "kFALSE: " << vM << vS << endl;

   return equals;
}

void permuteTime(const int n, double* tTMath, double* tStd)
{
   vector<Int_t> original(n);
   vector<Int_t> v(n);

   TStopwatch t; 

   initArray(n, original);

   // TMATH
   t.Start(); 
   for (int j = 0; j < npass; ++j) { 
      copy(original.begin(), original.end(), v.begin());
      while ( TMath::Permute(n, &v[0]) );
   }
   t.Stop(); 
   *tTMath =  t.RealTime();
   cout << "TMath::Permute time :\t " << t.RealTime();

   // STD
   t.Start();
   for (int j = 0; j < npass; ++j) { 
      copy(original.begin(), original.end(), v.begin());
      while ( std::next_permutation(&v[0], &v[n]) );
   }
   t.Stop();
   *tStd = t.RealTime();
   cout << "  std::next_permutation time :\t " << t.RealTime();
}

void testGSLPermute(Int_t n, double* tGSL)
{
   TStopwatch t; 

   gsl_permutation *p = gsl_permutation_alloc(n);

   gsl_permutation_init(p);

   t.Start();
   while ( gsl_permutation_next(p) == GSL_SUCCESS )
   {
//       gsl_permutation_fprintf(stdout, p, " %u");
//       fprintf(stdout, "\n");
   }
   t.Stop();
   *tGSL = t.RealTime();
   cout << "  gsl_permutation_next time :\t " << t.RealTime();
}

void testPermute() 
{
   vector<double> tM( arraysize );
   vector<double> tS( arraysize );
   vector<double> tG( arraysize );
   vector<double> index( arraysize );

   cout << "checkPermute()...." 
        << (checkPermute()? "OK" : "FAILED")
        << endl;

   for ( int i = minsize; i <= maxsize; i += 1)
   {
      permuteTime(i, &tM[ i - minsize ], &tS[ i -minsize ]);
      testGSLPermute(i, &tG[ i - minsize ]);
      index[ i - minsize ] = i;
      cout << endl;
   }

   for ( int i = minsize; i <= maxsize; i += 1)
      cout << tM[ i - minsize ] << ' ' << tS[ i - minsize ] << ' ' << tG[ i - minsize ] << endl;

   TCanvas* c1 = new TCanvas("c1", "Comparision of Permutation Time", 600, 400);
   TH2F* hpx = new TH2F("hpx", "Comparision of Permutation Time", arraysize, minsize, maxsize, arraysize, tM[0],tS[arraysize-1]);
   hpx->SetStats(kFALSE);
   hpx->Draw();
   
   TGraph* gM = new TGraph(arraysize, &index[0], &tM[0]);
   gM->SetLineColor(2);
   gM->SetLineWidth(3);
   gM->SetTitle("TMath::Permute()");
   gM->Draw("SAME");

   TGraph* gS = new TGraph(arraysize, &index[0], &tS[0]);
   gS->SetLineColor(3);
   gS->SetLineWidth(3);
   gS->SetTitle("std::next_permutation()");
   gS->Draw("SAME");

   TGraph* gG = new TGraph(arraysize, &index[0], &tG[0]);
   gG->SetLineColor(4);
   gG->SetLineWidth(3);
   gG->SetTitle("gsl_permutation_next()");
   gG->Draw("SAME");

   TLegend* legend = new TLegend(0.15,0.72,0.4,0.86);
   legend->AddEntry(gM, "TMath::Permute()");
   legend->AddEntry(gS, "std::next_permutation()");
   legend->AddEntry(gG, "gsl_permutation_next()");
   legend->Draw();

   hpx->GetXaxis()->SetTitle("Array Size");
   hpx->GetYaxis()->SetTitle("Time");
   

   c1->Show();

   cout << "Test Done!" << endl;
}

int main(int argc, char **argv)
{
   TApplication theApp("App",&argc,argv);
   testPermute();
   theApp.Run();

   return 0;
}