out of memory

classic Classic list List threaded Threaded
33 messages Options
12
Reply | Threaded
Open this post in threaded view
|

out of memory

Julien Cugniere
Hi,

I've tried the new lua 5 alpha, and the example life.lua dies with the error
"out of memory" (runs fine on 4.0). I could isolate the problem to the following
peace of code:

   s=""
   for i=1,100000 do
     s=s.."x"
   end

This brings the "out of memory" error on my system (256 Mo RAM, 256 Mo virtual
memory). The error seems to be in the virtual machine, as can be seen by
compiling the script on one version of lua and running on the other.

Sorry if this is a known bug... :)

Apart from that I like the new lua a lot; great work!

Julien Cugniere



Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Roberto Ierusalimschy
>   s=""
>   for i=1,100000 do
>     s=s.."x"
>   end

Are you sure this is from "life.lua"? I didn't find it there...

Anyway, that code can really gives an "out of memory" error. This is not
a bug, but a limitation of the way Lua manipulates strings. (Java has
similar problems.)

Everytime you do `s = s.."x"' you create a new string. So, when s has
size 50,000, after that statement you have two strings, the original one
with 50,000 elements and a new one with 50,001 elements. After another
loop you have three strings, and so on. Even if you do not run out of
memory, you will use huge amounts of memory and of CPU time.

See http://lua-users.org/wiki/OptimizedStrRep for a long discution about
how to do this "loop" efficiently (if you really need it).

See also http://www.bagley.org/~doug/shootout/bench/strcat/ for a
discussion about String Concatenation in several languages (and another
example on how to do it efficiently in Lua).

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Julien Cugniere


Roberto Ierusalimschy wrote:
 s=""
 for i=1,100000 do
   s=s.."x"
 end


Are you sure this is from "life.lua"? I didn't find it there...
The code I gave isn't; this is a simplification of life.lua's "draw" method:

  for y=1,self.h do
   for x=1,self.w do
      out=out..(((self[y][x]>0) and ALIVE) or DEAD)
    end
    out=out.."\n"
  end


Anyway, that code can really gives an "out of memory" error. This is not
a bug, but a limitation of the way Lua manipulates strings. (Java has
similar problems.)
I knew of this limitation (thanks to the wiki actually).

What makes me believe this is a bug is that with lua 5, life.lua dies after about 120 iterations, while it runs fine with lua 4. Similarly, the bit of code I gave runs fine (even though it takes time) with lua 4, but dies quickly with lua 5. Moreover, I can understand that concatenating strings this way is costly, but the corbage collector should reclaim unused memory... instead of that, memory usage grows, and once my 256 Mo of RAM are used the hard drive starts to trash and then the program dies...

Anyway, thanks for the reply and the info you gave.

Julien Cugniere


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Luiz Henrique de Figueiredo
In reply to this post by Julien Cugniere
>What makes me believe this is a bug is that with lua 5, life.lua dies after 
>about 120 iterations, while it runs fine with lua 4.

In my Linux box with 128Mb of RAM it runs to completion (2000 iterations).
Does it give you any kind of message when it dies?
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Edgar Toernig
Luiz Henrique de Figueiredo wrote:
> 
> >What makes me believe this is a bug is that with lua 5, life.lua dies after
> >about 120 iterations, while it runs fine with lua 4.
> 
> In my Linux box with 128Mb of RAM it runs to completion (2000 iterations).
> Does it give you any kind of message when it dies?

Something's fishy!  I got the problem too (x86-linux libc5).

lua5 -e 's="" for i=1,10000 do s=s.."x" end'

grows to >40MB (100000 is too much for my system) with only 200kb in
actual use (reported by mallinfo).  It seems, the heap is totally
fragmented with realloc unable to reuse anything at all (but nblocks
seems to be right!).

That does _not_ happen with 4.0 (heap grows to 143k with 52k used).

A malloc/free trace looks pretty similar on both version though...

Ciao, ET.

PS: Maybe Lua5 damages some libc datastructures?!? (wild guess)

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Edgar Toernig
Edgar Toernig wrote:
> 
> Something's fishy!  I got the problem too (x86-linux libc5).
> 
> lua5 -e 's="" for i=1,10000 do s=s.."x" end'
> 
> grows to >40MB (100000 is too much for my system) with only 200kb in
> actual use (reported by mallinfo).  It seems, the heap is totally
> fragmented with realloc unable to reuse anything at all (but nblocks
> seems to be right!).

I found the problem.  At least here it's a bug in realloc(x,0).  It's
not an alias for free(x).  It truncates x to a fixed small size (and
even returns that address).  Of course, that will prohibit any defrag-
mentation.  Replacing the freeing l_realloc in lmem.c by a free(block)
cures the problem.

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Julien Cugniere


Edgar Toernig wrote:
I found the problem.  At least here it's a bug in realloc(x,0).  It's
not an alias for free(x).  It truncates x to a fixed small size (and
even returns that address).  Of course, that will prohibit any defrag-
mentation.  Replacing the freeing l_realloc in lmem.c by a free(block)
cures the problem.

I confirm that this solves the problem for me too, both on djgpp (gcc 2.95.2) and mingw32 (gcc 3.2). Thanks a lot!


Julien Cugniere


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Björn De Meyer
Julien Cugniere wrote:
> 
> Edgar Toernig wrote:
> > I found the problem.  At least here it's a bug in realloc(x,0).  It's
> > not an alias for free(x).  It truncates x to a fixed small size (and
> > even returns that address).  Of course, that will prohibit any defrag-
> > mentation.  Replacing the freeing l_realloc in lmem.c by a free(block)
> > cures the problem.
> 
> I confirm that this solves the problem for me too, both on djgpp (gcc 2.95.2)
> and mingw32 (gcc 3.2). Thanks a lot!
> 
> Julien Cugniere

On my linux 2.2.10 system, with a libc.so.6 from 1999, the 
example Edgar Toernig gave worked fine. Apparently, this is 
an issue of realloc(x,0) not working in the same way under 
different C library implementations. 

I do not know what the ANSI C standard says about using 
realloc(x,0). Is it allowed according to the standard to 
use realloc to free memory? Or is it something undefined 
or non-canonical? I would have thought that the latter is 
the case...

-- 
"No one knows true heroes, for they speak not of their greatness." -- 
Daniel Remar.
Björn De Meyer 
[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Enrico Colombini
In reply to this post by Roberto Ierusalimschy
At 17.13 04/10/02 -0300, Roberto Ierusalimschy <[hidden email]> wrote:
>Anyway, that code can really gives an "out of memory" error. This is not
>a bug, but a limitation of the way Lua manipulates strings. (Java has
>similar problems.)

I'd like to use Lua for text adventures, but I soon found out that fast
string manipulation (especially repeated concatenation) is not the
language's stronger point.
Also, I haven't found out a practical way to write long strings (~5 kchars)
in a script, so that they could be properly read and edited by people using
an 80-char/line editor. Using a .. line concatenation to write a long
string as multiple source lines raises the above problem.

By the way, why is Basic so efficient in string handling and concatenation?
I don't remember encountering problems even when creating very large
strings char-by-char. It uses reference counting, if I remember correctly.
Maybe a moderate amount of over-allocation for strings could at least make
most concatenations a lot more efficient. It could be proportional to the
current string's length, ranging from 0 extra chars (for 1..3 chars
strings) to a fixed (customizable) limit, say 1 kB, for larger strings.

>Everytime you do `s = s.."x"' you create a new string. So, when s has
>size 50,000, after that statement you have two strings, the original one
>with 50,000 elements and a new one with 50,001 elements. After another
>loop you have three strings, and so on. Even if you do not run out of
>memory, you will use huge amounts of memory and of CPU time.

Why out of memory? Shouldn't the garbage collector get rid of the old strings?
And (asking out of ignorance) couldn't reference counting be useful for
strings, e.g. for getting rid of temporary strings like those created in
the above loop? After all, strings do not contain references to other
objects, so there is no risk of cross-referencing.

  Enrico


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Björn De Meyer
Enrico Colombini wrote:
> 
/snip
> Also, I haven't found out a practical way to write long strings (~5 kchars)
> in a script, so that they could be properly read and edited by people using
> an 80-char/line editor. Using a .. line concatenation to write a long
> string as multiple source lines raises the above problem.

What's wrong with a long string between [[ ]] ?
You could say then:

room["lua list"].describe = [[
Many lua programmers are in this room, typing away at their keyboards. 
On the wall hang posters made of printed-out ASCII art. 
Etc, etc, etc... ]]

As for the answer to your other question, it turned out to be a problem
with the C library on some systems. Please read Edgar Toernig's mails.

-- 
"No one knows true heroes, for they speak not of their greatness." -- 
Daniel Remar.
Björn De Meyer 
[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Edgar Toernig
In reply to this post by Björn De Meyer
> I do not know what the ANSI C standard says about using
> realloc(x,0).

ANSI C99 about memory management functions in general:

       If the size of the space requested  is
       zero,  the behavior is implementation-defined: either a null
       pointer is returned, or the behavior is as if the size  were
       some  nonzero  value, except that the returned pointer shall
       not be used to access an object.

and about realloc itself [the part where free is mentioned]:

       If the realloc function returns a  null  pointer
       when  size is zero and ptr is not a null pointer, the object
       it pointed to has been freed.

So it seems one cannot depend on realloc(x,0) to free x and my
libc is not buggy (puh *g*).  Perfectly legal behaviour: truncate
to some small size and return a valid and unique pointer.

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Luiz Henrique de Figueiredo
In reply to this post by Luiz Henrique de Figueiredo
>Apparently, this is 
>an issue of realloc(x,0) not working in the same way under 
>different C library implementations. 

I'm very surprised that this is a problem in modern Linuxes. It works fine in
my old Red Hat 5.2. The only system I know that had a problem with realloc(x,0)
was good old Sun OS (not Solaris). (Actually, I think the problem was free(NULL)

>I do not know what the ANSI C standard says about using 
>realloc(x,0). Is it allowed according to the standard to 
>use realloc to free memory? Or is it something undefined 
>or non-canonical?

ANSI C says that realloc(x,0) is the same as free(x) if x!=NULL. The only
murky case occurs with realloc(NULL,0), which is free(NULL), but could be
(wrongly) interpreted as malloc(0)...

Here is what my the page in my RH5.2 says:

       realloc()  changes the size of the memory block pointed to
       by ptr to size bytes.  The contents will be  unchanged  to
       the minimum of the old and new sizes; newly allocated mem-
       ory will be uninitialized.  If ptr is NULL,  the  call  is
       equivalent  to malloc(size); if size is equal to zero, the
       call is equivalent to free(ptr).  Unless ptr is  NULL,  it
       must  have  been  returned by an earlier call to malloc(),
       calloc() or realloc().

--lhf

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Edgar Toernig
> Here is what the man page in my RH5.2 says:
> 
>  [realloc(x,0) == free(x)]

That's what my man page says too.  But on Linux the man pages
regarding libc are 2nd class citizens.  They are collected
from various places (posix, ansi, *bsd, ...) and sometime do
not reflect actual behaviour.

The libc info pages are the real documentation and there's
nothing about realloc(x,0) freeing objects (it even warns
that realloc(0,s) does not work on all systems).

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Enrico Colombini
In reply to this post by Björn De Meyer
At 13.30 05/10/02 +0200, Björn De Meyer wrote:
>What's wrong with a long string between [[ ]] ?

Suppose I want to write:

function Flame()
  if some_condition then
    say[[
      you are in a vast room whose other end is lost
      in the distance;\n the room is crammed full of 
      Lua programmers hotly debating a minor issue.\n
      Most on them have small dragons on long leashes, 
      whose fiery breath is scorching all that seem to
      disagree with their master.
      ...and so on and so on for an awful lot of lines...
    ]]
    other_code_here
  end
end

I see two problems here:
- first, newlines are inserted in the string. I can't tell them
  from those I inserted as '\n'.
- second, if I indent my text for better reading, spaces are 
  added at the beginning of each line.

I could either use kilometric lines (most editors don't like them, and
readability goes down the drain), or concentenate the lines with '..'
(which would be acceptable if the parser could read them as a single string).

>As for the answer to your other question, it turned out to be a problem
>with the C library on some systems. Please read Edgar Toernig's mails.

Didn't he refer to Lua 5.0? I am still planning to use 4.0, and I already
encountered the slow concatenation problem in another application (saving a
large and complex table to a string took minutes).

  Enrico


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

John Belmonte-2
Enrico Colombini wrote:
function Flame()
  if some_condition then
    say[[
      you are in a vast room whose other end is lost
in the distance;\n the room is crammed full of Lua programmers hotly debating a minor issue.\n Most on them have small dragons on long leashes, whose fiery breath is scorching all that seem to
      disagree with their master.
      ...and so on and so on for an awful lot of lines...
    ]]
    other_code_here
  end
end

I see two problems here:
- first, newlines are inserted in the string. I can't tell them
  from those I inserted as '\n'.
- second, if I indent my text for better reading, spaces are added at the beginning of each line.

I could either use kilometric lines (most editors don't like them, and
readability goes down the drain), or concentenate the lines with '..'
(which would be acceptable if the parser could read them as a single string).

Your other option is to use some type of markup and do post processing on the strings. A simple implementation might treat a blank line as a paragraph break, otherwise converting any run of newlines and spaces into a single space. However, implementing something slightly more complex like a few HTML tags might provide advantages, such as the ability to specify bold/italic.

-John



--
http:// i      .   /


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Björn De Meyer
In reply to this post by Edgar Toernig
Edgar Toernig wrote:
> 
> That's what my man page says too.  But on Linux the man pages
> regarding libc are 2nd class citizens.  They are collected
> from various places (posix, ansi, *bsd, ...) and sometime do
> not reflect actual behaviour.
> 
> The libc info pages are the real documentation and there's
> nothing about realloc(x,0) freeing objects (it even warns
> that realloc(0,s) does not work on all systems).
> 
> Ciao, ET.

So, the conclusion is that the Linux manpages for realloc() 
are faulty. The ANSI C standard which Edgar quoted is clear 
enough. Using realloc(x,0) causes undefined behaviour. 
Therefore, IMO, it should be avoided and replaced free(),
so LUA stays on the safe side of ANSI C. It's a harsh standard, 
but still, the standard.


-- 
"No one knows true heroes, for they speak not of their greatness." -- 
Daniel Remar.
Björn De Meyer 
[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Björn De Meyer
In reply to this post by Enrico Colombini
Enrico Colombini wrote:
/snip
> I see two problems here:
> - first, newlines are inserted in the string. I can't tell them
>   from those I inserted as '\n'.
> - second, if I indent my text for better reading, spaces are
>   added at the beginning of each line.
> 
/snip

To solve these problems you can:
- use <br> in stead of \n. Postprocess with gsub.
- trim away the excess spaces. Gsun is again useful there. 

This is how you can do it in Lua itself:

aid = gsub(description, "%s+", " ")
description = gsub(aid, "<br>", "\n"))

It may be more performant to do this kind of postprocessing
in C. If you really wat top n,otch performance, you could customise the 
Lua parser so multiple spaces are seen as a single one when parsing a 
long string. 

> Didn't he refer to Lua 5.0? I am still planning to use 4.0, and I already
> encountered the slow concatenation problem in another application (saving a
> large and complex table to a string took minutes).

Yes, sorry, I misunderstood. However, string concatenation
is slow in many scripting languages. I doubt VB is that much faster 
than Lua in this aspect. This is a performance problem that may 
need some extra attention, but has no easy solution. 


-- 
"No one knows true heroes, for they speak not of their greatness." -- 
Daniel Remar.
Björn De Meyer 
[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Enrico Colombini
In reply to this post by John Belmonte-2
At 14.56 05/10/02 -0500, John Belmonte wrote:
>Your other option is to use some type of markup and do post processing 
>on the strings. 

Yes, of course, but that's just a way to program around the 'long constant
string' issue :-)
The same problem arises when defining strings that must be aligned in some
way. For example, while programming in C for a 16x2 LCD display, I can
format my code just as the user will see it [better read with a monospaced
font]:

 char errmsg[] = "Unknown error   "
                 "don't do that!  ";

That's very useful for catching mis-alignments in the source code.

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Enrico Colombini
In reply to this post by Björn De Meyer
At 23.45 05/10/02 +0200, Björn De Meyer wrote:
>- use <br> in stead of \n. Postprocess with gsub.

Avoiding post-processing in long constant strings was the whole point.

>However, string concatenation
>is slow in many scripting languages. I doubt VB is that much faster 
>than Lua in this aspect. This is a performance problem that may 
>need some extra attention, but has no easy solution. 

I don't know about VB; I'll run some tests with QBasic or VBD and see what
comes out.

What's wrong with my suggestion to use extra allocation and reference
counting for strings? (I am not a language designer, so please don't hit me
too hard if the answer is obvious).

  Enrico


Reply | Threaded
Open this post in threaded view
|

Re: out of memory

Enrico Colombini
>I'll run some tests with QBasic or VBD and see what comes out.

Here are the results. I had to use a 16-bit DOS Basic (Microsoft's VBD) as
I don't have a 32-bit Basic installed, so the results are probably skewed
(I don't know in what direction, but 16-bit computations are *probably*
faster - I don't know modern CPUs well enough to tell; on the other hand,
the Basic program ran in a limited memory space).
I was also forced to limit the string size to about 30 kB (could somebody
re-run the test using VB?).

Lua program:

 s = ""
 for i = 1,30000 do
   s = s .. "x"
 end

Basic program:

 s$ = ""
 FOR i = 1 TO 30000
   s$ = s$ + "x"
 NEXT


Running times on my Pentium II/350, in seconds:

 Lua (standalone interpreter): 7.75
 VBD (interpreted):            4.94
 VBD (compiled):               0.17

The first two results are more or less equivalent (it could boil down to
the 32-bit vs. 16-bit difference), but the third one sounds interesting.
Maybe there could be space for string concatenation optimization, after all.

  Enrico


12