kimr@eiffel.UUCP (Kim Rochat) (03/23/90)
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 <Row> the row before this one
baseColor <anInteger> 1=black; 0=white as in Form masks.
The baseColor for this row.
Class variables:
Rand <Random> 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 <stream.h>
::::::::::::
: 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; i<size; i++) {
cout << contents[i];
};
cout << "\n";
};
// Class Row
// Implements a dynamic array of stitches.
Row* Row::nextRow()
{
Row* tmp = new Row (size, this, contrastColor());
return tmp;
};
int Row::contrastColor()
{
return this->baseColor ^ 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-1; i++)
addRandomColorAt(i);
};
void Row::addBaseColorAt(int index)
{
contents[index] = baseColor;
};
void Row::addContrastColorAt(int index)
{
contents[index] = contrastColor();
};
void Row::addRandomColorAt(int index)
{
if (random()&01)
addBaseColorAt(index);
else addContrastColorAt(index);
};
void Row::initRow()
// Fill in the first and last stitches, constrained to be the baseColor.
{
addBaseColorAt(0);
addBaseColorAt(size -1);
};
void Row::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.
{
initRow();
for (int i=1; i<size-1; i++)
if (contrastColorCanAppearAt(i))
addRandomColorAt(i);
else addBaseColorAt(i);
};
int Row::contrastColorCanAppearAt(int index)
{
// Indexes 0..index-1 of the receiver have been filled.
// Answer true (1) 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.
// 2) no more than two adjoining contrast colors
// 3) the contrast color must appear in the same spot in the row
// below since it has to be slipped,
// Otherwise answer false (0)
if ((index <= 0) || (index >= 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<size; i++)
delete rows[i];
}
// class mosaic
// Adds behavior to RowArray to initialize, fill, and print the mosaic pattern.
void mosaic::print()
{
// Print out in reverse order: knitters expect the first row to be on
// the bottom of the chart.
for (int i = size - 1; 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;
}jjc@jclark.UUCP (James Clark) (03/23/90)
In article <274@eiffel.UUCP>, kimr@eiffel.UUCP (Kim Rochat) presents
implementations of a small program in Eiffel, C++ and Smalltalk-80,
compares the performance of the implementations, and concludes
(amongst other things) that
any perception that C++ has superior performance to Eiffel may
be invalid.
It appears to me that the comparison between C++ and Eiffel is
vitiated by a failure to make any use of inline functions in the C++
version of the program.
I modified the C++ version of the program to make use of inline
functions. I compared the original version of the program against the
version which used inlining. I also compared it with another version
which additionally replaced the heavily used random() function by a
simple inline random number generator. As well as declaring functions
inline, it was necessary to reorder the function definitions and to
make a cosmetic change to one function to work around a limitation in
cfront's inlining capabilities.
I performed the comparison on a Sun 4/370 and on a 386 PC. On the Sun
4 I used both cfront 2.0 and g++ 1.37.1; I found no measurable
difference in performance. On the 386 I used only g++ 1.37.1. Also on
the 386 I used a 700 by 700 pattern, since the machine had only 4M of
RAM, and the 1000 by 1000 pattern caused it to thrash.
User Sys Real
Sun 4, w/o inline 5.8 .7 6.6
Sun 4, with inline 4.7 .6 5.4
Sun 4, with inline & 3.8 .6 4.6
inline random()
386, w/o inline 12.5 .6 13.4
386, with inline 6.4 .6 7.3
386, with inline & 5.8 .6 6.7
inline random()
The use of inline also resulted in a small decrease in the size of the
executables.
I should be glad to provide the modified version of the program to
anybody who wants it.
James Clark
jjc@jclark.uucpark@alice.UUCP (Andrew Koenig) (03/24/90)
In article <274@eiffel.UUCP>, kimr@eiffel.UUCP (Kim Rochat) writes: > 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. I thought it would be interesting to see what could be done trivially to speed up the C++ version of this program, so I profiled it. My machine does not have the Berkeley random() function, so I substituted an equivalent function, nrand() from our local C library. I found the following front-runners: %time function 20 Row::contrastColorCanAppearAt 17 nrand 15 Row::subsequentRow 11 Row::contrastColor 10 mcount (the C profiler itself!) 10 Row::addRandomColorAt 8 Row::addBaseColorAt 3 Row::addContrastColorAt Of the six C++ functions shown here, four of them were so short that many C++ programmers would have written them as inline as a matter of routine, namely Row::contrastColor, Row::addRandomColorAt, Row::addBaseColorAt, and Row::addContrastColorAt. Row::subsequentRow was not called many times and Row::contrastColorCanAppearAt was fairly large, so inlining wouldn't help either of these much. With these trivial changes, the run time on my machine (a MicroVax II) went from 161 to 100 seconds (timed without profiling). Profiling the revised program showed 30% spent in nrand, which suggests that it would be hard to obtain further dramatic improvement without first obtaining a faster random number generator. -- --Andrew Koenig ark@europa.att.com
khaw@parcplace.com (Mike Khaw) (03/27/90)
I'm posting this for Peter Deutsch, ParcPlace Systems' Chief Scientist:
----------
In <274@eiffel.UUCP> of comp.lang.eiffel, Kim and Roxanna Rochat of ISE
(formerly Tektronix) posted some numbers regarding the performance of a
simple integer and array manipulation program in C++, Eiffel, and
Smalltalk-80. They point out that the choice of C compiler can have as
much as a 30% influence on the measured time for the Eiffel
implementation. Taking their observation to heart, I measured the
performance of their program on a different Smalltalk-80
implementation: Objectworks for Smalltalk-80, version 2.5, from
ParcPlace Systems. I used the same hardware (diskless Sun-3/60 with 12
Mb of RAM, running SunOS 4.0.3) as they reported. The result was:
Sun Smalltalk Ow/ST-80,v2.5 240
[Just to confirm that our numbers are comparable to those posted by
the Rochats, I compiled mosaic.c using ATT's 2.0 C++ cfront and Sun's
cc, with "-O -Bstatic" flags, and matched their 41 sec. time on the
same machine that we ran the Smalltalk version on. -- Mike Khaw]
This is approximately a factor of 6 slower than the fastest, and a
factor of about 4 slower than the slowest, of the C++ and Eiffel
results, and a factor of about 12 faster than the Tek Smalltalk figure
(correcting for the roughly 25% difference in machine speed). Not bad
for a language that is often (inaccurately) slandered as being
"interpretive" and too slow to use for real work.
After reading Andrew Koenig's posting, it seemed reasonable to us that if
he could modify the program in ways that any reasonably experienced C++
programmer would, we could modify it in ways that a reasonably experienced
Smalltalk programmer would. Most of the time goes into the random number
calculation, and most of that time goes into the floating point arithmetic,
which is very slow in Smalltalk. So we modified the program by adding a
new message to Random that returns a random boolean, avoiding the floating
point. We replaced the two uses of 'Rand next < 0.5' in the Mosaic program
by 'Rand nextBoolean'. Here is the new method, and the revised timing
results:
Random methodsFor: 'accessing'
nextBoolean
"Answer the next random Boolean."
^self step < (modulus bitShift: -1)
This change cut the measured time from 240 seconds to 175.
Some may argue that adding code to a library class is not a legitimate way
to improve the performance of a program. We take the view that given the
"all source code available" culture promoted by the Smalltalk-80 system,
adding methods to library classes is natural and appropriate; we believe
that extending this culture to other languages would benefit the user
community greatly.
I would like to thank the authors for posting their test code in the
article.
----------
--
Mike Khaw
ParcPlace Systems, Inc., 1550 Plymouth St., Mountain View, CA 94043
Domain=khaw@parcplace.com, UUCP=...!{uunet,sun,decwrl}!parcplace!khawjamiller@hpcupt1.HP.COM (Jim Miller) (03/27/90)
>------------------------------------------------------------------------------ > 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 ... >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. Wait A minute. Eiffel is faster AND slower. It's just about the BEST and the WORST on both machines. It is very interesting data, thanks. jim miller
kimr@eiffel.UUCP (Kim Rochat) (03/29/90)
In article <10617@alice.UUCP>, ark@alice.UUCP (Andrew Koenig) writes: > Of the six C++ functions shown (below), four of them were so short that > many C++ programmers would have written them as inline as a matter of > routine, namely Row::contrastColor, Row::addRandomColorAt, > Row::addBaseColorAt, and Row::addContrastColorAt. The Eiffel and C++ benchmarks were intended to be constructed to make the same number of function calls, so as not to be comparing the function call overhead of the various machines. In reviewing the benchmarks, it appears that I didn't quite succeed. Looking only at the inner loop of subsequentRow, where the vast majority of the time is spent, the following diagram is an attempt to convey the call structure of each routine. Horizontal lines indicate entering a new function. C++ Eiffel subsequentRow subsequentRow ----------------------------- ----------------------------- if contrastColorCanAppearAt then if contrastColorCanAppearAt then addRandomColorAt dont_care ----------------------------- ----------------------------- if random then randbit addBaseColorAt -------------- else addContrastColorAt random ----------------------- -------------- ContrastColor <no correspondence> ----------------------- ----------------------------- else addBaseColorAt else <no correspondence> ----------------------------- ----------------------------- There are no function calls in the Eiffel code corresponding to the C++ calls to ContrastColorAt or the conditional calls to addBaseColorAt by subsequentRow. As ark implies, the benchmarks would have been fairer if these two routines had been inlined. This entire discussion brings up another interesting topic, which is how can you tell how many function calls you're generating with your code? Under C++, inlining is directly under programmer control. With Eiffel, it's under the control of the compiler and optimizer. For example, I don't count calls to "enter" and "entry" for the Eiffel code, since I happen to know that the compiler inlined" them. Since I used C package generation for Eiffel, the compiler also ran an optimizer which analyzes routines and inlines suitable candidates. In reviewing what the compiler actually did, it chose to inline the routines "firstrow" and "subsequentRow". Their omission accounts for only 1000 calls out of several million. As the readers of the original article pointed out, any of the three versions of the program could be further optimized for improved performance. The authors were attempting to benchmark obvious implementations of the algorithm - i.e. versions which conform to the spirit and style of each language without any iterations tuning performance. Ark might suggest that we didn't conform to the spirit of C++ because we didn't use inline functions. I accept that criticism with the defense that we didn't use them because our local style guidelines suggested that inlines not be used for C++, both because they violate encapsulation by placing implementation in the header files, and because inlining was unreliable under cfront 2.1, under which the C++ version was first developed. I'd like to thank everyone for their comments on the article and reports on subsequent experiments. I regret that I cannot revise my benchmark results due to a change in employment. Kim Rochat Interactive Software Engineering kimr@eiffel.com
jos@cs.vu.nl (Jos Warmer) (03/29/90)
kimr@eiffel.UUCP (Kim Rochat) writes: > Under C++, inlining is directly under programmer control. Isn't it more correct to state that it is under more programmer control. If a programmer makes a function inline, it is only a hint to the compiler. The C++ compiler does not have to inline each occurrence. This was the situation with version 1.2 of the AT&T translator, I don't know the situation with newer versions. Jos Warmer jos@cs.vu.nl