Memory Management Glossary: W

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

weak-key hash table

A hash table which has weak references (1) to its keys. If the key dies, the value for that key is automatically deleted from the table too. It can be used to store extra information about objects without keeping them alive.

In the MPS

See AWL (Automatic Weak Linked).

weak-value hash table

A hash table which has weak references (1) to its value. If the value dies, any keys that refer to that value are automatically deleted from the table too. It can be used to index a set of objects without keeping them alive.

In the MPS

See AWL (Automatic Weak Linked).

weak hash table

A weak-key or weak-value hash table (usually the former).

weak reference(1)

In tracing garbage collection, a weak reference is a reference that does not keep the object it refers to alive.

A weak reference does not keep the referent alive, but it will continue to refer to the object as long as it remains otherwise alive. When only weak references to the object remain, the weak references can be deleted (“splatted” or “cleared”) and the object reclaimed.

Java offers three kinds of weak references, called soft references, weak references (2), and phantom references, in order of increasing weakness.

Opposite term

strong reference.

See also

weak root.

weak reference(2)

In Java terminology, weak reference is used to mean a reference encapsulated in a reference object of class WeakReference.

Weak references form one of three kinds of weak reference (1) in Java. They are handy for associating extra data with objects when you cannot store it in the objects themselves.

See also

weakly reachable.

weak root

A weak root is a root, such that all references in it are weak references (1); that is, they do not affect the liveness of the objects referred to.

Opposite term

strong root.

In the MPS

A weak root has rank mps_rank_weak().

weak tri-color invariant
weak tri-colour invariant
weak tricolor invariant
weak tricolour invariant

The weak tri-color invariant is the property of a reference graph that all white nodes pointed to by a black node are also reachable from some gray node through a chain of white nodes.

By preserving this property throughout tri-color marking, a tracing algorithm can ensure that the collector (2) will not miss reachable objects, even if the mutator manipulates the graph during the collection. Mutator actions might need to change the color of the nodes affected in order to preserve the invariant.

Algorithms using this invariant are snapshot-at-the-beginning algorithms.

Related publications

Johnstone (1997), Pirinen (1998).

weakly reachable

In Java, an object is weakly reachable if it is neither strongly nor softly reachable and there is a path from the roots to it that contains at least one weak reference (2) but no phantom references.

When the Java collector (1) determines that an object is weakly reachable, it clears all the weak references involved, and declares the object finalizable. (Operationally, finalization works as if it was implemented by a class of “final references” that stand between weak and phantom references.) Also, the reference objects containing the weak references are enqueued, if they were registered with a queue.

weighted buddies

A buddy system allocation mechanism using two series of size classes: binary buddies (2, 4, 8, …) and three-times-power-of-two (3, 6, 12, …). A block that is in the latter series may be split in two different ways. Thus a block of size 12 may be split into two blocks of size 6 or one block of size 4 and one block of size 8. The same applies for coalescing. This gives this system more flexibility than a regular buddy system.

Related publication

Wilson et al. (1995).

weighted reference counting

A technique for reference counting which is in common use for distributed garbage collection because of the low level of inter-process communication it requires.

Inter-process references to objects are counted, but instead of simply counting the number of references, each reference is given a weight. When an object is created, the initial pointer to it is assigned a weight, which is usually a power of 2 for easy division. The object records the sum of all the weights of all of its references. Whenever a reference is copied, its weight is divided equally between the new and original copies. Since this operation preserves the weighted reference sum, there is no need for communication with the object at this time. When a reference is deleted, the weighted reference sum is decremented by the weight of the reference. This is communicated to the object by sending it a message. When the object detects that the weighted reference sum has dropped to zero, it may be reclaimed. The algorithm is tolerant of communication protocols which don’t guarantee order of arrival of deletion messages.

white

In a tri-color marking scheme, white objects are objects that were condemned at the beginning of the collection cycle and have not been shown to be reachable. When tracing is complete, white objects will be subject to reclamation.

Opposite terms

gray, black.

word

Also known as

machine word.

Almost all processor architectures have a characteristic data size that is handled most efficiently. This is known as the word size, and data of that size are known as words. The word size is usually a power of two multiple of bytes (2).

Often the platform’s word size is used to characterize the architecture by quoting the number of bits in it. For example, a 32-bit platform has a word size of four bytes and a 64-bit platform has eight-byte words (assuming 8-bit bytes). Typically, pointers are the size of a word, and traditionally this determined the word size. Nowadays, word size is usually driven by the need for more accuracy and range in mathematical calculations.

Historical note

In the past, the convenience of dealing with powers of two was not as significant, and word sizes such as 36- or 72-bits were not unknown.

See also

alignment, grain.

working set

The working set of a program or system is that memory (2) or set of addresses which it will use in the near future.

This term is generally used when discussing miss rates at some storage level; the time scale of “near future” depends upon the cost of a miss. The working set should fit in the storage level; otherwise the system may thrash.

Related publication

Denning & Schwartz (1972).

worst fit

The allocation policy that always allocates from the largest free block. Commonly implemented using a size-ordered free block chain (largest first).

In practice, this tends to work quite badly because it eliminates all large blocks, so large requests cannot be met.

Related publication

Wilson et al. (1995).

wrapped

A value is wrapped if it is encoded with type information.

Opposite term

unwrapped.

See also

wrapper, boxed, tag.

Related publication

Gudeman (1993).

wrapper

A wrapper is that part of a wrapped representation that is copied when the value is passed by value.

The wrapper does not include parts of the representation that are accessed indirectly, and are not copied when the value is passed.

For instance, a Lisp implementation might use the top two bits of a value representation as a tag to distinguish between integers and cons (1) cells, setting these bits to 01 for a pointer to a cons cell and 11 for an integer. Then the wrapped value of the number 4 would have binary representation 11000…00100, and the wrapper for this number is the whole of this wrapped value. The pointer to a cons cell stored at location 4 would have binary representation 01000…00100. The wrapped value of the cons cell is the combination of this pointer and the cons cell in memory itself. The wrapper of the cons cell is just the pointer; when the cons cell is passed as a function argument, just the pointer is passed.

See also

wrapped, boxed.

Related publication

Gudeman (1993).

write barrier

A write barrier (1) is a block on writing to certain memory (2) locations by certain threads or processes.

Relevance to memory management

Write barriers are used for incremental or concurrent garbage collection. They are also used to maintain remembered sets for generational collectors (1).

See also

read barrier.

write fault

An exception which occurs when writing to an address in virtual memory.

This is probably either a page fault, an invalid page fault or a protection fault.

Similar term

segmentation violation.

See also

read fault.