OpenEuphoria

Re: EUPHORIA BUG!!!! & Test

• Posted by Robert Craig <rds at RapidEuphoria.com> Jun 24, 2002
• 362 views

Jordah Ferguson writes:
> I still have no clue as to the cause of this bug and if it is being
> dealt with. As far as i know this is a very very Nusty Bug. That is
> causing delays in many people's code.
>
> x = x & x1 & x2 -- is not at all optimized(very very slow)  compared to
>
> x &= x1 & x2

In your example it appears that you are looping 100,000 times,
while creating a sequence that grows from 1 to 200,000 in size.

Keep in mind that the time to perform a string concatenation,
c = a & b
will normally be proportional to the sum of the lengths of a and b,
since what will typically happen is that space will be allocated equal
to length(a) + length(b), and then all the elements of a plus all the
elements of b will be copied into the new space, c. Only the top-level
elements are actually copied, e.g. only a 4-byte pointer is copied for
a string or other sequence.

That means if you perform a concatenation inside a loop, n times,
growing a large sequence, the time to perform that loop will grow
in proportion to n-squared. for example, looping 100,000 times 
should take 100x (not 10x) longer, than looping only 10,000 times.

You should not be asking why the first form is so slow.
You should be asking why the second form is so incredibly fast.  

Seriously, there are some additional cases of concatenation that can be
optimized. For example:
          a = b & c & d
can be made faster by copying b and c and d into a new space for a,
rather than, as happens now, b and c are copied into a temp, and
then the temp and d are copied into a space for a. This means that
the data for b and c are copied *twice*. This will only give you
modest speed-up however. The real speed-ups come when Euphoria
reserves some extra space at the end of a large sequence, 
and inserts the second sequence, rather than making a whole 
new sequence by copying.
e.g.
    s = s & t
where t is much smaller than s, will simply insert t at the end of
s, provided there is enough space, and provided s only has 
one reference count.

Anyway, I'll look into optimizing concatenation some more.

Thanks,
   Rob Craig
   Rapid Deployment Software
   http://www.RapidEuphoria.com