2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – kaya3
    Commented Nov 7, 2023 at 19:21
  • $\begingroup$ @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. $\endgroup$
    – user23013
    Commented Nov 7, 2023 at 19:35
  • $\begingroup$ 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. $\endgroup$
    – Barmar
    Commented Nov 7, 2023 at 21:58
  • $\begingroup$ You claim that a C++ library could use that technique. I'm not sure how. $\endgroup$
    – Barmar
    Commented Nov 7, 2023 at 21:58
  • $\begingroup$ @Barmar Just allocate memory with two element long padding, and return the first valid address after that. $\endgroup$
    – user23013
    Commented Nov 7, 2023 at 22:05

1 Answer 1

Reset to default
2
$\begingroup$

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, it starts at "Take 3 - Storing the bucket number within a dereferencable pointer"

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to PLDI! $\endgroup$
    – Rydwolf Programs
    Commented Nov 11, 2023 at 20:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .