Pointer swizzling at page fault time usually provides good performance for most applications with good locality of reference. However, applications that exhibit poor locality of reference, especially those with large sparsely-accessed index data structures, may not produce best results with such coarse-grained translation mechanisms. Applications that access big multi-way index trees are a good example; usually, such applications sparsely access the index tree, that is, only a few paths are followed down from the root. If the tree nodes are large and have a high fanout, the first access to a node will cause all those pointers to be swizzled, and possibly reserve several pages of virtual address space. However, most of this swizzling is probably unnecessary since only a few pointers will be dereferenced.
The solution is to provide a fine-grained address translation mechanism which translates pointers individually, instead of doing it a page at a time. Unlike the coarse-grained mechanism where the swizzling was triggered by an access-protection violation, the actual translation of a pointer may be triggered by one of two events--either when it is ``found''15 or when it is dereferenced.
There are many ways of implementing a fine-grained (pointer-wise) address translation mechanism as we described above. We have selected an implementation strategy that remains consistent with our goals of portability and compatibility with existing off-the-shelf compilers, by using the C++ smart pointer abstraction [18,7,13]. Below, we first briefly explain this abstraction and then describe how we use it for implementing fine-grained translation in Texas. We also discuss how both fine-grained and coarse-grained schemes can coexist to create a mixed-granularity environment.