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
Release: 

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.github.com/pgsin/fc779f7ce7d4724221fe2dc5450e9358#file-gsl_permutation_next-test-c-L111>,
more specifically - this line
<https://gist.github.com/pgsin/fc779f7ce7d4724221fe2dc5450e9358#file-gsl_permutation_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

 

(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-f8d8.
    Corresponding source code