bugGNU Scientific Library - Bugs: bug #51104, gsl_permutation_next efficiency

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #51104: gsl_permutation_next efficiency

Submitter:  Patrick Alken <psa>
Submitted:  Wed 24 May 2017 08:45:59 AM UTC
   
 
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Operating System: 
Status:  None Assigned to:  None
Open/Closed:  Open Release: 

Discussion

Wed 24 May 2017 08:46:44 AM UTC, comment #1: 

from rsmith =at= whistlin =dot= com

I think Pavel Sinitcyn's code gives a more literal translation of step L3 in
Knuth's description of the algorithm ("Algorithm L" in AoCP vol 4, page 319).
The change decreases the running time by over 10% in my tests.  I haven't
tested for accuracy, though.

Incidentally, the existing version of gsl_permutation_next() in permutatiion.c
has a superfluous check in the boolean expression on line 155:

    (p->data[j] > p->data[i]) && (p->data[j] < p->data[k])

The while loop starting on line 141 guarantees that p->data[j] < p->data[k] for
i<k<j (Knuth explains this in step L3).  But I think the slow down is caused by
the structure of the for loop, which seems awkward compared to the
straightforward textbook version.

Regis

Patrick Alken <psa>
Group administrator
Wed 24 May 2017 08:45:59 AM UTC, original submission:  

from pgsinitsyn =at= gmail =dot= com

Hello everyone,

I was reading the permutation module of GSL and found that a function
"gsl_permutation_next" can be improved (you can see function
gsl_permutation_next0
<https://gist.gith ... _next-test-c-L111>,
more specifically - this line
<https://gist.gith ... _next-test-c-L135>
).

I made a benchmarking on my computer (AMD Opteron(TM) Processor 6276; gcc
-O2; gcc Ubuntu 4.8.4-2ubuntu1~14.04.3) and found a significant difference
in the performance (result contains stdout; bencmark.pdf - visualisation).

Best,
Pavel Sinitcyn

Patrick Alken <psa>
Group administrator

 

Attached Files

Attached Files
file #40775:  benchmark.pdf added by psa (6.3KiB - application/pdf)
file #40776:  result.txt added by psa (1.7KiB - text/plain)

 

Dependencies

This item does not depend on any other items.

No items depend on this one.

 

Mail Notification Carbon-Copy List

Carbon-Copy List
  • -email is unavailable- added by psa (Submitted the item)
  •  

    History

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-05-24 psa Attached File- Added benchmark.pdf, #40775
        Attached File- Added result.txt, #40776

    Back to the top

    Powered by Savane 3.16-598c.
    Corresponding source code