paper.ps

c programming pearls answer

%!PS-Adobe-2.0
%%Copyright: Copyright (c) 1993 AT&T, All Rights Reserved
%%Version: 3.4
%%DocumentFonts: (atend)
%%Pages: (atend)
%%BoundingBox: (atend)
%%EndComments
/DpostDict 200 dict def
DpostDict begin
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 prologue for troff files.
%

/#copies 1 store
/Prologue (dpost.ps) def
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	addmetrics
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/landscapepage {
	landscape not {
		0 height scaling div neg translate	% not quite
		90 rotate
	} if
} bind def

/portraitpage {
	landscape {
		width scaling div 0 translate	% not quite
		-90 rotate
	} if
} bind def

/addmetrics {
	/Symbol /S null Sdefs cf
	/Times-Roman /S1 StandardEncoding dup length array copy S1defs cf
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newencoding exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall

	newencoding type /arraytype eq {newdict /Encoding newencoding put} if

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
end
%%EndProlog
%%BeginSetup
DpostDict begin
mark
/rotation 1 def
/gotpagebbox true def
/linewidth 0.5 def
/xoffset 0 def
/yoffset 0 def
/#copies 1 store
/magnification 1 def
%%FormsPerPage: 1
/formsperpage 1 def
%%Patch from lp
%%EndPatch from lp
/landscape false def
/resolution 720 def
setup
2 setdecoding
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 drawing procedures for dpost. Automatically pulled in when
% needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
/build_ob {
    pop
    size 3 mul 16 div /rad exch def
    currentpoint
    newpath
    rad add exch rad add exch rad 0 360 arc
    stroke
} def
end
%%EndSetup
%%Page: 1 1
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
1 pagesetup
12 B f
(Timing Trials, or, the Trials of Timing:)6 2019 1 1870 1230 t
(Experiments with Scripting and User-Interface Languages)5 2999 1 1380 1380 t
10 I f
(Brian W. Kernighan)2 814 1 2473 1620 t
10 R f
(Bell Laboratories)1 696 1 2532 1800 t
(Murray Hill, NJ 07974)3 916 1 2422 1920 t
10 CW f
([e-mail])2370 2040 w
10 I f
(Christopher J. Van Wyk)3 960 1 2400 2280 t
10 R f
(Department of Mathematics and Computer Science)5 2049 1 1855 2460 t
(Drew University)1 668 1 2546 2580 t
(Madison, NJ 07940)2 786 1 2487 2700 t
10 CW f
([e-mail])2400 2820 w
10 I f
(ABSTRACT)2643 3200 w
10 R f
( script-)1 281(This paper describes some basic experiments to see how fast various popular)11 3069 2 1330 3460 t
( found)1 272( We)1 202( representative tasks.)2 862(ing and user-interface languages run on a spectrum of)8 2264 4 1080 3580 t
( in performance, depending on many factors, some uncontrollable and)9 2824(enormous variation)1 776 2 1080 3700 t
( predicting performance in other than a)6 1557( seems to be little hope of)6 1033( There)1 283(even unknowable.)1 727 4 1080 3820 t
( that no benchmark result)4 1083(most general way; if there is a single clear conclusion, it is)11 2517 2 1080 3940 t
(should ever be taken at face value.)6 1376 1 1080 4060 t
(A few general principles hold:)4 1214 1 1330 4216 t
10 S f
(\267)1230 4372 w
10 R f
( faster than interpreted code: the more a program has)9 2216(Compiled code usually runs)3 1152 2 1312 4372 t
(been ``compiled'' before it is executed, the faster it will run.)10 2411 1 1080 4492 t
10 S f
(\267)1230 4648 w
10 R f
( how)1 212(Memory-related issues and the effects of memory hierarchies are pervasive:)9 3153 2 1315 4648 t
( can change runtimes)3 878(memory is managed, from hardware caches to garbage collection,)8 2722 2 1080 4768 t
( most aspects of memory manage-)5 1447( users have no direct control over)6 1420(dramatically. Yet)1 733 3 1080 4888 t
(ment.)1080 5008 w
10 S f
(\267)1230 5164 w
10 R f
( are woefully inad-)3 762(The timing services provided by programs and operating systems)8 2616 2 1302 5164 t
( purely)1 286( is difficult to measure runtimes reliably and repeatably even for small,)11 2911(equate. It)1 403 3 1080 5284 t
( does much)2 481(computational kernels, and it becomes significantly harder when a program)9 3119 2 1080 5404 t
(I/O or graphics.)2 629 1 1080 5524 t
( are visible and sometimes)4 1080(Although each language shines in some situations, there)7 2270 2 1330 5680 t
( encountered)1 514( We)1 191(surprising deficiencies even in what should be mainstream applications.)8 2895 3 1080 5800 t
(bugs, size limitations, maladroit features, and total mysteries for every language.)10 3223 1 1080 5920 t
10 B f
(INTRODUCTION)720 6280 w
10 R f
( the performance of scripting languages \(like Awk, Perl,)8 2261(This paper describes experiments to compare)5 1809 2 970 6436 t
( a set of representative)4 925(and Tcl\) and interface-building languages \(like Tck/Tk, Java, and Visual Basic\) on)11 3395 2 720 6556 t
( than we)2 348( found this challenging, with more difficulties and fewer clear-cut results)10 2954( We)1 192(computational tasks.)1 826 4 720 6676 t
(had expected.)1 548 1 720 6796 t
( usually interpreted, using them sacrifices some)6 1954(Since scripting and interface-building languages are)5 2116 2 970 6952 t
( single-)1 303( ``wasted'' CPU time doesn't matter for short,)7 1896( This)1 235(speed in return for programming convenience.)5 1886 4 720 7072 t
( nor does it matter if the scripting language is)9 1839(use programs, or for programs that run in only a few seconds,)11 2481 2 720 7192 t
( sets)1 182( small programs for small data)5 1258( But)1 203(mainly used as ``glue'' to control efficient large-scale operations.)8 2677 4 720 7312 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 45 514 691
%%EndPage: 1 1
%%Page: 2 2
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
2 pagesetup
10 R f
(- 2 -)2 166 1 2797 480 t
( sets; for instance, Awk and Perl have been used to write)11 2317(can evolve into big programs that run on big data)9 2003 2 720 840 t
( evolves into)2 513( sometimes the glue itself)4 1030( And)1 224(programs of thousands of lines that process megabyte data sets.)9 2553 4 720 960 t
( fast different languages run, performance com-)6 1938( quantifying how)2 693( By)1 172(a major component of an application.)5 1517 4 720 1080 t
( application, and what)3 882(parisons could suggest which languages would be appropriate for different parts of an)12 3438 2 720 1200 t
(the penalty might be for choosing convenience over efficiency.)8 2519 1 720 1320 t
( a comprehensive set of represen-)5 1367( Choose)1 356( runtimes seems straightforward.)3 1327(At first blush, comparing)3 1020 4 970 1476 t
( equivalent programs in the different languages, measure the runtimes on several systems,)12 3612(tative tasks, write)2 708 2 720 1596 t
( create a)2 347( approach is an obvious generalization of test programs that)9 2445( This)1 235(then present them all in a table.)6 1293 4 720 1716 t
( and benchmarks that compare)4 1235(cost model for primitive operations in a single language like C [Bentley 91])12 3085 2 720 1836 t
(implementations of a single language like Java [Hardwick 97, Caffeine 97].)10 3022 1 720 1956 t
( exer-)1 239(The seemingly easy job of comparison, however, has proved to be much more than a routine)15 3831 2 970 2112 t
( hope that this journal of our)6 1228( We)1 203( encountered problems, puzzles, and surprises at every step.)8 2506(cise. We)1 383 4 720 2232 t
( perform)1 353(expedition will encourage readers to view published comparisons with caution, and to design and)13 3967 2 720 2352 t
(their own experiments carefully.)3 1297 1 720 2472 t
( often say that a program in one language ran some)10 2150(When reporting results of our experiments, we)6 1920 2 970 2628 t
( a snap-)2 314( such results represent)3 893( All)1 181(amount faster or slower than an equivalent program in another language.)10 2932 4 720 2748 t
( performance of language processors that were readily available to us.)10 2869(shot, in the summer of 1997, of the)7 1451 2 720 2868 t
( on other)2 383(They provide no warrant for drawing conclusions about the relative performance of languages)12 3937 2 720 2988 t
(machines or using other versions of software.)6 1816 1 720 3108 t
( cannot state many firm conclusions, there are some themes that recur often in the)14 3403(Even though we)2 667 2 970 3264 t
(experiments described below.)2 1189 1 720 3384 t
10 S f
(\267)1120 3540 w
10 R f
(Compilation wins over interpretation, and interpretation from an intermediate representation)9 3833 1 1207 3540 t
( exact speedup is unpredictable,)4 1308( The)1 214( program text.)2 581(wins over repeated interpretation of the original)6 1967 4 970 3660 t
( the most part, we have)5 996( For)1 203(however, and compilation may even slow the program down instead.)9 2871 3 970 3780 t
( are always available, while compilers are often experimental,)8 2623(tested only interpreters, since they)4 1447 2 970 3900 t
( in Section 7 indicate)4 852( limited results presented)3 1005( The)1 206(unsupported, inaccessible, or an extra-cost option.)5 2007 4 970 4020 t
(that compilation is generally, but not always, of modest benefit.)9 2548 1 970 4140 t
10 S f
(\267)1120 4296 w
10 R f
( espe-)1 249( course the absolute amount available on a machine is important,)10 2718( Of)1 168(Memory matters.)1 701 4 1204 4296 t
( hard-)1 240( buffers and caches \(at several different levels of)8 1985( But)1 201(cially once paging \(or thrashing\) begins.)5 1644 4 970 4416 t
( memory allocation and garbage collection can also)7 2152(ware and software\) and the implementation of)6 1918 2 970 4536 t
( factors often lie beyond user control.)6 1494( These)1 288(have dramatic effects on performance.)4 1530 3 970 4656 t
10 S f
(\267)1120 4812 w
10 R f
( simple timing loops can exhibit erratic runtimes for no)9 2342( Even)1 270(Accurate timing is very hard.)4 1223 3 1205 4812 t
( a program interacts with its environment by doing significant I/O or graphics,)12 3175( Once)1 264(obvious reason.)1 631 3 970 4932 t
( well known problems are exacer-)5 1364( These)1 290( becomes even larger.)3 875(the variation in runtime measurements)4 1541 4 970 5052 t
( also have not found a satisfactory)6 1400( We)1 194( unreliable internal ``timing'' routines.)4 1569(bated by systems with)3 907 4 970 5172 t
( all systems, so head-to-head comparisons between languages are some-)9 2886(way to charge startup costs to)5 1184 2 970 5292 t
(times difficult.)1 589 1 970 5412 t
10 B f
(1. Methodology)1 686 1 720 5652 t
10 R f
( three dimensions: task, programming language, and machine.)7 2578(We started to construct a table with)6 1492 2 970 5808 t
( problem solved by the program as a fourth dimension, and we changed)12 2883(Eventually we added the size of the)6 1437 2 720 5928 t
( the problem size helped us to detect unusual runtime)9 2299( Varying)1 396( from tables to graphs.)4 972(the presentation)1 653 4 720 6048 t
( perfor-)1 301(effects, while a graphical presentation highlights patterns and trends in runtime instead of individual)13 4019 2 720 6168 t
(mance scores.)1 559 1 720 6288 t
( studies, we do not)4 791( some benchmarking)2 852( Unlike)1 332(We present measurements for each task separately.)6 2095 4 970 6444 t
( problem with this common)4 1118( One)1 220(combine the results of several different experiments into a single number.)10 2982 3 720 6564 t
( outcome [Becker)2 733(practice is that one can choose different weighting factors to create almost any desired)13 3587 2 720 6684 t
(87].)720 6804 w
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 96 514 764
%%EndPage: 2 2
%%Page: 3 3
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
3 pagesetup
10 R f
(- 3 -)2 166 1 2797 480 t
10 B f
(Choice of Tasks)2 678 1 720 840 t
10 R f
( or)1 113(It is hard to devise small yet representative tasks that do not give too big an edge to one language)19 3957 2 970 996 t
( one or two language features, and will require)8 1947( each task will test only)5 1001( Ideally,)1 364(unduly penalize another.)2 1008 4 720 1116 t
( the comparison to be sen-)5 1061( For)1 191( are easy and natural to express in any language.)9 1946(short, simple, programs that)3 1122 4 720 1236 t
( we do not)3 440( While)1 302(sible, the programs also must be expressed in a ``colloquial'' fashion in each language.)13 3578 3 720 1356 t
(claim that any of the tasks we present is definitive, we believe that each is reasonably fair.)16 3598 1 720 1476 t
( language features \(Section 3\); arrays and)6 1704(We have organized the presentation by type of task: basic)9 2366 2 970 1632 t
( 7 describes experi-)3 790( Section)1 354( input/output \(Section 5\); basic GUI operations \(Section 6\).)8 2405(strings \(Section 4\);)2 771 4 720 1752 t
( programs and test)3 771( The)1 217( includes further explanations of the tasks.)6 1761( section)1 319( Each)1 260(ments with compilation.)2 992 6 720 1872 t
(data are available at)3 794 1 720 1992 t
10 CW f
(www.cs.bell-labs.com/\304bwk)1539 1992 w
10 R f
(.)3039 1992 w
10 B f
(Choice of Languages)2 889 1 720 2232 t
10 R f
(We report timings for the eight languages summarized in Table 1.)10 2632 1 970 2388 t
9 S f
(_ _______________________________________________________________________________________________)1 4311 1 724 2573 t
9 R f
( Scheme)1 537( Limbo)1 437( Basic)1 223( Visual)1 446( Java)1 439( Tcl)1 429( Perl)1 473(C Awk)1 586 8 1372 2683 t
9 S f
(_ _______________________________________________________________________________________________)1 4311 1 724 2703 t
9 R f
( indexed)1 -2473( indexed)1 514( indexed)1 547( indexed)1 984( assoc)1 929( assoc)1 423(arrays indexed)1 782 7 763 2813 t
(and assoc)1 348 1 2184 2923 t
(indexed)3045 2813 w
(and assoc)1 348 1 3045 2923 t
9 S f
(_ _______________________________________________________________________________________________)1 4311 1 724 2943 t
9 R f
( embed-)1 293( Tk)1 304( none)1 408(graphics libraries)1 787 4 763 3053 t
(ding\(1\))2162 3163 w
(yes)2720 3053 w
(\(Tk\))2720 3163 w
(standard)3066 3053 w
(library)3066 3163 w
(standard)3586 3053 w
(library)3586 3163 w
(Tk embed-)1 393 1 4089 3053 t
(ding)4089 3163 w
(Tk embed-)1 393 1 4603 3053 t
(ding\(1\))4603 3163 w
9 S f
(_ _______________________________________________________________________________________________)1 4311 1 724 3183 t
9 R f
( Irix)1 -3593(Inferno 1.0)1 401 2 4085 3293 t
(version)763 3403 w
(native)1242 3293 w
(compiler)1242 3403 w
(Bell Labs)1 348 1 1697 3293 t
(1996)1697 3403 w
(Perl 5.003)1 371 1 2173 3293 t
(Perl 5.004)1 371 1 2173 3403 t
(Tcl 7.6)1 256 1 2672 3293 t
(Tk 4.2)1 236 1 2672 3403 t
(MIT)4657 3293 w
(Scheme)4657 3403 w
(7.3)4657 3513 w