The deployment of Java as a concurrent programming language has created a critical need for high-performance, concurrent, and incremental multiprocessor garbage collection. We present the Recycler, a fully concurrent pure reference counting garbage collector that we have implemented in the Jalapeno Java virtual machine running on shared memory multiprocessors.While a variety of multiprocessor collectors have been proposed and some have been implemented, experimental data is limited and there is little quantitative basis for comparison between different algorithms. We present measurements of the Recycler and compare it against a non-concurrent but parallel load-balancing mark-and-sweep collector (that we also implemented in Jalapeno), and evaluate the classical tradeoff between response time and throughput.When processor or memory resources are limited, the Recycler runs at about 90% of the speed of the mark-and-sweep collector. However, with an extra processor to run collection and with a moderate amount of memory headroom, the Recycler is able to operate without ever blocking the mutators and achieves a maximum measured mutator delay of only 2.6 milliseconds for our benchmarks. End-to-end execution time is usually within 5%.

Jalape~no is a virtual machine for Java TM servers written in Java. A running Java program involves four layers of functionality: the user code, the virtual-machine, the operating system, and the hardware. By drawing the Java / non-Java boundary below the virtual machine rather than above it, Jalape~no reduces the boundary-crossing overhead and opens up more opportunities for optimization. To get Jalape~no started, a boot image of a working Jalape ~no virtual machine is concocted and written to a file. Later, this file can be loaded into memory and executed. Because the boot image consists entirely of Java objects, it can be concocted by a Java program that runs in any JVM. This program uses reflection to convert the boot image into Jalape~no's object format. A special Magic class allows unsafe casts and direct access to the hardware. Methods of this class are recognized by Jalape~no's three compilers, which ignore their bytecodes and emit special-purpose machine code. User code w...

This paper addresses a problem which arises during the design of an integrated data base: this is to generate a set of physical data structures capable of supporting a desired set of logical data structures. A prototype design aid which generates physical data structures for IMS is described. A state diagram is used to represent the constraints imposed by IMS, and a modified depth first tree search is used to find the physical data structures. One can force the solution to either satisfy bounds on one or more objective functions, and/or optimize a single objective function.

A nonparametric sequential pattern classifier called a linear sequential classifier (LSC) is presented. The pattern components are measured sequentially and the decisions either to measure the next component or to stop and classify the pattern are made using linear functions derived from sample patterns based on the least mean-square error criterion. The required linear functions are computed using an adaption of Greville's recursive algorithm for computing the generalized inverse of a matrix. A recursive algorithm for computing the least mean-square error is given and is used to determine the order in which the pattern components are measured. Under the assumption of two equiprobable classes that are normally distributed with equal covariance matrices, it is shown that the LSC is equivalent to Wald's sequential probability ratio test. Computer-simulated experiments indicate that the LSC is more effective than existing nonparametric sequential classifiers.