Quiz: String performance optimization


This code takes .03 seconds to run on my computer Try running it on yours.


 


ns=SECONDS()


x=””


FOR i = 1 TO 30000


      x=x+”OneTwoThree”


ENDFOR


?SECONDS()-ns


?LEN(x)


 


 


Modified slightly, it takes 15 seconds. That’s 500 times slower!


 


ns=SECONDS()


x=””


FOR i = 1 TO 30000


      x=”OneTwoThree”+x


ENDFOR


?SECONDS()-ns


?LEN(x)


 


I


Why the difference?


 

Comments (7)

  1. Steven says:

    I would guess that the first method could expose an optimisation that uses an efficient memory reallocation scheme, as C’s realloc or C++’s std::vector could, thus growing the string as it needs to, with only handful of memory allocations (assuming the allocated memory doubles in size when it needs to grow).

    In the second case, a temporary string object is probably created that has the appropriate size, this is then placed in x, with the original x being discarded. This would result in 30000 allocations and 30000 deallocations.

  2. tony says:

    darn somebody beat me to it!!

  3. Even if the second method is doing a realloc also (which it ought to be, if it’s smart enough to do it in the first case), the second method has to be O(n^2) because the original string has to be shifted to the right, which means copying n*len("OneTwoThree") chars of data n times.

    The first case can leave the existing data in place and stick the new data on the end.

  4. Travis Owens says:

    Great little micro optimization post, I would have never thought of this. I’ll have to try this out in C# and see if the results are similar.

  5. Frank Camp says:

    Hi Travis,

    Markus Egger and Rod Paddock wrote an article about the string performances in VFP and C#:

    http://www.eps-cs.com/VFPConversion/Article.aspx?quickid=030054

  6. Fabio Lunardon says:

    however the optimization

    should be removed when

    there is a passage for reference

    CLEAR

    x=REPLICATE(‘1’,100)

    X= x + CSTUFF(@x)

    ? x && ‘null’

    x=REPLICATE(‘1’,101)

    X= x + CSTUFF(@x)

    ? x && ‘4444’

    PROCEDURE cstuff(sss)

    SSS = ‘4444’

    RETURN NULL

  7. In this post: Quiz: String performance optimization , I showed some very similar code with drastically