<p>Java has compressed oops, NodeJS has compressed pointers, they all use a common &quot;base&quot; address to encode/decode pointer values. There is an obvious downside: total heap size get rather limited.</p>
<p>As compressed pointers are stored in RAM, why not use a narrow (e.g. 32-bit) offset, relative to its own residential address, which is wide (e.g. 64-bit).</p>
<p>E.g. in C notation</p>
<pre class="lang-c prettyprint-override"><code>void* load_relptr(int32_t* a) {
  return (void*)(((int64_t)a) + *a);
}

void store_relptr(int32_t* a, void* p) {
  *a = (int32_t)(((int64_t)p) - a);
}
</code></pre>
<p>This way, wide pointers can be stored in RAM &quot;compressed&quot;, yet without the very heap-size limitation, and the cache is even free of a hot &quot;base&quot; address in encoding/decoding pointers.</p>
<p>Why not? I can't think of any downside of this &quot;relative&quot; encoding schema, compared to the Java/NodeJS approach (namely &quot;base&quot; encoding).</p>
<hr />
<p><a href="https://stackoverflow.com/questions/13549787/can-i-use-more-heap-than-32-gb-with-compressed-oops">https://stackoverflow.com/questions/13549787/can-i-use-more-heap-than-32-gb-with-compressed-oops</a></p>
<p><a href="https://v8.dev/blog/pointer-compression" rel="nofollow noreferrer">https://v8.dev/blog/pointer-compression</a></p>

<pointers>
Compressed pointers, why not "relative" rather than "base" encoding?
CC BY-SA 4.0
2024-06-12T17:03:36.290Z
The biggest downside is that you can no longer just copy most data types from one place to another; you have to do arithmetic to correct all the pointers. Likewise for comparing pointer equality.
kaya3
CC BY-SA 4.0
2024-06-12T17:09:02.810Z
Pointer-copying usually has to coop with ref-counting or garbage-collection, I don't see that can be done with mere `memcpy()` in a bulk manner, relative encoding would add minimum overhead there I'd expect.
Compl Yue
CC BY-SA 4.0
2024-06-12T17:11:14.880Z
Once loaded into registers, such "decompressed" ptrs are directly comparable as usual, I'd expect direct mem-mem comparison of ptrs to be rare.
Compl Yue
CC BY-SA 4.0
2024-06-12T17:21:45.633Z
You say "once loaded into registers", but you have to do arithmetic in order to do that loading.
kaya3
CC BY-SA 4.0
2024-06-12T18:02:25.560Z
There are relative jump instructions in the x86 instruction set. It's difficult to imagine how something could be more likely to refer to nearby data than data in the same array in other use cases.
user23013
CC BY-SA 4.0
2024-06-12T18:11:26.397Z
Relative *jumps* take advantage of the fact that jump destinations in machine code are fixed (do not change dynamically) and the reordering of basic blocks to optimise for relative jumps is done at compile-time, so it doesn't matter as much if it's slow.
kaya3
<blockquote>
<p>This way, wide pointers can be stored in RAM &quot;compressed&quot;, yet without the very heap-size limitation, and the cache is even free of a hot &quot;base&quot; address in encoding/decoding pointers.</p>
</blockquote>
<p>Unfortunately, the upside is not reliable enough to actually benefit from. Since &quot;relative&quot; pointers can't point to allocations more than 4GB away, objects must be allocated in such a pattern that such distant pointers are never needed. However, the allocator doesn't know ahead of time which objects will want to point at which addresses, so taking a pointer is now a potentially slow operation which requires reallocating objects to put them close enough together.</p>
<p>Not to mention, it's possible for this combinatorial problem to actually have no solution! Imagine you have an 8GB-large array of objects. The first object in the array simply cannot hold a pointer to the last one. So taking a pointer is now a fallible operation. Or imagine you have a slightly-larger than 8GB array of pointers; the middle one cannot point anywhere outside of the same array, and the first and last ones can't point to the same thing.</p>
<p>So practically speaking, you are still generally limited to 4GB of memory. At best, in specific cases you might be able to compute a memory layout at compile-time which, based on static type information, is guaranteed to never require pointers at long distances.</p>
<blockquote>
<p>Why not? I can't think of any downside of this &quot;relative&quot; encoding schema, compared to the Java/NodeJS approach (namely &quot;base&quot; encoding).</p>
</blockquote>
<p>The biggest downside is that you can no longer just copy most data types from one place to another; you have to do arithmetic to correct all the pointers. Likewise for comparing pointer equality.</p>
<p>In the comments you've said you don't think this is a big deal. It's true that copying memory often requires manipulating refcounts or GC metadata anyway; at least, this is true in languages which use reference counting or garbage collection (which is not all languages).</p>
<p>However, even in such languages there are many common operations which can be performed by copying memory without this extra overhead: when reallocating a <a href="https://en.wikipedia.org/wiki/Dynamic_array" rel="noreferrer">dynamic array</a>, rotating an array, moving portions of an array while sorting, or more generally any operation where the compiler can determine that a reference count increment will cancel out with a decrement.</p>
<p>For example, in the CPython source code for the <code>list</code> type, the function <a href="https://github.com/python/cpython/blob/127c1d2771749853e287632c086b6054212bf12a/Objects/listobject.c#L80" rel="noreferrer"><code>list_resize</code></a> performs a memory copy but does not invoke <code>Py_INCREF</code> or <code>Py_DECREF</code>. This function will be called very frequently, since any operation adding an element to a list could trigger a resize.</p>

CC BY-SA 4.0
2024-06-12T17:37:15.153Z
2024-06-12T17:42:57.847Z
2024-06-12T17:42:57.847Z
kaya3
CC BY-SA 4.0
2024-06-12T18:56:30.370Z
Yes, I realized that pointing to far-away address will still invoke the heap size limit, indeed.
Compl Yue
CC BY-SA 4.0
2024-06-13T11:21:10.160Z
"objects must be allocated in such a pattern that such distant pointers are never needed" – this rather reminds me of "near" and "far" pointers in 16-bit MS-DOS/Win3.x programming...
user1686
# Compressed pointers, why not "relative" rather than "base" encoding?
Posted by: username_0 on 2024-06-12
Java has compressed oops, NodeJS has compressed pointers, they all use a common "base" address to encode/decode pointer values. There is an obvious downside: total heap size get rather limited.
As compressed pointers are stored in RAM, why not use a narrow (e.g. 32-bit) offset, relative to its own residential address, which is wide (e.g. 64-bit).
E.g. in C notation
void* load_relptr(int32_t* a) {
  return (void*)(((int64_t)a) + *a);
}

void store_relptr(int32_t* a, void* p) {
  *a = (int32_t)(((int64_t)p) - a);
}

This way, wide pointers can be stored in RAM "compressed", yet without the very heap-size limitation, and the cache is even free of a hot "base" address in encoding/decoding pointers.
Why not? I can't think of any downside of this "relative" encoding schema, compared to the Java/NodeJS approach (namely "base" encoding).

https://stackoverflow.com/questions/13549787/can-i-use-more-heap-than-32-gb-with-compressed-oops
https://v8.dev/blog/pointer-compression
**Tags:** pointers
> **Comments:**
> **username_1**: The biggest downside is that you can no longer just copy most data types from one place to another; you have to do arithmetic to correct all the pointers. Likewise for comparing pointer equality.  
> **username_0**: Pointer-copying usually has to coop with ref-counting or garbage-collection, I don't see that can be done with mere `memcpy()` in a bulk manner, relative encoding would add minimum overhead there I'd expect.  
> **username_0**: Once loaded into registers, such "decompressed" ptrs are directly comparable as usual, I'd expect direct mem-mem comparison of ptrs to be rare.  
> **username_1**: You say "once loaded into registers", but you have to do arithmetic in order to do that loading.  
> **username_2**: There are relative jump instructions in the x86 instruction set. It's difficult to imagine how something could be more likely to refer to nearby data than data in the same array in other use cases.  
> **username_1**: Relative *jumps* take advantage of the fact that jump destinations in machine code are fixed (do not change dynamically) and the reordering of basic blocks to optimise for relative jumps is done at compile-time, so it doesn't matter as much if it's slow.  
---
## 1 answers
### Answer by username_1 on 2024-06-12. Score: 5
> This way, wide pointers can be stored in RAM "compressed", yet without the very heap-size limitation, and the cache is even free of a hot "base" address in encoding/decoding pointers.

Unfortunately, the upside is not reliable enough to actually benefit from. Since "relative" pointers can't point to allocations more than 4GB away, objects must be allocated in such a pattern that such distant pointers are never needed. However, the allocator doesn't know ahead of time which objects will want to point at which addresses, so taking a pointer is now a potentially slow operation which requires reallocating objects to put them close enough together.

Not to mention, it's possible for this combinatorial problem to actually have no solution! Imagine you have an 8GB-large array of objects. The first object in the array simply cannot hold a pointer to the last one. So taking a pointer is now a fallible operation. Or imagine you have a slightly-larger than 8GB array of pointers; the middle one cannot point anywhere outside of the same array, and the first and last ones can't point to the same thing.

So practically speaking, you are still generally limited to 4GB of memory. At best, in specific cases you might be able to compute a memory layout at compile-time which, based on static type information, is guaranteed to never require pointers at long distances.

> Why not? I can't think of any downside of this "relative" encoding schema, compared to the Java/NodeJS approach (namely "base" encoding).

The biggest downside is that you can no longer just copy most data types from one place to another; you have to do arithmetic to correct all the pointers. Likewise for comparing pointer equality.

In the comments you've said you don't think this is a big deal. It's true that copying memory often requires manipulating refcounts or GC metadata anyway; at least, this is true in languages which use reference counting or garbage collection (which is not all languages).

However, even in such languages there are many common operations which can be performed by copying memory without this extra overhead: when reallocating a [dynamic array](https://en.wikipedia.org/wiki/Dynamic_array), rotating an array, moving portions of an array while sorting, or more generally any operation where the compiler can determine that a reference count increment will cancel out with a decrement.

For example, in the CPython source code for the `list` type, the function [`list_resize`](https://github.com/python/cpython/blob/127c1d2771749853e287632c086b6054212bf12a/Objects/listobject.c#L80) performs a memory copy but does not invoke `Py_INCREF` or `Py_DECREF`. This function will be called very frequently, since any operation adding an element to a list could trigger a resize.
> **Comments:**
> **username_0** (2024-06-12): Yes, I realized that pointing to far-away address will still invoke the heap size limit, indeed.  
> **username_3** (2024-06-13): "objects must be allocated in such a pattern that such distant pointers are never needed" – this rather reminds me of "near" and "far" pointers in 16-bit MS-DOS/Win3.x programming...  
---
