unacceptable memory consumption

[p5pRT]

Migrated from rt.perl.org#48004 (status was 'resolved')

Searchable as RT48004$

[p5pRT]

From @salva

Created by @salva

The script below has two versions of the same algorithm\, one using "for" and the other "map". The "map" version uses an unacceptable amount of memory.

--------------------------

#!/usr/bin/perl

$| = 1;

my $max = 50000; my @​l = ('a'..'z'); my @​keys;

if (1) {   # this version uses ~ 300MB   @​keys = map { join ''\, map $l[rand @​l]\, 0..71 } 0..$max;

} else {   # this version uses ~ 9MB   for (0..$max) {   push @​keys\, join ''\, map $l[rand @​l]\, 0..71;   }

}

print "sleeping...\n"; sleep 100;

---------------------------

Perl Info

``` Flags: category=core severity=medium Site configuration information for perl v5.8.8: Configured by Debian Project at Mon Nov 12 06:19:22 UTC 2007. Summary of my perl5 (revision 5 version 8 subversion 8) configuration: Platform: osname=linux, osvers=2.6.22.10, archname=i486-linux-gnu-thread-multi uname='linux ninsei 2.6.22.10 #1 smp preempt thu oct 25 08:49:01 pdt 2007 i686 gnulinux ' config_args='-Dusethreads -Duselargefiles -Dccflags=-DDEBIAN -Dcccdlflags=-fPIC -Darchname=i486-linux-gnu -Dprefix=/usr -Dprivlib=/usr/share/perl/5.8 -Darchlib=/usr/lib/perl/5.8 -Dvendorprefix=/usr -Dvendorlib=/usr/share/perl5 -Dvendorarch=/usr/lib/perl5 -Dsiteprefix=/usr/local -Dsitelib=/usr/local/share/perl/5.8.8 -Dsitearch=/usr/local/lib/perl/5.8.8 -Dman1dir=/usr/share/man/man1 -Dman3dir=/usr/share/man/man3 -Dsiteman1dir=/usr/local/man/man1 -Dsiteman3dir=/usr/local/man/man3 -Dman1ext=1 -Dman3ext=3perl -Dpager=/usr/bin/sensible-pager -Uafs -Ud_csh -Ud_ualarm -Uusesfio -Uusenm -Duseshrplib -Dlibperl=libperl.so.5.8.8 -Dd_dosuid -des' hint=recommended, useposix=true, d_sigaction=define usethreads=define use5005threads=undef useithreads=define usemultiplicity=define useperlio=define d_sfio=undef uselargefiles=define usesocks=undef use64bitint=undef use64bitall=undef uselongdouble=undef usemymalloc=n, bincompat5005=undef Compiler: cc='cc', ccflags ='-D_REENTRANT -D_GNU_SOURCE -DTHREADS_HAVE_PIDS -DDEBIAN -fno-strict-aliasing -pipe -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64', optimize='-O2', cppflags='-D_REENTRANT -D_GNU_SOURCE -DTHREADS_HAVE_PIDS -DDEBIAN -fno-strict-aliasing -pipe -I/usr/local/include' ccversion='', gccversion='4.2.3 20071014 (prerelease) (Debian 4.2.2-3)', gccosandvers='' intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234 d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12 ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8 alignbytes=4, prototype=define Linker and Libraries: ld='cc', ldflags =' -L/usr/local/lib' libpth=/usr/local/lib /lib /usr/lib libs=-lgdbm -lgdbm_compat -ldb -ldl -lm -lpthread -lc -lcrypt perllibs=-ldl -lm -lpthread -lc -lcrypt libc=/lib/libc-2.6.1.so, so=so, useshrplib=true, libperl=libperl.so.5.8.8 gnulibc_version='2.6.1' Dynamic Linking: dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E' cccdlflags='-fPIC', lddlflags='-shared -L/usr/local/lib' Locally applied patches: @INC for perl v5.8.8: /etc/perl /usr/local/lib/perl/5.8.8 /usr/local/share/perl/5.8.8 /usr/lib/perl5 /usr/share/perl5 /usr/lib/perl/5.8 /usr/share/perl/5.8 /usr/local/lib/site_perl . Environment for perl v5.8.8: HOME=/home/salva LANG=C LANGUAGE (unset) LD_LIBRARY_PATH (unset) LOGDIR (unset) PATH=/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/games PERL_BADLANG (unset) SHELL=/bin/bash ____________________________________________________________________________________ Be a better sports nut! Let your teams follow you with Yahoo Mobile. Try it now. http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ ```

[p5pRT]

From @druud62

Salvador Fandiño schreef​:

The script below has two versions of the same algorithm\, one using "for" and the other "map". The "map" version uses an unacceptable amount of memory.

--------------------------

#!/usr/bin/perl

$| = 1;

my $max = 50000; my @​l = ('a'..'z'); my @​keys;

if (1) { # this version uses ~ 300MB @​keys = map { join ''\, map $l[rand @​l]\, 0..71 } 0..$max;

} else { # this version uses ~ 9MB for (0..$max) { push @​keys\, join ''\, map $l[rand @​l]\, 0..71; }

}

Why is the memory consumption of the map-map version more "unacceptable" than that of the map-for version?

There is a scale difference between the two of 50000\, so shouldn't the 9 MB actually use no more than 300 MB / 50000 is less than 1 kB? ;)

The map-for version can also be written like this​:

  push @​keys\, join(''\, map $l[rand @​l]\, 0..71) for 0..$max;

I brought it back to 4 MB (RSS)\, but I am not sure it is equivalent​:

sub lazymap (&@​) {   my $_code = shift;   my @​_return;   push @​_return\, sub {$_code->($_)}->($_) for @​_;   return @​_return; }

  # this version uses ~ 4 MB (RSS)   @​keys = lazymap { join ''\, lazymap {$l[rand @​l]} 0..71 } 0..$max;

-- Affijn\, Ruud

"Gewoon is een tijger."

[p5pRT]

The RT System itself - Status changed from 'new' to 'open'

[p5pRT]

From @schwern

Salvador Fandiño (via RT) wrote​:

# this version uses ~ 300MB @​keys = map { join ''\, map $l[rand @​l]\, 0..71 } 0..$max;

My first thought was that for (1..$x) is optimized to iterate rather than create the intermediate array\, but that doesn't account for 300 megs.

There are other inefficiencies in the map approach\, like that it has to build the entire array in the map and then copy it to @​keys. But that should account for\, at most\, another 9 megs.

If you half 71 down to 35 the memory usage halves. That should not be. It suggests that something isn't getting deallocated.

It's also telling that replacing the inner map with a static string reduces memory consumption to what you'd expect\, 18 megs. Same if you replace the inner map with a for loop.

Here is the most damning evidence that the result of the inner map is leaking.

  @​keys = map {   my @​inner = map $l[rand @​l]\, 0..71;   join ''\, @​inner;   } 0..$max;

That takes 18 megs\, as expected.

-- 'All anyone gets in a mirror is themselves\,' she said. 'But what you gets in a good gumbo is everything.'   -- "Witches Abroad" by Terry Prachett

[p5pRT]

From @lizmat

At 5​:50 AM -0800 12/1/07\, Salvador Fandiˆ±o (via RT) wrote​:

--------------------------

#!/usr/bin/perl

$| = 1;

my $max = 50000; my @​l = ('a'..'z'); my @​keys;

if (1) { # this version uses ~ 300MB @​keys = map { join ''\, map $l[rand @​l]\, 0..71 } 0..$max;

} else { # this version uses ~ 9MB for (0..$max) { push @​keys\, join ''\, map $l[rand @​l]\, 0..71; }

}

print "sleeping...\n"; sleep 100;

---------------------------

What I find most disturbing about this\, is that nesting is related to execution time\, not compile time.

================================================================= my $max = 50000; my @​l = ('a'..'z'); my @​keys;

sub foo { join ''\, map { $l[rand @​l] } 0..71 }

# this version uses ~ 300MB @​keys = map { foo() } 0..$max;

exhibits the same memory "leaking" behaviour. Which means any subroutines called inside the context of a map {} can potentially leak *badly*. So *if* you call subroutines inside a map {}\, you'd better make sure no other map {}'s are being executed inside it.

Oddly enough\, a slight change in the foo() sub​:

============================================================ sub foo { my $foo = join ''\, map { $l[rand @​l] } 0..71; $foo }

and the problem is not as nearly as bad\, just memory usage for the copying of the large string (as Schwern already pointed out). So it apparently only happens with "open" nested map {}'s.

Oddly enough\, if you repeat the same map​:

============================================================ # this version uses ~ 300MB @​keys = map { foo() } 0..$max; @​keys = map { foo() } 0..$max;

the process size does *not* grow to 600 MB\, but instead stays at about 300 MB. So I guess Perl *is* able to re-use the memory used in the map {}.

So I'm wondering whether this is really a case of leaking\, or just an excessive amount of "temporary" space being used\, which isn't returned to the OS because of fragmentation.

Liz

[p5pRT]

From @nwc10

On Sat\, Dec 01\, 2007 at 03​:52​:27PM -0800\, Michael G Schwern wrote​:

Salvador Fandiño (via RT) wrote​:

# this version uses ~ 300MB @​keys = map { join ''\, map $l[rand @​l]\, 0..71 } 0..$max;

$ perl -MO=Concise -e '@​keys = map { join ""\, map $l[rand @​l]\, 0..71 } 0..$max;' s \<@​> leave[1 ref] vKP/REFC ->(end) 1 \<0> enter ->2 2 \<;> nextstate(main 2 -e​:1) v ->3 r \<2> aassign[t11] vKS/COMMON ->s - \<1> ex-list lK ->o 3 \<0> pushmark s ->4 9 \<|> mapwhile(other->a)[t10] lK/1 ->o 8 \<@​> mapstart lK*/2 ->9 4 \<0> pushmark s ->5 - \<1> null lK/1 ->5 - \<1> null lK/1 ->9 - \<@​> scope lK ->9 - \<0> ex-nextstate v ->a n \<@​> join[t7] sK/2 ->- a \<0> pushmark s ->b b \<$> const(PV "") s ->c g \<|> mapwhile(other->h)[t6] lK/1 ->n f \<@​> mapstart lK/2 ->g c \<0> pushmark s ->d - \<1> null lK/1 ->d m \<2> aelem sK/2 ->g i \<1> rv2av sKR/1 ->j h \<$> gv(*l) s ->i l \<1> rand[t3] sK/1 ->m k \<1> rv2av[t2] sK/1 ->l j \<$> gv(*l) s ->k e \<1> rv2av lKPM/1 ->f d \<$> const(AV ) s ->e - \<1> null lKM/1 ->8 7 \<1> flop lKM ->8 u \<1> flip[t9] lK/LINENUM ->8 5 \<|> range(other->6)[t8] lK/1 ->t t \<$> const(IV 0) s ->u - \<1> ex-rv2sv sK/1 ->7 6 \<$> gvsv(*max) s ->7 - \<1> ex-list lK ->r o \<0> pushmark s ->p q \<1> rv2av[t1] lKRM*/1 ->r p \<$> gv(*keys) s ->q -e syntax OK

I think that the only place where the temporaries get freed is in the nextstate op\, and the only nextstate op is outside all of the maps.

Here is the most damning evidence that the result of the inner map is leaking.

@​keys = map { my @​inner = map $l[rand @​l]\, 0..71; join ''\, @​inner; } 0..$max;

That takes 18 megs\, as expected.

$ cat schwern48004.pl @​keys = map {   my @​inner = map $l[rand @​l]\, 0..71;   join ''\, @​inner; } 0..$max; $ perl -MO=Concise schwern48004.pl 11 \<@​> leave[1 ref] vKP/REFC ->(end) 1 \<0> enter ->2 2 \<;> nextstate(main 3 schwern48004.pl​:2) v ->3 10 \<2> aassign[t13] vKS/COMMON ->11 - \<1> ex-list lK ->x 3 \<0> pushmark s ->4 9 \<|> mapwhile(other->a)[t12] lK/1 ->x 8 \<@​> mapstart lK*/2 ->9 4 \<0> pushmark s ->5 - \<1> null lK/1 ->5 - \<1> null lK/1 ->9 w \<@​> leave lKP ->9 a \<0> enter l ->b b \<;> nextstate(main 1 schwern48004.pl​:1) v ->c q \<2> aassign[t8] vKS ->r - \<1> ex-list lK ->o c \<0> pushmark s ->d h \<|> mapwhile(other->i)[t7] lK/1 ->o g \<@​> mapstart lK/2 ->h d \<0> pushmark s ->e - \<1> null lK/1 ->e n \<2> aelem sK/2 ->h j \<1> rv2av sKR/1 ->k i \<$> gv(*l) s ->j m \<1> rand[t4] sK/1 ->n l \<1> rv2av[t3] sK/1 ->m k \<$> gv(*l) s ->l f \<1> rv2av lKPM/1 ->g e \<$> const(AV ) s ->f - \<1> ex-list lK ->q o \<0> pushmark s ->p p \<0> padav[@​inner​:1\,2] lRM*/LVINTRO ->q r \<;> nextstate(main 2 schwern48004.pl​:3) v ->s v \<@​> join[t9] sK/2 ->w s \<0> pushmark s ->t t \<$> const(PV "") s ->u u \<0> padav[@​inner​:1\,2] l ->v - \<1> null lKM/1 ->8 7 \<1> flop lKM ->8 13 \<1> flip[t11] lK/LINENUM ->8 5 \<|> range(other->6)[t10] lK/1 ->12 12 \<$> const(IV 0) s ->13 - \<1> ex-rv2sv sK/1 ->7 6 \<$> gvsv(*max) s ->7 - \<1> ex-list lK ->10 x \<0> pushmark s ->y z \<1> rv2av[t1] lKRM*/1 ->10 y \<$> gv(*keys) s ->z schwern48004.pl syntax OK

I see 3 nextstate ops there\, which would mean that temporaries are getting freed within the inner maps.

So the inner map isn't leaking in absolute terms in the original code\, but it is "leaking" temporaries for the duration of its execution\, rather than reusing them.

I'm not sure how to fix this. I'm also not sure of the best way to measure the RSS\, but I'd have sneaking suspicion that this hack would work round it​:

@​keys = map { 1; join ""\, map $l[rand @​l]\, 0..71 } 0..$max;

Adding the seemingly useless 1 constant adds 2 nextstate ops.

Maybe pp_mapwhile should FREETMPS?

Nicholas Clark

[p5pRT]

From @rgs

On 03/12/2007\, Nicholas Clark \nick@&#8203;ccl4\.org wrote​:

Maybe pp_mapwhile should FREETMPS?

Maybe at least for the block form of map ? Also\, grep might be in the same case ?

[p5pRT]

From @nwc10

On Mon\, Dec 03\, 2007 at 11​:07​:51PM +0100\, Rafael Garcia-Suarez wrote​:

On 03/12/2007\, Nicholas Clark \nick@&#8203;ccl4\.org wrote​:

Maybe pp_mapwhile should FREETMPS?

Maybe at least for the block form of map ?

I can't think of a way to break it for the expression form of map\, but yes\, I also don't feel totally sure that it wouldn't be break-able.

Also\, grep might be in the same case ?

It seems to suffer from the same problem.

Nicholas Clark

[p5pRT]

From @iabyn

On Tue\, Dec 04\, 2007 at 11​:16​:35AM +0000\, Nicholas Clark wrote​:

On Mon\, Dec 03\, 2007 at 11​:07​:51PM +0100\, Rafael Garcia-Suarez wrote​:

On 03/12/2007\, Nicholas Clark \nick@&#8203;ccl4\.org wrote​:

Maybe pp_mapwhile should FREETMPS?

Maybe at least for the block form of map ?

I can't think of a way to break it for the expression form of map\, but yes\, I also don't feel totally sure that it wouldn't be break-able.

Also\, grep might be in the same case ?

It seems to suffer from the same problem.

Now fixed with this commit​:

commit b2a2a9010bb3413ad9c32e455d93e01069d0fd73 Author​: David Mitchell \davem@&#8203;iabyn\.com AuthorDate​: Mon Oct 4 15​:18​:44 2010 +0100 Commit​: David Mitchell \davem@&#8203;iabyn\.com CommitDate​: Mon Oct 4 15​:29​:24 2010 +0100

  stop map\,grep leaking temps [perl #48004]  
  The former behaviour of map and grep was to never free any temps.   Thus for large lists (and even worse\, nested maps)\, the tmps stack could   grow very large. For all cases expect list-context map\, the fix is easy​:   just do a FREETMPS at the end of each iteration.  
  The list-context map however\, needs to accumulate a list of temporaries   over the course of the iterations\, and finally return that list to the   caller (which is responsible for freeing them). We get round this by\, at   the end of each iteration\, directly manipulating the tmps stack to free   everything *except* the values to be returned. To make this efficient\,   we splice in the returned tmp items at the base of the stack frame\, move   PL_tmps_floor above them\, then do a FREETMPS (so they may appear twice on   the temps stack\, but initially only get freed once).

M pp_ctl.c M pp_hot.c M t/op/svleak.t

-- Hofstadter's Law​: It always takes longer than you expect\, even when you take into account Hofstadter's Law.

[p5pRT]

@iabyn - Status changed from 'open' to 'resolved'