LCB Performance

[Geoff Canyon]

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 <
use-livecode at lists.runrev.com> 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
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>