Possible improvement in next_permutation implementation

[David GONZALEZ MALINE]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testPermute.cxx
Type: text/x-c++src
Size: 4546 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20080305/a5cf3f86/attachment.bin>