FOR loops removal

On Aug 20, 4:07*pm, Jeremy Bailin <astroco...@gmail.com> wrote:
> > So vectorization comes down to instead of repeating an action per
> > element in matrix, putting all elements on the right spot in a matrix
> > and doing the action on the matrix, right?
>
> Yup, that sums it up pretty well!
>
> -Jeremy.

So I tested the new finetuned program on the standard image and
instead of a calculated 15 hour time profit it has become almost 20,5
hour time profit. The program takes now 2.15 hours instead of 22.5
hours. That is a major improvement (< 10x), so thanks for all the info
allready. So I started out with even more improvements, I haven't
found any vectorisation possibilities yet though. I tried to fasten
the following code:

n = 20
size = 2*n+1
array = randomn(seed, size)
array[0] = 0
array[5] = 0
array[10] = 0
array[20] = 0
array[size-2] = 0
array[size-1] = 0

FOR x = 1, size-2 DO BEGIN
IF (array[x] EQ 0) THEN BEGIN
IF ((array[x-1] LE 2) AND (array[x+1] LE 2)) THEN
BEGIN
array[x] = 2
ENDIF ELSE BEGIN
IF ((array[x-1] GE 2) AND (array[x+1] GE 2)) THEN
BEGIN
array[x] = -2
ENDIF
ENDELSE
ENDIF
ENDFOR

So I figured that if i use the WHERE function to find where the array
equals 0, and then use a FOR loop that only goes trough the indices
that the WHERE function has found. So If you consider the WHERE
function to be much faster than the FOR loop, you could expect that
the second FOR loop would be faster or equally fast than the first FOR
loop. The code for the second FOR loop goes like this (some other
extra IF functions are needed for special cases like a zero as a first
element, last element or no zero at all):

zeroindex = where (array EQ 0,m)
IF (zeroindex[0] NE -1) THEN BEGIN
IF (zeroindex[0] EQ 0) THEN k = 1 ELSE k = 0
IF (zeroindex[m-1] EQ size-1) THEN l = 2 ELSE l = 1
FOR i= k, m-l DO BEGIN
IF ((array[zeroindex[i]-1] LE 2) AND (array[zeroindex[i]+1]
LE 2)) THEN BEGIN
array[zeroindex[i]] = 2
ENDIF ELSE BEGIN
IF ((array[zeroindex[i]-1] GE 2) AND (array[zeroindex[i]
+1] GE 2)) THEN BEGIN
array[zeroindex[i]] = -2
ENDIF
ENDELSE
ENDFOR

you could hear me coming from afar ofcourse . The second FOR loop
doesn't go faster, at all, with the variables set as above and the two
loops repeated for 50000 times. The first loop takes 0.304 s and the
second one 0.337 s. Only if the n-value is made larger than 25 the
second loop starts to go faster. I checked out profiler to check if
the WHERE function makes up for this slowing down this bit of
programming and ofcourse it does, the difference in time is 0.033s
while the WHERE function takes up 0.066s. So the second loop goes
faster but the use of the WHERE function slows the whole program down.
This is some nice checking out ofcourse but it doesn't help me getting
any further. Is there a faster alternative of the WHERE function? Or
did I reach the limit in finetuning here?

On Aug 21, 8:59 am, loebasboy <stijn....@gmail.com> wrote:
> On Aug 20, 4:07 pm, Jeremy Bailin <astroco...@gmail.com> wrote:
>
> > > So vectorization comes down to instead of repeating an action per
> > > element in matrix, putting all elements on the right spot in a matrix
> > > and doing the action on the matrix, right?
>
> > Yup, that sums it up pretty well!
>
> > -Jeremy.
>
> So I tested the new finetuned program on the standard image and
> instead of a calculated 15 hour time profit it has become almost 20,5
> hour time profit. The program takes now 2.15 hours instead of 22.5
> hours. That is a major improvement (< 10x), so thanks for all the info
> allready. So I started out with even more improvements, I haven't
> found any vectorisation possibilities yet though. I tried to fasten
> the following code:
>
> n = 20
> size = 2*n+1
> array = randomn(seed, size)
> array[0] = 0
> array[5] = 0
> array[10] = 0
> array[20] = 0
> array[size-2] = 0
> array[size-1] = 0
>
> FOR x = 1, size-2 DO BEGIN
> IF (array[x] EQ 0) THEN BEGIN
> IF ((array[x-1] LE 2) AND (array[x+1] LE 2)) THEN
> BEGIN
> array[x] = 2
> ENDIF ELSE BEGIN
> IF ((array[x-1] GE 2) AND (array[x+1] GE 2)) THEN
> BEGIN
> array[x] = -2
> ENDIF
> ENDELSE
> ENDIF
> ENDFOR
>

Hi,

note that by updating the array as you iterate through the elements,
you'll get different results to doing the whole thing in one chunk
(because element x-1 may or may not have been changed when it was
evaluated iteratively, but definitely won't if you do it vectorially).
You'll have to figure out which you want. If you want to update as go,
I can't really see a way out of the for loop; otherwise how about:

PaddedArray = [0.1, Array, 0.1]
ZeroInds = Where(PaddedArray Eq 0, Count)
If Count NE 0 Then Begin
MinusOne = ZeroInds - 1
PlusOne = ZeroInds + 1
; Sum the elements either side of the zeroes.
EitherSide = PaddedArray[MinusOne] + PaddedArray[PlusOne]
Bigger = Where(EitherSide GE 4.0, BiggerCount)
If BiggerCount NE 0 Then $
PaddedArray[ ZeroInds[Bigger] ] = 2.0
Smaller = Where(EitherSide LE 4.0, SmallerCount)
If SmallerCount NE 0 Then $
PaddedArray[ ZeroInds[Smaller] ] = -2.0
EndIf
Array = PaddedArray[1:N_Elements(Array)]

Is 'vectorially' even a word, or am I making things up again? :-\
Regards,
Chris

On Aug 21, 3:59*am, loebasboy <stijn....@gmail.com> wrote:
> So I tested the new finetuned program on the standard image and
> instead of a calculated 15 hour time profit it has become almost 20,5
> hour time profit. The program takes now 2.15 hours instead of 22.5
> hours. That is a major improvement (< 10x), so thanks for all the info
> allready. So I started out with even more improvements, I haven't
> found any vectorisation possibilities yet though. I tried to fasten
> the following code:
>
> n = 20
> size = 2*n+1
> array = randomn(seed, size)
> array[0] = 0
> array[5] = 0
> array[10] = 0
> array[20] = 0
> array[size-2] = 0
> array[size-1] = 0
>
> * * * * * * FOR x = 1, size-2 DO BEGIN
> * * * * * * * IF (array[x] EQ 0) THEN BEGIN
> * * * * * * * * IF ((array[x-1] LE 2) AND (array[x+1] LE 2)) THEN
> BEGIN
> * * * * * * * * * array[x] = 2
> * * * * * * * * ENDIF ELSE BEGIN
> * * * * * * * * * IF ((array[x-1] GE 2) AND (array[x+1]GE 2)) THEN
> BEGIN
> * * * * * * * * * * array[x] = -2
> * * * * * * * * * ENDIF
> * * * * * * * * ENDELSE
> * * * * * * * ENDIF
> * * * * * * ENDFOR
>
> So I figured that if i use the WHERE function to find where the array
> equals 0, and then use a FOR loop that only goes trough the indices
> that the WHERE function has found. So If you consider the WHERE
> function to be much faster than the FOR loop, you could expect that
> the second FOR loop would be faster or equally fast than the first FOR
> loop. The code for the second FOR loop goes like this (some other
> extra IF functions are needed for special cases like a zero as a first
> element, last element or no zero at all):
>
> * * * *zeroindex = where (array EQ 0,m)
> * * * *IF (zeroindex[0] NE -1) THEN BEGIN
> * * * * *IF (zeroindex[0] EQ 0) THEN k = 1 ELSE k = 0
> * * * * *IF (zeroindex[m-1] EQ size-1) THEN l = 2 ELSE l = 1
> * * * * *FOR i= k, m-l DO BEGIN
> * * * * * IF ((array[zeroindex[i]-1] LE 2) AND (array[zeroindex[i]+1]
> LE 2)) THEN BEGIN
> * * * * * * array[zeroindex[i]] = 2
> * * * * * ENDIF ELSE BEGIN
> * * * * * * IF ((array[zeroindex[i]-1] GE 2) AND (array[zeroindex[i]
> +1] GE 2)) THEN BEGIN
> * * * * * * * array[zeroindex[i]] = -2
> * * * * * * ENDIF
> * * * * * ENDELSE
> * * * * *ENDFOR
>
> you could hear me coming from afar ofcourse . The second FOR loop
> doesn't go faster, at all, with the variables set as above and the two
> loops repeated for 50000 times. The first loop takes 0.304 s and the
> second one 0.337 s. Only if the n-value is made larger than 25 the
> second loop starts to go faster. I checked out profiler to check if
> the WHERE function makes up for this slowing down this bit of
> programming and ofcourse it does, the difference in time is 0.033s
> while the WHERE function takes up 0.066s. So the second loop goes
> faster but the use of the WHERE function slows the whole program down.
> This is some nice checking out ofcourse but it doesn't help me getting
> any further. Is there a faster alternative of the WHERE function? Or
> did I reach the limit in finetuning here?

The solution, of course, is to also replace the inner FOR loops with
WHEREs. :-)=

zeroindex = where(array[1:size-2] eq 0, nzero)
if nzero gt 0 then begin
smallneighbours = where(array[zeroindex-1] le 2 and array[zeroindex
+1] le 2, nsmall)
if nsmall gt 0 then array[zeroindex[smallneighbours]] = 2
bigneighbours = where(array[zeroindex-1] le 2 and array[zeroindex+1]
le 2, nbig)
if nbig gt 0 then array[zeroindex[bigneighbours]] = -2
endif

-Jeremy.

On Aug 21, 3:39*pm, Jeremy Bailin <astroco...@gmail.com> wrote:
> On Aug 21, 3:59*am, loebasboy <stijn....@gmail.com> wrote:
>
>
>
>
>
> > So I tested the new finetuned program on the standard image and
> > instead of a calculated 15 hour time profit it has become almost 20,5
> > hour time profit. The program takes now 2.15 hours instead of 22.5
> > hours. That is a major improvement (< 10x), so thanks for all the info
> > allready. So I started out with even more improvements, I haven't
> > found any vectorisation possibilities yet though. I tried to fasten
> > the following code:
>
> > n = 20
> > size = 2*n+1
> > array = randomn(seed, size)
> > array[0] = 0
> > array[5] = 0
> > array[10] = 0
> > array[20] = 0
> > array[size-2] = 0
> > array[size-1] = 0
>
> > * * * * * * FOR x = 1, size-2 DO BEGIN
> > * * * * * * * IF (array[x] EQ 0) THEN BEGIN
> > * * * * * * * * IF ((array[x-1] LE 2) AND (array[x+1] LE 2)) THEN
> > BEGIN
> > * * * * * * * * * array[x] = 2
> > * * * * * * * * ENDIF ELSE BEGIN
> > * * * * * * * * * IF ((array[x-1] GE 2) AND (array[x+1] GE 2)) THEN
> > BEGIN
> > * * * * * * * * * * array[x] = -2
> > * * * * * * * * * ENDIF
> > * * * * * * * * ENDELSE
> > * * * * * * * ENDIF
> > * * * * * * ENDFOR
>
> > So I figured that if i use the WHERE function to find where the array
> > equals 0, and then use a FOR loop that only goes trough the indices
> > that the WHERE function has found. So If you consider the WHERE
> > function to be much faster than the FOR loop, you could expect that
> > the second FOR loop would be faster or equally fast than the first FOR
> > loop. The code for the second FOR loop goes like this (some other
> > extra IF functions are needed for special cases like a zero as a first
> > element, last element or no zero at all):
>
> > * * * *zeroindex = where (array EQ 0,m)
> > * * * *IF (zeroindex[0] NE -1) THEN BEGIN
> > * * * * *IF (zeroindex[0] EQ 0) THEN k = 1 ELSE k = 0
> > * * * * *IF (zeroindex[m-1] EQ size-1) THEN l = 2 ELSE l = 1
> > * * * * *FOR i= k, m-l DO BEGIN
> > * * * * * IF ((array[zeroindex[i]-1] LE 2) AND (array[zeroindex[i]+1]
> > LE 2)) THEN BEGIN
> > * * * * * * array[zeroindex[i]] = 2
> > * * * * * ENDIF ELSE BEGIN
> > * * * * * * IF ((array[zeroindex[i]-1] GE 2) AND (array[zeroindex[i]
> > +1] GE 2)) THEN BEGIN
> > * * * * * * * array[zeroindex[i]] = -2
> > * * * * * * ENDIF
> > * * * * * ENDELSE
> > * * * * *ENDFOR
>
> > you could hear me coming from afar ofcourse . The second FOR loop
> > doesn't go faster, at all, with the variables set as above and the two
> > loops repeated for 50000 times. The first loop takes 0.304 s and the
> > second one 0.337 s. Only if the n-value is made larger than 25 the
> > second loop starts to go faster. I checked out profiler to check if
> > the WHERE function makes up for this slowing down this bit of
> > programming and ofcourse it does, the difference in time is 0.033s
> > while the WHERE function takes up 0.066s. So the second loop goes
> > faster but the use of the WHERE function slows the whole program down.
> > This is some nice checking out ofcourse but it doesn't help me getting
> > any further. Is there a faster alternative of the WHERE function? Or
> > did I reach the limit in finetuning here?
>
> The solution, of course, is to also replace the inner FOR loops with
> WHEREs. :-)=
>
> zeroindex = where(array[1:size-2] eq 0, nzero)
> if nzero gt 0 then begin
> * smallneighbours = where(array[zeroindex-1] le 2 and array[zeroindex
> +1] le 2, nsmall)
> * if nsmall gt 0 then array[zeroindex[smallneighbours]] = 2
> * bigneighbours = where(array[zeroindex-1] le 2 and array[zeroindex+1]
> le 2, nbig)
> * if nbig gt 0 then array[zeroindex[bigneighbours]] = -2
> endif
>
> -Jeremy.- Hide quoted text -
>
> - Show quoted text -

Good code, there was a +1 needed in the zeroindex declaration though.
It doesn't go any faster also, too bad, I guess that the use of the
WHERE function doesn't speed up. But thank you for the suggestion !

> Good code, there was a +1 needed in the zeroindex declaration though.

Ah yes, of course. Serves me right for not testing it before posting
it! ;-)

> It doesn't go any faster also, too bad, I guess that the use of the
> WHERE function doesn't speed up. But thank you for the suggestion !

Hmmm, that's too bad. It's possible that going down to two WHEREs over
the full array will be faster than using the first WHERE to thin the
array down. It'll depend on what fraction of the array contains zeros
- if there are lots of zeros, then the first WHERE doesn't help you
that much, whereas if there aren't many then it will help a lot.

Is this part of the code really one of the biggest remaining
bottlenecks? I doubt you'll be able to shave much more off of it.

-Jeremy.

What about something like this?

s= 2*(array le 2)-1
array = (array ne 0)*array + (array eq 0)*(shift(s,1)+shift(s,-1))

You'll have to manually fix the endpoints, but the rest should be
good. I tested this and the first loop on an array of 400,000
elements. The first loop rand in .54 seconds, while the second ran in .
054s.

Also, you should be a little careful when testing whether array equals
zero. If the array isn't an integer type (int, byte, long, etc), then
its possible to have numbers you think ought to be zero but, because
of finite precision arithmetic, have very small nonzero values. If you
suspect that this is happening, you can try a test like abs(array) le
eps, where eps is something like 10^-5 or something big enough to
cover roundoff error but small enough not to treat nonzero data you
care about as zero


chris

On Aug 21, 8:34*pm, Chris <beaum...@ifa.hawaii.edu> wrote:
> What about something like this?
>
> s= 2*(array le 2)-1
> array = (array ne 0)*array + (array eq 0)*(shift(s,1)+shift(s,-1))
>
> You'll have to manually fix the endpoints, but the rest should be
> good. I tested this and the first loop on an array of 400,000
> elements. The first loop rand in .54 seconds, while the second ran in .
> 054s.
>
> Also, you should be a little careful when testing whether array equals
> zero. If the array isn't an integer type (int, byte, long, etc), then
> its possible to have numbers you think ought to be zero but, because
> of finite precision arithmetic, have very small nonzero values. If you
> suspect that this is happening, you can try a test like abs(array) le
> eps, where eps is something like 10^-5 or something big enough to
> cover roundoff error but small enough not to treat nonzero data you
> care about as zero
>
> chris

Hello, thank you both for the input. Chris, yours doesn't go faster
also despite it is really elegant (and pointing me to the shift
function, which I didnt know exist and can come in handy). The reason
for the lack of speed profit is that I haven't a large array there
that needs to be processed, instead I have many small array that need
to be processed (the whole of my program exist of one BIG for loop)
and there are relatively a lot of zeros in the processed array (which
is why the WHERE function solution doesn't work either)

To answer Jeremy's question, the real bottleneck was the former FOR
loop removal problem, which was part of a function that is repeated
1359520 times for a test image and taking up 39.1 s now and 248.2 s
before. The FOR loop I was asking about now, is a part of a function
that is also repeated 1359520 times and takes up 29 s now. The former
function cannot be made any faster than it is now (thanks to all of
you ). So I started working on the simplest FOR loop in the latter
function but it didn't work out.

On Aug 22, 5:08 am, loebasboy <stijn....@gmail.com> wrote:
> On Aug 21, 8:34 pm, Chris <beaum...@ifa.hawaii.edu> wrote:
>
>
>
> > What about something like this?
>
> > s= 2*(array le 2)-1
> > array = (array ne 0)*array + (array eq 0)*(shift(s,1)+shift(s,-1))
>
> > You'll have to manually fix the endpoints, but the rest should be
> > good. I tested this and the first loop on an array of 400,000
> > elements. The first loop rand in .54 seconds, while the second ran in .
> > 054s.
>
> > Also, you should be a little careful when testing whether array equals
> > zero. If the array isn't an integer type (int, byte, long, etc), then
> > its possible to have numbers you think ought to be zero but, because
> > of finite precision arithmetic, have very small nonzero values. If you
> > suspect that this is happening, you can try a test like abs(array) le
> > eps, where eps is something like 10^-5 or something big enough to
> > cover roundoff error but small enough not to treat nonzero data you
> > care about as zero
>
> > chris
>
> Hello, thank you both for the input. Chris, yours doesn't go faster
> also despite it is really elegant (and pointing me to the shift
> function, which I didnt know exist and can come in handy). The reason
> for the lack of speed profit is that I haven't a large array there
> that needs to be processed, instead I have many small array that need
> to be processed (the whole of my program exist of one BIG for loop)
> and there are relatively a lot of zeros in the processed array (which
> is why the WHERE function solution doesn't work either)
>

Hi,

Given your response to Chris I think the teeeny suggestion I have to
share is a moot point. But I'll put it out there because it can be
handy. If I understand Chris' code snippet correctly, there can be a
spped up by using something like this...

mask1 = array ne 0
mask0 = ~mask1
array = mask1*array + mask0*(shift(s,1)+shift(s,-1))

It probably is a slim gain but can add up to a lot if you are
looping. In my simple minded test below I see better than 2x gain
usually.


a = RANDOMN(seed, 2000, 2000) > 0.0
b = A GT 0

PRINT, "~B test"
t0 = SYSTIME(/sec)
c = ~B
print, systime(/sec) - t0

PRINT, "B EQ 0 test"
t0 = SYSTIME(/sec)
c = b EQ 0
print, systime(/sec) - t0

IDL> @not_test
~B test
0.056261063
B EQ 0 test
0.13446379


Cheers,
ben

Are you looping 139520 times because you have that many images you are
reading from disk? If so, you probably aren't going to be able to do
any better. I/O is unavoidably slow. If not, what are you doing that
requires so my loops? How quickly do you process one image?

As a general guideline, most image processing on a single image (say a
few megapixels) should be on the order of a few seconds once
vectorized well. If you have several hundred thousand images, one
thing to consider is to merge them into larger files (by making data
cubes). This would reduce the number of hard-disk seeks during IO.

On Aug 22, 8:19*pm, Chris <beaum...@ifa.hawaii.edu> wrote:
> Are you looping 139520 times because you have that many images you are
> reading from disk? If so, you probably aren't going to be able to do
> any better. I/O is unavoidably slow. If not, what are you doing that
> requires so my loops? How quickly do you process one image?
>
> As a general guideline, most image processing on a single image (say a
> few megapixels) should be on the order of a few seconds once
> vectorized well. If you have several hundred thousand images, one
> thing to consider is to merge them into larger files (by making data
> cubes). This would reduce the number of hard-disk seeks during IO.

There is only 1 image that is processed. 1 loop works on a part of the
image, that is, several columns and all the rows. When 1 loop is done,
all columns are moved up one column spot and at the end of the part a
new column is added (from the full image). The first column is then
removed from the part. And so the the full image is processed. 600
columns means 600 loops minus the width of the part two times. Also in
every loop the process is repeated 4 times.