LiveCode Forums.

Posted: **Mon Oct 06, 2014 12:19 am**

Recently I also worked with other IDEs (Kivy, QT, Xojo, XCode/Swift). They have all their pros and contras compared to LC and an evaluation/ranking would depend heavily on the testing projects complexity. And whether one takes the best result of each or kind of averaging over the platform versions (sticking to Mac only is clearly a disadvantage of Swift).

What I found, where LC is close to unbeatable, is the creation of strings, that are a repeat of a "pattern" (any "basestring").

For small numbers of pattern-repeats nearly every repeat method is OK. But for large N (say N > 1024) or on a slow machine (Raspi) or a long basestring or a lot of repeated calls of the function (say more than 1000 repeats, may add up to these on one day) there are drastic differences. We all know and have experienced that.

Also, a repeat with i=1 to N, or a N-times repeat for each, or something that is starting such a repeat internally (like to put comma into item N of an empty string), is certainly not able to keep up with the IDE's mentioned above.

But this works to put LC on the top, The "Doubling Method":
The input basestring is doubled with each repeat until it's length is greater than or equal to the length goal.

Included are two examples, you need a button, a fld "timing" and one new image (=img 1), not too small, say 600x400 px.

[Edit. Don't use the following "function version". LC does internally textconversion with this and LC 7 is very slow with this. Instead you could use (the same code) as "inline version", see post below. Sorry, I tested the "inline version" and thought it would increase readability to post this "function version"].

Code: Select all

-- THE DOUBLING METHOD --
private function repeatString str, N
  put str into s
  put length(str)*N into n0
  put trunc(log2(n0)) into M
  # --> if you KNOW that n0 is a power of 2 then omit the next check
  if 2^M < n0 then add 1 to M
  repeat M
    put s after s
  end repeat
  return char 1 to n0 of s
end repeatString

on mouseUp -- Example 1: "Image", filling with color, here a "pattern"
  put the millisecs into strt
  set cursor to watch
  put numToByte(0) into c0; put numToByte(255) into c1
  put   c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 & \
        c0 & c1 & c0 & c0 & c0 & c1 & c0 & c0 & \
        c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 into s0
  put the width of img 1 into w; put the height of img 1 into h
  -- we need 4*w*h bytes, here w*h/6, because length(s0)=24
  set imageData of image 1 to repeatString(s0, w*h div 6 )
  put the millisecs - strt && "millsecs for" && \
        (w*h) && "pixels of 32 bit each" into fld "timing"
  select text of fld "timing"
end mouseUp

on mouseUp -- Example 2  "Text": 2^10 x 2^11 lines of len 23 = 46 MByte
  put the millisecs into strt
  set cursor to watch
  put 2^10 into r --> repeats 2^10 times the test
   repeat r
    put "0, 1, 2, 3, 4, 5, 6, 7"& cr into s0
    put repeatString(s0,2^11) into nirwana --> 2^11 lines of s0
  end repeat
  put the millisecs - strt && "millsecs for" && \
        r*length(nirwana) / 2^20 && "MByte of TEXT" into fld "timing"
  select text of fld "timing"
end mouseUp

On a MacMini (2.5 GHz i5), with LC 6.6/6.7 I get [in brackets times with LC 7rc2]:
Ex 1 needs in average 55 [45] millisecs (600x400 image=240000 px = 960 KByte),
Ex 2 needs in average 520 [1560] millisecs (result has 46 MByte).

You may have a faster method for special cases, for example when repeating one single char. It would be fine if such methods could be posted here, together with the comparison results to the 'doubling method' above on your machine (use the above examples, please).

Posted: **Mon Oct 06, 2014 9:30 pm**

Hi Hermann,

try this instead of your mouseUp 1 (the one with the image, I used an image 600 px wide 400 px heigh as per your suggestion.)

Code: Select all

on mouseUp
   put the milliseconds into strt
   set cursor to watch
   put (the width of image 1) * 4 into tOneRow
   put the height of image 1 into tRows
   
   put numToByte (0) into c0
   put numToByte (255) into c1
   
   repeat tOneRow
      put c0 after s0
   end repeat
   
   put 24 into tStepSize
   repeat with i = 0 to (tOneRow - tStepSize) step tStepSize
      put c1 into byte i + 10 of s0
      put c1 into byte i + 14 of s0
   end repeat 
 
   repeat tRows
      put s0 after s1
   end repeat
   
   set the imageData of image 1 to s1
   put the millisecs - strt && "millsecs for" && \
         (the width of image 1*tRows) && "pixels of 32 bit each" into fld "timing"
   select text of fld "timing"
end mouseUp

Kind regards
Bernd

Posted: **Tue Oct 07, 2014 12:00 am**

Hi Bernd.

Wow, this is crazy fast, more than three times faster than the doubling method!

Well, you use the special structure of my simple example and optimize it 'manually'. If the pattern doesn't fit this perfect in a row you have to do with your method more math that needs time. Nevertheless I believe that it will remain clearly the faster one.

How would you create a row pattern (rotate current pattern)? And how a 45-degrees pattern?

Hermann

Posted: **Tue Oct 07, 2014 10:24 am**

Hi Hermann,

you can keep your generalized solution and make it faster by avoiding the doubling within a variable. When you double a data within a variable Livecode apparently has to make a copy of that data and merge it with itself and put it back into the variable, this needs a lot of memory allocation and freeing.

(disclaimer: I don't know anything of what is going on behind the scene, this is just what I have gathered from discussions about memory and variables and I might be incorrect)

Likewise if you do one byte operations they are very fast because it is just pointer arithmetic. No need to change memory etc.
Like this

Code: Select all

repeat with i = 0 to (tOneRow - tStepSize) step tStepSize
      put c1 into byte i + 10 of s0
      put c1 into byte i + 14 of s0
   end repeat

is very fast in spite of repeat with because it does not have to count e.g commas as in items.

The real trouble with repeat with i = 1 to the number of items is that this form allows you to change the original text. That is the reason why Livecode has to count the number of items with every iteration.
This is not the case for repeat for each item, you are not allowed to change the original text. And Livecode just goes from item to item without recounting every time.

To make your general solution about twice as fast use this for your private function

Code: Select all

private function repeatString str, N
   repeat N
      put str after s1
   end repeat
   return s1
end repeatString

One trick that helps in my code is to make the strings rather large, in my example I used the width of the image for the data to be duplicated. Then appending data only goes for for the "number of rows" = the height of the image.

Kind regards
Bernd

Posted: **Tue Oct 07, 2014 12:29 pm**

Hi Hermann,

could you try this version of the "repeatString" function?

all this mod / div stuff of course makes me dizzy and I would like to have your opinion on the correct working and the math.

This is the attempt to first construct a larger string and then append it.

Code: Select all

private function repeatString str, N
   put N div 5 into tNum -- 5 is just an arbitrary number
   put N div tNum into tNum2
   
   put N mod 5 into tMod
   
   repeat tNum
      put str after s1
   end repeat
   
   repeat tNum2
      put s1 after s2
   end repeat
   
   repeat tMod
      put str after s2
   end repeat
   
   return s2
end repeatString

Kind regards
Bernd

Posted: **Tue Oct 07, 2014 1:47 pm**

OK,

I did some further testing and this seems to be quite optimal with values between 20 and 40 for tFactor

Code: Select all

private function repeatString str, N
   put 40 into tFactor -- tFactor is just an arbitrary number seems to work well with 20 to 40
   if N > tFactor * 2 then
      
      put N div tFactor into tNum 
      put N div tNum into tNum2
      
      put N mod tFactor into tMod
            
      repeat tNum
         put str after s1
      end repeat
      
      repeat tNum2
         put s1 after s2
      end repeat
      
      repeat tMod
         put str after s2
      end repeat
      
   else
      repeat N
         put str after s2
      end repeat
   end if
   
   return s2
end repeatString

Kind regards
Bernd

Edit: added a check for small repeat numbers and only use the optimized routine if N > tFactor * 2, this avoids a problem with
N div tNum if tNum is 1.
Hermann, this needs your math attention. You know I only experiment.

Posted: **Tue Oct 07, 2014 6:48 pm**

Hermann,

here are the horizontal red stripes

Code: Select all

private function repeatString str, N
   put 40 into tFactor -- tFactor is just an arbitrary number seems to work well with 20 to 40
   if N > tFactor then
      
      put N div tFactor into tNum 
      put N div tNum into tNum2
      
      put N mod tFactor into tMod
      
      repeat tNum
         put str after s1
      end repeat
      
      repeat tNum2
         put s1 after s2
      end repeat
      
      repeat tMod
         put str after s2
      end repeat
      
   else
      repeat N
         put str after s2
      end repeat
   end if
   
   return s2
end repeatString



on mouseUp -- Example 1: "Image", filling with color, here a "pattern"
   put the millisecs into strt
   set cursor to watch
   put numToByte(0) into c0; put numToByte(255) into c1
   put   c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 & \
         c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 & \
         c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 into s0
   put the width of img 1 into w; put the height of img 1 into h
   -- we need 4*w*h bytes, here w*h/6, because length(s0)=24
   put repeatString (s0, w*h div 6 ) into tImg
   
   
   
   put w*4 into tRow
   put tRow * h into tAll
   put w*h into tAllPixel
   
   -- horizontal stripes
   -- get a row red
   put c0 & c1 & c0 & c0 into tRed
   put repeatString (tRed, w) into tRedRow
   
   repeat with i = 0 to h -1 step 4
      put i * tRow into tTarget
      put tRedRow into byte tTarget + 1 to tTarget + tRow of tImg
   end repeat
   
   
   --   -- -- random pixel
   --   repeat 30000
   --      put random (tAllPixel) into tPix
   --      put c1 into byte tPix*4 + (random (3) + 1) of tImg -- 
   --   end repeat
   
   
   set the imageData of image 1 to tImg
   -- set imageData of image 1 to repeatString(s0, w*h div 6 )
   put the millisecs - strt && "millsecs for" && \
         (w*h) && "pixels of 32 bit each" into fld "timing"
   select text of fld "timing"
end mouseUp

Tip: if you set the paintCompression to "RLE" you save again some milliseconds

I just made a checkbox button

Code: Select all

  if the hilite of me then
      set the paintcompression to "RLE"
   else
      set the paintcompression to "PNG"
   end if

Kind regards
Bernd

Posted: **Tue Oct 07, 2014 9:10 pm**

Found an error,
see comment in function repeatString,

had to subtract mod from N

here is corrected version, it includes a random pixel colorizer, which is currently blocked.

Code: Select all

private function repeatString str, N
   put 40 into tFactor -- tFactor is just an arbitrary number seems to work well with 20 to 40
   if N > tFactor then
      
      put N div tFactor into tNum 
      put N mod tFactor into tMod
      
      put (N - tMod) div tNum into tNum2 -- this is corrected version, had to subtract mod from N
    
      repeat tNum
         put str after s1
      end repeat
      
      repeat tNum2
         put s1 after s2
      end repeat
      
      repeat tMod
         put str after s2
      end repeat
      
   else
      repeat N
         put str after s2
      end repeat
   end if
   
   return s2
end repeatString



on mouseUp -- Example 1: "Image", filling with color, here a "pattern"
   put the millisecs into strt
   set cursor to watch
   put numToByte(0) into c0; put numToByte(255) into c1
   
   put c0 & c0 & c0 & c0 into s0 -- one pixel = 4 Bytes = 32 bits
   put the width of img 1 into w; put the height of img 1 into h
   put repeatString (s0, w*h  ) into tImg
   
   
   
   put w*4 into tRow
   put tRow * h into tAll
   put w*h into tAllPixel
      
   -- horizontal stripes
   -- get a row red
   put c0 & c1 & c0 & c0 into tRed
   put repeatString (tRed, w) into tRedRow
      
   put 6 into tStepSize
   
   repeat with i = 2 to (h  - tStepSize) step tStepSize
      put i * tRow into tTarget
      put tRedRow into byte tTarget + 1 to tTarget + tRow of tImg
      add tRow to tTarget
      put tRedRow into byte tTarget + 1 to tTarget + tRow of tImg
   end repeat
   
   
   -- -- random pixel
   --   repeat 30000
   --      put random (tAllPixel) into tPix
   --      put c1 into byte tPix*4 + (random (3) + 1) of tImg -- 
   --   end repeat
   
   
   set the imageData of image 1 to tImg
   put the millisecs - strt && "millsecs for" && \
         (w*h) && "pixels of 32 bit each" into fld "timing"
   select text of fld "timing"
end mouseUp


on mouseUp -- Example 2  "Text": 2^10 x 2^11 lines of len 23 = 46 MByte
   put the millisecs into strt
   set cursor to watch
   put 2^10 into r --> repeats 2^10 times the test
   repeat r
      put "0, 1, 2, 3, 4, 5, 6, 7"& cr into s0
      put repeatString(s0,2^11) into nirwana -->2^11 lines of s0
      -- put repeatString(s0,41) into nirwana
   end repeat
   put the millisecs - strt && "millsecs for" && \
         r*length(nirwana) / 2^20 && "MByte of TEXT" into fld "timing"
   select text of fld "timing"
end mouseUp

@Hermann, if you don't answer soon I will find my errors all by myself...

Kind regards
Bernd

Posted: **Wed Oct 08, 2014 12:46 pm**

Hi Bernd,

this is very interesting. Let us first concentrate on the general method, independent of pattern.

The doubling method is in theory optimal (in a math sense, that is, if the number of needed repeats and output size is large enough, there is no better method). The problem is to find the point where it switches. It's the same with sorting: Everybody uses QuickSort, which is NOT optimal, but the datasize where it switches to be inferior is in average not yet reached.
The switching point depends also strongly on memory handling of the software used (LC >= 6.6.3 has memory leaks, look in your system log).

Aspect 1 (Determine size of output/number of repeats)
You worked this already out for the 'appending constant length'-method (for short AM). It will also be a good way for the 'doubling method' (for short DM).

Aspect 2 (The data handling of LC)
[I needed two hours to find out this ...]
I tested again with other IDE's and found the big difference to my tests: You do the data handling within "mouseUp", I also in the test, but in my first post I used a function. This is and should be no problem for an usual image size (say up to 1 MByte). Sadly it is with LC:
By using a function your data looses it's "binary" state, LC does internally text-conversions. I tried to force it by using byte 1 to -1 of variable instead of variable. LC answered with additional conversions.

So there was only one remedy: Do the doubling method inside ONE handler.

This helps also to force "Text" to be handled as bytes.
Once again, LC7 slows down usual text handling *very* much. If one forces it to handle binary data you can improve that a little bit, but it remains to be about three times slower, just like with LC 6.5 on Raspi.

Now this is the "correct" script of AppendingMethod and DoublingMethod for the following examples

Image 528x256 and 128 repeats of image data creation, 1 times setting image Data.
Text pattern 32 byte length, 2^11 repeats of this pattern and 2^11 repeats of this data creation, 1 times putting text into a field.

[Obviously an upload of stacks here is not welcome any more, since one year, meanwhile admitted. So I will not use a little stack ]
You need:
1 Btn, 1 image 528x512, 1 fld "timing", 1 fld "OUT", 1 switch AM/DM, 1 switch IMG/TEXT
Compared to my first post I changed the examples to have now about the same size for "IMG" and "TEXT".

Code: Select all

on mouseUp
  put the milliseconds into strt
  set cursor to watch
  if the hilite of btn "DM" then -- Doubling Method
    if the hilite of btn "IMG" then -- Example 1: Image 528x512
      put 2^7 into r
      repeat r
        put empty into s0
        put numToByte(0) into c0; put numToByte(255) into c1        
        put   c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 & \
              c0 & c0 & c1 & c0 & c0 & c0 & c1 & c0 & \
              c0 & c0 & c1 & c0 & c0 & c0 & c1 & c0 & \
              c0 & c0 & c0 & c0 & c0 & c0 & c0 & c0 into s0
        put the width of img 1 into w  -- w=2^10
        put the height of img 1 into h -- h=2^8
        -- we need 4*w*h bytes
        put length(s0) into L; put 4*w*h into imL
        put trunc(log2(imL div L)) into M
        repeat M
          put s0 after s0
        end repeat
        -- in case the pattern doesn't fit truncate last input
        put byte 1 to (imL - L*2^M) of s0 after s0
      end repeat
      set imageData of image 1 to s0
      put the millisecs - strt && "millisecs for" && \
            (r*w*h) && "32bit-pixels (=" & trunc(100*r*imL / 2^20)/100 & " MByte)" into fld "timing"
    else -- Example 2: "Textstring", 2^10 lines of len 32
      put 2^11 into r
      repeat r
        put "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10"&cr into s0 -- 32 byte
        put length(s0) into L
        repeat trunc(log2(2^11)) -- repeating 2^11 times the pattern s0
          put s0 after s0
        end repeat
        -- in case the pattern doesn't fit truncate last input
        put byte 1 to L*(2^11) - length(s0) of s0 after s0 -- len(s0)=2^11*2^5
      end repeat
      put s0 into fld "OUT"
      put the millisecs - strt && "millisecs for" && \
            trunc(100*r*L*2^11/ 2^20)/100 && "MByte of TEXT" into fld "timing"
    end if
  else -- Appending Method: Example: Image 528x512 (Pattern as above)
    put 2^7 into r
    repeat r
      put (the width of image 1) * 4 into tOneRow
      put the height of image 1 into tRows
      put empty into s0; put empty into s1
      
      put numToByte (0) into c0
      put numToByte (255) into c1
      repeat tOneRow
        put c0 after s0
      end repeat
      
      put 32 into tStepSize
      repeat with i = 0 to (tOneRow - tStepSize) step tStepSize
        put c1 into byte i + 10 of s0
        put c1 into byte i + 14 of s0
        put c1 into byte i + 18 of s0
        put c1 into byte i + 22 of s0
      end repeat
      repeat tRows
        put s0 after s1
      end repeat
    end repeat
    set the imageData of image 1 to s1
    put the width of image 1 into tCols
    put the millisecs - strt && "millsecs for" && \
          (r*tCols*tRows) && "32bit-pixels (=" & \
          trunc(100*r*4*tCols*tRows / 2^20)/100 & " MByte)" into fld "timing"
  end if
  select text of fld "timing"
end mouseUp

Average Timing from MacMini and LC 6.6.3/6.7rc2/7.0rc2
AM (IMG): 58/45/190 ms for 132 MByte (= 128*4*528*512 bytes)
DM (IMG): 30/30/190 ms for 132 MByte (= 128*4*528*512 bytes)
DM (TXT): 45/45/110 ms for 132 MByte (= 2^11*2^5*2^11 bytes)

Do you also have this big slowdown by LC7 with imagedata?

I'll try now to built in your improvements and to apply this to rectangle patterns (especially one row 1xn and one col nx1). I'll come back.

Hermann

[Edit. Corrected image size to 528x512]

Posted: **Thu Oct 09, 2014 5:58 pm**

Hello Bernd,

I tested again with the appending method, especially with your "cutting-into-pieces" technique. It is for *small* imagedata faster.

Perhaps this could be kind of summary for (large) imagedata:
Build up the (usually small) pattern with a combination of direct 'pointer-arithmetic' and appending method as you showed us.
Then use (for large imagedata), inside ONE handler the doubling method.

I wonder if the 'outsourcing' of code into handlers and functions (and connected internal conversions of variables) is the reason for this many of slowdowns that LC 7 shows?

Hermann

Posted: **Sun Nov 09, 2014 12:38 am**

A slight variation on a handler from my book (3rd print):

Code: Select all

function repeatString s,l
  set the itemDel to s
  put s into item l of myString
  return myString
end repeatString

If I have understand the above conversation correctly (i.e. s contains only one byte), this is what you want.

Kind regards,

Mark

Posted: **Mon Nov 10, 2014 12:36 am**

Hi Mark,

I already saw this earlier in the useList-archives (by you and RG?).

This is rather clever but not as fast as doubling if we have to repeat often (for example 1920 x 1080 > 2* 10^6 pixels). Please do a timing with that, whether one byte or more (see below).
Actually we talked more generally about repeating (32Bit/4Byte) colors or rectangle schemes (patterns) of these. But special kind of these could indeed be done with this approach because [as a note for the next edition of your book],
starting with LC 7 you can use any string as itemdelimiter, not only single byte chars ...

Hermann

So, also from this actual reason, the script from Mark's post above could go into everybody's toolbox, it's fast enough for "daily use".

LiveCode Forums.

Fast method for repeating a fixed string

Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string

Re: Fast method for repeating a fixed string