Reduce copying when sending

[servo]

Reduce copying when sending

[asajeffrey]

One possibility is a DeepClone trait:

trait DeepClone {
  type DeepCloned;
  fn deep_clone(&self) -> Self::DeepCloned;
}

and then adding a method send_deep_clone(data: &T) to IpcSender<U> where T: DeepClone<DeepCloned=U>, which has the same semantics as send(data.deep_clone()) without actually doing the deep clone. This would rely on the serialization of data being the same as that of data.deep_clone().

There's a PoC implementation of DeepClone at https://github.com/asajeffrey/deep-clone.

[asajeffrey]

IRC chat with @nox and @antrik: http://logs.glob.uno/?c=mozilla%23servo&s=10+Mar+2017&e=10+Mar+2017#c628793

TL;DR: We agreed that a) DeepClone should be named something more clearly about serde, and possibly live in serde, and b) it should have a type parameter rather than an associated type. There was discussion about whether it should be a marker trait or not.

[asajeffrey]

Some more IRC chat: http://logs.glob.uno/?c=mozilla%23servo&s=10+Mar+2017&e=10+Mar+2017#c628968

TL;DR perhaps our proposed "serde round trip" trait should inherit from PartialEq<U>? Then we could write specs/tests of the form x == x.serialize().deserialize().

[asajeffrey]

A first-cut implementation of round-tripping: https://github.com/asajeffrey/serde/blob/roundtripping/serde/src/roundtrip.rs

[asajeffrey]

IRC chat (unlogged) with @nox on #serde:

<ajeffrey> Alan Jeffrey dtolnay and nox: I wrote a first-cut trait for round-tripping: https://github.com/asajeffrey/serde/blob/roundtripping/serde/src/roundtrip.rs
12:43 PM the idea is that if S: RoundTrip<T> then you can serialize an S, deserialize a T, and all will be well.
12:45 PM 
<nox> Yeah I still don't agree with that trait having a method.
12:45 PM 
<ajeffrey> Alan Jeffrey nox: I thought you might say that :)
12:46 PM the machinery is pretty much the same with or without the method.
12:47 PM the tricky part is getting it to fly without specialization.
12:47 PM 
<nox> Why would you need specialization?
12:47 PM 
<ajeffrey> Alan Jeffrey hence the SameDeserialization trait.
12:48 PM 
<nox> I also don't understand why you need that trait,
12:48 PM 
<ajeffrey> Alan Jeffrey nox: if you do the obvious thing for refs, e.g.
12:48 PM 
<nox> given AFAIK all we want is similar serialisation.
12:48 PM 
<ajeffrey> Alan Jeffrey impl Rc<S>: RoundTrip<T> where S: RoundTrip<T> and
12:49 PM impl S: RoundTrip<Rc<T>> where S: RoundTrip<T> then
12:49 PM 
<nox> That doesn't tell me why we need specialisation.
12:49 PM 
<ajeffrey> Alan Jeffrey the impls overlap and boom you need something like specialization.
12:50 PM AFAICT you need something stronger than the current impl of specialization too,
12:50 PM or my ability to run Knuth-Bendix manually is shot :/
12:51 PM 
<nox> I don't understand why you need these impls.
12:51 PM 
<ajeffrey> Alan Jeffrey which ones?
12:51 PM impl Rc<S>: RoundTrip<T> where S: RoundTrip<T> and
12:51 PM 
<nox> I don't know, the thing you pasted weren't valid Rust.
12:52 PM 
<ajeffrey> Alan Jeffrey impl S: RoundTrip<Rc<T>> where S: RoundTrip<T>?
12:53 PM (note this applies to all ptr-like types, I was just doing Rc as an example)
12:54 PM 
<nox> Why do you need it both ways?
12:54 PM 
<ajeffrey> Alan Jeffrey nox: do you want to round-trip an Rc<T> into a T?
12:54 PM 
<nox> No I don't.
12:55 PM 
<ajeffrey> Alan Jeffrey OK, what about a &T into a Box<T>?
12:55 PM 
<nox> That's the direction I care about,
12:55 PM and that doesn't need to be bidirectional.
12:56 PM If you state that Rc<T> serialises the same way as anything that serialises the same way as T,
12:56 PM 
<ajeffrey> Alan Jeffrey OK, what about Cow<'a,T> to T?
12:56 PM 
<nox> you can send a &T and receive a Rc<T>, and be happy.
12:56 PM Why would I need that?
12:57 PM You can always get a &T from a Cow<T>.
12:57 PM 
<ajeffrey> Alan Jeffrey OK, so you want &T to Rc<T>,
12:57 PM do you also want Rc<T> to Rc<T>?
12:57 PM 
<nox> Rc<T> serialises the same way as Rc<T>.
12:58 PM I'm not sure what you mean by "to".
12:58 PM The only reason you ask that question is because your trait has a method.
12:58 PM 
<ajeffrey> Alan Jeffrey yes, but I'm doing requirements capture here,
12:59 PM 
<nox> The only requirement we want is to state that a type serialises the same way as the other.
12:59 PM 
<ajeffrey> Alan Jeffrey trying to work out which "same serializations" you care about.
12:59 PM 
<nox> To optimise ipc-channel we don't even need to care about the deserialisation side.
1:00 PM 
<ajeffrey> Alan Jeffrey nox: we certainly want soundness: S: RoundTrip<T> implies S has the same serialization as T,
1:00 PM 
<nox> That's what I just said.
1:00 PM 
<ajeffrey> Alan Jeffrey but I'm not sure about completness.
1:00 PM 
<nox> I don't understand what completeness is here.
1:01 PM 
<ajeffrey> Alan Jeffrey S has the same serialization as T implies S: RoundTrip<T>.
1:01 PM 
<nox> Why do you need that?
1:01 PM Rc<T> derefs to T.
1:01 PM 
<ajeffrey> Alan Jeffrey that was what I was saying: I'm not sure we need completeness,
1:02 PM which means we have a heuristic for which S: RoundTrip<T> we care about,
1:02 PM 
<nox> I feel like you are overthinking this a great deal.
1:02 PM 
<ajeffrey> Alan Jeffrey hence requirements capture.
1:02 PM nox: Vec<Rc<T>> doesn't deref to Vec<T> though,
1:03 PM the nasty cases are nested uses of serialization.
1:03 PM 
<nox> No, but a trivial wrapper around that Vec<Rc<T>> to serialise it the same way is very easy to write.
1:03 PM 
<ajeffrey> Alan Jeffrey The original example was Msg<Data>.
1:03 PM 
<nox> Same.
1:04 PM 
<ajeffrey> Alan Jeffrey we'd like to be able to send the msg without cloning the data.
1:04 PM so we build a Msg<&Data> and send that.
1:06 PM the other end deserializes it as a Msg<Data>.
1:06 PM 
<dtolnay> nox any idea why servo/components/style and canvas_traits both depend on serde/unstable?
1:06 PM 
<nox> dtolnay: NonZero most probably.
1:06 PM Or some stuff like that.
1:06 PM 
<ajeffrey> Alan Jeffrey but Msg<&Data> doesn't deref to Msg<Data>.
1:07 PM 
<nox> Solution: impl the marker trait.
1:07 PM Still doesn't need to go both ways.
1:07 PM I mentioned deref only because you were talking about sending a Rc<T> and receiving a T.
1:08 PM 
<ajeffrey> Alan Jeffrey well yes, you can redo that example with Msg<Rc<Data>>.
1:08 PM 
<nox> Same solution?
1:10 PM 
<ajeffrey> Alan Jeffrey Still not sure you can get rid of SameDeserialization,
1:10 PM 
<nox> Well ok.
1:10 PM 
— nox goes back to weekending.
1:10 PM 
<ajeffrey> Alan Jeffrey if you want to round trip &T to T and to Box<T>.
1:12 PM (at least not without O(N^2) impls, where N is the number of ref types).
1:12 PM nox: have a good weekend!

TL;DR: a) can we use a marker trait rather than one with the round_trip method, and b) can we get rid of th SameDeserialization trait?

[asajeffrey]

@nox: we can probably get the same functionality with SameSerialization rather than SameDeserialization, would this improve matters?

[asajeffrey]

With this trait we could write sender.send(&data) as well as sender.send(data), for any type T: RoundTrip<T>. This is still a breaking change, as currently sender.send(data) only requires T: Serializable, but this is less of a breaking change than only supporting sender.send(&data).

[asajeffrey]

Published https://crates.io/crates/serde_roundtrip and https://crates.io/crates/serde_roundtrip_derive today, which means we can have sender.send_borrowed(data) where data: S, sender: IpcSender<T> and S: RoundTrip<T>. This includes the original case where data: &T, as long as T: RoundTrip<T>.

[antrik]

OK, so here's the deal: every time I take a stab at reviewing this, I get stuck trying to figure out what you are attempting to do here... Most notably, why do you need two traits?

Correct me if I'm wrong: but as far as I understand the requirements, all you really need is a way to express that superficially different types result in the same serde/bincode output, i.e. a SameSerialization or SerializesAs trait. What do you need the RoundTrip trait for: why can't you just express the interface for the generalised send() method in terms of SameSerialization or SerializeAs directly?

(To clarify, the difference between SameSerialization and SerializesAs as I see it, is that the former would define a relationship between any two types sharing a common representation; while with the latter, there would be one "canonical" type for each serialisation, and all equivalent types would only declare the equivalence with the "canonical" type. The latter seems preferable, as it avoids an explosion of equivalence pairs -- I'm just not sure whether the extra indirection would pose any problems in expressing the actual trait bounds...)

Aside from that, when talking about the specific interfaces of the methods involved, I think we need to understand that there are two mostly orthogonal issues here: one is the ability to send a borrowed data structure rather than an owned one; and the other is sending different but equivalent types from what the channel is defined as.

I do understand why you need both to cover your use case; and I also do see that there is some conceptual overlap in some cases. However, I think other users might need only one or the other -- and for clarity, it seems necessary to me to consider them as separate issues. Your proposed send_borrowed() interface seems to conflate them in a new method that introduces both sending borrowed data and sending equivalent types at the same time...

As I explained in my latest comment on #138 , I think the cleanest approach for covering the borrowed data use case, is adding two new methods (send_copy() and send_mut()), to complement the existing send() method.

As for sending equivalent types, I must admit that I lack experience in this area to judge how best to define the more generic methods -- though I wonder whether, instead of changing/expanding the set of send methods, we could just introduce a method that transmogrifies a sender into a sender of another, compatible channel type?...

Lastly, a formality: why did you decide to publish this as an independent crate? Did you encounter any problems when you prototyped it as part of Serde? I still believe that Serde/bincode is where this should be implemented, since that's where the serialisations are defined, and thus where the primary knowledge about equivalence of serialisations resides...

(Among other things, it seems to me that implementing the SerializesAs derive right along the Serialize derive itself, would substantially simplify the code...)

[asajeffrey]

The problem with defining the same-serialization trait directly is that it produces conflicting impls, for example (https://play.rust-lang.org/?gist=d1cc6c854d0b062303666dc632977260):

trait SameSerializationAs<T> {}

impl<'a, S, T> SameSerializationAs<S> for &'a T where S: SameSerializationAs<T> {}
impl<'a, S, T> SameSerializationAs<&'a S> for T where S: SameSerializationAs<T> {}

generates:

error[E0119]: conflicting implementations of trait `SameSerializationAs<&_>` for type `&_`:
 --> <anon>:4:1
  |
3 | impl<'a, S, T> SameSerializationAs<S> for &'a T where S: SameSerializationAs<T> {}
  | ---------------------------------------------------------------------------------- first implementation here
4 | impl<'a, S, T> SameSerializationAs<&'a S> for T where S: SameSerializationAs<T> {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`

This was how I stared trying to implement RoundTrip, but in order to avoid overlapping impls I introduced the helper traits. They are just there to avoid overlap.

We could do something like this ( https://play.rust-lang.org/?gist=d31463b1d582a8888646203ac2f1f093):

trait CanonicalSerialization {
    type Canonical;
}

impl<'a, T> CanonicalSerialization for &'a T where T:CanonicalSerialization { type Canonical = T::Canonical; }
impl<'a, T> CanonicalSerialization for &'a [T] where T:CanonicalSerialization { type Canonical = Vec<T::Canonical>; }
impl<'a, T> CanonicalSerialization for Vec<T> where T:CanonicalSerialization { type Canonical = Vec<T::Canonical>; }

Then have something like chan.send_canonical(data) where data:T:CanonicalSerialization and chan:Sender<T::Canonical>.

This approach is slightly weaker, for example it doesn't allow a &T to be round-tripped to a Box<T>. I think the problem here is a trade-off between complexity of the API and trying to capture as many examples as possible.

I just implemented this outside serde since it was easy, I'm quite happy for something like this to be rolled in. One advantage of putting in serde itself is that Serialize could play the role of CanonicalSerialization.

[antrik]

It seems your SameSerializationAs is what I meant with SameSerialization, and your CanonicalSeralization is what I meant with SerializesAs... Though your naming is probably clearer :-)

AIUI, the overlap problem is only because of the blanket implementations; while it wouldn't exist if we derived all equivalence pairs explicitly instead?... Though as I said, the number of pairs explodes as we add more equivalence types -- so it's probably not the best approach.

In your &T -> Box<T> example, AIUI the canonical type for both is just T? So I guess it would be covered, if the channel type is just T, and we define a transmogrify method on the receiver as well. (Or a receive_canonical(), if we stick with that approach...)

I suspect what you actually meant though is for the channel type to be Box<T>. This brings in the "indirection" I mentioned: my idea was that the transmogrify method would allow mapping a Sender<T> to a Sender<S> for any pair of types, where T::Canonical and S::Canonical are the same. Is there any problem with that?

(Again, we could also stick with special send methods instead of transmogrify -- though I guess they should be named something else than send_canonical() in that case...)

Good point about the possibility of adding Canonical to the existing Serialize trait (and I suppose also Deserialize) directly. Is that a breaking change?

[asajeffrey]

Yes, I'm not sure we could get the version where we derived equivalence pairs directly to fly, there's a lot of them!

If we were to do this by modifying serde, we could add T::Canonical to both Serialize and Deserizlize, in which case send would have type:

   impl<T: Serialize> Sender<T> {
      fn send<S: Serialize<Canonical=T::Canonical>>(data: S);
   }

and ditto recv. The type for channel could then be:

   fn channel<S: Serialize, T:Deserialize<Canonical=S::Canonical>>() -> (Sender<S>, Receiver<T>);

Would this be a breaking change? I think not, if we provided a default implementation of Canonical, something like:

   trait Serialize {
      type Canonical = Self;
      ...
   }

and ditto Deserialize. There are some cases where type inference will fail due to the extra generality, but I believe this is allowed by Rust's interpretation of semver.

We could also add the transmogrify methods, something like:

   impl Sender<S: Serialize> {
      fn transmogrify<T: Serialize<Canonical=S::Canonical>>() -> Sender<T> { ... }
   }

Would something like this be worth adding to serde itself?

[antrik]

Hrm, I dropped the ball again...

You are suggesting to allow a channel itself to be instanced with different (compatible) Sender vs. Receiver types; and at the same time to have magic send()/receive() methods that automatically accept different (compatible) types from what the channel is instanced with? That seems a problematic combination, since with no requirement for the types to match strictly at any point, it would completely break inference of channel types from the sent/received data items alone...

If we do explicit transmogrify() rather than magic send()/receive(), I can see some allure to channel having decoupled sender/receiver types (which is something I haven't considered before): since in simple cases, where only one data type is ever sent and another one received, it should just work without any explicit conversions... On the other hand, I'm sceptical of it for the same reason I prefer transmogrify over magic send()/receive(): Rust usually favours explicitness, because auto-magic can be confusing in general, and create confusing error output in particular. And a single transmogrify() call at the sender or receiver is really not much extra effort to avoid...

As for adding something like transmogrify() to Serde itself, that's really just the old discussion about only defining marker traits vs. providing an actual short-circuit method... While I'm not dead set against it like @nox seems to be, I still think it's extra complexity that we'd probably do better to avoid, unless and until someone has an actual (not just hypothetical) use case for it...

(BTW, in case it isn't clear, "transmogrify" is a working title :-) While it would be kinda funny to actually call it that, I suspect users might prefer something more specific...)

[asajeffrey]

True, there'd be problems with inference if we allowed channel to generate different send and receive types. This is probably something of a minority sport, and people who want this effect can use transmogrify().

The signature I was thinking for transmogrify was something like:

   impl IPCSender<S: Serialize> {
      ...
      pub fn transmogrify<T>(&self) -> IPCSender<T> where
         T: Serialize<Canonical = S::Canonical> 
      { ... }
   }

(and diitto for receivers) this would allow (e.g.) sender.transmogrify().send(&data).

Now, should Canonical be in serde or in some other crate? It would be more convenient in serde, but it's still a bit half-baked. Perhaps behind a feature gate?

And yes, transmogrify is a working title!

[antrik]

I guess another follow-up would have been in order?...

@asajeffrey the latest signature you proposed for transmogrify() seems to be exactly what I had in mind :-)

I still think Serde/bincode is the right place to implement this -- in fact, I think it's the only place were we can implement this, if we want Canonical to be added to the existing Serialize and Deserialize traits?...

A feature gate might be in order, if we expect the interface might change between the point at which it is first merged to the upstream master branch, and the point at which it becomes part of the official stable API... Not sure whether this is likely. I guess that's really up to the Serde/bincode maintainers to decide?

[nox]

These days I'm also thinking hard about a dumbed down zero-copy capnproto-like encoding that deserialises slices and whatnot in place, directly in the owned buffer input.

[antrik]

@nox note that mere in-place deserialisation is not exactly the same as the Cap'n Proto approach of working with serialised types directly. It's a less radical departure from the Serde/bincode approach. It might have some merit as a middle-ground, though.

(I suggest moving this over to #138 though, where the previous discussion is much more relevant to this particular topic...)