Pre-RFC: Copy-like trait for large types

language design
1

In my understanding, only small types that are quick to memcpy should be marked as Copy, since Copy changes the behavior of the type to enable implicit copying rather than moving, while Clone requires explicit cloning but does not require that the type be trivially copyable with memcpy.

I would like for there to be a trait that marks a type as trivially copyable with memcpy, but does not change the semantics to implicit copying. This would be useful for large data types that must be trivially copyable, such as packet headers, IPC data types, arrays, etc.

Thoughts? Am I misunderstanding the Copy trait?

3 Likes
2

Both moving and copying are done with memcpy, so changing a type to non-Copy doesn't actually reduce copying. The only difference is whether the original location is still considered valid after the data is copied to the new location. I don't agree that Copy is only appropriate for small types.

Edit: Can you provide an example of some code you'd like to write where a Copy or Clone bound is inappropriate but the proposed ExplicitCopy trait is better?

9 Likes
3

I can try to put together some example code later tonight. To provide some more clarification, though, the goal is to make any copies explicit, since they would be expensive. Along these lines, perhaps it would be good to also require explicit moves, though I don't know if that's possible in the Rust compiler today.

4

I seem to recall Clippy having a lint for moving(/copying) a (very) large type around, but I can't seem to find the name right now.

2 Likes
5

In general, avoiding large copies of large objects is hard due to calling convention hilarity. If you have a big struct you don't want to move around, your best bet is to either allocate it on the stack and work with mutable references to it[1], or to allocate it on the heap or in an arena.

[1] Perhaps some day we'll get &move references...

2 Likes
6

I see a lot of confusion when I read comments on here regarding Copy/Clone and memcopy with respect to move.

"Move" in Rust refers to the logical movement of ownership of a memory location from one variable to another. It does not (directly) refer to whether the contents of that memory location are moving or being copied or anything else.

The "Copy" trait simply says that the given type can be copied, instead of being moved, so ownership transfer isn't necessary when assigning one variable to another or calling a function, etc. All fundamental/primitive types are "Copy" (like i32) because the values can be copied without breaking semantics AND they are trivially mem-copyable (meaning they don't require any deallocation of memory or other resources through drop) with little to no overhead. Types that are not ""Copy" cannot have ownership ''''Moved" by simply making another "Copy" of the thing.

Think of it like this: If I have something that can be trivially copied, and you want one, I can make a copy and give it to you (Digital Songs are a good example); however, if I have a '67 Mustang, and you want one, I can't just make a copy (easily) and give it to you. Instead, I need to give it to you. So, if something is "Copy", I can give it to you and keep it at the same time. We both end up with one and they are both of equal value and utility. Something that isn't copy, I must give (or sell) it to you for you to have it. We both can't possess (Own) it at the same time.

Now, I could make you a copy of my '67 Mustang (clone it), but, that won't be cheap. If I clone it, you'll then have one and I'll still have one, but, there was a significant cost involved (unlike the copy of "Mmm-Bop" I gave you where I still have my copy of "Mmm-Bop" and can still listen to it whenever I want and giving you a copy cost me almost nothing).

If I own something, and you want one there are the following options:

  • If the thing is easily/cheaply copied I can make a copy and give it to you. Now, you own one and I own one, but, they are not the same one, and it cost me or you almost nothing for me to give you a copy. These are "Copy" types.
  • If the thing can be duplicated through some expensive process, I can clone mine and give you the clone. Now, also, we both have one, and the one you have is not the same as the one I have; however, either your or I had to pay a significant cost to have the clone created.
  • I can transfer ownership to you. Now, you have it and control it, but, I don't have it anymore and can't use it. For example, I could just give you my '67 Mustang. I could also give you my Copy of "Mmm-Bop" without making a new Copy and I'll never be able have to listen to it again.
  • I can loan it to you, with the understanding you'll return it when you're done with it AND that no-one else can use it (including me) while you're using it. This is an exclusive loan, also known, by somewhat of a misnomer, as a "mutable borrow" (&mut thing : Thing).
  • I can allow you to use it, but, I may also continue to use it, and I may also let other people use it (and you may let other people use it as well), with the understanding that the thing cannot (by design) be misused by any of us to adversely effect the others' usage of the same. This is a "immutable borrow" (& thing : Thing) - also, somewhat of a misnomer.

When I say that "mutable borrow" and "immutable borrow" are misnomers, I say that because the important thing is "Exclusive Access" without ownership vs "Shared Access" without ownership. For example, I could lease you my '67 Mustang, and you would have exclusive access. Whether or not you could modify it, is a separate issue, that would be dictated by the contract (Visibility, Traits, and Functions that operate on it). For example, if I leased you the car, it would be with the understanding that you could use all of the car's functions as designed. If the car had a mechanism to change the color, you'd be free to change the color. Not because you have exclusive access, but, because the contract of the functionality the car provides says you can change the color as long as you have exclusive access to it. If the contract that comes with the car says you can only change the color if you are the owner, then, you can't change the color just because you have exclusive access (mut). By the same token, if the contract that comes with the car says that you can change the color of the car even if you only have shared access to the car, then you can change the color of the car with a shared borrow. The contract only allows what is safe to do. A contract that allowed you to change the color, even though you didn't have exclusive access, would be a bad/invalid (Undefined Behavior) contract if changing the color while someone else was using it would POTENTIALLY adversely effect that person. The contract could allow you to change the color with shared access as long as you verify before doing so that you changing the color right then wouldn't adversely impact anyone else - that would be an "unsafe" contract (but, not necessarily "undefined behavior" as long as you are sure to check and make sure it is OK to change the color right then. That "unsafe" contract is frowned upon in Rust because now the other users of the car can't be guaranteed that your actions will not cause them problems.

Now, getting back to the Copy and Clone traits: They are only meaningful when talking about ownership, not borrowing (shared or exclusive). If I loan you the thing (whether shared or exclusive), the thing is neither copied nor cloned. What Copy and Clone indicates, is what kind of transfer of ownership is feasible/efficient.

  • Copy - says, if you want what I have, and I can easily/trivially give you a copy of what I have and now we'll both own one. If this is the case, the compiler will automatically make these copies instead of transferring ownership when what I have is what you need.
  • Clone -says, if you want what I have, I can give you a copy of what I have, but, there will be a significant cost involved. We'll still both end up with our own independent copy of the original, but, it would've had a cost. The compiler will not automatically do this to transfer ownership. If you want what I have, and I want to keep the one I have, and the thing can be cloned, I have to decide to clone it and give you the clone. I paid the price knowing the cost and understanding that I'd rather pay the price than give up ownership of my own copy.
  • Without Clone or Copy, the only way you can have (own) what I have (own) is for me to surrender it to you and give up my ownership and allow you to take ownership. This is what the compiler will do automatically on assignment or passing a value to a function when the thing is not trivially copyable (Copy).

So, you want a new Trait that isn't Copy, but, isn't Clone. For what purpose? How does it fit into all of the above. Copy and Clone is not about whether or not something can or can't be mem-copied, it is about whether or not a mem-copy should happen automatically or not when you want ownership of something I own. With your new trait, what should happen implicitly differently (if anything).

I personally think that you don't understand what "Move", "Borrow'" means if you are asking for this, and I hope the above explanation helps to clarify things.

9 Likes
7

On top of @gbutler's excellent points, it's worth adding one more thing: a move and a copy, at the hardware level, are the exact same operation. The only difference is whether you are allowed to use the location that was moved from.

Omitting a Copy impl can be useful to avoid implicit copying, but just replacing the copies with moves doesn't make it cheaper. To avoid the cost of copying the bytes around, you need to put it behind a ptr.

2 Likes
8

But how would that be different from Clone?

.clone() on trivial types is memcpy.

9

In practice though, having a big struct on the stack can result in a lot of unnecessary copying data around. Yes, sometimes compiler can optimize such moves out, but more often it will not (e.g. if you haven't enabled LTO and use a function from outside crate not marked #[inline]). So if you end up with a huge type, sometimes it makes sense to allocate part of it on the heap.

As for the the OP proposal, I also don't quite see use-cases for which difference between non-trivial Clone impl and memcpy-based one will be important.

2 Likes
10

Thanks for the exposition. That all makes sense and fits with my existing comprehension, other than that I thought Copy also implied trivially copyable with memcpy. I'm aware that a value being moved does not necessarily imply that it was memcpy'd.

I guess what I'm really asking for is two separate things:

  1. A marker trait for trivially copyable types, e.g. TrivialCopy. This would presumably be an unsafe and auto-derived trait with opt-out, similar to Send.
  2. A guarantee that a particular type is not implicitly memcpy'd. All memcpy's would be clearly explicit in the code.

A TrivialCopy+Clone type would get close to 2, except for the possiblity of accidentally passing by value (assuming Rust does not optimize pass by value of large types into pass by reference).

I forsee a few use cases for these. I will try to write them up later tonight and comment here.

1 Like
11

You could simply make the trait "TrivialCopy" and provide a blanket impl for "Copy". So anything that implements "Copy" implicitly implements "TrivialCopy". This can be done today as a crate and does not require any cooperation from the compiler or the standard library. There is no reason to have it be auto-derive.

If you want a struct to be "TrivialCopy" that isn't already "Copy" you simply implement "TrivialCopy" for that struct, but, don't implement "Copy". You could also provide a derive macro for it that could be used. The derive macro would derive "TrivialCopy" for any struct/enum where all the members were "TrivialCopy" (which due to the blanket impl of "TrivialCopy" for "Copy", would automagically include all existing "Copy" types).

Voila!

No RFC needed. Just make the crate. Shouldn't take long at all. Then use the create wherever/whenever you wanted this functionality.

Wouldn't that solve your use-case? You'd be able to have structs that are "TrivialCopy", but, not "Clone". If a type implements "Copy" it also implicitly (due to blanket implementation) implements "TrivialCopy" and "Clone". If, however, you wanted a type that would never automagically "Copy" implicitly, but, that is marked as trivially copyable, so, you could manually call, thing.copy() knowing that it would be copying, but, that the copy would be "cheap", then you simply implement "TrivialCopy" for that type and don't implement "Copy".

The only downside I can see, is that if a type is "TrivialCopy" it should maybe also b implicitly "Clone" (Just like if a type is "Copy" today it is also implicitly "Clone"). If that were needed, this would need added to the standard library (requiring an RFC) so that there could be a blank impl of "Clone" for "TrivialCopy" as well as "Copy". Personally, I don't see why that would be needed/useful, but, I'm struggling with the usefulness of this anyway.

My suggestion would be to implement the crate as I've described, and get some usage out of it. Only if it proves useful should it be considered for incorporation into the standard library.

1 Like
12

Funnily enough, it isn't. Only when the type is actually Copy does it emit a memcpy, otherwise it generates horrible code (even if the type could be Copy).

13

This thread reminds me of a common discussion that comes up in C++ circles about when std::move is important. C++'s move semantics are kind of a garbage fire, but, somewhat like in Rust, moves are treated as an optimized copy, where you can assume no one will inspect the T&& you moved out of; Rust merely enforces this rule.

In C++, this is perhaps best illustrated by the fact that, if a class does not incorporate members with custom move constructors (and something something Rule of Five), it doesn't have a move constructor, and, as such, assignment with std::move results in calling the copy constructor instead.

Mind, in Rust, all our copy/move "constructors" are trivial, and moves, rather than copies, are default, but the idea applies: unless your type has fancy invariants, your moves are copies because there's nothing else interesting to do. After all, when you compile

fn alloc(x: [u8; 1024]) -> Box<[u8; 1024]> {
  Box::new(x)
}

the best you can roughly expect is (fairly simplified)

// Callee-saves elided, assume the stack address 
// of |x| is loaded into |a0|.
addi sp, sp, -4
sw a0, 4(sp)
li a0, 1024
call malloc
lw a1, 4(sp)
li a2, 1024
call memcpy
addi sp, sp, 4
ret

(I've given it in RISC-V because it's what I'm most familiar with right now.) This is regardless of whether the array is a copyable type: you need to get the array data out of wherever it was passed in and into the heap. Moves have nothing to do with it. Depending on calling convention, you may get a bonus copy due to x having to be in a specific stack location, just for this function.

1 Like
14

I don't think there is a lint to warn for large copies yet. There is an issue for it though.

3 Likes
15

On the contrary, I'm quite certain that it does imply it was memcpy'd.

@gbutler's post does not seem correct to me at all. If you e.g. return a struct from a function, then as far as the abstract machine is concerned, it's going to have to be memcpy'd regardless of whether or not the type implements Copy. In practice, the same assumption might as well be made even for simple things like assigning a local to another local, because it's just simpler that way. (LLVM can figure out what's no longer used and elide the copy)

The only difference between Copy and !Copy is that, with !Copy, the compiler internally marks the value as uninitialized after the move. (and in some cases, the state of a runtime drop flag may be changed.)

So, copies are not the enemy. All moves are, whether they are copies or not.

...which is why I like this proposal:

The linked issue suggests a lint on passing structs "by value." a.k.a. a lint on both moves and copies of large structs to encourage the use of pointer types. That's the sort of thing we need.

4 Likes
16

I don't know about the abstract machine, but the way this is actually implemented is that the caller allocates space for the structure to be returned, and passes the address of that space to the callee as a hidden argument. The callee could initialize that space by copying from an instance in its own activation record (or whereever) but it doesn't have to.

For instance look at what you get from rustc --crate-type lib --emit asm -O on this file (ignore all the "field is never read" warnings):

pub struct S {
    a: i32, b: i32, c: i32, d: i32, e: i32, f: i32, g: i32, h: i32
}

pub fn make_s(x: i32) -> S {
    S { a:x, b:1+x, c:2+x, d:3+x, e:4+x, f:5+x, g:6+x, h:7+x }
}

(Disclaimer: I only know that this is what happens on x86, but this technique for returning aggregates was invented upwards of 30 years ago and I'd be surprised to find an ABI that doesn't use it nowadays.)

17

I don't think that is right. "Move" means that ownership is moving from one variable to another. It does not mean that the bytes that make up the underlying value are moving (and in most cases that is not a requirement or implied). To perform a "Move" (of ownership), the compiler may or may not be copying bytes depending on the nature of the owner of both the source and destination. For example, if both the source owner and the destination owner are local variables, then, no bytes will be copied anywhere. Similarly, when passing ownership into a function, the compiler does not necessarily need to copy the bytes into the destination functions stack-frame (it may today, but, that isn't required by the definition of "Move" semantics that I can see). Also, when returning an owned value from a function, it isn't strictly necessary that bytes are copied. In the presence of RVO, the called function may have built the new value directly into the stack-frame of the calling function in the first place. In other words, "Move" isn't saying bytes will or won't be copied, it is just saying that ownership is moving. Whether or not bytes are or aren't being copied in that case is entirely a matter of optimizations and is not relevant to the semantic model (that I can see).

On the other hand the "Copy" trait is specifically saying that, "This type can be copied reliably, inexpensively, and safely so go ahead and make a copy INSTEAD of moving ownership when you would have normally moved ownership". The "Clone" trait says, "This type can be copied reliably and safely, but, it may be costly. Don't automagically make copies just because the type defines this trait. If the user wants to make a copy, they can by cloning it, but, then the user knows that they're invoking a potentially expensive operation".

Even if a type doesn't define Copy or Clone, that doesn't mean the bytes can't be relocated in memory. In fact, Rust type system and semantics guarantees that any type that isn't Pin is safe to relocate in memory simply by byte-copying the memory of the value of the type in its entirety. '"Move" semantics exploits that fact to make moving ownership from function to function and from stack to heap and from structure to structure, etc., but, doesn't always need to use it in order for ownership to move.

18

I also thought it worked that way, but I have checked the ASM emitted by this code. The compiler inlines the functions, and yet there are three calls to memcpy.

pub fn increase(mut x:[i32;100])->[i32;100]{
    for e in x.iter_mut(){
        *e+=1;
    }
    x
}
struct Large([i32;100]);
impl Large{
    pub fn increase(mut self)->Large{
        for e in self.0.iter_mut(){
            *e+=1;
        }
        self
    }
}
fn main(){
    let x=increase([0;100]);
    println!("{:?}",x[5]);
    let x=Large(x).increase();
    println!("{:?}",x.0[5]);
}
19

I think the point being made is that the reserved return location on the stack needs to be written at some point; this is now a question about RVO though, and since Rust does not have observeable copies it's a little moot. Ultimately, it is a memcpy, but any reasonable compiler can see through memcpys when necessary and, if possible, elide them completely. For example, you expect the following optimization:

void* ptr = alloca(0x100);
do_whatever(ptr);
memcpy(out_ptr, ptr, 0x100);
// Becomes:
do_whatever(out_ptr);

This is a problem of calling convention. An alternative calling convention might convert passing T (for "large" size T) into passing &T, and performing a copy onto the callee stack when and if mutation happens. A copy still needs to happen in some cases, especially if (like C++) Rust does not distinguish between taking a T const or mut.

While I think Rust could do with more aggressive copy elision, that is completely orthogonal to move/copy semantics; this optimization can be implemented for both Copy and non-Copy types, since memcpy has no side effects (especially since on modern ISAs most things will get stuck into registers, anyway).

"memcpy", for the purposes of this discussion, is a compiler intrinsic operating on LLVM SSA variables, not pointers.

2 Likes
20

I think that alludes to what @CryZe said. See https://godbolt.org/z/dMHvZr, where you get all the hilarious AVX instructions with the right flags.

Edit: nm I completely misread the assembly. It looks like some of those memcpys are sad RVO?