Atkinson dither algorithm & 'for each' loop

[Peter Reid]

One note of caution regarding the use of the "repeat for each" loop, whilst you will get a loop iteration for every value in the collection (fldhexa3 in your example), you are not guaranteed the order in which they will occur.  This doesn't matter in a lot of cases but does matter when the sequence is significant.  In the case of your example I believe sequence is critical, otherwise the pixels might appear to be scrambled!

The following adjusted loop guarantees the sequence at the expense of speed:

  put 1 into i
  repeat for each word theWord in fldhexa3
     put word i of fldhexa3 into theWord
     put 00 & theword & theword & theword after tVar2
     add 1 to i
  end repeat

The original "improved" loop reduces the run-time to 25%.  However, the "modified improved" loop only manages to reduce the original run-time to 50%.

The suggested loop above takes advantage of the "for each" mechanism to produce a set of iterations very rapidly but gets slowed by the need to guarantee sequence. I wonder whether the LC engine could impose strict sequence more effectively with a variant of the "for each" loop such as

  repeat for each sequenced word x in theCollection
     ...
  end repeat

My own tests, comparing the speed of the 4 common repeat loops, imply that the current "for each" form is hugely faster than the others.  I tested "repeat for each...", "repeat while...", "repeat until...", "repeat with..." and a simulated "repeat for each sequenced..." forms using a simple loop body that added lines of text one after another, e.g.

  put empty into tData
  repeat with i = 1 to tMaxI
    put line i of tList & return after tData
  end repeat

I ran this test for 250,000 iterations for each type of loop, which produced the following timings:

  Starting test for 250,000 iterations...
  repeat for each... 0 mins 0 secs 111 millisecs
  repeat while... 0 mins 30 secs 569 millisecs
  repeat until... 0 mins 30 secs 379 millisecs
  repeat with... 0 mins 30 secs 341 millisecs
  repeat for each seq... 0 mins 30 secs 524 millisecs

As you can see, in this test the "repeat for each..." form was approx. 275 times faster than the other forms.  Also the simulated "repeat for each sequenced..." form was no faster than the other forms.  This shows how variable the speed will be with the simulated "repeat for each sequenced...", depending on the details of the loop body.

If there was a "repeat for each sequenced..." form of loop in LC, any speed-up could be very beneficial even if the amount of speed-up was only 10 times faster!

Cheers

Peter
--
Peter Reid
Loughborough, UK

> On 9 Oct 2017, at 10:18am, use-livecode-request at lists.runrev.com wrote:
> 
> Message: 12
> Date: Sat, 7 Oct 2017 15:53:44 +0200
> From: Malte Pfaff-Brill <revolution at derbrill.de>
> To: use-livecode at lists.runrev.com
> Subject: Re: Atkinson dither algorithm  
> Message-ID: <42023B36-0A4E-4251-BB0C-9CD46DE55807 at derbrill.de>
> Content-Type: text/plain; charset=us-ascii
> 
> Hi Al,
> 
> I already posted on the forums, but for completeness also here:
> 
> a lot can be done by replacing repeat with with repeat for each where you can.
> 
> --    repeat with i = 1 to the number of words of fldhexa3
>   --       put 00 & word i of fldhexa3 & word i of fldhexa3 & word i of fldhexa3 after tVar2
>   --    end repeat
> 
>   repeat for each word theWord in fldhexa3
>      put 00 & theword & theword & theword after tVar2
>   end repeat
> 
> 
> A sidenode:
> 
> I always use strict compile mode, therefore I added the needed variable declarations and noticed you use startTime as a variablename, which is a reserved keyword. That is not a good idea.  (I noticed, because I managed to freeze liveCode where I fixed only half of the use of startTime. Booom.)
> 
> Cheers,
> 
> malte