Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > more efficient shift register?

Reply
Thread Tools

more efficient shift register?

 
 
xhoster@gmail.com
Guest
Posts: n/a
 
      05-25-2006
Brian Wakem <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Chris Richmond - MD6-FDC ~
Guest
Posts: n/a
 
      05-25-2006
In article <(E-Mail Removed)>,
"Dr.Ruud" <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
John W. Krahn
Guest
Posts: n/a
 
      05-25-2006
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
 
Reply With Quote
 
DJ Stunks
Guest
Posts: n/a
 
      05-26-2006
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

 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      05-26-2006
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
 
Reply With Quote
 
Chris Richmond - MD6-FDC ~
Guest
Posts: n/a
 
      05-26-2006
In article <(E-Mail Removed) .com>,
"DJ Stunks" <(E-Mail Removed)> 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

 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      05-26-2006
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

 
Reply With Quote
 
Dr.Ruud
Guest
Posts: n/a
 
      05-26-2006
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."


 
Reply With Quote
 
Dr.Ruud
Guest
Posts: n/a
 
      05-26-2006
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."


 
Reply With Quote
 
xhoster@gmail.com
Guest
Posts: n/a
 
      05-26-2006
Mirco Wahab <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java left shift and right shift operators. Sanny Java 38 04-29-2011 10:02 PM
what "shift" does, if not "$_ = shift;" ? devphylosoff Perl Misc 3 12-04-2007 12:27 AM
Left Shift / Right Shift Operators Santosh Nayak C Programming 16 11-30-2006 05:10 PM
Shift - byte[] buf shift Roberto Gallo Java 3 01-27-2004 04:26 PM
left shift then right shift an unsigned int Wenjie C++ 3 07-11-2003 08:22 PM



Advertisments