Working with identity (comparing equality of references/pointers)

In some program, I want to treat references retrieved from an Iterator (or Stream) differently, depending on whether a reference occurs multiple times. I learned that I can use std::ptr::eq to compare references (not the values they refer to) for equality.

ptr::eq::<T> just coerces its arguments to a *const T and then compares the pointers for equality.

Likewise, it seems possible to coerce references to pointers and store them in a HashSet, such that it is possible to check if a reference has been processed previously:

use std::collections::HashSet;

struct S {}

fn count_distinct<'a>(items: impl IntoIterator<Item = &'a S>) -> usize {
    let mut count = 0;
    let mut memorized: HashSet<*const S> = HashSet::new();
    for item in items {
        if memorized.insert(item as *const S) {
            count += 1;
        }
    }
    count
}

fn main() {
    let s1 = S {};
    let s2 = S {};
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    println!("Distinct count: {}", count_distinct(s));
}

(Playground)

This code seems to run fine, as it creates the following output:

Distinct count: 2

The code also seems to be correct because the references are immutable and should live at least as long as the iterator does. While count_distinct is executed, it should not be possible to drop any values behind the references, thus the pointers will be valid until count_distinct returns. Note that no unsafe code is needed, because I don't need to dereference any pointer but only compare them (in the HashSet).

When I try to convert the code to async, weird things happen:

use std::collections::HashSet;

struct S {}

async fn count_distinct<'a>(
    items: impl IntoIterator<Item = &'a S>,
) -> usize {
    let mut count = 0;
    let mut memorized: HashSet<*const S> = HashSet::new();
    for item in items {
        if memorized.insert(item as *const S) {
            count += 1;
        }
    }
    count
}

#[tokio::main]
async fn main() {
    let s1 = S {};
    let s2 = S {};
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    println!("Distinct count: {}", count_distinct(s).await);
}

(Playground)

This code executes with the following output:

Distinct count: 1

My first question is: Is my code in the first example (non-async) correct or do I miss something that makes the code unsafe or causes undefined behavior?

My second question is: Can anyone explain what's going on in the second example? Why does it return a count of 1 instead of 2?

Another issue is that *const _ is !Send, which means any futures containing such pointers are also !Send. A workaround is to coerce the pointer to an usize and use a HashSet<usize>, as a usize can be sent to different threads, but that means I lose type information. I could also implement my own type storing the pointer and make it Send using unsafe:

#[derive(Clone, Copy, Eq, PartialEq, Hash)]
struct SId(*const S);
unsafe impl Send for SId {}

However, using unsafe doesn't seem right, as the code really isn't unsafe. Maybe the best way to go is this:

#[derive(Clone, Copy, Eq, PartialEq, Hash)]
struct SId(usize);
impl SId {
    fn new(s: &S) -> Self {
        SId(s as *const S as usize)
    }
}

But that also feels like a lot of code just for the purpose of working around *const _ not being Send :slightly_frowning_face:. Or is Rust protecting me from doing bad stuff for my own good?

See also: Shouldn’t pointers be Send + Sync? Or

1 Like

It prints 1 if you test it in release mode. Since the S is a zero sized type, it's not needed to put two variables of them in different memory location. I guess on async fn the compiler performs this kind of stack space optimization even on debug mode.

4 Likes

If there's no unsafe, there's no UB, modulo bugs in not-your-code.

But you can't assume the addresses of zero-sized types (ZSTs) are different. I don't think you can assume they're the same, either, though. Guess that's what your experiment shows in fact.

You can at least rely on the same elements of a slice having a consistent address, it seems.

I don't think much of this is normalized. One thing you definitely can't do is read data behind the pointer; it's dangling.

3 Likes

Oh, so indeed some optimization happened. I didn't expect that! Is there any part in the reference describing this sort of behavior? I just checked the Rust Reference – Type Layout and didn't find anything (or maybe I overlooked it?). Anyway, no complaints, it generally makes sense to not allocate memory for these zero-sized types. My example was just badly chosen then, using a "dummy" struct S with no members.

What do you mean with normalized?

Let me fix my example and get to my last point though, where I worry about *const S being !Send. The following code will fail to compile:

use std::collections::HashSet;
use std::future::Future;
use std::pin::Pin;

struct S {
    _value: i32,
}

async fn count_distinct<'a, I: IntoIterator<Item = &'a S>>(
    items: I,
) -> usize {
    let mut count = 0;
    let mut memorized: HashSet<*const S> = HashSet::new();
    // Use instead:
    // let mut memorized: HashSet<usize> = HashSet::new();
    for item in items {
        if memorized.insert(item as *const S) { // And: item as *const S as usize
            count += 1;
        }
        tokio::task::yield_now().await;
    }
    count
}

#[tokio::main]
async fn main() {
    let s1 = S { _value: 0 };
    let s2 = S { _value: 0 };
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    let fut: Pin<Box<dyn Future<Output = usize> + Send>> =
        Box::pin(count_distinct(s));
    println!("Distinct count: {}", fut.await);
}

(Playground)

As said above, it can be fixed by not storing a *const S in the HashSet but a usize containing the memory address. But that seems error-prone, as I lose type information then. What's the best solution to solve this when I need (or want) my future to be Sendable?

Sorry, I meant normative. As in most of it hasn't been nailed down.

Here's part of the nomicon, and another.

I'd probably say the new-type around *const _ for maximal semantic meaning and forward compatibility.

Implementing an unsafe trait means "I've read the requirements and believe I have upheld all the invariants I must to avoid undefined behavior." Like that IRLO thread says, you need more unsafe elsewhere for this particular case to cause problems really, to boot. That makes the proof of safety pretty easy :slight_smile:.

Pretty much any compiler nowadays needs to perform extensive optimizations in order to lower abstractions efficiently. This is not specific to Rust and is not something that needs to be put in the reference. It's just how things are.

Ah okay. I checked the nomicon too, but didn't find this particular problem described either. (If I missed it, please let me know.) On the other hand, I didn't find any guarantees on the semantics of pointers (and their difference for references to different values) either.

I thought on how I could create a typesafe new-type (let's name it RefId<'a, T>) for an inner *const _, which

  • captures the underlying type T and lifetime 'a of the reference used to create the new-type,
  • implements Eq and Hash (and ideally also Clone and Copy).

I came up with this:

use std::marker::PhantomData;

pub struct RefId<'a, T> { 
    id: usize, 
    phantom: PhantomData<&'a T>, 
} 
 
impl<'a, T> From<&'a T> for RefId<'a, T> { 
    fn from(reference: &'a T) -> Self { 
        RefId { 
            id: reference as *const _ as usize, 
            phantom: PhantomData, 
        } 
    } 
} 

impl<'a, T> PartialEq for RefId<'a, T> { 
    fn eq(&self, other: &Self) -> bool { 
        self.id == other.id 
    } 
} 
 
impl<'a, T> Eq for RefId<'a, T> {}

(Note that I use usize as an inner value to avoid having to add an unsafe impl here, but that usize isn't exposed to the outside.)

Usage is then very easy:

    let mut memorized: HashSet<RefId<_>> = HashSet::new();
    for item in items {
        if memorized.insert(RefId::from(item)) {
            count += 1;
        }
    }

And capturing the lifetime makes operations like that be illegal (i.e. cause a compile-time error):

fn illegalA<'a, 'b>(reference: &'a S) -> RefId<'b, S> {
    RefId::from(reference)
}

fn illegalB(value: S) {
    let id = RefId::from(&value);
    drop(value);
    drop(id);
}

Though, when I tried to use #[derive(Clone, Copy, Eq, PartialEq, Hash)] (see Playground), instead of manually implementing Eq and Hash, I get errors:

error[E0277]: the trait bound `S: Eq` is not satisfied
error[E0277]: the trait bound `S: Hash` is not satisfied

I guess that's because the derive macro won't derive Eq and Hash if the type parameter isn't Eq and Hash either. However, I don't want to require T to be Eq in order for RefId<'a, T> to support Eq. I guess that means I have to manually implement these traits. Full example also including Clone and Copy:

pub struct RefId<'a, T> { 
    id: usize, 
    phantom: PhantomData<&'a T>, 
} 
 
impl<'a, T> From<&'a T> for RefId<'a, T> { 
    fn from(reference: &'a T) -> Self { 
        RefId { 
            id: reference as *const _ as usize, 
            phantom: PhantomData, 
        } 
    } 
} 
 
impl<'a, T> From<RefId<'a, T>> for *const T { 
    fn from(ref_id: RefId<'a, T>) -> Self { 
        ref_id.id as *const T 
    } 
} 
 
impl<'a, T> Clone for RefId<'a, T> { 
    fn clone(&self) -> Self { 
        RefId { 
            id: self.id, 
            phantom: PhantomData, 
        } 
    } 
} 
 
impl<'a, T> Copy for RefId<'a, T> {} 
 
impl<'a, T> PartialEq for RefId<'a, T> { 
    fn eq(&self, other: &Self) -> bool { 
        self.id == other.id 
    } 
}

impl<'a, T> Eq for RefId<'a, T> {}

use std::hash::{Hash, Hasher};
impl<'a, T> Hash for RefId<'a, T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state)
    }
}

Now that is a lot of code (compared to simply writing as *const _ as usize), but I guess it's what I need to do when solving this problem in an abstract and type-safe way? (Playground with the full working example)

I guess it would make sense to create a crate for such a new generic type? That is, we can assume std::ptr::eq to compare "references for equality". The documentation literally says it can be used to compare references "by their address":

This can be used to compare &T references (which coerce to *const T implicitly) by their address rather than comparing the values they point to (which is what the PartialEq for &T implementation does).

But what does "comparing by their address" mean, if the compiler may re-organize addresses as it wants in order to optimize code?

I think that when optimizations change the otherwise documented behavior of the language or (standard) libraries, then these optimizations (and the change of behavior) should be documented as well (and that's also the case for other compilers AFAIK). I'm not clear whether it is documented somewhere whether pointer equivalence can be used to compare the identity of values (see my quote above).

However, if the compiler can arbitrarily optimize memory layout (and doesn't need to document it), then any operations with pointers would become unpredictable. I doubt that's intended, and I doubt that's the case. Or am I wrong here?

Optimizations aren't allowed to do that by definition, so they can't be arbitrary. An optimization needs to be a transformation that preserves guaranteed observable behavior. Or, conversely, anything which can change under optimization is by definition not guaranteed. The address of zero-sized types is exactly such a case. It shouldn't matter whether two zero-sized values are at the same place in memory, because their overlap is always zero-sized.

Your mistake is that you are trying to detect object identity by merely comparing base addresses, and not by comparing overlaps of memory ranges. I.e., you made a naïve assumption, which relies on a definition of identity that is not sufficiently general in the presence of zero-sized types.

This is not unpredictability; this is a perfectly predictable behavior of zero-sized types, which, however, might not be obvious to someone not specifically looking for such an edge case. Accordingly, the following function works correctly for objects of zero and positive size as well, even when they are dynamically-sized and when they have the same base address, even in release mode: Playground

fn objects_overlap<T: ?Sized>(p: &T, q: &T) -> bool {
    let p_start = p as *const T as *const u8 as usize;
    let p_end = p_start + size_of_val(p);
    let q_start = q as *const T as *const u8 as usize;
    let q_end = q_start + size_of_val(q);

    !intersect(p_start..p_end, q_start..q_end).is_empty()
}

fn intersect(mut p: Range<usize>, mut q: Range<usize>) -> Range<usize> {
    if p.start > q.end {
        swap(&mut p, &mut q);
    }
    p.start.max(q.start)..p.end.min(q.end)
}
8 Likes

That makes sense, but I wonder if there is any remark on that in the reference. I think if there isn't, it might be a good idea to describe this difference regarding behavior of non-zero-sized vs zero-sized types. I agree, however, that it may be surmised. I just didn't think of it. But still, I think it's a good idea to clarify that in the reference.

The only part in the "Type Layout" section where the layout of zero-sized types seems to be explained is in a side note on ():

Tuple Layout

Tuples do not have any guarantees about their layout.

The exception to this is the unit tuple ( () ) which is guaranteed as a zero-sized type to have a size of 0 and an alignment of 1.

You have a good point here. If T was a slice, then I guess I need to compare base address and length. But in my above example of RefId<'a, T>, T will automatically be required to be Sized. Thus comparing the base address is sufficient to check for equality (disregarding the corner case of zero-sized types), right?

Now with all that knowledge, what is the right way to implement a type RefId<'a, T> that can be used as a HashSet key? Your idea to include a length would double the key-size in order to fix the odd case of zero-sized types. Is there any way to disallow T to be zero-sized? Or would I need to add a remark to the RefId type to never use it with zero-sized types (which then doesn't get enforced by the compiler)?


As it doesn't seem possible to add a trait like !ZeroSized, I guess the best (or only) zero-cost way is to document the behavior for such a RefId type and to warn users to not use it with zero-sized types (or expect random behavior in that case).

There it says:

Safe code need not worry about ZSTs, but unsafe code must be careful about the consequence of types with no size.

As pointer comparison is considered to be safe, I would assume that the above statement from the nomicon is a bit misleading?

Eh, the statement is generally true in the vast vast vast majority of cases.

2 Likes

The size of the type is available using std::mem::size_of::<T>(), so you don't need to include the size in the struct. You can assert that the size is greater than 0 on RefId creation. That assertion should get optimized out during compilation for a non-ZST. Naturally, it will be a runtime panic for a ZST.

2 Likes

I understand that the example I brought up may be an edge case that may not be relevant in practice (usually). However, I still encountered it by accident, when creating an example for asking a question about how to store Sendable pointers.

I believe that too, and (currently) I can't think of a case, where someone really wants to compare addresses of zero-sized types. I guess it could happen if some code was using generics and does identity checks through pointer comparison and a user of such code uses () in place of the generic type because they don't want to store any additional data.

Well, and it did happen in my case, so I guess it can also happen when someone tries to understand the behavior of the language and constructs (simple) example cases and then gets confused by behavior that changes depending on compiler settings. Perhaps my mistake was to use something special, such as a ZST as an example struct, as some "dummy example data", while it's actually a very special kind of type and not the usual case.

That is why I would appreciate a tiny warning somewhere in the documentation, because someone else might make the same error as I did. It didn't seem to be the last thing to do to come up with struct S {} (or use ()) when you quickly need some dummy type, and I have seen () in a lot of example code here on the forum.

And of course, using () is fine in most cases of non-unsafe code. Just not when you try to show something about pointer identity or test somthing related to pointer identity. (Unless there are some other specialties about ZSTs that can appear in safe code?) Therefor, I find the statement in the Rustonomicon a (tiny) bit misleading, as it doesn't seem to be 100% true.

I don't want to say the documentation is bad, and I really appreciate all of Rust's documentation (whether reference or additional materials).

Why do I want to compare memory addresses at all? I do it because it gives me some sort of "object ID" that is valid as long as the data is pinned to memory (e.g. because it's explicitly pinned or because I have a non-mutable reference to it). And I get this "object ID" for free, without needing any additional memory or having to calculate it as an auto-incremented integer or something like that. But I hope I can rely on the address not changing for the lifetime of a non-mutable reference to it!? :fearful:

I believe identifying values (by their address) can be helpful in a couple of algorithms.

Moving a value to a different memory location is only allowed in safe code when there are no extant references, unless you swap in a replacement value at the same time.

If you’re holding a shared & reference, this swap can only happen with UnsafeCell and friends; if you have an exclusive &mut reference, only you are allowed to do the swap.

1 Like

I know that the compiler doesn't actually do it currently, but it would not be surprising to me if merging the two integers into a single address was an allowed optimization in the following code.

fn main() {
    let s1 = 1;
    let s2 = 1;
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    println!("Distinct count: {}", count_distinct(s));
}
2 Likes

You keep coming back to address identity. But that's simply not the tool that you need to use. You need to compare regions, i.e. include address and size. Rust has zero-sized types and so comparing objects by address only is by definition broken. Maybe it didn't match your expectation, but it's not a bug in the language, it's not a defect in the documentation either, it's just something that you will have to live with.

In other words, you should write your code in a way that it's as general as possible, so that it works with all types uniformly. You should not expect that people won't call your code with () or struct Empty or an empty slice.

2 Likes

And how about:

fn main() {
    let s1 = vec![];
    let s2 = vec![];
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    println!("Distinct count: {}", count_distinct(s));
}

The Vec is immutable, so it shouldn't matter that it's two different Vecs.

My point is: Where to stop here? I could even argue that

fn main() {
    let s1 = 1;
    let s2 = 2;
    let s = vec![&s1, &s1, &s1, &s2, &s2];
    println!("Distinct count: {}", count_distinct(s));
}

could be optimized to use a single address, as the value is never read.

Does that mean, in consequence, I can't use memory addresses for checking identity at all?

That comment is not helpful. Comparing size doesn't make sense when I have a known size, and comparing size just for the special case of ZSTs would be unnecessary overhead for a corner case that doesn't seem to make a lot of sense in most practical cases. Plus, it doesn't help in case the base address doesn't differ due to optimization, as in the example brought up by @alice.

Edit: Also note that generic type parameters are Sized by default, as I said here.

It's fine if checking "identity" isn't possible in Rust, i.e. requires an auto-increment integer or something like that. I could do it. It's easy. But it's overhead.

Well, ultimately I don't really know what the guarantees about memory address comparisons are, so it's hard to say. But I do in general think that identity comparisons are difficult to define in a reasonable way in Rust.

1 Like

I think being able to compare memory addresses (or ranges) for equality can be a helpful tool for a couple of algorithms. And I wouldn't be surprised if some crates already do that in order to solve certain tasks efficiently.

Now if Rust really doesn't give any guarantees, then these (hypothetical) implementations could break in future. Of course, it would be a mistake of those (yet hypothetical) crates to assume you can compare base addresses (or ranges) in order to do identity checks.

I would like if there was any form of statement in the reference that allows to deduce in which cases (if any cases at all) it is possible to use pointer comparison (or wide-pointer comparison, including length) for identity checks, because that could be helpful for a couple of algorithms and would avoid having to add otherwise useless auto-increment integers to data structures.

Even in case Rust decides to not give any guarantees, such a hint could be helpful, and it would motivate me to include runtime-overhead in my code to make my code sound.

If you can't find official documentation or an RFC, it's probably not considered normative / guaranteed, so if you want to be robust, take the conservative route. Rust sometimes gives an explicit non-guarantee (e.g. #[repr(Rust)] layout), but more often just does not give a positive guarantee on topics that are undecided or where flexibility is still desired.

E.g.

Even if addresses are a safe choice for your situation (heap allocated, live, not resized?), and even if you're talking about Sized, non-ZST types, you need to at least keep track of the type / only do this for a restricted set of types (vs. a *const () or usize or whatnot) to ensure identity. A struct and a field inside that struct can have the same address.

4 Likes