| Subject: | [PATCH] 2x faster LCS |
Hello,
I have optimized LCS function, so now it runs 96% faster when $keyGen is undef, the only change is removal of unnecessary calls of keygen functions. Looks like subroutine calls are really expensive in Perl.
Unfortunately my patch has one downside, when $keyGen is actually defined, LCS is 4% slower than it was without my changes. I don't think it's a problem, because typically LCS is used without $keyGen.
Patch is attached.
Cheers,
Tomasz
Test script:
use strict;
use warnings;
use Algorithm::Diff;
use Algorithm::OldDiff;
use Benchmark qw/:all/;
use Digest::MD5 qw/md5_hex/;
my @aa = (('z') x 100, 'a', 'b', 'c', ('dupa')x70000, 'd', 'kupa');
my @bb = (('z') x 100, 'a', 'b', 'c', ('dupz')x70000, 'f', 'kupa');
my $hash = sub { md5_hex(shift) };
cmpthese(50, {
'my patch' => sub { Algorithm::Diff::LCS(\@aa, \@bb) },
'orginal' => sub { Algorithm::OldDiff::LCS(\@aa, \@bb) },
});
cmpthese(50, {
'my patch' => sub { Algorithm::Diff::LCS(\@aa, \@bb, $hash) },
'original' => sub { Algorithm::OldDiff::LCS(\@aa, \@bb, $hash) },
});
Results:
PS E:\Dokumenty\difftest> perl .\lcs.pl
Rate orginal my patch
orginal 2.41/s -- -49%
my patch 4.72/s 96% --
Rate my patch original
my patch 1.39/s -- -3%
original 1.44/s 4% --
| Subject: | faster_lcs.patch |
ÿþ- - - D i f f . p m . o l d 2 0 1 4 - 1 1 - 2 6 0 6 : 4 1 : 5 4 . 0 0 0 0 0 0 0 0 0 + 0 1 0 0
+ + + D i f f . p m 2 0 1 4 - 1 2 - 2 3 2 1 : 0 3 : 5 1 . 0 0 0 0 0 0 0 0 0 + 0 1 0 0
@ @ - 4 2 , 7 + 4 2 , 7 @ @
f o r ( $ i n d e x = $ s t a r t ; $ i n d e x < = $ e n d ; $ i n d e x + + )
{
m y $ e l e m e n t = $ a C o l l e c t i o n - > [ $ i n d e x ] ;
- m y $ k e y = & $ k e y G e n ( $ e l e m e n t , @ _ ) ;
+ m y $ k e y = $ k e y G e n ? & $ k e y G e n ( $ e l e m e n t , @ _ ) : $ e l e m e n t ;
i f ( e x i s t s ( $ d { $ k e y } ) )
{
u n s h i f t ( @ { $ d { $ k e y } } , $ i n d e x ) ;
@ @ - 1 4 7 , 1 2 + 1 4 7 , 7 @ @
# s e t u p c o d e r e f s
# N o t e t h a t t h e s e a r e o p t i m i z e d .
- i f ( ! d e f i n e d ( $ k e y G e n ) ) # o p t i m i z e f o r s t r i n g s
- {
- $ k e y G e n = s u b { $ _ [ 0 ] } ;
- $ c o m p a r e = s u b { m y ( $ a , $ b ) = @ _ ; $ a e q $ b } ;
- }
- e l s e
+ i f ( $ k e y G e n ) # o p t i m i z e f o r s t r i n g s
{
$ c o m p a r e = s u b {
m y $ a = s h i f t ;
@ @ - 1 7 5 , 7 + 1 7 0 , 8 @ @
# F i r s t w e p r u n e o f f a n y c o m m o n e l e m e n t s a t t h e b e g i n n i n g
w h i l e ( $ a S t a r t < = $ a F i n i s h
a n d $ b S t a r t < = $ b F i n i s h
- a n d & $ c o m p a r e ( $ a - > [ $ a S t a r t ] , $ b - > [ $ b S t a r t ] , @ _ ) )
+ a n d ( $ k e y G e n ? & $ c o m p a r e ( $ a - > [ $ a S t a r t ] , $ b - > [ $ b S t a r t ] , @ _ )
+ : ( $ a - > [ $ a S t a r t ] e q $ b - > [ $ b S t a r t ] ) ) )
{
$ m a t c h V e c t o r - > [ $ a S t a r t + + ] = $ b S t a r t + + ;
$ p r u n e d C o u n t + + ;
@ @ - 1 8 4 , 7 + 1 8 0 , 8 @ @
# n o w t h e e n d
w h i l e ( $ a S t a r t < = $ a F i n i s h
a n d $ b S t a r t < = $ b F i n i s h
- a n d & $ c o m p a r e ( $ a - > [ $ a F i n i s h ] , $ b - > [ $ b F i n i s h ] , @ _ ) )
+ a n d ( $ k e y G e n ? & $ c o m p a r e ( $ a - > [ $ a F i n i s h ] , $ b - > [ $ b F i n i s h ] , @ _ )
+ : ( $ a - > [ $ a F i n i s h ] e q $ b - > [ $ b F i n i s h ] ) ) )
{
$ m a t c h V e c t o r - > [ $ a F i n i s h - - ] = $ b F i n i s h - - ;
$ p r u n e d C o u n t + + ;
@ @ - 2 0 0 , 7 + 1 9 7 , 7 @ @
m y ( $ i , $ a i , $ j , $ k ) ;
f o r ( $ i = $ a S t a r t ; $ i < = $ a F i n i s h ; $ i + + )
{
- $ a i = & $ k e y G e n ( $ a - > [ $ i ] , @ _ ) ;
+ $ a i = $ k e y G e n ? & $ k e y G e n ( $ a - > [ $ i ] , @ _ ) : $ a - > [ $ i ] ;
i f ( e x i s t s ( $ b M a t c h e s - > { $ a i } ) )
{
$ k = 0 ;