317
• Preventing compiler optimizations through the dereferencing
method. A complicated pointer translation might negatively impact
the compiler’s optimization passes. The translation method should
ideally avoid operations that depend on an external state because
that will prevent, among other things, auto-vectorization.
Satisfying the preceding requirements while maintaining low-overhead and C99
standard compliance is surprisingly difficult. We explored several options:
• The 8-byte offset pointer, relative to the beginning of the pool, was
quickly ruled out because it did not satisfy the second requirement
and needed a pool base pointer to be provided to the translation
method.
• 8-byte self-relative pointers, where the value of the pointer is the
offset between the object’s location and the pointer’s location. This
is potentially the fastest implementation because the translation
method can be implemented as `ptr + (*ptr)`. However, this does
not satisfy the second basic requirement. Additionally, it would
require a special assignment method because the value of the pointer
to the same object would differ depending on the pointer’s location.
• 8-byte offset pointers with embedded memory pool identifier,
which allows the library to satisfy the second requirement. This is
an augmentation of the first method that additionally stores the
identifier in the unused part of the pointer value by taking advantage
of the fact that the usable size of the virtual address space is smaller
than the size of the pointer on most modern CPUs. The problem with
this method, however, is that the number of bits for the pool identifier
is relatively small (16 bits on modern CPUs) and might shrink with
future hardware.
• 16-byte fat offset pointer with pool identifier. This is the most obvious
solution, which is similar to the one earlier but has 8-byte offset
pointers and 8-byte pool identifiers. Fat pointers provide the best
utility, at the cost of space overhead and some runtime performance.
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures
• Preventing compiler optimizations through the dereferencing
method. A complicated pointer translation might negatively impact
the compiler’s optimization passes. The translation method should
ideally avoid operations that depend on an external state because
that will prevent, among other things, auto-vectorization.
Satisfying the preceding requirements while maintaining low-overhead and C99
standard compliance is surprisingly difficult. We explored several options:
• The 8-byte offset pointer, relative to the beginning of the pool, was
quickly ruled out because it did not satisfy the second requirement
and needed a pool base pointer to be provided to the translation
method.
• 8-byte self-relative pointers, where the value of the pointer is the
offset between the object’s location and the pointer’s location. This
is potentially the fastest implementation because the translation
method can be implemented as `ptr + (*ptr)`. However, this does
not satisfy the second basic requirement. Additionally, it would
require a special assignment method because the value of the pointer
to the same object would differ depending on the pointer’s location.
• 8-byte offset pointers with embedded memory pool identifier,
which allows the library to satisfy the second requirement. This is
an augmentation of the first method that additionally stores the
identifier in the unused part of the pointer value by taking advantage
of the fact that the usable size of the virtual address space is smaller
than the size of the pointer on most modern CPUs. The problem with
this method, however, is that the number of bits for the pool identifier
is relatively small (16 bits on modern CPUs) and might shrink with
future hardware.
• 16-byte fat offset pointer with pool identifier. This is the most obvious
solution, which is similar to the one earlier but has 8-byte offset
pointers and 8-byte pool identifiers. Fat pointers provide the best
utility, at the cost of space overhead and some runtime performance.
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures