This paper describes some basic experiments to see how fast various popular scripting and user-interface languages run on a spectrum of representative tasks. We found enormous variation in performance, depending on many factors, some uncontrollable and even unknowable. There seems to be little hope of predicting performance in other than a most general way; if there is a single clear conclusion, it is that no benchmark result should ever be taken at face value. A few general principles hold: Compiled code usually runs faster than interpreted code: the more a program has been ‘compiled’ before it is executed, the faster it will run. Memory-related issues and the effects of memory hierarchies are pervasive: how memory is managed, from hardware caches to garbage collection, can change runtimes dramatically. Yet users have no direct control over most aspects of memory management. The timing services provided by programs and operating systems are woefully inadequate. It is difficult to measure runtimes reliably and repeatably even for small, purely computational kernels, and it becomes significantly harder when a program does much I/O or graphics. Although each language shines in some situations, there are visible and sometimes surprising deficiencies even in what should be mainstream applications. We encountered more than a few bugs, size limitations, maladroit features, and total mysteries. © 1998 John Wiley & Sons, Ltd.

Geometric algorithmsare usually described assuming that arithmetic operations are performed exactly on real numbers.A program implemented using a naive substitution of floating-point arithmetic for real arithmetic can fail, since geometric primitives depend upon sign-evaluation and may not be reliable if evaluated approximately.Geometric primitives are reliable if evaluated exactly with integer arithmetic, but this degrades performance since software extended-precision arithmetic is required.We describe static-analysis techniques that reduce the performance cost of exact integer arithmetic used to implement geometric algorithms.We have used the techniques for a number of examples, including line-segment intersection in two dimensions, Delaunay triangulations, and a three-dimensional boundary-based polyhedral modeller.In general, the techniques are appropriate for algorithms that use primitives of relatively low algebraic total degree, e.g., those involving flat objects (points, lines, planes) in two or three dimensions.The techniques have been packaged in a preprocessor for reasonably convenient use.

We experiment with exact integer arithmetic to implement primitives for geometric algorithms. Naive use of exact arithmetic—either modular or multiprecision integer—increases execution time dramatically over the use of floating-point arithmetic. By combining tuned multiprecision integer arithmetic and a floating-point filter based on interval analysis, we can obtain the effect of exact integer arithmetic at a cost close to that of floating-point arithmetic. We describe an experimental expression compiler that conveniently packages our techniques.

Abstract Simultaneous equations arise naturally in problems from a variety of application areas. This paper describes how to use two object‐oriented features of C++—operator overloading and virtual functions—to allow a programmer to express and to solve a system of simultaneous equations directly in a C++ program.

Paint one side of a rubber disk black and the other side white; stretch the disk any way you wish in three-dimensional space, subject to the condition that from any point in space, if you look down you see either the white side of the disk or nothing at all. Now make the stretched disk transparent but color its boundary black; project its boundary into a plane that lies below the disk. The resulting curve is self-overlapping. We show how to test whether a given curve is self-overlapping, and how to count how many essentially different stretchings of the disk could give rise to the same curve.

We present an algorithm that triangulates a simple polygon on n vertices in Ο(n log* n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into $n - 2$ triangles by adding $n - 3$ nonintersecting diagonals. We propose an $O(n\log \log n)$-time algorithm for this problem, improving on the previously best bound of $O(n\log n)$ and showing that triangulation is not as hard as sorting. Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.

In "A linear-time algorithm for triangulating a simple polygon" [Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), 380-388. 486], the analysis showing that the authors' triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far they have been unable to obtain a linear-time algorithm for the triangulation problem. They have been able to obtain an O(n loglogn)-time algorithm, however. The details are described in "An O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon," SIAM Journal on Computing 17, 1 (February, 1988), to appear.

Hashing with lazy deletion is a simple method for maintaining a dynamic dictionary: items are inserted and sought as usual in a separate-chaining hash table; however, items that no longer need to be in the data structure remain until a later insertion operation stumbles on them and removes them from the table. Because hashing with lazy deletion does not delete items as soon as possible, it keeps more items in the dictionary than methods that use more careful deletion strategies. On the other hand, its space overhead is much smaller than those more careful methods, so if the number of extra items is not too large, hashing with lazy deletion can be a practical algorithm when space is scarce. In this paper, we analyze the expected amount of excess space used by hashing with lazy deletion.

A simple polygon with n vertices is triangulated by adding to it n-3 line segments between its vertices that partition the interior of the polygon into triangles.We present an algorithm for triangulating a simple polygon in time proportional to its size.This result has a number of applications in computational geometry.

Abstract Although AWK is usually presented as a language for simple data retrieval and formatting, it is also well suited to writing program generators. This use gives AWK much more power as a means of communicating among programs than its usual role as reformatter suggests. This paper discusses features of AWK that are especially useful for program generation. As an extended example, it presents a complete AWK program for typesetting charts in TROFF documents.

We describe a method for inferring constraints that are desirable for a given (rough) drawing and then modifying the drawing to satisfy the constraints wherever possible. The method has been implemented as part of an online graphics editor running under the UNIX™ operating system and it has undergone modifications in response to user input. Although the framework we discuss is general, the current implementation is polygon-oriented. The relations examined are: approximate equality of the slope or length of sides, collinearity of sides, and vertical and horizontal alignment of points.

Abstract We discuss a simple algorithm for solving sets of simultaneous equations. The algorithm can solve systems of linear and some kinds of non‐linear equations, although it has nowhere near the power of a general non‐linear equation solver. Its principal advantages over more general algorithms are simplicity and speed. Versions of the algorithm have been used in a graphics language and in a system for interactively modifying the equations that constitute financial models. We discuss the second application in more detail here.

A programming language that includes special constructs for drawing pictures is discussed.The language has been designed so that programs to draw pictures can reflect the structure of those pictures.Picture elements are called boxes.They are defmed by declaring algebraic relationships that should exist among their significant points and requesting actions to be performed at those points.The algebraic relationships are processed by an equation solver to determine the absolute location of significant points.A new mechanism of variable reference and scope makes the expression of relationships that should exist among picture elements more direct than it is in conventional languages.Some common picture operations--drawing lines using a pattern, filling in areas with textures, and obscuring parts of a picture by other parts--are all expressed readily once the mechanism for defining and using boxes is in place.The language has been implemented, and used by several authors to prepare figures for their papers and books.It was also used to prepare this paper.