more efficient shift register?

Discussion in 'Perl Misc' started by Chris Richmond - MD6-FDC ~, May 25, 2006.

  1. Folks,

    This is a trivial example of a larger problem I'm trying to
    speed up. What I want to know is if there is a faster way
    to impliment a shift register for text chars. I already tried
    using arrays and unshifting and popping, and it was 2-3x slower.

    Thx, Chris

    Output:

    -> 0000 -> (pre-shifting)
    1 -> 1000 -> 0
    1 -> 1100 -> 0
    1 -> 1110 -> 0
    0 -> 0111 -> 0
    1 -> 1011 -> 1
    1 -> 1101 -> 1
    1 -> 1110 -> 1
    0 -> 0111 -> 0
    0 -> 0011 -> 1
    0 -> 0001 -> 1
    1 -> 1000 -> 1
    0 -> 0100 -> 0
    1 -> 1010 -> 0
    0 -> 0101 -> 0
    1 -> 1010 -> 1
    1 -> 1101 -> 0
    1 -> 1110 -> 1
    1 -> 1111 -> 0
    0 -> 0111 -> 1
    0 -> 0011 -> 1
    0 -> 0001 -> 1
    0 -> 0000 -> 1


    Script:

    #!/usr/bin/perl -w

    $shift_register = '0000';

    $input_data = ' ';
    $output_data = ' ';

    print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";

    while(defined($input_data=(<DATA>))) {

    chomp($input_data);

    $shift_register = $input_data . $shift_register; # prepending $input_data char
    $output_data = chop( $shift_register ); # shifting off the last char to $output_data

    print " $input_data -> $shift_register -> $output_data\n";
    }

    __DATA__
    1
    1
    1
    0
    1
    1
    1
    0
    0
    0
    1
    0
    1
    0
    1
    1
    1
    1
    0
    0
    0
    0


    --
    Chris Richmond | I don't speak for Intel & vise versa
    Chris Richmond - MD6-FDC ~, May 25, 2006
    #1
    1. Advertising

  2. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Chris Richmond - MD6-FDC ~ schreef:

    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    >
    > <snip>
    > __DATA__
    > 1
    > 1


    #!/usr/bin/perl
    use strict ;
    use warnings ;

    my $data = '1110111000101011110000' ;

    my @val = split '', '0000' ;
    my @data = split '', $data ;

    local $" = '' ;
    print " -> @val -> (pre-shifting)\n" ;

    for my $i (0 .. $#data)
    {
    unshift @val, shift @data ;
    print "$val[0] -> @val[0..3] -> $val[4]\n" ;
    }

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 25, 2006
    #2
    1. Advertising

  3. Chris Richmond - MD6-FDC ~

    DJ Stunks Guest

    Chris Richmond - MD6-FDC ~ wrote:
    > Folks,
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.
    >
    > Thx, Chris
    >
    > Output:
    >
    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    > 1 -> 1110 -> 0
    > 0 -> 0111 -> 0
    > 1 -> 1011 -> 1
    > 1 -> 1101 -> 1
    > 1 -> 1110 -> 1
    > 0 -> 0111 -> 0
    > 0 -> 0011 -> 1
    > 0 -> 0001 -> 1
    > 1 -> 1000 -> 1
    > 0 -> 0100 -> 0
    > 1 -> 1010 -> 0
    > 0 -> 0101 -> 0
    > 1 -> 1010 -> 1
    > 1 -> 1101 -> 0
    > 1 -> 1110 -> 1
    > 1 -> 1111 -> 0
    > 0 -> 0111 -> 1
    > 0 -> 0011 -> 1
    > 0 -> 0001 -> 1
    > 0 -> 0000 -> 1
    >
    >
    > Script:
    >
    > #!/usr/bin/perl -w
    >
    > $shift_register = '0000';
    >
    > $input_data = ' ';
    > $output_data = ' ';
    >
    > print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";
    >
    > while(defined($input_data=(<DATA>))) {
    >
    > chomp($input_data);
    >
    > $shift_register = $input_data . $shift_register; # prepending $input_data char
    > $output_data = chop( $shift_register ); # shifting off the last char to $output_data
    >
    > print " $input_data -> $shift_register -> $output_data\n";
    > }
    >
    > __DATA__
    > 1
    > 1
    > 1
    > 0
    > 1
    > 1
    > 1
    > 0
    > 0
    > 0
    > 1
    > 0
    > 1
    > 0
    > 1
    > 1
    > 1
    > 1
    > 0
    > 0
    > 0
    > 0
    >


    Try benchmarking this. I'm sure C will perform this operation much
    faster than Perl. I'm pretty sure Bit::Vector is a core module.

    #!/usr/bin/perl

    use strict;
    use warnings;

    use Bit::Vector;

    my $shift_register = Bit::Vector->new(4);

    my ($input_data,$output_data) = (' ',' ');

    printf "%s -> %s -> %s (pre-shifting)\n",
    $input_data, $shift_register->to_Bin(), $output_data;

    while( $input_data = <DATA> ) {
    chomp $input_data;

    $output_data = $shift_register->shift_right($input_data);

    printf "%s -> %s -> %s\n",
    $input_data, $shift_register->to_Bin(), $output_data;
    }

    __DATA__
    1
    1
    1
    0
    1
    1
    1
    0
    0
    0
    1
    0
    1
    0
    1
    1
    1
    1
    0
    0
    0
    0

    -jp
    DJ Stunks, May 25, 2006
    #3
  4. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Dr.Ruud schreef:
    > Chris Richmond - MD6-FDC ~ schreef:
    >
    >> -> 0000 -> (pre-shifting)
    >> 1 -> 1000 -> 0
    >> 1 -> 1100 -> 0
    >>
    >> <snip>
    >> __DATA__
    >> 1
    >> 1

    >
    > #!/usr/bin/perl
    > use strict ;
    > use warnings ;
    >
    > my $data = '1110111000101011110000' ;
    >
    > my @val = split '', '0000' ;
    > my @data = split '', $data ;
    >
    > local $" = '' ;
    > print " -> @val -> (pre-shifting)\n" ;
    >
    > for my $i (0 .. $#data)
    > {
    > unshift @val, shift @data ;
    > print "$val[0] -> @val[0..3] -> $val[4]\n" ;
    > }


    String-variant:

    #!/usr/bin/perl
    use strict ;
    use warnings ;

    my $data = reverse ('0000' . '1110111000101011110000') ;

    my $i = length( $data ) - 4 ;

    printf " -> %s -> (pre-shifting)\n", substr( $data, $i, 4 );

    while ( --$i >= 0 )
    {
    printf "%s -> %s -> %s\n", substr( $data, $i, 1 )
    , substr( $data, $i, 4 )
    , substr( $data, $i+4, 1 ) ;
    }

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 25, 2006
    #4
  5. "Chris Richmond - MD6-FDC ~" <> wrote in
    message news:e54prh$p8r$...
    > Folks,
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.
    >
    > Thx, Chris
    >
    > Output:
    >
    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    > 1 -> 1110 -> 0
    > 0 -> 0111 -> 0
    > 1 -> 1011 -> 1
    > 1 -> 1101 -> 1
    > 1 -> 1110 -> 1
    >

    .... snip...
    >
    >
    > --
    > Chris Richmond | I don't speak for Intel & vise versa
    >


    Hi Chris,

    if you don't need the output character I would replace the lines
    $shift_register = "$input_data$shift_register"; # prepending
    $input_data char
    $output_data = chop( $shift_register ); # shifting off the
    last char to $output_data

    by the line
    $shift_register = sprintf("%4.4s", $input_data . $shift_register);

    on my Hardware (Perl 5.8.7 on P4 3.2GHz) this executes tow times faster than
    your code. If you need the output, I've not found anything faster than your
    solution.

    I've assumed that you would like to shift any type of text instead of only
    binary numbers.

    Regards
    Ralph
    Ralph Ganszky, May 25, 2006
    #5
  6. In article <>,
    "Dr.Ruud" <> writes:
    > my @val = split '', '0000' ;
    > my @data = split '', $data ;
    >
    > local $" = '' ;
    > print " -> @val -> (pre-shifting)\n" ;
    >
    > for my $i (0 .. $#data)
    > {
    > unshift @val, shift @data ;
    > print "$val[0] -> @val[0..3] -> $val[4]\n" ;
    > }


    This works, but also similar to what I tried that was much slower.
    The actual register strings are varying widths.

    Thx, Chris

    --
    Chris Richmond | I don't speak for Intel & vise versa
    Chris Richmond - MD6-FDC ~, May 25, 2006
    #6
  7. Chris Richmond - MD6-FDC ~

    Brian Wakem Guest

    Chris Richmond - MD6-FDC ~ wrote:

    > Folks,
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.
    >
    > Thx, Chris
    >
    > Output:
    >
    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    > 1 -> 1110 -> 0
    > 0 -> 0111 -> 0
    > 1 -> 1011 -> 1
    > 1 -> 1101 -> 1
    > 1 -> 1110 -> 1
    > 0 -> 0111 -> 0
    > 0 -> 0011 -> 1
    > 0 -> 0001 -> 1
    > 1 -> 1000 -> 1
    > 0 -> 0100 -> 0
    > 1 -> 1010 -> 0
    > 0 -> 0101 -> 0
    > 1 -> 1010 -> 1
    > 1 -> 1101 -> 0
    > 1 -> 1110 -> 1
    > 1 -> 1111 -> 0
    > 0 -> 0111 -> 1
    > 0 -> 0011 -> 1
    > 0 -> 0001 -> 1
    > 0 -> 0000 -> 1
    >
    >
    > Script:
    >
    > #!/usr/bin/perl -w
    >
    > $shift_register = '0000';
    >
    > $input_data = ' ';
    > $output_data = ' ';
    >
    > print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";
    >
    > while(defined($input_data=(<DATA>))) {
    >
    > chomp($input_data);
    >
    > $shift_register = $input_data . $shift_register; # prepending
    > $input_data char
    > $output_data = chop( $shift_register ); # shifting off the
    > last char to $output_data
    >
    > print " $input_data -> $shift_register -> $output_data\n";
    > }
    >
    > __DATA__
    > 1
    > 1
    > 1
    > 0
    > 1
    > 1
    > 1
    > 0
    > 0
    > 0
    > 1
    > 0
    > 1
    > 0
    > 1
    > 1
    > 1
    > 1
    > 0
    > 0
    > 0
    > 0
    >
    >



    You'll need to bechmark it of course, but you could try substr.

    while(defined($input_data=(<DATA>))) {
    chomp($input_data);
    $output_data = substr($shift_register,-1,1);
    $shift_register = $input_data . substr($shift_register,0,3);
    print " $input_data -> $shift_register -> $output_data\n";
    }


    --
    Brian Wakem
    Email: http://homepage.ntlworld.com/b.wakem/myemail.png
    Brian Wakem, May 25, 2006
    #7
  8. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Dr.Ruud schreef:

    > my $data = reverse ('0000' . '1110111000101011110000') ;


    Clearer:

    my $data = '0000' . reverse '1110111000101011110000' ;

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 25, 2006
    #8
  9. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Chris Richmond - MD6-FDC ~ schreef:
    > Dr.Ruud:


    >> my @val = split '', '0000' ;
    >> my @data = split '', $data ;
    >>
    >> local $" = '' ;
    >> print " -> @val -> (pre-shifting)\n" ;
    >>
    >> for my $i (0 .. $#data)
    >> {
    >> unshift @val, shift @data ;
    >> print "$val[0] -> @val[0..3] -> $val[4]\n" ;
    >> }

    >
    > This works, but also similar to what I tried that was much slower.
    > The actual register strings are varying widths.


    Do you mean this is faster or slower than what you had?

    If slower, could you tell more about your data then? Which widths do you
    talk about: 32, 64, 128, ...?

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 25, 2006
    #9
  10. Chris Richmond - MD6-FDC ~

    Guest

    wrote:
    > Folks,
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.


    The code you posted spents most of it's time in the print statement.
    If you are serious about optimizing this, you need to come up with
    a better test harness--a little less trivial but lot more realistic.

    Unless of course you real problem includes the print statement. In that
    case, the shift register is probably not your problem.

    Xho

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , May 25, 2006
    #10
  11. Chris Richmond - MD6-FDC ~

    Guest

    Brian Wakem <> wrote:

    > You'll need to bechmark it of course, but you could try substr.
    >
    > while(defined($input_data=(<DATA>))) {
    > chomp($input_data);
    > $output_data = substr($shift_register,-1,1);


    As long as we are done at that end of the string, we may as well trim it,
    too:

    $output_data = substr($shift_register,-1,1,'');

    > $shift_register = $input_data . substr($shift_register,0,3);


    This copies $shift_register when you should be trying to operate on it in
    place. (Plus I'd rather not have the length of shift_register hard
    coded.):

    substr($shift_register,0,0,$input_data);

    (This will make a huge difference for large shift_register, but probably
    won't if it is only 4 characters long)

    Xho

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , May 25, 2006
    #11
  12. In article <>,
    "Dr.Ruud" <> writes:
    >> This works, but also similar to what I tried that was much slower.
    >> The actual register strings are varying widths.

    >
    >Do you mean this is faster or slower than what you had?


    The splitting to arrays and unshifting and poping was
    much slower.

    >If slower, could you tell more about your data then? Which widths do you
    >talk about: 32, 64, 128, ...?


    Somewhat random lengths between 2-3 chars and maybe 150. They aren't powers
    of 2 wide. These are scan chains. The original code really is shifting
    the data through a string that represents the chain. The inner loop
    processes individual chain data (random length per chain), the outer loop
    loops through all chains (fixed # per loop).

    Chris
    --
    Chris Richmond | I don't speak for Intel & vise versa
    Chris Richmond - MD6-FDC ~, May 26, 2006
    #12
  13. Chris Richmond - MD6-FDC ~ wrote:
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.
    >
    > Output:
    >
    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    >
    > [snip]
    >
    > 0 -> 0011 -> 1
    > 0 -> 0001 -> 1
    > 0 -> 0000 -> 1
    >
    >
    > Script:
    >
    > #!/usr/bin/perl -w
    >
    > $shift_register = '0000';
    >
    > $input_data = ' ';
    > $output_data = ' ';
    >
    > print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";
    >
    > while(defined($input_data=(<DATA>))) {
    >
    > chomp($input_data);
    >
    > $shift_register = $input_data . $shift_register; # prepending $input_data char
    > $output_data = chop( $shift_register ); # shifting off the last char to $output_data
    >
    > print " $input_data -> $shift_register -> $output_data\n";
    > }
    >
    > __DATA__
    > 1
    > 1
    > 1
    >
    > [snip]


    This may be faster but you will have to benchmark it to be sure:

    #!/usr/bin/perl
    use warnings;
    use strict;

    my $shift_register = '0000';

    my $format = 'a' . length( $shift_register ) . 'a*';

    my $input_data = ' ';
    my $output_data = ' ';

    print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";

    while ( $input_data = <DATA> ) {

    chomp $input_data;

    ( $shift_register, $output_data ) = unpack $format, $input_data .
    $shift_register;

    print " $input_data -> $shift_register -> $output_data\n";
    }

    __DATA__
    1
    1
    1
    ....



    John
    --
    use Perl;
    program
    fulfillment
    John W. Krahn, May 26, 2006
    #13
  14. Chris Richmond - MD6-FDC ~

    DJ Stunks Guest

    Chris Richmond - MD6-FDC ~ wrote:
    > Folks,
    >
    > This is a trivial example of a larger problem I'm trying to
    > speed up. What I want to know is if there is a faster way
    > to impliment a shift register for text chars. I already tried
    > using arrays and unshifting and popping, and it was 2-3x slower.


    A benchmark. Please let me know if you see any glaring errors.

    #!/usr/bin/perl

    use strict;
    use warnings;

    my $iterations = shift;

    our @input_data = split //, '1110111000101011110000';

    sub krahn {
    my $shift_register = '0000';

    my $format = 'a' . length( $shift_register ) . 'a*';

    my $output_data;
    for my $input_data ( @input_data ) {
    ( $shift_register, $output_data )
    = unpack $format, $input_data.$shift_register;
    }
    }

    sub peavy {
    use Bit::Vector;

    my $shift_register = Bit::Vector->new(4);

    my $output_data;
    for my $input_data ( @input_data ) {
    $output_data = $shift_register->shift_right($input_data);
    }
    }

    sub original {
    my $shift_register = '0000';

    my $output_data;
    for my $input_data ( @input_data ) {
    $shift_register = $input_data . $shift_register;
    $output_data = chop( $shift_register );
    }
    }

    sub ruud2 {
    my $data = reverse ('0000' . '1110111000101011110000') ;

    my $i = length( $data ) - 4 ;

    my ($input_data,$shift_register,$output_data);
    while ( --$i >= 0 ) {
    $input_data = substr( $data, $i, 1 );
    $shift_register = substr( $data, $i, 4 );
    $output_data = substr( $data, $i+4, 1 );
    }
    }

    sub compare {
    my ($iterations) = @_;

    print "\n[$iterations times]\n";

    use Benchmark qw{ cmpthese };
    cmpthese -$iterations, {
    original => 'original()',
    krahn => 'krahn()',
    peavy => 'peavy()',
    ruud => 'ruud2()',
    };

    return;
    }

    compare($iterations);

    __END__

    C:\tmp>tmp.bench.pl 100

    [100 times]
    Rate krahn original ruud peavy
    krahn 8910/s -- -67% -67% -74%
    original 26846/s 201% -- -1% -22%
    ruud 26990/s 203% 1% -- -21%
    peavy 34308/s 285% 28% 27% --

    As predicted, C outstrips perl significantly in this regard.

    However, I was told by the OP that his actual problem is only
    casually related to the example originally posted.

    In any event, I think that if a true shift register is desired,
    a true shift register should be used.

    -jp
    DJ Stunks, May 26, 2006
    #14
  15. Chris Richmond - MD6-FDC ~

    Mirco Wahab Guest

    Thus spoke DJ Stunks (on 2006-05-26 02:45):

    > A benchmark. Please let me know if you see any glaring errors.


    Thanks for providing this good comparison. The week
    ends - and I got some time to try one for myself.
    I straightened up your source a bit and added another
    variant of it (scanning through the string by Regex,
    which is much slower than I could have imagined).

    The Regex-variant (wahab) works already with
    arbitary register widths - but it's somehow
    too slow for real work :-(

    [10 times]
    Rate krahn ruud wahab peavy original
    krahn 433/s -- -72% -73% -77% -84%
    ruud 1526/s 253% -- -4% -20% -45%
    wahab 1596/s 269% 5% -- -16% -43%
    peavy 1900/s 339% 24% 19% -- -32%
    original 2786/s 544% 83% 75% 47% --
    [-> 5.8.7/Win32/WinXP]

    Additionally, I used a longer bit string - better account
    for the real processing:

    #!/usr/bin/perl -w
    use strict;
    use warnings;

    my $iterations = shift || 10;
    our $input_str = '11101110001010111100001110111000'
    .'10101111000011101110001010111100'
    .'00111011100010101111000011101110'
    .'00101011110000111011100010101111'
    .'00001110111000101011110000111011'
    .'10001010111100001000101011110000';
    our @input_data = split //, $input_str;
    our $shift_register = '0000';

    sub krahn {
    my $format = 'a' . length( $shift_register ) . 'a*';
    my $output_data;
    for my $input_data ( @input_data ) {
    ( $shift_register, $output_data )
    = unpack $format, $input_data.$shift_register;
    }
    }

    sub peavy {
    use Bit::Vector;
    my $shift_register = Bit::Vector->new(4);
    my $output_data;
    for my $input_data ( @input_data ) {
    $output_data = $shift_register->shift_right($input_data);
    }
    }

    sub original {
    my $output_data;
    for my $input_data ( @input_data ) {
    $shift_register = $input_data . $shift_register;
    $output_data = chop( $shift_register );
    }
    }

    sub ruud2 {
    my $data = reverse ($shift_register . $input_str) ;
    my $i = length( $data ) - 4 ;
    my ($input_data,$shift_register,$output_data);
    while ( --$i >= 0 ) {
    $input_data = substr( $data, $i, 1 );
    $shift_register = substr( $data, $i, 4 );
    $output_data = substr( $data, $i+4, 1 );
    }
    }

    sub wahab {
    $_ = ' '. $shift_register . $input_str;
    my $L = length($shift_register) - 1;
    my $R = qr/(?<=(.)(.{$L}))(.)(?=(.))/;
    1 while /$R/g;
    # to get the required output, use:
    # print "$1 <- $2$3 <- $4\n" while /$R/g;
    # or something
    }

    sub compare {
    my ($iterations) = @_;
    print "\n[$iterations times]\n";
    use Benchmark qw{ cmpthese };
    cmpthese -$iterations, {
    original => 'original()',
    krahn => 'krahn()',
    peavy => 'peavy()',
    ruud => 'ruud2()',
    wahab => 'wahab()',
    };
    return;
    }

    compare($iterations);
    __END__


    Regards

    Mirco
    Mirco Wahab, May 26, 2006
    #15
  16. In article <>,
    "DJ Stunks" <> writes:
    > [100 times]
    > Rate krahn original ruud peavy
    > krahn 8910/s -- -67% -67% -74%
    > original 26846/s 201% -- -1% -22%
    > ruud 26990/s 203% 1% -- -21%
    > peavy 34308/s 285% 28% 27% --
    >
    >As predicted, C outstrips perl significantly in this regard.


    >However, I was told by the OP that his actual problem is only
    >casually related to the example originally posted.
    >
    >In any event, I think that if a true shift register is desired,
    >a true shift register should be used.


    This is a really nice comparison. Thanks a bunch! Too bad I
    have to use chars instead of bits. I'm now trying to figure
    out how to use in-line C for the shifting. Our perl install
    doesn't seem to have the right modules to support that.

    Thx, Chris

    --
    Chris Richmond | I don't speak for Intel & vise versa
    Chris Richmond - MD6-FDC ~, May 26, 2006
    #16
  17. Chris Richmond - MD6-FDC ~

    Mirco Wahab Guest

    Thus spoke DJ Stunks (on 2006-05-26 02:45):

    > A benchmark. Please let me know if you see any glaring errors.


    Thanks for providing this good comparison. The week
    ends - and I got some time to try one for myself.
    I straightened up your source a bit and added another
    variant of it (scanning through the string by Regex,
    which is much slower than I could have imagined).

    The Regex-variant (wahab) works already with
    arbitary register widths - but it's somehow
    little bit too slow for real work :-(

    (I posted this already one moment ago, but canceled
    it after realizing that I didn't make sure the input
    data isn't modified by the algorithms - so the
    results were completely useless.
    Now here comes the reals thing.)

    [10 times]
    Rate krahn original ruud wahab peavy
    krahn 446/s -- -61% -71% -72% -77%
    original 1135/s 154% -- -27% -30% -42%
    ruud 1566/s 251% 38% -- -3% -20%
    wahab 1615/s 262% 42% 3% -- -17%
    peavy 1955/s 338% 72% 25% 21% --


    #!/usr/bin/perl -w
    use strict;
    use warnings;

    my $iterations = shift || 10;
    my $Input_str = '11101110001010111100001110111000'
    .'10101111000011101110001010111100'
    .'00111011100010101111000011101110'
    .'00101011110000111011100010101111'
    .'00001110111000101011110000111011'
    .'10001010111100001000101011110000';
    my @Input_data = split //, $Input_str;
    my $Shift_register = '0000';

    sub krahn {
    my $shift_register = $Shift_register;
    my $format = 'a' . length( $shift_register ) . 'a*';
    my $output_data;
    for my $input_data ( @Input_data ) {
    ( $shift_register, $output_data )
    = unpack $format, $input_data.$shift_register;
    }
    }

    sub peavy {
    use Bit::Vector;
    my $shift_register = Bit::Vector->new(length($Shift_register));
    my $output_data;
    for my $input_data ( @Input_data ) {
    $output_data = $shift_register->shift_right($input_data);
    }
    }

    sub original {
    my $output_data;
    my $shift_register = $Shift_register;
    for my $input_data ( @Input_data ) {
    $shift_register = $input_data . $shift_register;
    $output_data = chop( $shift_register );
    }
    }

    sub ruud2 {
    my $data = reverse ($Shift_register . $Input_str) ;
    my $i = length( $data ) - length($Shift_register);
    my ($input_data,$shift_register,$output_data);
    while ( --$i >= 0 ) {
    $input_data = substr( $data, $i, 1 );
    $shift_register = substr( $data, $i, 4 );
    $output_data = substr( $data, $i+4, 1 );
    }
    }

    sub wahab {
    my $l = length($Shift_register) - 1;
    my $r = qr/(?<=(.)(.{$l}))(.)(?=(.))/o;
    $_ = ' '. $Shift_register . $Input_str;
    1 while /$r/g;
    # to get the required output, use:
    # print "$2 <- $1$3 <- $4\n" while /$r/g;
    }

    sub compare {
    my ($iterations) = @_;
    print "\n[$iterations times]\n";
    use Benchmark qw{ cmpthese };
    cmpthese -$iterations, {
    original => 'original()',
    krahn => 'krahn()',
    peavy => 'peavy()',
    ruud => 'ruud2()',
    wahab => 'wahab()',
    };
    return;
    }

    compare($iterations);
    __END__

    (Please correct if I made substantial mistakes.)

    Regards

    Mirco
    Mirco Wahab, May 26, 2006
    #17
  18. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Chris Richmond - MD6-FDC ~ schreef:
    > DJ Stunks:


    >> [100 times]
    >> Rate krahn original ruud peavy
    >> krahn 8910/s -- -67% -67% -74%
    >> original 26846/s 201% -- -1% -22%
    >> ruud 26990/s 203% 1% -- -21%
    >> peavy 34308/s 285% 28% 27% --
    >>
    >> As predicted, C outstrips perl significantly in this regard.

    >
    >> However, I was told by the OP that his actual problem is only
    >> casually related to the example originally posted.
    >>
    >> In any event, I think that if a true shift register is desired,
    >> a true shift register should be used.

    >
    > This is a really nice comparison. Thanks a bunch! Too bad I
    > have to use chars instead of bits. I'm now trying to figure
    > out how to use in-line C for the shifting. Our perl install
    > doesn't seem to have the right modules to support that.
    >
    > Thx, Chris


    I redistributed some overhead, and got to this:

    [2 times]
    Rate krahn wahab original peavy ruud
    krahn 1390/s -- -57% -67% -71% -79%
    wahab 3247/s 134% -- -22% -33% -52%
    original 4175/s 200% 29% -- -14% -38%
    peavy 4869/s 250% 50% 17% -- -27%
    ruud 6714/s 383% 107% 61% 38% --


    #!/usr/bin/perl
    use strict;
    use warnings;

    use Bit::Vector;

    my $iterations = shift || 10;
    our $G_input_str = '11101110001010111100001110111000'
    .'10101111000011101110001010111100'
    .'00111011100010101111000011101110'
    .'00101011110000111011100010101111'
    .'00001110111000101011110000111011'
    .'10001010111100001000101011110000';
    our $G_bits = 4 ;
    our $G_shift_register = '0' x $G_bits;
    our @G_input_data = split //, $G_input_str;
    our $G_input_data = ' '. $G_shift_register . $G_input_str;

    sub krahn {
    my $format = 'a' . $G_bits . 'a*';
    my $output_data;
    for my $input_data ( @G_input_data ) {
    ( $G_shift_register, $output_data )
    = unpack $format, $input_data . $G_shift_register;
    }
    }

    sub peavy {
    my $shift_reg = Bit::Vector->new($G_bits);
    my $output_data;
    for my $input_data ( @G_input_data ) {
    $output_data = $shift_reg->shift_right($input_data);
    }
    }

    sub original {
    my $output_data;
    for my $input_data ( @G_input_data ) {
    $G_shift_register = $input_data . $G_shift_register;
    $output_data = chop( $G_shift_register );
    }
    }

    sub ruud2 {
    my $n = length($G_input_data) - $G_bits ;
    my $output_data;
    for my $i ( 1 .. $n ) {
    $output_data = substr( $G_input_data, $i, $G_bits );
    }
    }

    sub wahab {
    my $R = qr/(?<=.(.{$G_bits}))(.)(?=.)/ ;
    1 while $G_input_data =~ /$R/g ;
    # output_data in $2$3
    }

    sub compare {
    my ($iterations) = @_;
    print "\n[$iterations times]\n";
    use Benchmark qw{ cmpthese };
    cmpthese -$iterations, {
    original => 'original()',
    krahn => 'krahn()',
    peavy => 'peavy()',
    ruud => 'ruud2()',
    wahab => 'wahab()',
    };
    return;
    }

    compare($iterations);
    __END__

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 26, 2006
    #18
  19. Chris Richmond - MD6-FDC ~

    Dr.Ruud Guest

    Mirco Wahab schreef:

    > I rewrote the comparison provided by DJ Stunks
    > (modified by Dr. Ruud) in order to _have the
    > correct data (char_in, shift_reg, char_out)
    > available in /every iteration/ (but not actually
    > printing it).
    >
    > (I tested every printout and commented it out then.)


    If you look at the orignal post, you'll see that only 5 bits are shown,
    not 6:

    > -> 0000 -> (pre-shifting)
    > 1 -> 1000 -> 0
    > 1 -> 1100 -> 0
    > 1 -> 1110 -> 0
    > 0 -> 0111 -> 0
    > 1 -> 1011 -> 1
    > 1 -> 1101 -> 1



    I propose this:

    sub ruud2_2 {
    # out: my $R = $G_bits -1 ;
    # out: $R = qr/^((.).{$R})(.)/ ;

    my $w = $G_bits + 1 ; # window size
    my $n = length($G_input_data) - $w ;

    for my $i ( 0 .. $n ) {
    $_ = substr( $G_input_data, $i, $w );
    # out: /$R/ and print " $2 -> $1 -> $3 \n" ;
    }
    }

    ;)

    --
    Affijn, Ruud

    "Gewoon is een tijger."
    Dr.Ruud, May 27, 2006
    #19
  20. Chris Richmond - MD6-FDC ~

    Guest

    Mirco Wahab <> wrote:
    >
    > sub wahab {
    > my $l = length($Shift_register) - 1;
    > my $r = qr/(?<=(.)(.{$l}))(.)(?=(.))/o;
    > $_ = ' '. $Shift_register . $Input_str;
    > 1 while /$r/g;
    > # to get the required output, use:
    > # print "$2 <- $1$3 <- $4\n" while /$r/g;
    > }


    I uncommented the print, and the output I get doesn't look like
    the specification. I don't know if that is a formatting problem
    or something worse.

    000 <- 0 <- 1
    000 <- 01 <- 1
    001 <- 01 <- 1
    011 <- 01 <- 0
    111 <- 00 <- 1
    110 <- 11 <- 1
    101 <- 11 <- 1
    011 <- 11 <- 0
    111 <- 00 <- 0
    110 <- 10 <- 0
    100 <- 10 <- 1
    000 <- 11 <- 0
    001 <- 00 <- 1
    010 <- 01 <- 0
    101 <- 00 <- 1
    010 <- 11 <- 1
    101 <- 01 <- 1
    011 <- 11 <- 1
    111 <- 01 <- 0
    111 <- 10 <- 0
    110 <- 10 <- 0
    100 <- 10 <- 0
    000 <- 10 <- 1
    000 <- 01 <- 1
    001 <- 01 <- 1

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , May 27, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roberto Gallo

    Shift - byte[] buf shift

    Roberto Gallo, Jan 27, 2004, in forum: Java
    Replies:
    3
    Views:
    2,049
    Thomas Schodt
    Jan 27, 2004
  2. Wenjie
    Replies:
    3
    Views:
    1,035
    Ron Samuel Klatchko
    Jul 11, 2003
  3. Santosh Nayak

    Left Shift / Right Shift Operators

    Santosh Nayak, Nov 30, 2006, in forum: C Programming
    Replies:
    16
    Views:
    1,450
    CBFalconer
    Nov 30, 2006
  4. Sanny
    Replies:
    38
    Views:
    3,397
    Thomas Richter
    Apr 29, 2011
  5. devphylosoff

    what "shift" does, if not "$_ = shift;" ?

    devphylosoff, Nov 29, 2007, in forum: Perl Misc
    Replies:
    3
    Views:
    326
    Michele Dondi
    Dec 4, 2007
Loading...

Share This Page