Basic Costs

Fine-grained address translation techniques usually incur some inherent costs due to their basic implementation strategy. These costs can be divided into the usual time and space components, as well as less tangible components related to implementation complexity. We believe that these costs are likely to be on the order of tens of percent, even in well-engineered systems with custom compilers and fine-tuned run-time systems. Some of the typical costs incurred in a fine-grained approach are as follows:

• A major component of the total cost can be attributed to pointer validity checks. These checks can include both swizzling checks and residency checks. A swizzling check is used to verify whether a reference is translated into valid local format or not⁸ while a residency check verifies whether the referent is resident and accessible. These two checks, while conceptually independent of each other, are typically combined in implementations of fine-grained schemes.
• Another important component of the overall cost is related to the implementation of a custom object replacement policy, which is typically required because physical memory is directly managed by the persistence mechanism. This cost is usually directly proportional to the rate of execution because it requires a read barrier.⁹ We discuss this further in the next subsection.
• As resident objects are evicted from memory, a proportional cost is usually incurred in invalidating references to the evicted objects. This is necessary for maintaining referential integrity by avoiding ``dangling pointers.'' This cost is directly proportional to the rate of eviction and locality characteristics of the application.
• By definition, fine-grained translation techniques permit references to be in different formats during application execution. This requires that pointers be checked to ensure that they are in the right format before they can be used, even for simple equality checks. It may also be necessary to check transient pointers, depending on the underlying implementation strategy. As such, there is a continual pointer format checking cost that is also dependent on the rate of execution and pointer use.
• Finally, it is possible to incur other costs that exist mainly because of unusually constrained object and/or pointer representations used by the system. For example, accessing an object through an indirection via a proxy object is likely to require additional instructions.¹⁰ Another example is the increased complexity required for handling languages features such as interior pointers.¹¹

Note that all cost factors described above do not necessarily contribute to the overall performance penalty in every fine-grained address translation mechanism. However, the basic costs are usually present in some form in most systems.

Footnotes

... not⁸

For example, all swizzled pointers in Texas must contain valid virtual memory address values.

... barrier.⁹

The term read barrier, borrowed from garbage collection research [22], is used to denote a trigger that is activated on every read operation. A corresponding term, write barrier, is used to denote triggers that are activated for every write operation.

... instructions.¹⁰

Some systems use crude replacement and/or checkpointing policies to simplify integration with persistence and garbage collection mechanisms. These may incur additional costs due to the choice of suboptimal policies.

... pointers.¹¹

Interior pointers are those that point inside the bodies of objects rather than at their heads.