OpenEuphoria

Re: Is this leaking?

• Posted by Robert Craig <rds at ATTCANADA.NET> Nov 28, 1999
• 443 views

Falkon writes:
> The following loop is giving me trouble and I can't understand it.
> r = {}
> for c = 1 to length( s ) do
>     r = r & n1 & n2
> end for
> n1 and n2 are integers.  With s being a length 1,017 sequence,
> it works just fine.  If s is a length 115,444 sequence, it locks up,
> as if it were in an infinite loop...

The loop takes time (roughly) proportional to
the *square* of length(s). I timed it for various lengths of s:

1000    .22
2000    .94
4000   4.39
8000  16.86
16000 75.85

So when you jumped from 1017 to 115,444, you should
expect the time to increase by a factor of 12885. On a P-150
you're probably looking at close to an hour.

> Either of the following, OTOH,  work just fine, even
> with the large image it's finished before I can blink,
> no lockups or windows errors.
>   r = {}
>   for c = 1 to length( s ) do
>      r2 = r2 & { n1, n2 }
>   end for
---------
>   r = {}
>   for c = 1 to length( s ) do
>      r2 = r2 & ( n1 & n2 )
>   end for

These run much faster because Euphoria will optimize
things when it can see that you are concatenating
onto the same variable. Euphoria doesn't recognize
the first form as being a case that it can optimize.

Why does the time go up as length(s) squared?
It's because in the unoptimized case Euphoria
will allocate a new block of memory for r2 each time,
and then copy r2 plus n1 (or n2) into it. r2 keeps
growing in size, so the time goes up in proportion to
length(s) * (average length(r2)) or length(s) * (length(s)) / 2

In the optimized case, Euphoria will allocate more than
enough space for r2, and will then simply insert n1 or n2
many times before having to allocate a bigger space
and copy r2.

Conclusion: maybe the optimizer should be a bit smarter.

> My best guess is that maybe it's not releasing the memory
> used by the temporary sequences formed by the
> concatenation until after it exits the loop,

I don't think you are running out of space.
Euphoria recycles the space as it goes, inside the loop.
It doesn't wait until after the loop to do it. You will however
have a copy of r2 stored in an internal temporary variable.

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