Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucsd!hub!eiffel!kimr From: kimr@eiffel.UUCP (Kim Rochat) Newsgroups: comp.lang.eiffel Subject: Benchmark article - Eiffel vs. C++ vs. Smalltalk-80 Keywords: benchmark, Eiffel, C++, performance Message-ID: <274@eiffel.UUCP> Date: 23 Mar 90 02:56:08 GMT Organization: Interactive Software Engineering, Santa Barbara CA Lines: 943 The following article, based on a presentation at the Eiffel User's group meeting last October, was intended for the Eiffel User's Group newletter. Circumstances have prevented its being published to date but inquiries on the net about Eiffel performance prompt me to post it here. When this article was prepared, the authors were employed by Tektronix, Beaverton, Oregon. Kim Rochat kimr@eiffel.com ------------------------------------------------------------------------------- A Comparison of Mosaic in Three Languages Kim Rochat Interactive Software, Inc. 270 Storke Rd. Suite 7 Goleta, CA 93117 E-mail: kimr@eiffel.com Roxanna Rochat Interactive Software, Inc. 270 Storke Rd. Suite 7 Goleta, CA 93117 E-mail: roxier@eiffel.com Introduction Mosaic is a small program originally written in Smalltalk-80(TM) to generate patterns for mosaic knitting. The program has subsequently been manually translated to Eiffel(TM) and C++. This article presents performance benchmarks and observations about the three implementations, as well as complete listings of the program code. It is shown that the choice of C compiler used with Eiffel can affect execution speed by up to 30 percent. Mosaic Description The Mosaic program generates a pattern for mosaic knitting. The pattern is rectangular, consisting of a specific number of rows, each having the same number of stitches. Each stitch may be one of two colors. The base color of each row alternates. The first and last stitch of each row must be the base color. The intermediate stitches in the first row have their colors determined randomly to start off the pattern. Intermediate stitches in following rows are the base color unless the corresponding stitch in the row before is of the contrasting color, in which case the contrasting color may be pulled up to the current row. No more than two adjacent stitches may be of the contrasting color. In each case where the contrasting color might appear in a row, a random decision is made whether to pull the stitch up from the preceding row or not. Mosaic Algorithm Each of the three programs uses an array of integers to represent a row of stitches. Each stitch is represented by the integer zero for a white stitch, one for a black stitch. A mosaic pattern is an array of rows. The pattern is displayed by printing out the integer values for each stitch, one row per line. The programs are written to dynamically adapt to the number of rows and stitches supplied by the user at execution time. To simplify the comparison by eliminating command line interface code, the number of rows and stitches are hard coded into the programs shown here. Each program dynamically allocates the first row, selects a base color, and randomly fills in the intermediate stitches with the contrasting color. Additional rows are dynamically allocated one at a time, each row having its stitches filled in based on the stitches in the previous row. Two primary classes are used. One class (Mosaic or RowArray, depending on the program) contains a dynamically sized array of row objects and operations to create and print rows. Row objects contain a dynamically sized integer array representing the stitches in the row and the operations to fill in the stitches based on the stitches in a previous row. History The Smalltalk program provided is a subset of one written to generate actual knitting designs. The original program was designed to use graphics and allow interactive control over the pattern generation. The solution, although expressed in an object-oriented language, does not make use of polymorphism or garbage collection. In fact, it would have been about as easy to write a solution in a procedural language, such as C. While the mosaic program doesn't exercise method lookup or other object-oriented features, it does test fundamental behavior of almost any program; integer and array operations. Once we had the Smalltalk implementation, we tried to preserve its semantics during translation to Eiffel and C++ to provide a fair comparison of the three languages. Any of the implementations could be tuned to provide better performance, but we tried to keep the comparison more equal by using the same obvious algorithm. C++ Implementation Observations We wanted a class which was a dynamically sized array of integers. Since C++ lacks a generic array class, we wrote an intArray class. The implementation of intArray uses a pointer to access the dynamically allocated storage for the array. An indirection could be eliminated in accessing array elements if the array were stored in the intArray class itself. This can be accomplished by having the class allocate space for itself, a common technique involving assigning to "this" allowed in Cfront version 1.2 but considered an anachronism in Cfront 2.0. Eiffel Implementation Observations The external C function "random()" is used by the Eiffel implementation to generate random colors. The class RANDOM encapsulates this C routine, and is used by both the MOSAIC class to determine the base color of the first row and by the ROW class to determine what color a stitch should be. Since this was our first Eiffel program, we experimented with two techniques for gaining access to the features of RANDOM. In ROW, we simply inherited from RANDOM. In MOSAIC, we used a "once" routine to create a single instance of the RANDOM class which could be used subsequently. Of course, it's only called once in MOSAIC. Another choice would have been to declare an attribute of type RANDOM in MOSAIC and called the Create routine for that attribute in MOSAIC's Create routine. It seems stylistically preferable to us to use the "once" function to declare and create an instance of an object for use by a class than to divide the declaration of an attribute from its creation. To avoid the use of inheritance for a "uses" relationship, ROW should be rewritten to have a once routine which returns an instance of RANDOM rather than to inherit from RANDOM. Source Size Comparisons We compared the source code size of the three implementations, but didn't arrive at a meaningful conclusion. The number of code lines is determined more by the formatting style than by the actual length of the program. Excluding command and blank lines, the listings contain around 100 lines of code for Smalltalk and about 150 lines each for Eiffel and C++. For those interested in metrics concerning tokens (identifiers and symbols), there are 421 for Smalltalk, 518 for Eiffel, and 788 for C++. The only conclusion we feel safe drawing is that the C++ source code is larger than Eiffel or Smalltalk due to the need to implement an additional class (intArray) and the redundant function declarations in the header file. Performance Comparisons The three implementations of Mosaic were compiled and executed on two 68020 workstations using a variety of compilers. Figure 1 shows the results of these measurements with statistics reported by the Unix "time" command. In each case, a design consisting of 1000 rows with 1000 stitches per row was created. While impractical, this size was chosen for benchmarking to increase the execution time relative to the measurement increment. To avoid biasing the measurements with the I/O overhead of the workstation, the resulting pattern was not printed. ------------------------------------------------------------------------------- Figure 1: Mosaic Benchmark Results Host Language[2] Compiler[3] Execution Time (secs)[4] Executable Size[5] [1] User System Wall Text Data BSS ---- ----------- ----------- ---- ------ ---- ----- ---- ----- Tek Smalltalk Tek ST-80 3600 Tek Eiffel Greenhills 69.2 1.0 70 40960 11264 36004 Tek C++ CC1.2/GH 55.3 1.7 57 15360 5120 34508 Tek C++ CC1.2/gcc 54.2 1.3 56 15360 5120 34498 Tek C++ g++ 52.9 1.3 54 20480 8192 32056 Tek Eiffel gcc 49.9 1.4 51 39936 11264 35616 Sun Eiffel Sun 54.7 1.0 56 65535 8192 3872 Sun C++ CC2.0/gcc 41.3 1.2 42 32768 8192 0 Sun C++ g++ 40.6 0.9 41 40960 8192 0 Sun Eiffel gcc 40.4 1.1 41 65535 8192 536 Sun C++ CC2.0/cc 39.9 1.3 41 40960 8192 0 Notes: 1) Platforms are Sun-3/60 running SunOS 4.0.3 and Tektronix 4317 running UTek 4.1. Both have 12Mb RAM. 2) Eiffel version 2.1 was used. All checking was turned off and C package generation always used. 3) The g++ compiler was version 1.35.1-. The gcc compiler was version 1.35. The Greenhills compiler was version 1.8.3A. Cfront version 1.2 was used with the Greenhills and GNU C compilers. Cfront version 2.0 was used with the GNU and Sun C compilers. All compilers were run with the -O option. Smalltalk was Tektronix Smalltalk version 2.3.0a. 4) All times in seconds as reported by the csh time command for the second execution of the program. 5) All sizes in decimal bytes as reported by the size command. Sun executables were statically linked. ------------------------------------------------------------------------------- Execution Times Benchmarking at its best is an uncertain activity, since you are never sure exactly what you're measuring. This article intends to provide enough information for others to duplicate the benchmark results. If you aren't familiar with the UNIX(TM) "time" command, the wall clock time in seconds is the easiest one to use for comparison. User time is the time the process spent executing user code. System time is the amount of time spent in the kernel. Since loading a program can take a noticeable time, each program was executed twice in sequence and the time from the second execution was used. This allowed the kernel disk buffer to be used for the second program load and avoided accessing the disk. Much of the work done by mosaic for both C++ and Eiffel is in the C library "random" routine. This library routine is common to all C++ and Eiffel executions on a host, making even more remarkable the magnitude of the performance differences seen with Eiffel. C++ Execution Time The time required to execute the program in C++ is pretty much the same on a given host regardless of the compiler used. CC 1.2 and CC 2.0 are two versions of the AT&T "cfront" C++ translator, which emits C code. Gcc is the Free Software Foundation's C compiler, and g++ is the FSF native code C++ compiler. In addition, the standard workstation compilers were used with cfront, the Sun C compiler for Sun and the Greenhills compiler for Tektronix. Eiffel Execution Time Using the GNU C compiler instead of the C compiler supplied with the workstation the mosaic program executes about 30 percent faster. We have not analyzed the generated code to determine the cause of the performance difference. It may simply be that GNU compiles the specific code used by Eiffel for array accesses more efficiently. In other C applications we have observed that the GNU C compiler provides a 10 to 20 percent speedup over the C compiler supplied with the workstation. Note that Eiffel is just as fast as C++ on the Sun and faster than C++ on the Tektronix workstation. This seems ironic since C++ is touted as being efficient and the mosaic program exercises features which should be efficiently implemented in C. Smalltalk Execution Time We expected Smalltalk to be about ten times slower than the compiled languages and were surprised to find it significantly slower. Profiling showed that 85 percent of the time was spent computing random numbers. Modifying the method or replacing it with a user primitive would result in performance numbers nearer those expected. Normally, mosaic patterns are relatively small. Smalltalk's performance is entirely adequate for these cases. Code Sizes The code sizes reported by the UNIX "size" command are included, but must be interpreted carefully. The sizes reported for the Sun are multiples of 8K-bytes, and so are only accurate to that increment. While it appears that Eiffel code is twice as large as C++ code on the Tektronix machine, this may be due to a 20K-byte constant overhead in the Eiffel runtime system. Conclusions While bearing in mind that mosaic is a small program exercising a limited subset of the languages, two major conclusions can be drawn. First, any perception that C++ has superior performance to Eiffel may be invalid. Second, if you're using Eiffel, a different C compiler may result in significantly increased performance. By itself, mosaic is too small to obtain reliable measurements for code complexity, reuse, maintenance and development time, although informal comparisons of the programs may be useful. In combination with similar exercises, a better picture of the strengths and weaknesses of each language can be achieved. Resources For information on the GNU compiler products, contact: Free Software Foundation 675 Mass Ave Cambridge, MA 02139 ------------------------------------------------------------------------------- Smalltalk-80 is a trademark of ParcPlace Systems, Inc. Eiffel is a trademark of Interactive Software Engineering, Inc. UNIX is a trademark of AT&T. Listing 1: Mosaic program in Smalltalk-80. Array variableSubclass: #Row instanceVariableNames: 'previousRow baseColor' classVariableNames: 'Rand' poolDictionaries: '' category: 'Mosaic-Support' Row comment: 'This class is an Array of Integers (0 and 1) representing a row of two-colored knitting stitches in a mosaic block. Instance variables: previousRow the row before this one baseColor 1=black; 0=white as in Form masks. The baseColor for this row. Class variables: Rand number generator for determining the color of unconstrained stitches ' Row methodsFor: 'accessing' baseColor "1=black; 0=white" ^baseColor Row methodsFor: 'next row generation' nextRow ^self class new: self size lastRow: self blackOrWhite: self contrastColor Row methodsFor: 'color accessing' addBaseColorAt: index self at: index put: self baseColor addContrastColorAt: index self at: index put: self contrastColor addRandomColorAt: index Rand next < 0.5 ifTrue: [self addBaseColorAt: index] ifFalse: [self addContrastColorAt: index]. contrastColor "Assuming the colors are 0 and 1, xor the baseColor with 1 to produce the contrasting color." ^(self baseColor bitXor: 1) contrastColorCanAppearAt: index "Indexes 1..index-1 of the receiver have been filled. Answer true only if adding a contrast color at the specified index would not violate the following constraints: 1) the first and last stitches must be the base color. 3) no more than two adjoining contrast colors 2) the contrast color must appear in the same spot in the row below since it has to be slipped, Otherwise answer false." (index <= 1 or: [index >= self size]) ifTrue: [^false]. "Assert: index is in the range 2 .. self size - 1." (previousRow at: index) = self contrastColor ifFalse: [^false]. "Assert: the previous row contains the contrasting color at this index." index < 4 ifTrue: ["Assert: index is 2 or 3; no more than 2 consecutive contrasting colors appear." ^true]. (self at: index - 1) = self baseColor ifTrue: [^true]. "Assert: previous color was a contrast color. Check the one before that. If it was the baseColor, answer true; false otherwise." ^(self at: index - 2) = self baseColor Row methodsFor: 'row accessing' firstRow "This is the first row. Generate a random pattern for all but the first and last stitches which have to be the baseColor." self initRow. 2 to: self size - 1 do: [:index | self addRandomColorAt: index] initRow "Fill in the first and last stitches, constrained to be the baseColor." self addBaseColorAt: 1. self addBaseColorAt: self size subsequentRow "This is not the first row. Generate a constrained yet random pattern for all but the first and last stitches which have to be the baseColor." self initRow. 2 to: self size - 1 do: [:index | (self contrastColorCanAppearAt: index) ifTrue: [self addRandomColorAt: index] ifFalse: [self addBaseColorAt: index]]. Row methodsFor: 'private' setLastRow: lastRow blackOrWhite: flag "1=black; 0=white" previousRow _ lastRow. baseColor _ flag. Rand _ Random new. previousRow isNil ifTrue: [self firstRow] ifFalse: [self subsequentRow] Row class methodsFor: 'instance creation' new: rowSize lastRow: lastRow blackOrWhite: flag | row | row _ super new: rowSize. row setLastRow: lastRow blackOrWhite: flag. ^row Row class methodsFor: 'class initialization' initialize "Row initialize" Rand _ Random new Row class methodsFor: 'constants' randomColor ^Rand next < 0.5 ifTrue: [0] ifFalse: [1] Array variableSubclass: #Mosaic instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'Mosaic-Support' Mosaic comment: 'Mosaic knitting is a special kind of two color knitting where only one color is actively used in each row. Contrasting stitches that appear in that row must therefore slipped from the row below. The active color is alternated with each row and the first and last stitches must be worked in that color. Since slipping a stitch from the row below results in a float of the active color on the wrong side, another constraint commonly placed on mosaic knitting is that no more than two consecutive constrasting stitches may appear together to minimize the length of the floats. This class is a subclass of Array. It holds a collection of Rows.' Mosaic methodsFor: 'filling board' fillRowsOfSize: rowSize "Fill the receiver with rows of size rowSize." | aRow | self size = 0 ifTrue: [^self]. self at: 1 put: (aRow _ Row new: rowSize lastRow: nil blackOrWhite: Row randomColor). 2 to: self size do: [:index | self at: index put: (aRow _ aRow nextRow)] Mosaic methodsFor: 'printing' printOn: aStream "Print out in reverse order: knitters read the first row on the bottom of the chart." self reverse do: [:each | each printOn: aStream] andBetweenDo: [aStream cr]. Mosaic class methodsFor: 'instance creation' rows: numberOfRows columns: rowSize "Mosaic rows: 6 columns: 6" ^(super new: numberOfRows) fillRowsOfSize: rowSize Listing 2: Mosaic program in C++ :::::::::::: : mosaic.h : :::::::::::: // Mosaic knitting is a special kind of two color knitting where only one // color is actively used in each row. Contrasting stitches that appear // in that row must therefore slipped from the row below. The active color // is alternated with each row and the first and last stitches must be // worked in that color. Since slipping a stitch from the row below // results in a float of the active color on the wrong side, another // constraint commonly placed on mosaic knitting is that no more than two // consecutive constrasting stitches may appear together to minimize the // length of the floats. extern "C" int random(); // color definitions representing two contrasting colors enum color {white, black}; const int nil = 0; // Class intArray // Implements a dynamic array of integers. class intArray { public: int size; // size of intArray int* contents; // the intArray itself void print(); intArray(int arraySize); ~intArray() {delete contents;}; }; // Class Row // Implements a dynamic array of stitches. class Row : public intArray { private: int baseColor; Row* previousRow; // pointer to previousRow int contrastColor(); void firstRow(); void subsequentRow(); void addBaseColorAt(int index); void addContrastColorAt(int index); void addRandomColorAt(int index); void initRow(); int contrastColorCanAppearAt(int index); public: Row(int rowSize, Row* lastRow, int flag); Row* nextRow(); }; // class RowArray // Implements a dynamic array of pointers to rows class RowArray { public: int size; // size of the Array Row** rows; // the rowArray itself void print(); RowArray(int size); ~RowArray(); }; // class mosaic // Adds behavior to RowArray to initialize, fill, and print the mosaic pattern. class mosaic: public RowArray { public: void print(); mosaic(int numberOfRows, int rowSize); }; #include :::::::::::: : mosaic.c : :::::::::::: // This program produces valid mosaic knitting patterns. The user is prompted // for the number of rows in the pattern and the number of stitches in each // row. The pattern is influenced randomly subject to certain constraints. #include "mosaic.h" // Class intArray // Implements a dynamic array of integers. intArray::intArray(int arraySize) { contents = new int[arraySize]; size = arraySize ; }; void intArray::print() { // Print an ascii representation of the receiver on stdout. for (int i=0; ibaseColor ^ 1; }; Row::Row(int rowSize, Row* lastRow, int flag) : (rowSize) { previousRow = lastRow; baseColor = flag; if (!previousRow) firstRow(); else this->subsequentRow(); }; void Row::firstRow() // This is the first row. Generate a random pattern for all but the first // and last stitches which have to be the baseColor. { initRow(); for (int i=1; i= size - 2)) return 0; // Assert: index is in the range 2 .. self size - 1. if (!(previousRow->contents[index] == contrastColor())) return 0; // Assert: the previous row contains the contrasting color at this index." if (index < 3) // Assert: index is 2 or 3; no more than 2 consecutive contrasting colors appear. return 1; if (contents[index - 1] == baseColor) return 1; // Assert: previous color was a contrast color. // Check the one before that. If it was the baseColor, answer true; false otherwise. return contents[index - 2] == baseColor; }; // class RowArray // Implements a dynamic array of pointers to rows RowArray::RowArray(int arraySize) { rows = new Row* [arraySize]; size = arraySize; }; RowArray::~RowArray() { for (int i=0; i= 0; i--) { if (i < 9) cout << " "; cout << i + 1 << " "; rows[i]->print(); } cout << "\n"; }; mosaic::mosaic(int numberOfRows, int rowSize) : (numberOfRows) { if (size == 0) return; Row* aRow = new Row((int) rowSize, (Row*) 0, random()&01); rows[0] = aRow; for (int i=1; i < size; i++) { aRow = aRow->nextRow(); rows[i] = aRow;} }; main() // generate and print the mosaic pattern. { mosaic* mos = new mosaic(1000, 1000); // mos->print(); }; Listing 3: Mosaic program in Eiffel ::::::::::::: : mosaic.e : ::::::::::::: class MOSAIC export black, white inherit ARRAY[ROW] rename Create as array_Create; STD_FILES feature black: INTEGER is 1; white: INTEGER is 0; printBoard is local i: INTEGER do from i := upper --invariant -- i_2_big: i <= upper; i_2_small: i >= lower - 1; --variant -- i_not_decreasing: i until i < lower loop if not entry(i).Void then if i < 10 then output.putchar(' ') end; -- if output.putint(i); entry(i).printOn(output) end; -- if i := i - 1 end -- loop end; --printBoard rand: RANDOM is -- Return a pointer to the sole instance of RANDOM once Result.Create; end; -- rand Create is local i: INTEGER; color: INTEGER; r,previousRow: ROW do color := rand.dont_care; array_Create(1,1000); from i := lower --invariant -- i_2_small: i >= lower; i_2_big: i <= upper + 1 --variant -- i_not_increasing: upper - i + 1 until i > upper loop r.Create(previousRow, color, size); enter(i, r); previousRow := r; i := i + 1; if color = black then color := white; else color := black end -- if end; -- loop --printBoard; end -- Create end; -- MOSAIC ::::::::::::: : row.e : ::::::::::::: class ROW export printOn inherit ARRAY[INTEGER] rename Create as array_create; RANDOM; STD_FILES feature previousRow: ROW; baseColor: INTEGER; printOn(io: FILE) is local i: INTEGER do io.putchar(' '); from i := lower until i > upper loop io.putint(entry(i)); i := i + 1; end; -- loop io.new_line end; -- printOn initRow is do enter(lower, baseColor); enter(upper, baseColor) end; -- initRow firstRow is -- I'm the first row and can be any pattern I like. local i: INTEGER do initRow; from i := lower+1 until i = upper loop enter(i, dont_care); i := i + 1 end -- loop end; -- firstRow subsequentRow is -- I have to color myself based on the pattern of the previous row. local i: INTEGER do initRow; from i := lower+1 until i = upper loop if contrastColorCanAppearAt(i) then enter(i, dont_care) else enter(i, baseColor) end; -- if i := i + 1; end; -- loop end; -- subsequentRow contrastColorCanAppearAt(i: INTEGER): BOOLEAN is do Result := (i > lower and i < upper) -- can't change the first or last stitch and then (previousRow.entry(i) /= baseColor) -- contrast color can only appear here if it's in the row below and then (i <= lower + 2 or else (entry(i-1) = baseColor or entry(i-2) = baseColor)); -- no more than 2 contrast colors together to minimize floats end; -- contrastColorCanAppearAt Create(lastrow: ROW; blackOrWhite: INTEGER, row_size: INTEGER) is do array_create(1, row_size); baseColor := blackOrWhite; previousRow := lastrow; if lastrow.Void then firstRow else subsequentRow end -- if end -- Create end -- ROW ::::::::::::: : random.e : ::::::::::::: class RANDOM -- Randomly return 1 or 0 each time dont_care is called export dont_care feature dont_care: INTEGER is external randbit: INTEGER name "randbit" language "C" do Result := randbit; end -- dont_care; end -- random ::::::::::::: : randbit.c : ::::::::::::: extern int random(); int randbit() { return random() & 01; }