November 1977 - Vol. 20 No. 11

This paper reports simulation data showing that, in dynamic memory allocation, the average free-to-allocated-block ratio can differ considerably and in both directions from the predictions of the 50 percent rule. A new derivation is given, and it is shown that previous derivations make an assumption that may be violated frequently. On the basis of the simulation data and the derivation, it is hypothesized that the anomalous behavior results from the combined effects of systematic placement and the statistics of the release process. Additional simulations support this hypothesis. Systematic placement, which refers to the natural convention of always allocating storage requests against the same end of the free block selected by the allocation strategy, tends to order blocks within contiguous groups according to their allocation time. The degree of anomalous behavior depends on the extent to which allocated blocks are released in the order of their allocation. For non-Markovian release processes, the extent of the correlation between allocation order and release order varies approximately inversely with the coefficient of variation of the memory residence time distribution. The simulations show that allocation efficiency depends strongly on the residence time distribution; efficiency decreases as the distribution's coefficient of variation increases. Some practical implications are briefly discussed.

The population of programming languages is steadily growing, and there is no end of this growth in sight. Many language definitions appear in journals, many are found in technical reports, and perhaps an even greater number remains confined to proprietory circles. After frequent exposure to these definitions, one cannot fail to notice the lack of “common denominators.” The only widely accepted fact is that the language structure is defined by a syntax. But even notation for syntactic description eludes any commonly agreed standard form, although the underlying ancestor is invariably the Backus-Naur Form of the Algol 60 report. As variations are often only slight, they become annoying for their very lack of an apparent motivation.

Earlier it was shown by the present author [1] that among the classical algorithms for the generation of permutation sequences, only the Trotter-Johnson algorithm [2, 3] has the property that the reflection of any permutation in the first half of the enumeration appears only in the second half. Two permutations are called reflections of each other if one read from left to right is the same as the other read from right to left. Lenstra [4] has discussed the usefulness of this property in certain applications. Recently Ives [5] has produced a series of four permutation algorithms of which two (algorithms c and d) possess the said property.

The classical fixedpoint approach toward recursive programs suggests choosing the “least defined fixedpoint” as the most appropriate solution to a recursive program. A new approach is described which introduces an “optimal fixedpoint,” which, in contrast to the least defined fixedpoint, embodies the maximal amount of valuable information embedded in the program. The practical implications of this approach are discussed and techniques for proving properties of optimal fixedpoints are given. The presentation is informal, with emphasis on examples.

Application development today is too labor-intensive. In recent years, very high-level languages have been increasingly explored as a solution to this problem. The Business Definition Language (BDL) is such a language, one aimed at business data processing problems. The concepts in BDL mimic those which have evolved through the years in businesses using manual methods. This results in three different sublanguages or components: one for defining the business forms, one for describing the business organization, and one for writing calculations.

A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered. Given a set I of identifiers, two methods are presented for building, in a mechanical way, perfect hashing functions, i.e. functions transforming the elements of I into unique addresses. The first method, the “quotient reduction” method, is shown to be complete in the sense that for every set I the smallest table in which the elements of I can be stored and from which they can be retrieved by using a perfect hashing function constructed by this method can be found. However, for nonuniformly distributed sets, this method can give rather sparse tables. The second method, the “remainder reduction” method, is not complete in the above sense, but it seems to give minimal (or almost minimal) tables for every kind of set. The two techniques are applicable directly to small sets. Some methods to extend these results to larger sets are also presented. A rough comparison with ordinary hashing is given which shows that this method can be used conveniently in several practical applications.

A simple algorithm which uses an indexed temporary table to perform reduction of operator strength in strongly connected regions is presented. Several extensions, including linear function test replacement, are discussed. These algorithms should fit well into an integrated package of local optimization algorithms.

A new technique of program transformation, called “recursion introduction,” is described and applied to two algorithms which solve pattern matching problems. By using recursion introduction, algorithms which manipulate a stack are first translated into recursive algorithms in which no stack operations occur. These algorithms are then subjected to a second transformation, a method of recursion elimination called “tabulation,” to produce programs with a very efficient running time. In particular, it is shown how the fast linear pattern matching algorithm of Knuth, Morris, and Pratt can be derived in a few steps from a simple nonlinear stack algorithm.

e of 35 dynamic memory allocation algorithms when used to service simulation programs as represented by 18 test cases. Algorithm performance was measured in terms of processing time, memory usage, and external memory fragmentation. Algorithms maintaining separate free space lists for each size of memory block used tended to perform quite well compared with other algorithms. Simple algorithms operating on memory ordered lists (without any free list) performed surprisingly well. Algorithms employing power-of-two block sizes had favorable processing requirements but generally unfavorable memory usage. Algorithms employing LIFO, FIFO, or memory ordered free lists generally performed poorly compared with others.

Sequences of character strings with an order relation imposed between sequences are considered. An encoding scheme is described which produces a single, order-preserving string from a sequence of strings. The original sequence can be recovered from the encoded string, and one sequence of strings precedes another if and only if the encoding of the first precedes the encoding of the second. The strings may be variable length, without a maximum length restriction, and no symbols need be reserved for control purposes. Hence any symbol may occur in any string. The scheme is useful for multifield sorting, multifield indexing, and other applications where ordering on more than one field is important.

The file allocation problem — i.e. the problem of finding the optimal set of network sites at which to locate copies of a file — is known to be, in general, polynomial complete. Heuristics and other aids to finding optimal, or near-optimal, solutions are therefore much needed. In this paper we present three theorems which can be applied a priori to indicate that certain sites should (or should not) be included in an optimal allocation.