Re: Atkinson dither algorithm & 'for each' loop

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Atkinson dither algorithm & 'for each' loop

J. Landman Gay via use-livecode
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, [hidden email] wrote:
>
> Message: 12
> Date: Sat, 7 Oct 2017 15:53:44 +0200
> From: Malte Pfaff-Brill <[hidden email]>
> To: [hidden email]
> Subject: Re: Atkinson dither algorithm  
> Message-ID: <[hidden email]>
> 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


_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Atkinson dither algorithm & 'for each' loop

J. Landman Gay via use-livecode
Hi Peter,

> 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.

Are you sure? My understanding has always been that chunk items, e.g.
        repeat for each [ byte | char | word | item | line] <var> in <container>

will always be sequential (indeed that's why this structure is fast) - it's
only when dealing with hashed arrays that the sequence is not reliable, i.e.
        repeat for each key <var> in <array>
        repeat for each element <var> in <array>

Do you have experience to the contrary?

best regards,

Ben

On 12/10/2017 12:05, Peter Reid via use-livecode wrote:

> 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, [hidden email] wrote:
>>
>> Message: 12
>> Date: Sat, 7 Oct 2017 15:53:44 +0200
>> From: Malte Pfaff-Brill <[hidden email]>
>> To: [hidden email]
>> Subject: Re: Atkinson dither algorithm
>> Message-ID: <[hidden email]>
>> 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
>
>
> _______________________________________________
> use-livecode mailing list
> [hidden email]
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Atkinson dither algorithm & 'for each' loop

J. Landman Gay via use-livecode
That is correct Ben. It's not the repeat for each that is unreliable (probably a bad word to use here) but it is arrays which do not retain the sequence of key/values in the order they were put in.

To get around this, when possible use numbered keys, then:

put  the keys of aMyArray into tKeyList
sort the lines of tKeyList numeric ascending
repeat for each line tKey in tKeyList
...

Bob S


> On Oct 12, 2017, at 04:48 , Ben Rubinstein via use-livecode <[hidden email]> wrote:
>
> Hi Peter,
>
>> 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.
>
> Are you sure? My understanding has always been that chunk items, e.g.
> repeat for each [ byte | char | word | item | line] <var> in <container>
>
> will always be sequential (indeed that's why this structure is fast) - it's only when dealing with hashed arrays that the sequence is not reliable, i.e.
> repeat for each key <var> in <array>
> repeat for each element <var> in <array>
>
> Do you have experience to the contrary?
>
> best regards,
>
> Ben


_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Atkinson dither algorithm & 'for each' loop

J. Landman Gay via use-livecode
In reply to this post by J. Landman Gay via use-livecode
Peter Reid wrote:

 > 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.

Maybe I misunderstand, but are you thinking of arrays there?

With string containers a "repeat for each" expression should parse from
beginning to end, sequentially.

Any exception to that would be prohibitively unpredictable, and should
be reported as a bug.


 > 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

The speed lost there appears to be the result of a redundancy, and a
particularly expensive one:

We love the convenience of chunk expressions, but in loops we want to
remain mindful of "<chunk> <number> of <container>" because satisfying
such expressions will require the engine to start from the beginning of
the container, examine every character and counting delimiters, until it
reaches the number of such delimiters specified in "<number>".

So the "repeat" line above parses the chunk value into theWord, but then
the next line ignores that that's already happened and reassigns the
same theWord value using an expression that requires then engine to
count words from the beginning of fldhexa3 each time through the loop.


With this specific algo I believe there may be further benefits in using
a chunk type other than word (based on a a hunch derived from word
chunks being parsed more flexibly than items or lines), and perhaps not
converting the binary data to hex at all, instead parsing bytes directly
with a "step 4" option in the loop to keep track of the four components
that define each pixel.

--
  Richard Gaskin
  Fourth World Systems
  Software Design and Development for the Desktop, Mobile, and the Web
  ____________________________________________________________________
  [hidden email]                http://www.FourthWorld.com

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Atkinson dither algorithm & 'for each' loop

J. Landman Gay via use-livecode
In reply to this post by J. Landman Gay via use-livecode
HI All

Hoping I'm not teaching my granny to suck eggs ... Here is a great article
I remembered reading  from a few years ago. It's easy to find on google so
you probably know of it ...

http://www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/

In any case his projects and how he writes about them are interesting

 http://www.tannerhelland.com/programming-directory/

Lagi

On 12 October 2017 at 12:05, Peter Reid via use-livecode <
[hidden email]> wrote:

> 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, [hidden email] wrote:
> >
> > Message: 12
> > Date: Sat, 7 Oct 2017 15:53:44 +0200
> > From: Malte Pfaff-Brill <[hidden email]>
> > To: [hidden email]
> > Subject: Re: Atkinson dither algorithm
> > Message-ID: <[hidden email]>
> > 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
>
>
> _______________________________________________
> use-livecode mailing list
> [hidden email]
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>
_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode