comment on

I can obtain a modest (< 10%) but consistent speedup by modifying the permutation generator so that it doesn't even generate sequences that would fail the extended precheck. Like this:

sub fannkuch {
    my ( $a, $level, $split ) = ( @_, 0, 1 );
    my ( $index, $ok, $copy ) = ( $level, $level + 1 == length( $a ), 
+$a );

    if ($ok) {
        # print "Before munging: ($split) ", unpack('C*', $copy);
        $index = $split - 1;
        substr($copy, $index, 0) = chop($copy);
    }

    do {
        if ($ok) {
            # print "($split) ", unpack('C*', $copy);
            my $q = $copy;
            my ( $k, $flips );
            for ( $flips = 0; ( $k = ord( $q ) ) != 1; $flips++ ) {
                substr( $q, 0, $k ) = reverse substr( $q, 0, $k );
            }
            if ( $flips >= $maxflips ) {
                if ( $flips == $maxflips) {
                    push @max_sequence, $copy;
                }
                else {
                    $maxflips     = $flips;
                    @max_sequence = ($copy);
                }
            }
        }
        else {
            fannkuch( $copy, 1 + $level, $split );
            $split = $level + 1 if $index == $split;
        }
        substr( $copy, $index - 1, 2 ) = reverse substr( $copy, $index
+ -1, 2 );

    } while $index--;
    return $maxflips;
}
[download]

The idea is that $split is the smallest positive number for which all the elements in substr($copy, 0, $split) are less than or equal to $split.

This table shows a few examples:

sequence $split

15342 1

21345 2

23145 3

23415 4

31425 4

31542 5

(The commented-out debugging statements may make it easier to follow what's going on. They certainly helped me to understand it as I was writing it.)

On each top-level run (i.e. where $ok is true) we can skip directly to the first permutation where the moving element (which starts out as the last one in the list) has passed the split-point.

I've also reordered the maxflips logic, which gives an additional small improvement.

On an unloaded Linux PC, I get the following results. This is the output from diff --side-by-side -W 80, with the output from BrowserUk's code on the left, and mine on the right:

[rpc142: /tmp]$ diff --side-by-side -W 80 fann-char-orig.out fann-char
+.out
Pfannkuchen(1) = 0 for:                 Pfannkuchen(1) = 0 for:
8.7e-05 elapsed seconds.              | 1
                                      > 0.000118 elapsed seconds.

Pfannkuchen(2) = 1 for:                 Pfannkuchen(2) = 1 for:
21                                      21
7.7e-05 elapsed seconds.              | 6.4e-05 elapsed seconds.

Pfannkuchen(3) = 2 for:                 Pfannkuchen(3) = 2 for:
231                                     231
312                                     312
0.000134 elapsed seconds.             | 0.000133 elapsed seconds.

Pfannkuchen(4) = 4 for:                 Pfannkuchen(4) = 4 for:
2413                                    2413
3142                                    3142
0.000307 elapsed seconds.             | 0.000281 elapsed seconds.

Pfannkuchen(5) = 7 for:                 Pfannkuchen(5) = 7 for:
31452                                   31452
0.001292 elapsed seconds.             | 0.001164 elapsed seconds.

Pfannkuchen(6) = 10 for:                Pfannkuchen(6) = 10 for:
365142                                  365142
415263                                  415263
416523                                  416523
456213                                  456213
564132                                  564132
0.008305 elapsed seconds.             | 0.007341 elapsed seconds.

Pfannkuchen(7) = 16 for:                Pfannkuchen(7) = 16 for:
3146752                                 3146752
4762153                                 4762153
0.062369 elapsed seconds.             | 0.056875 elapsed seconds.

Pfannkuchen(8) = 22 for:                Pfannkuchen(8) = 22 for:
61578324                                61578324
0.541676 elapsed seconds.             | 0.498606 elapsed seconds.

Pfannkuchen(9) = 30 for:                Pfannkuchen(9) = 30 for:
615972834                               615972834
5.347029 elapsed seconds.             | 4.943895 elapsed seconds.

Pfannkuchen(10) = 38 for:               Pfannkuchen(10) = 38 for:
59186210473                             59186210473
58.118665 elapsed seconds.            | 54.24672 elapsed seconds.
[download]

In reply to Re: Speed/Efficiency tweaks for a fannkuch benchmark script? by robin
in thread Speed/Efficiency tweaks for a fannkuch benchmark script? by thundergnat

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Just another Perl shrine
	PerlMonks