LCB Performance

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

LCB Performance

Skip Kimpel via use-livecode
This is a continuation of some code introduced in the "valueDiff" thread,
but wanted to take it in a slightly different direction.  We had some great
success at getting a process that took over 50 seconds on my machine down
to under 10 seconds.  It isn't anything that we would actually use in
production, but I'm sure things like this can help us in the real world.

I decided to try and port the fastest of the methods over to LCB.  I'm sure
quite a bit of it is due to my lack of experience, but the speeds were much
slower.  I ended up putting some hard coded limits in my stack so that LCB
wasn't used over 100,000 for the List and Array version and 1,000,000 for
the Byte version.

What I found was that for arrays, the requirement to convert the number to
a string killed the performance (my guess anyway).  Here is a full list of
the various versions that I've tried:

"Find primes up to 100000, repeat 1 time(s)"
"Byte (bernd)" - 0.065108 seconds
"Byte (bwm)" - 0.103379 seconds
"Byte (alex)" - 0.122581 seconds
"Array (mark)" - 0.323269 seconds
"Array (bwm)" - 0.345896 seconds
"Array (original)" - 0.386326 seconds
"Byte (LCB)" - 1.125969 seconds
"List (LCB)" - 136.770451 seconds
"Array (LCB)" - 845.35211 seconds

I've updated the stack that I uploaded with the new tests (but one would
need to compile/install the LCB for the last 3 tests)
https://milby.us/lc/Primes.livecode

Here's one of the handlers that I converted:

public handler getPrimesLCB_List(in pN as Number) returns String
   variable tMroot as Number
   variable tPrimes as String
   variable tIsItPrime as List
   variable tTenK as List
   variable tYes as Data
   variable tNo as Data
   variable tI as Number
   variable tJ as Number
   put the byte with code 66 into tYes
   put the byte with code 65 into tNo
   if pN < 2 then
      return the empty string
   else if pN = 2 then
      return "2"
   end if
   put (the trunc of sqrt(pN)) - 1 into tMroot
   put the empty list into tIsItPrime
   if pN >= 10000 then
      put the empty list into tTenK
      repeat 10000 times
         push tYes onto tTenK
      end repeat
      repeat (pN / 10000) times
         put tTenK & tIsItPrime into tIsItPrime
      end repeat
   end if
   repeat pN mod 10000 times
      push tYes onto tIsItPrime
   end repeat
   put "2" into tPrimes
   repeat with tI from 3 up to tMroot by 2
      if tIsItPrime[tI] is tNo then
         next repeat
      end if
      put "\n" & tI formatted as string after tPrimes
      repeat with tJ from tI^2 up to pN by tI
         put tNo into tIsItPrime[tJ]
      end repeat
   end repeat
   repeat with tI from tMroot + (tMroot + 1) mod 2 up to pN - 1 by 2
      if tIsItPrime[tI] is tYes then
         put "\n" & tI formatted as string after tPrimes
      end if
   end repeat
   return tPrimes
end handler


Is there any way to optimize the speed of LCB to meet/exceed the same code
in LCS or is the intention more for things where the speed isn't the main
factor (like UI widgets and interacting with external code via FFI)?

Thanks,
Brian
_______________________________________________
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: LCB Performance

Skip Kimpel via use-livecode
You might be better off building the primes as a List, then converting to a string at the end. Although the conversion of each number is only done once so it probably doesn't make too much difference (apart from being a bit more LCBy).

In general LCB should be written to prefer structure over strings - it better represents the flow of individual values - which makes any future optimisations at the vm level more effective.

LCB should really be considered the language to use for widgets and foreign extensions - for much algorithmic stuff you'll get better performance from LCS.

To be fast LCB needs an optimisation phase which would lower the level of operations it performs - the internal structure of LCB makes this feasible but as yet not done.

In contrast LCS is pretty quick - it also needs an optimisation phase really - but with its current implementation that's largely infeasible!

(The optimisation phase would actually be the same - the problem is that both need to be translated to a slightly lower level common bytecode form first - then optimised).

Warmest Regards,

Mark.

Sent from my iPhone

> On 7 Aug 2018, at 22:54, Brian Milby via use-livecode <[hidden email]> wrote:
>
> This is a continuation of some code introduced in the "valueDiff" thread,
> but wanted to take it in a slightly different direction.  We had some great
> success at getting a process that took over 50 seconds on my machine down
> to under 10 seconds.  It isn't anything that we would actually use in
> production, but I'm sure things like this can help us in the real world.
>
> I decided to try and port the fastest of the methods over to LCB.  I'm sure
> quite a bit of it is due to my lack of experience, but the speeds were much
> slower.  I ended up putting some hard coded limits in my stack so that LCB
> wasn't used over 100,000 for the List and Array version and 1,000,000 for
> the Byte version.
>
> What I found was that for arrays, the requirement to convert the number to
> a string killed the performance (my guess anyway).  Here is a full list of
> the various versions that I've tried:
>
> "Find primes up to 100000, repeat 1 time(s)"
> "Byte (bernd)" - 0.065108 seconds
> "Byte (bwm)" - 0.103379 seconds
> "Byte (alex)" - 0.122581 seconds
> "Array (mark)" - 0.323269 seconds
> "Array (bwm)" - 0.345896 seconds
> "Array (original)" - 0.386326 seconds
> "Byte (LCB)" - 1.125969 seconds
> "List (LCB)" - 136.770451 seconds
> "Array (LCB)" - 845.35211 seconds
>
> I've updated the stack that I uploaded with the new tests (but one would
> need to compile/install the LCB for the last 3 tests)
> https://milby.us/lc/Primes.livecode
>
> Here's one of the handlers that I converted:
>
> public handler getPrimesLCB_List(in pN as Number) returns String
>   variable tMroot as Number
>   variable tPrimes as String
>   variable tIsItPrime as List
>   variable tTenK as List
>   variable tYes as Data
>   variable tNo as Data
>   variable tI as Number
>   variable tJ as Number
>   put the byte with code 66 into tYes
>   put the byte with code 65 into tNo
>   if pN < 2 then
>      return the empty string
>   else if pN = 2 then
>      return "2"
>   end if
>   put (the trunc of sqrt(pN)) - 1 into tMroot
>   put the empty list into tIsItPrime
>   if pN >= 10000 then
>      put the empty list into tTenK
>      repeat 10000 times
>         push tYes onto tTenK
>      end repeat
>      repeat (pN / 10000) times
>         put tTenK & tIsItPrime into tIsItPrime
>      end repeat
>   end if
>   repeat pN mod 10000 times
>      push tYes onto tIsItPrime
>   end repeat
>   put "2" into tPrimes
>   repeat with tI from 3 up to tMroot by 2
>      if tIsItPrime[tI] is tNo then
>         next repeat
>      end if
>      put "\n" & tI formatted as string after tPrimes
>      repeat with tJ from tI^2 up to pN by tI
>         put tNo into tIsItPrime[tJ]
>      end repeat
>   end repeat
>   repeat with tI from tMroot + (tMroot + 1) mod 2 up to pN - 1 by 2
>      if tIsItPrime[tI] is tYes then
>         put "\n" & tI formatted as string after tPrimes
>      end if
>   end repeat
>   return tPrimes
> end handler
>
>
> Is there any way to optimize the speed of LCB to meet/exceed the same code
> in LCS or is the intention more for things where the speed isn't the main
> factor (like UI widgets and interacting with external code via FFI)?
>
> Thanks,
> Brian
> _______________________________________________
> 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: LCB Performance

Skip Kimpel via use-livecode
In reply to this post by Skip Kimpel via use-livecode
This is not in LCB script, but you posting this reminded me of some code I
wrote a long time ago when I needed (for a programming challenge) to write
a function that would return primes up to 10^9 or so. That was far too
large to do the traditional "build an array of excluded values" sort of
thing, so I wrote code that self-groomed the array as it went, discarding
the bits it no longer needed.

I checked and I didn't have the stack anymore, so I rewrote it. It's about
as fast as the traditional way (as you coded), and as designed, given time
should be able to calculate up to... maybe 10 to a 100 million prime
numbers? The working array only has a max of as many entries as the current
number of found primes, so who knows? Anyway, I thought it was clever, here
it is:

function getPrimes2 pN
   if pN < 2 then return empty
   put "2" into tPrimes
   put trunc(sqrt(pN - 1)) into maxFactor
   repeat with tI = 3 to pN - 1 step 2
      if p[tI] is empty then
         if tI <= maxFactor then put (2*tI),"" after p[tI^2]
         put cr & tI after tPrimes
      else
         repeat for each item i in p[tI]
            put i,"" after p[tI + i]
         end repeat
      end if
      delete variable p[tI] -- not sure whether this should be here or in
the else section above
   end repeat
   return tPrimes
end getPrimes2

The reason for the uncertainty of the delete is that I'm not sure whether
LC creates/allocates the array element just based on testing if it is
empty. If LC does, then the delete needs to be where it is. If LC doesn't,
then it can be in the else, where we know the element exists.

On Tue, Aug 7, 2018 at 8:54 PM Brian Milby via use-livecode <
[hidden email]> wrote:

> This is a continuation of some code introduced in the "valueDiff" thread,
> but wanted to take it in a slightly different direction.  We had some great
> success at getting a process that took over 50 seconds on my machine down
> to under 10 seconds.  It isn't anything that we would actually use in
> production, but I'm sure things like this can help us in the real world.
>
> I decided to try and port the fastest of the methods over to LCB.  I'm sure
> quite a bit of it is due to my lack of experience, but the speeds were much
> slower.  I ended up putting some hard coded limits in my stack so that LCB
> wasn't used over 100,000 for the List and Array version and 1,000,000 for
> the Byte version.
>
> What I found was that for arrays, the requirement to convert the number to
> a string killed the performance (my guess anyway).  Here is a full list of
> the various versions that I've tried:
>
> "Find primes up to 100000, repeat 1 time(s)"
> "Byte (bernd)" - 0.065108 seconds
> "Byte (bwm)" - 0.103379 seconds
> "Byte (alex)" - 0.122581 seconds
> "Array (mark)" - 0.323269 seconds
> "Array (bwm)" - 0.345896 seconds
> "Array (original)" - 0.386326 seconds
> "Byte (LCB)" - 1.125969 seconds
> "List (LCB)" - 136.770451 seconds
> "Array (LCB)" - 845.35211 seconds
>
> I've updated the stack that I uploaded with the new tests (but one would
> need to compile/install the LCB for the last 3 tests)
> https://milby.us/lc/Primes.livecode
>
> Here's one of the handlers that I converted:
>
> public handler getPrimesLCB_List(in pN as Number) returns String
>    variable tMroot as Number
>    variable tPrimes as String
>    variable tIsItPrime as List
>    variable tTenK as List
>    variable tYes as Data
>    variable tNo as Data
>    variable tI as Number
>    variable tJ as Number
>    put the byte with code 66 into tYes
>    put the byte with code 65 into tNo
>    if pN < 2 then
>       return the empty string
>    else if pN = 2 then
>       return "2"
>    end if
>    put (the trunc of sqrt(pN)) - 1 into tMroot
>    put the empty list into tIsItPrime
>    if pN >= 10000 then
>       put the empty list into tTenK
>       repeat 10000 times
>          push tYes onto tTenK
>       end repeat
>       repeat (pN / 10000) times
>          put tTenK & tIsItPrime into tIsItPrime
>       end repeat
>    end if
>    repeat pN mod 10000 times
>       push tYes onto tIsItPrime
>    end repeat
>    put "2" into tPrimes
>    repeat with tI from 3 up to tMroot by 2
>       if tIsItPrime[tI] is tNo then
>          next repeat
>       end if
>       put "\n" & tI formatted as string after tPrimes
>       repeat with tJ from tI^2 up to pN by tI
>          put tNo into tIsItPrime[tJ]
>       end repeat
>    end repeat
>    repeat with tI from tMroot + (tMroot + 1) mod 2 up to pN - 1 by 2
>       if tIsItPrime[tI] is tYes then
>          put "\n" & tI formatted as string after tPrimes
>       end if
>    end repeat
>    return tPrimes
> end handler
>
>
> Is there any way to optimize the speed of LCB to meet/exceed the same code
> in LCS or is the intention more for things where the speed isn't the main
> factor (like UI widgets and interacting with external code via FFI)?
>
> Thanks,
> Brian
> _______________________________________________
> 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