diff options
| author | John Naylor <john.naylor@postgresql.org> | 2024-04-08 18:54:35 +0700 |
|---|---|---|
| committer | John Naylor <john.naylor@postgresql.org> | 2024-04-08 18:54:35 +0700 |
| commit | 0fe5f64367bc2fc70baa1f0f993638830f8aa6a5 (patch) | |
| tree | 82bcd215954af3b3063ee0018468f4da6b078ca9 /src/include/lib/radixtree.h | |
| parent | f35bd9bf359d3d740063997e1cbab9b69df7af99 (diff) | |
| download | postgresql-0fe5f64367bc2fc70baa1f0f993638830f8aa6a5.tar.gz postgresql-0fe5f64367bc2fc70baa1f0f993638830f8aa6a5.zip | |
Teach radix tree to embed values at runtime
Previously, the decision to store values in leaves or within the child
pointer was made at compile time, with variable length values using
leaves by necessity. This commit allows introspecting the length of
variable length values at runtime for that decision. This requires
the ability to tell whether the last-level child pointer is actually
a value, so we use a pointer tag in the lowest level bit.
Use this in TID store. This entails adding a byte to the header to
reserve space for the tag. Commit f35bd9bf3 stores up to three offsets
within the header with no bitmap, and now the header can be embedded
as above. This reduces worst-case memory usage when TIDs are sparse.
Reviewed (in an earlier version) by Masahiko Sawada
Discussion: https://postgr.es/m/CANWCAZYw+_KAaUNruhJfE=h6WgtBKeDG32St8vBJBEY82bGVRQ@mail.gmail.com
Discussion: https://postgr.es/m/CAD21AoBci3Hujzijubomo1tdwH3XtQ9F89cTNQ4bsQijOmqnEw@mail.gmail.com
Diffstat (limited to 'src/include/lib/radixtree.h')
| -rw-r--r-- | src/include/lib/radixtree.h | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index 6764b58b52a..dc4c00d38a6 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -105,6 +105,10 @@ * involving a pointer to the value type, to calculate size. * NOTE: implies that the value is in fact variable-length, * so do not set for fixed-length values. + * - RT_RUNTIME_EMBEDDABLE_VALUE - for variable length values, allows + * storing the value in a child pointer slot, rather than as a single- + * value leaf, if small enough. This requires that the value, when + * read as a child pointer, can be tagged in the lowest bit. * * Optional parameters: * - RT_SHMEM - if defined, the radix tree is created in the DSA area @@ -437,7 +441,13 @@ static inline bool RT_VALUE_IS_EMBEDDABLE(RT_VALUE_TYPE * value_p) { #ifdef RT_VARLEN_VALUE_SIZE + +#ifdef RT_RUNTIME_EMBEDDABLE_VALUE + return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC); +#else return false; +#endif + #else return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC); #endif @@ -451,7 +461,19 @@ static inline bool RT_CHILDPTR_IS_VALUE(RT_PTR_ALLOC child) { #ifdef RT_VARLEN_VALUE_SIZE + +#ifdef RT_RUNTIME_EMBEDDABLE_VALUE + /* check for pointer tag */ +#ifdef RT_SHMEM + return child & 1; +#else + return ((uintptr_t) child) & 1; +#endif + +#else return false; +#endif + #else return sizeof(RT_VALUE_TYPE) <= sizeof(RT_PTR_ALLOC); #endif @@ -1729,6 +1751,15 @@ have_slot: { /* store value directly in child pointer slot */ memcpy(slot, value_p, value_sz); + +#ifdef RT_RUNTIME_EMBEDDABLE_VALUE + /* tag child pointer */ +#ifdef RT_SHMEM + *slot |= 1; +#else + *((uintptr_t *) slot) |= 1; +#endif +#endif } else { @@ -2888,6 +2919,7 @@ RT_DUMP_NODE(RT_NODE * node) #undef RT_DEFINE #undef RT_VALUE_TYPE #undef RT_VARLEN_VALUE_SIZE +#undef RT_RUNTIME_EMBEDDABLE_VALUE #undef RT_SHMEM #undef RT_USE_DELETE #undef RT_DEBUG |