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
Operating System:  Status:  None
Assigned to:  None Open/Closed:  Open

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.


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
more specifically - this line

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).

Pavel Sinitcyn

Patrick Alken <psa>
Group administrator


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

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


Depends on the following items: None found

Items that depend on this one: None found


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

    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.13-b921.
    Corresponding source code