1. Is this leaking?
- Posted by Falkon 1313 <Falkon1313 at AOL.COM>
Nov 28, 1999
-
Last edited Nov 29, 1999
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, though it obviously isn't. (It might eventually do
something, but I waited about 10 minutes, and it's never taken more than a
few minutes to get an 'out of memory' error from infinite recursion.) In
Windows98, I can kill it with Ctrl+Break, but before long I get fatal errors
and 'System Dangerously Low on Resources', so it's using up a lot of RAM and
not releasing it when broken out of. In DOS I have to reboot. I have 64MB
of RAM.
Counting sequence overhead, the final version of r should only be
(230,888 * 4 + 24) = 923,576 bytes. At most, while processing the last byte,
the expression would only be: 923,568 = 923,568 & 4 & 4 for 1,847,144 bytes,
and I'd think it'd be more like 923,568 = 8 & 4 & 4 = for 923,584bytes.
Unless I'm counting wrong. Either way, that shouldn't cause a lockup. Even
if I didn't have enough RAM, it should give an Out of Memory error instead of
appearing to go into an infinite loop.
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, and somehow that's causing an 'under-the-hood' infinite loop.
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
---------
All three forms are logically equivalent if not procedurally the same.
So what's the difference? The temporary memory used by literal sequences,
atom & atom concatenations, or sequence & sequence concatenations is released
or reused for each iteration, while that used by sequence & atom
concatenation isn't? Why no out-of-memory crash?
2. Re: Is this leaking?
- Posted by Robert Craig <rds at ATTCANADA.NET>
Nov 28, 1999
-
Last edited Nov 29, 1999
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
3. Re: Is this leaking?
- Posted by Kat <KSMiTH at PELL.NET>
Nov 28, 1999
-
Last edited Nov 29, 1999
----- Original Message -----
From: Robert Craig <rds at ATTCANADA.NET>
To: <EUPHORIA at LISTSERV.MUOHIO.EDU>
Sent: Sunday, November 28, 1999 10:38 PM
Subject: Re: Is this leaking?
> Conclusion: maybe the optimizer should be a bit smarter.
Like not optimizing inside a loop until forced to?
> > 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.
Maybe this is a good example of the programmer knowing there are enough
resources available,, or testing to be sure while running, and inhibiting a
garbage collection until done with this loop? Like, inside the loop: if
$availmem < SomeVal ) { DoGarbageCollection }?
Kat,
curious as.
4. Re: Is this leaking?
- Posted by Falkon 1313 <Falkon1313 at AOL.COM>
Nov 29, 1999
-
Last edited Nov 30, 1999
From: Robert Craig
>The loop takes time (roughly) proportional to
>the *square* of length(s). I timed it for various lengths of s:
[...]
>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.
That makes sense. I should have known to try timing it, but I didn't
even think about it. Ordinarily, as in the optimized case, Euphoria's so
fast that the time would be insignificant for what I'm doing. That really
does show off the optimizations...from an hour down to a second. Thanks for
the quick reply.
5. Re: Is this leaking?
Falkon wrote:
> That really does show off the optimizations...from an hour down to a
> second.
It also shows, that most of the time we are still kept, just like the
proverbial mushrooms, in the dark. The lack of optimization info is,
as far as I am concerned, one of the most irritating aspects of
programming in Euphoria. Quite often I spend more time timing
countless alternatives of critical routines than doing something
really useful.
What I need, what we all need, I suspect, is a short document from Rob
outlining which routines / alternatives are already optimized, and
even more importantly, which ones are still in the 'to do soon'
basket.
I must also add I very much appreciate Rob's improved responsiveness
over the last few weeks. Thanks, Rob. jiri
6. Re: Is this leaking?
- Posted by Robert Craig <rds at ATTCANADA.NET>
Nov 30, 1999
-
Last edited Dec 01, 1999
Jiri Babor writes:
> What I need, what we all need, I suspect, is a
> short document from Rob outlining which
> routines / alternatives are already optimized, and
> even more importantly, which ones are still in the
> 'to do soon' basket.
euphoria\doc\perform.doc (or perform.htm)
already has a discussion like this. It unfortunately
does not mention the recent issue of concatenation
within a loop. I'll add something about concatenation
to perform.doc, as well as anything else that I can think of.
I intend to keep optimizing things, but I can't say exactly
what will come first. There are lots of optimizations in the
"almost worth it" category.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
7. Re: Is this leaking?
Rob Craig wrote:
> euphoria\doc\perform.doc (or perform.htm) already has a discussion
> like this. It unfortunately does not mention the recent issue of
> concatenation within a loop. I'll add something about concatenation
> to perform.doc, as well as anything else that I can think of.
perform.doc is a very useful document. In fact it should be a
compulsory read for anybody serious about Euphoria. Unfortunately it
has one or two glaring omissions, and it is also slightly misleading,
I feel, at the point where it deals with the 'short circuit'
evaluation. It fails to mention this evaluation is currently
unoptimized (see Rob's recent note) and it can be considerably slower
than 'chained' equivalents.
I realize, this sort of thing does not make any perceptible
difference in a vast majority of cases, but it can be a very
frustrating, wasteful experience, if you are trying to push the
envelope.
jiri
