Re^4: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster)

Thanks a lot for your time and interest. I had to rewrite the loop in "buk3" like this:

for my $y ( 0 .. $HEIGHT-1 ) {
    my $s = substr( $$str, $y * $WIDTH, $WIDTH );
    while( $s =~ m[(([^\0])+)]g ) {
        my $c = ord($1); #, $-[0], $+[0];
        $b[ $c ][ LEFT   ] = $-[0]   if $-[0]   < $b[ $c ][ LEFT   ];
        $b[ $c ][ RIGHT  ] = $+[0]-1 if $+[0]-1 > $b[ $c ][ RIGHT  ];
        $b[ $c ][ TOP    ] = $y      if      $y < $b[ $c ][ TOP    ];
        $b[ $c ][ BOTTOM ] = $y      if      $y > $b[ $c ][ BOTTOM ];
    }
}
[download]

Otherwise it goes forever. We can't match globally against substr (as lvalue?), can we? When I run your code (5.24 on Windows), it says:

yr() took 3.484375
buk() took 1.233143
buk2() took 0.670660
buk3() took 0.029448
[download]

I.e. no hundreds of seconds, for my sub, at all. I would not otherwise publish it here and call it 'fast' :) Also, your test 'image' is something interesting, we can look at it if:

PDL::IO::Image-> new_from_pdl( 
    pdl([ unpack 'C*', $pdl ])
        -> reshape( 1000, 1000 )-> bitnot
)-> save( 'buk.png', 'PNG' );
[download]

Not exactly representative as real life image. For typical real image it's this:

PDL: Short D [7616,1200]
max = 145

       s/iter unpack   buk2  regex   buk3
unpack   3.02     --    -6%   -36%   -88%
buk2     2.84     6%     --   -32%   -87%
regex    1.92    57%    48%     --   -81%
buk3    0.362   733%   684%   430%     --
[download]

Anyway, your "buk3" algorithm is fastest.

Comment on Re^4: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster) Select or Download Code

Replies are listed 'Best First'.
Re^5: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster) by BrowserUk (Patriarch) on Nov 21, 2016 at 13:44 UTC
Curiouser and curiouser! When I run the code under 5.10, I get the sort of timings I posted above: `C:\test>1176081 -WIDTH=1000 -HEIGHT=1000 yr() took 330.252300 buk() took 1.584859 buk2() took 1.277809 buk3() took 0.226701` [download] But if I run it under 5.22, your sub runs very much faster* and buk3() doesn't terminate at all: which is weird and indicates (IMO) a bug in the later versions (I have an idea about the cause of the slowness in 5.10; I'll need to think of a way to verify it.) Modifying buk3() along the lines of your modification, but taking an lvalue ref outside the while loop and using it within the loop, allows it to work again: sub buk3{ my $str = shift; my @b = map[ ( 1e99, 0 ) x 2 ], 1 .. 256; for my $y ( 0 .. $HEIGHT-1 ) { my $ref = \substr( $$str, $y $WIDTH, $WIDTH ); while( $$ref =~ m[((.)\2*)]sg ) { my $c = ord($1); $b[ $c ][ LEFT ] = $-[0] if $-[0] < $b[ $c ][ LEFT + ]; $b[ $c ][ RIGHT ] = $+[0]-1 if $+[0]-1 > $b[ $c ][ RIGH +T ]; $b[ $c ][ TOP ] = $y if $y < $b[ $c ][ TOP + ]; $b[ $c ][ BOTTOM ] = $y if $y > $b[ $c ][ BOTT +OM ]; } } return \@b; } C:\test>\perl22\bin\perl 1176081.pl -WIDTH=1000 -HEIGHT=1000 yr() took 2.438320 buk() took 1.068071 buk2() took 0.681810 buk3() took 0.160666 [download] Which is okay, but a strange difference. It kinda takes the steam out of my amazing speedup figures -- 15x instead of 7000x -- but the thrill is transitory anyway :) And now I can run your sub on a larger image, even that gain is far less: `C:\test>\perl22\bin\perl 1176081.pl -WIDTH=10000 -HEIGHT=10000 yr() took 12.714030 buk() took 110.152981 buk2() took 70.100982 buk3() took 8.158657` [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^6: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster) by dbuckhal (Chaplain) on Nov 22, 2016 at 03:51 UTC
(*I have an idea about the cause of the slowness in 5.10; I'll need to think of a way to verify it.) I came across this article a little while back. It might help explain the speed difference. I certain have seen a difference running a Perl application between 5.1x and 5.22. How We Spent Two Days Making Perl Faster Hope you find it interesting!	[reply]
Re^7: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster) by BrowserUk (Patriarch) on Nov 22, 2016 at 08:39 UTC
If this difference in performance between versions was due to optimisations of the internals between those versions, then: Wouldn't you expect it to apply pretty evenly to all the subroutines rather than just one of them? If they'd succeeded in making Perl run 135x faster, I'm pretty sure we'd all have heard about it. The idea I had about a possible cause of the pathological behaviour of yr() code is my memory of this Windows memory allocation bug What could cause excessive page faults? that I discovered 7 years ago that, under some very specific circumstances, caused the CRT code underlying Perl to generate millions of page faults. But that is not the cause here. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^5: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (FAQ6: $&) by BrowserUk (Patriarch) on Nov 22, 2016 at 09:19 UTC
It turns out that the reason for the pathologic behaviour of your code under 5.10 is entirely down to your use of $&, as described in the FAQ since circa 1999 or before. Replacing `my $c = ord( $& ) - 1;` with `my $c = ord( substr $$str, $-[0], 1 ) - 1;` entirely eliminates the performance problem on 5.10.1. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^6: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (FAQ6: $&) by vr (Curate) on Nov 22, 2016 at 10:42 UTC
Thanks. I can allow myself :) to run all my code under new versions, and disregard performance issues of $&. Btw, using $& instead of creating capture groups and $1 gives a slight boost to "buk3". Also, I earlier experimented with "yr" - using "pos" (as it is) also gives quite a boost against using $-[0] or $+[0].	[reply]
Re^7: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (FAQ6: $&) by BrowserUk (Patriarch) on Nov 22, 2016 at 11:19 UTC
Btw, using $& instead of creating capture groups and $1 gives a slight boost to "buk3". Also, I earlier experimented with "yr" - using "pos" (as it is) also gives quite a boost against using $-[0] or $+[0]. Interesting. Something for me to experiment with next time I'm doing something similar. Also, did you see the results from eily's approach to the problem? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]