Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uwm.edu!bionet!parc!boehm From: boehm@parc.xerox.com (Hans Boehm) Newsgroups: comp.lang.scheme Subject: Re: Benchmarking Scheme Message-ID: Date: 2 May 91 18:55:32 GMT References: <1991May2.155838.20830@bronze.ucs.indiana.edu> Sender: news@parc.xerox.com Distribution: comp.lang.scheme Organization: Xerox PARC Lines: 33 huntley@copper.ucs.indiana.edu (Haydn Huntley) writes: >... I learned how expensive it is to >implement generic arithmetic, garbage collection, and type checking! >Each one of them costs something like a factor of 2 in performance! >--Haydn At least in the case of garbage collection, I think this statement is a bit misleading. Depending on your ratio of accessible to available memory, caching effects, frequency of side effects, etc., allocating objects on the heap instead of stack allocating them can easily cost you a factor of 2 in performance. But if you compare garbage collection to heap allocation and explicit deallocation (as with C malloc/free), it's not clear that garbage collection costs you anything in total execution time. I've seen cases, running with a trace and sweep allocator, where inserting explicit deallocations slowed down the code. It's often cheaper for a garbage collector to restore a large collection of objects to free lists at once, than it is to deallocate them one at a time. Looking only at cpu cycles, this effect should usually be more pronounced for copying collectors. (Copying collectors have other disadvantages, but that's another story.) I suspect the problem with this example is some combination of superfluous allocation and generic arithmetic. The example isn't entirely fair to Scheme either, since there are other ways to solve this problem that actually use Scheme's builtin BigNums, and are probably much faster. The C program is reimplementing BigNums in a pretty clumsy way. (Our desk calculator utility computes 3000 digits of PI in about 10 seconds on a SPARCstation 2, using a fancier algorithm, and taking advantage of BigNum arithmetic. It's written in Russell, but spends most of its time in the DEC/INRIA BigNum package, which is written in C.) Hans (boehm@xerox.com)