Mac OS X Memory Deallocation Bug

Topics include:

1. The original bug described - 20 Jul 2001
2. The Awk script
3. The bug disappears with Perl - 27 Jan 2002
4. The Perl script
5. Timings show it is still there - 18 Feb 2002
6. Bug located and a workaround - 4 Sep 2002
7. 10.2.2: Problem Still There - 12 Nov 2002
8. 10.2.6: I'm Getting Upset - 27 Jun 2003
9. 10.3: Fixed! - 27 Nov 2003
10. The Bug Explained - 12 Dec 2003

If you want a copy of the script & file of cities, email me.

Mac OS X Bug

From: Dan Allen
Sent: Saturday, July 21, 2001 12:08 PM
To: MPW
Subject: Unix / Win / Mac comparison


Awk Benchmark
20 Jul 2001
By Dan Allen




I wrote an interesting Awk script that greps through a list of over
150,000 US cities and does some calculations.  This script runs extremely
slowly under Mac OS 10.0.4, hereafter referred to as Unix.  Here are the
details:




UNIX
====
On a Macintosh G4 Cube with 450 MHz G4 processor, 320 MB of RAM, and Mac
OS 10.0.4, I ran the following from Terminal:


	awk -f cities.awk USCities.txt


This took 1,800 seconds (30 minutes!!) to run on 10.0.4, and it used over
300 MB of virtual RAM.


Here are a few snapshots from the "top" command while it ran:


  PID COMMAND   %CPU   TIME   #TH #PRTS #MREGS RPRVT  RSHRD  RSIZE  VSIZE
  497 awk      69.7% 13:23.95   1    16    21   245M+  100K-  245M+  247M+
  497 awk      80.9% 19:01.76   1    16    22   231M+  220K   161M+  282M+
  497 awk      83.6% 20:57.76   1    16    22   233M   220K   180M+  300M+
  497 awk      87.9% 22:58.63   1    16    22   233M-  220K   193M+  314M


The awk I used I built myself using sources from Brian Kernighan's website.
I built it using the GCC that comes with Apple's Developer CD using the -O3
level of optimizations which results in an executable 136,476 bytes in size.
Small awk scripts run in an acceptable time, but this large script shows up
a major problem in memory allocation.




WINDOWS 2000
============
If I run the same command on a 450 MHz Pentium III Dell computer using
Windows 2000 and 256 MB of RAM, the job runs in 50 seconds and uses 32 MB
of RAM.  (The Mem Usage is 32 MB and the VM Size is 32 MB, as measured by
the Windows Task Manager.  This does not mean 64 MB of RAM--it means that
all of the RAM that was virtually allocated also was resident in physical
RAM.)  For Windows I built awk using Visual C++ 6.0 -Ox from the exact same
sources as for Unix and Mac.  The resulting awk binary is 139,264 bytes
in size.




MAC OS 9.1
==========
If I run the same script on the same G4 Cube but running under Mac OS 9.1
and MPW, the job runs in 269 seconds and uses a maximum of 26 MB of memory.
This version of awk is 101,938 bytes in size and was built using MPW's
MRC 4.1 with the -opt speed level of optimization, thus all 3 builds of
awk were optimized for speed.  Note: The sort was actually done via piping
the output of the cities.awk script into the sort tool under MPW as my port
of Awk under MPW does not support piping or the system command from an MPW
tool.  The sort, however, happens near instantly on all systems so it is
in the noise.)




SUMMARY
=======
On all three platforms (Mac, Unix, Windows) the same results are returned,
a file about 679 KB in size.  (It is a list of cities showing the city names
that are the most commonly used and a list of the states that each city is
found in.  It also computes the geographic center of the cities that share
a common name.)


Comparative Stats:


Windows is 36 times faster than Unix.
Windows is 5.4 times faster than Mac OS.
Mac OS is 6.7 times faster than Unix.


Mac OS uses 26 MB of memory, about 81% of Windows.
Windows uses 32 MB of memory, about 10% of Unix.
Unix uses 314 MB of memory, about 12 times Mac OS.


This explains why Apple's new Unix is incredibly slow compared to the Mac OS:
memory allocation has major problems!  Why is over 314 MB allocated when the
other operating systems use 25-32 MB of RAM?  It seems to me that solving this
problem would solve a lot of Mac OS X sluggishness problems, such as those in
the Finder and menus.



APPENDIX 1 - Cities.awk script used in this test

==========


#!/Users/danallen/bin/awk -f
# cities.awk  - city name frequencies from USCities.txt
# 17 Jul 2001 - Created by Dan Allen.
# 19 Jul 2001 - Average location computed.
# 20 Jul 2001 - Ported to OS X.


BEGIN { FS = OFS = "\t" }


$3 == "Puerto Rico" || $3 == "Guam" { next }


{
	name = $1
	lat = DMS2Dec($4)
	lon = DMS2Dec($5)
	if (lat ~ "NAN" || lon ~ "NAN") next
	sub(/,.*/,"",name)
	sub(/ ?\(.*\)/,"",name)
	sub(/St\.? /,"Saint ",name)
	if (!index(a[name],$3)) {
		a[name] = a[name] ", " $3
		avgLat[name] += DMS2Dec($4)
		avgLon[name] += DMS2Dec($5)
		numPts[name]++
	}
}


END {
  for (i in a) {
    n = split(a[i],t,",") - 1
    sub(/^, /,": ",a[i])
    if (n > 3)
      print n, avgLat[i] / numPts[i],avgLon[i] / numPts[i],i a[i] | "sort -n"
    sum += n
  }
  print sum,"total cities"
}


function DMS2Dec(dms,  neg) { # ddmmssx --> dd.ddddd
  CONVFMT = "%.5f"
  if (length(dms) == 7) { # latitude
    neg = (substr(dms,7,1) == "S") ? -1 : 1
    return neg * (substr(dms,1,2) + substr(dms,3,2)/60 + substr(dms,5,2)/3600)
  }
  else if (length(dms) == 8) { # longitude
    neg = (substr(dms,7,1) == "E") ? -1 : 1
    return neg * (substr(dms,1,3) + substr(dms,4,2)/60 + substr(dms,6,2)/3600)
  }
}







APPENDIX 2 - Sample from USCities.txt
==========


City		County		State		Latitude	Longitude
Abanda		Chambers	Alabama	330603N	0853147W
Abbeville	Henry		Alabama	313418N	0851502W
Abbot Springs	Shelby		Alabama	332139N	0862854W
Abel		Cleburne	Alabama	333255N	0854245W
.
.
(153,000+ cities omitted)




Daniel K. Allen
Measure | Analyze | Communicate

Perl Update - 27 Jan 2002

38 seconds and uses 24.5 MB of memory!

This does not make any sense of course. Awk scripts generally run faster than Perl scripts, but the Awk version takes 30 minutes and uses 300+ MB of memory on OS X, leading to the following bug report below... As to why the new Perl version runs so fast, I do not know. Note that the Awk version runs very quickly on Mac OS 9.2 or Windows 2000.

Cities script - Perl version

#!/usr/bin/perl
#  cities.pl  - city name frequencies from USCities.txt
# 17 Jul 2001 - Created by Dan Allen. (Paradise, CA)
# 19 Jul 2001 - Average location computed. (Paradise, CA, 3:00 AM)
# 27 Jan 2002 - Converted from Awk to Perl via a2p.


$[ = 1;			# set array base to 1
$\ = "\n";		# set output record separator
$FS = $, = "\t";
open(SORT__N, '|sort -n') || die 'Cannot pipe to "sort -n".';


line: while (<>) {
	chomp;	# strip record separator
	($Fld1,$Fld2,$Fld3,$Fld4,$Fld5) = split($FS, $_, 9999);
	if ($Fld3 eq 'Puerto Rico') { next line; }
	if ($Fld3 eq 'Guam') { next line; }
	$name = $Fld1;
	$lat = &DMS2Dec($Fld4);
	$lon = &DMS2Dec($Fld5);
	if ($lat =~ 'NAN' || $lon =~ 'NAN') { next line; }
	$name =~ s/,.*//;
	$name =~ s/ ?\(.*\)//;
	$name =~ s/St\.? /Saint /;
	if (!index($a{$name}, $Fld3)) {
		$a{$name} = $a{$name} . ', ' . $Fld3;
		$avgLat{$name} += &DMS2Dec($Fld4);
		$avgLon{$name} += &DMS2Dec($Fld5);
		$numPts{$name}++;
	}
}


foreach $i (keys %a) {
	$n = (@t = split(/,/, $a{$i}, 9999)) - 1;
	$a{$i} =~ s/^, /: /;
	print SORT__N $n, $avgLat{$i} / $numPts{$i},$avgLon{$i} / $numPts{$i}, $i . $a{$i} if $n > 3;
	$sum += $n;
}
print $sum, 'total cities';


sub DMS2Dec {
	local($dms, $neg) = @_;
	# ddmmssx --> dd.ddddd
	$CONVFMT = '%.5f';
	if (length($dms) == 7) {
		# latitude 472945N
		$neg = (substr($dms, 7, 1) eq 'S') ? -1 : 1;
		return $neg * (substr($dms, 1, 2) + substr($dms,3,2) / 60 + substr($dms, 5, 2) / 3600);
	}
	elsif (length($dms) == 8) {
		# longitude 1214708W
		$neg = (substr($dms, 7, 1) eq 'E') ? -1 : 1;
		return $neg * (substr($dms, 1, 3) + substr($dms,4,2) / 60 + substr($dms, 6, 2) / 3600);
	}
}

Timing Comparison

[~/AwkTrue] % time awk -f cities.awk cities.txt > foo
 1472.970u 22.420s  36:08.55   68.9%    0+0k 0+16io 0pf+0w
[~/AwkTrue] % time perl cities.pl cities.txt > foopl
   41.540u  0.940s   1:46.48   39.8%    0+0k 3+5io 0pf+0w

Problem Identified

The source for this is available from http://www.opensource.apple.com/projects/darwin/1.4/projects.html, the Libc-186.tgz component, in the file Libc/gen.subproj/scalable_malloc.c. I am studying it now to see what the problem is.

On a new dual 1 GHz G4 tower I was able to get much better performance by changing the routine tfree in Awk's run.c source as follows:

void tfree(Cell *a)	/* free a tempcell */
{
	if (freeable(a)) {
		   dprintf( ("freeing %s %s %o\n", NN(a->nval), NN(a->sval), a->tval) );
		#ifdef __APPLE__ /* DKA 4 Sep 2002 */
		a->sval = NULL;
		#else
		xfree(a->sval);
		#endif
	}
	if (a == tmps)
		FATAL("tempcell list is curdled");
	a->cnext = tmps;
	tmps = a;
}

My change was to not call free at all but to just set the pointer to NULL. This change changes virtual RSIZE RAM usage from 320 MB to 83 MB! Interesting how NOT freeing up memory uses much less memory. Memory management is definitely screwed up.

Here are the times without the fix and then with the fix on a Dual 1GHz G4 Tower running 10.2:

[~/AwkTrue] % time ./awk -f cities.awk < cities.txt > foo
1079.520u   9.030s   18:21.95   98.7%    0+0k 0+10io 0pf+0w
[~/AwkTrue] % time ./awk -f cities.awk < cities.txt > foo
  18.300u   0.830s    0:19.27   99.2%    0+0k 0+12io 0pf+0w

Problem Still There

I'm Getting Upset

Fixed!

The Bug Explained

Back to Dan Allen's home page.

Created:  27 Feb 2001
Modified: 12 Dec 2003