<p>Some examples:</p>
<ol>
<li><p>To support checking whether an object is of a subclass of a specific class in constant time, in a language using single inheritance, the compiler could arrange the vtables of classes in lexicographic order of the inheritance paths, and compare whether the vtable address is in a specific range. This may not work easily if multiple parts are independently compiled and linked together.</p>
</li>
<li><p>In graph related algorithms that one may need to get reversed edges frequently, one could make each pair of the odd and even numbered edges always the corresponding reversed edges in the data structure. In case it uses pointers instead of indexes to refer to the edges, it would be helpful if the address of the edge list always start at a fixed number mod (2 * size of element). It would be helpful if the language could provide a mechanism to allocate memory, but always start at a position satisfying such criteria. (Though it is possible to implement this in a library in C++, with a few bytes of waste due to the limitations of the operating system.)</p>
</li>
</ol>
<p>I consider these ideas tricks that are unlikely to be formally the standard ways in a bigger system such as a language. But as they work, before dismissing these ideas completely, I'd like to know, are there existing language features or specific implementations taking advantage of the numeric nature of the addresses like in the examples?</p>
<p>I'm not asking about special values such as the null pointer. It's about the cases that the criteria of the address has caused data to not be placed in arbitrary memory location. And it's not about the cases limited to the defined order of data in a struct or array. It's for the cases that the allocation process is affected.</p>

<memory-management><pointers>
Are there languages making addresses to have other significant meaning?
CC BY-SA 4.0
2023-11-07T19:21:33.763Z
Not sure if this counts, but some language implementations take advantage of the fact that pointers are always even numbers (on certain common architectures) in order to use the least significant bit as a discriminant between pointer and non-pointer values.
kaya3
CC BY-SA 4.0
2023-11-07T19:35:59.367Z
@kaya3 It's contained in "special values such as the null pointer", or bit field implementations composing addresses and other data together but not affecting the meaning of the effective part of the addresses, depending on how it is used. In amd64, the 16 most significant bits are also always sign extended, though I think there is no guarantee it will not change later.
user23013
CC BY-SA 4.0
2023-11-07T21:58:12.667Z
Your first example seems to be a language implementation detail, not part of the language specification. The second example appears to be about something implemented in the language, but I don't think most languages give applications enough control over addresses that it could be done.
Barmar
CC BY-SA 4.0
2023-11-07T21:58:53.997Z
You claim that a C++ library could use that technique. I'm not sure how.
Barmar
CC BY-SA 4.0
2023-11-07T22:05:56.570Z
@Barmar Just allocate memory with two element long padding, and return the first valid address after that.
user23013
CC BY-SA 4.0
2023-11-12T17:24:44.920Z
I'm not sure if it counts, but hotspot has a special concept of 'compressed oops', for heaps between 2^31 and 2^35 bytes in size, which uses the fact all java heap objects are 8 byte aligned, to store pointer into a 64 bit heap as a 32 bit index, calculating base + index * 8 whenever it needs to load from memory, which due to the nature of the x86 instruction set, can often be done with 0 to 1 instruction overhead.
user1937198
CC BY-SA 4.0
2023-11-12T17:30:06.983Z
Again, runtime rather than language, but you might also be interested in the C4 garbage collector which uses the memory mapping the pointers are pointing at to store whether a pointer has been updated to point to the new location during a compaction sweep. https://www.azul.com/sites/default/files/images/c4_paper_acm.pdf
user1937198
<blockquote>
<p>I'd like to know, are there existing language features or specific implementations taking advantage of the numeric nature of the addresses like in the examples?</p>
</blockquote>
<p>There is an interesting memory allocator implementation technique that places allocation size in dereferenceable pointer. <a href="https://accu.org/journals/overload/26/146/ignatchenko_2533/" rel="nofollow noreferrer">See this article for explanation</a>, it starts at &quot;Take 3 - Storing the bucket number within a dereferencable pointer&quot;</p>

CC BY-SA 4.0
2023-11-11T19:33:25.293Z
2023-11-11T19:33:25.293Z
Iwa
CC BY-SA 4.0
2023-11-11T20:26:32.237Z
Welcome to PLDI!
rydwolf
# Are there languages making addresses to have other significant meaning?
Posted by: username_0 on 2023-11-07
Some examples:

1. To support checking whether an object is of a subclass of a specific class in constant time, in a language using single inheritance, the compiler could arrange the vtables of classes in lexicographic order of the inheritance paths, and compare whether the vtable address is in a specific range. This may not work easily if multiple parts are independently compiled and linked together.
2. In graph related algorithms that one may need to get reversed edges frequently, one could make each pair of the odd and even numbered edges always the corresponding reversed edges in the data structure. In case it uses pointers instead of indexes to refer to the edges, it would be helpful if the address of the edge list always start at a fixed number mod (2 \* size of element). It would be helpful if the language could provide a mechanism to allocate memory, but always start at a position satisfying such criteria. (Though it is possible to implement this in a library in C++, with a few bytes of waste due to the limitations of the operating system.)

I consider these ideas tricks that are unlikely to be formally the standard ways in a bigger system such as a language. But as they work, before dismissing these ideas completely, I'd like to know, are there existing language features or specific implementations taking advantage of the numeric nature of the addresses like in the examples?

I'm not asking about special values such as the null pointer. It's about the cases that the criteria of the address has caused data to not be placed in arbitrary memory location. And it's not about the cases limited to the defined order of data in a struct or array. It's for the cases that the allocation process is affected.
**Tags:** memory-management pointers
> **Comments:**
> **username_1**: Not sure if this counts, but some language implementations take advantage of the fact that pointers are always even numbers (on certain common architectures) in order to use the least significant bit as a discriminant between pointer and non-pointer values.  
> **username_0**: @kaya3 It's contained in "special values such as the null pointer", or bit field implementations composing addresses and other data together but not affecting the meaning of the effective part of the addresses, depending on how it is used. In amd64, the 16 most significant bits are also always sign extended, though I think there is no guarantee it will not change later.  
> **username_2**: Your first example seems to be a language implementation detail, not part of the language specification. The second example appears to be about something implemented in the language, but I don't think most languages give applications enough control over addresses that it could be done.  
> **username_2**: You claim that a C++ library could use that technique. I'm not sure how.  
> **username_0**: @Barmar Just allocate memory with two element long padding, and return the first valid address after that.  
> **username_3**: I'm not sure if it counts, but hotspot has a special concept of 'compressed oops', for heaps between 2^31 and 2^35 bytes in size, which uses the fact all java heap objects are 8 byte aligned, to store pointer into a 64 bit heap as a 32 bit index, calculating base + index * 8 whenever it needs to load from memory, which due to the nature of the x86 instruction set, can often be done with 0 to 1 instruction overhead.  
> **username_3**: Again, runtime rather than language, but you might also be interested in the C4 garbage collector which uses the memory mapping the pointers are pointing at to store whether a pointer has been updated to point to the new location during a compaction sweep. https://www.azul.com/sites/default/files/images/c4_paper_acm.pdf  
---
## 1 answers
### Answer by username_4 on 2023-11-11. Score: 2 | Accepted answer
> I'd like to know, are there existing language features or specific implementations taking advantage of the numeric nature of the addresses like in the examples?

There is an interesting memory allocator implementation technique that places allocation size in dereferenceable pointer. [See this article for explanation](https://accu.org/journals/overload/26/146/ignatchenko_2533/), it starts at "Take 3 - Storing the bucket number within a dereferencable pointer"
> **Comments:**
> **username_5** (2023-11-11): Welcome to PLDI!  
---
