In some areas of the system, related data items were linked using a singly linked list. A singly linked list is one in which each data object contains a link field which points to the next data object. In a doubly linked list each data object contains two link fields, one which points to the next data object and a second which points to the previous data object. On smaller systems, where the length of a list tends to be shorter, the time taken to traverse a list is not significant. On a large system, however, the increased length of a list means that more time is required for adding or removing a particular item on the list. Having the list doubly linked enables the thread to traverse the list in either direction quickening the addition or removal of a particular item.
The cost of launching a new process, known as a fork, was also a prime area for improvement. When the system is asked to fork a child process, a number of resources must be constructed for the use of this process. Typically, some of these are constructed immediately while others are setup at the child process' first access of a resource such as memory. This is known as "faulting in" the memory. However a memory fault is a fairly expensive operation in terms of machine cycles compared to allocating some memory resources at the time of the fork. This enhancement is very noticeable in large commercial systems which require a large number of processes.
Another area for improvement is the hashing functions that are used to store and retrieve data objects. A hash function is one which takes some component of the data object and performs a calculation upon it. The result of this calculation is an index which is used to determine to which list within the hash table the data should be placed. A hash function that does not balance the number of entries within each list, thereby leading to increased hash collisions. Hash collisions occur when multiple data objects occupy the same list.
An efficient hash function will attempt to reduce the number of hash collisions by balancing the number of items in all of the hash tables. Increasing the width of the hash table can reduce collisions. Statistically, generating a random table entry would tend to balance the lengths of the tables, but one can exploit the nonrandom properties of the actual data to ensure even fewer collisions than truly random keys would produce.
