ZeroCow: a one-element, owned-or-borrowed VarULE

[sffc]

Related: #5523 and #5531 #1556

It fits into the holistic zerovec design to have a new type ZeroCow.

It holds onto an owned-or-borrowed VarULE. There is no need to have a ZeroCowULE because the ULE will be the VarULE.

Crucial differences from alloc::borrow::Cow:

1. It will have correct (borrowing) impls in serde
2. It can avoid branching like we did in ZeroVec
3. Might be able to reduce stack size: Box instead of Vec for the owned type

@Manishearth

[Manishearth]

The owned type for Cow for these types should already be Box (except for str). I don't really see a huge benefit to (2), and we already have workarounds for (1), this feels like an unnecessary microoptimization. I don't really want to duplicate the Cow infrastructure for this.

[Manishearth]

Actually, I'm a bit confused as to the use case: where are we even putting VarULE types in a Cow?

[robertbastian]

I totally support this for serde borrowing, which is broken for Cow.

Might be able to reduce stack size: Box instead of Vec for the owned type

I don't think this is possible. The &[u8]/Box<[u8]> don't have a niche, so we need an additional usize to store the discriminator.

[Manishearth]

I basically don't think this makes sense in the zerovec universe. It may make sense in the ICU4X universe because avoiding the Cow problem is something that crops up often for us. It is not something I expect to crop up as often for zerovec clients.

[robertbastian]

icu4x/components/plurals/src/provider.rs

Line 371 in 3694bfe

pub elements: Cow<'data, PluralElementsPackedULE<V>>,

[Manishearth]

Yeah, I see. I think optimizing this is an ICU4X concern, not a zerovec concern. I really don't think this fits into the holistic design that well, it's just a slight improvement over Cow in a couple ways that most users won't care about.

[sffc]

It's a zerovec concern to create ZeroVec<T>. We could have just had Cow<ZeroSlice<T>>.

It's a zerovec concern to create VarZeroVec<V>. We could have just had Cow<VarZeroSlice<V>>.

I think it is also a zerovec concern to create ZeroCow<V>.

Another advantage I'll add:

4. The bounds on the serde impls get simpler. VarULE is already serializable to bytes, so the borrowed serde impl doesn't require any extra bounds. The Cow serde impl just requires an EncodeAsVarULE bound. We can also get rid of ToOwned bounds which are known by experience to cause problems, not to mention deserialize_with.

[sffc]

About stack size: what I was thinking (the reason I said "might") is that there are some various ways of various levels of desirability that we could get an extra niche. The most likely is that we limit the length of the VarULE to be 1 bit less than the length of a usize; to be most general, the inner representation would be:

(*const u8, u32)

Where the u32 has 1 bit for the discriminant (owned/borrowed) and 31 bits for the length. The total size of this type is 8 bytes on wasm32 and 16 bytes on aarch64. I'm comfortable with this length limit because it is the same as ICU4C's length limit: it uses i32 lengths, and all negative numbers are essentially used for discriminants when needed.

With this representation, a read would & the u32 on 0x7fffffff, which is one step but no branching and therefore probably cheaper than a Cow branch.

These are optimizations we can do with ZeroCow that we can't do with Cow, and the optimizations are VarULE-specific, providing further evidence that this type belongs in the zerovec universe

[Manishearth]

It's a zerovec concern to create ZeroVec<T>
...
It's a zerovec concern to create VarZeroVec<V>

... barely. I actually think in retrospect trying to design this crate to contain its own Cow types wasn't the best idea, and we now need to maintain gnarly VZV mutation code, even though in practice users are either constructing fresh VZVs or are just reading from them.

We kind of ended up with this after multiple iterations on the design where ZV and VZV were more "parallel" to each other in behavior. I think it made a bit more sense then, but we've moved past that when we learned that design didn't work well.

The cow-iness of the primary types here comes from an assumption about supporting both human readable and binary deserialization, which is true for ICU4X but isn't actually that necessary for a lot of people choosing to use zero-copy deserialization. Cow is commonly useful in zero-copy deserialization, but it's an orthogonal concern.

If I were to design these types today, I'd potentially have ZeroSlice<T>, Cow<ZeroSlice<T>> (wrapping either Vec<T::ULE> or a fully owned ZeroVec<T::ULE>), and VarZeroSlice<T>, Cow<VarZeroSlice<T>> (wrapping a fully owned VarZeroVec<T> which may not actually have mutation methods). Given that we've put the work into these and have some optimizations in them now that we need, I'd rather not remove the existing ones, but I really don't think it's a zerovec concern and don't want to add more.

I think it is also a zerovec concern to create ZeroCow<V>.

At least with ZeroVec/VarZeroVec the types were ones we created and we needed to make owned/borrowed versions. That's not the case with VarULE types, they're often third party and already work with Cow.

The Cow serde impl just requires an EncodeAsVarULE bound. We can also get rid of ToOwned bounds which are known by experience to cause problems, not to mention deserialize_with.

I can't see this working, EncodeAsVarULE is too generic to give you a concrete owned type. We would need something like ToOwned, still, for a ZeroCow to work.

The bounds on the serde impls get simpler

Only if we wish to lose convenient human-readable deserialization.

---

I think this issue is proposing adding a type to zerovec to work around a serde concern. I know serde has refused to move forward on this, but I don't think that makes it zerovec's job: I think if anyone is to do this it should be some common ICU4X crate (icu_shared as previously proposed?). We already do this to some extent with the icu_provider Cow helpers.

[sffc]

I think this issue is proposing adding a type to zerovec to work around a serde concern.

I used to think this, but my thinking shifted when I thought more about it.

icu_shared as previously proposed?

I remain generally opposed to icu_shared except for macros that can be shared without a runtime dependency. If we need a common dep, it should be in its own crate.

I can't see this working, EncodeAsVarULE is too generic...

It's not EncodeAsVarULE, sorry, it's just Box<V>: Deserialize that we need in the bound. Still, one nice clean bound. My point stands that VarULE is already deserializable.

---

Your response is primarily focused on the theoretical best home for this type.

I still think zerovec is the correct home. zerovec exists because of Serde. If it weren't for ICU4X wanting to support Serde and then Serde forcing us into [u8] for borrowed data, we could have used Cap'n Proto or similar for our zero-copy data. I realize a potential second user of zerovec could be byte stream APIs, those which zerocopy serves, but this has not been a goal so far. Serde has been our goal, period. Therefore, zerovec can and should provide types that ease the interface between its wire types and Serde structs. ZeroVec, VarZeroVec, and ZeroCow.

I agree with you about mutation; I was never super excited about mutation. A design I might have preferred, and could see myself supporting if we wanted to move in this direction, would be type ZeroVec = ZeroCow<ZeroSlice>.

You also didn't address the technical benefits that my proposed type can bring above and beyond what Cow can offer. Is that because you're generally in agreement that we should have the type, and only in disagreement about where it should live?

[Manishearth]

zerovec exists because of Serde

Okay, but it's for zero-copy deserialization in serde. It is not for fixing every shortcoming that serde has. I think patching the Cow thing is out of scope for this crate. I also think "a stack size optimized Cow" is out of scope for this crate: that is a benefit ICU4X and as far as I can tell basically only ICU4X cares about.

You also didn't address the technical benefits that my proposed type can bring above and beyond what Cow can offer. Is that because you're generally in agreement that we should have the type, and only in disagreement about where it should live?

So I'm not convinced of the benefits either, for a general audience. The benefits seem extremely marginal over Cow. The stack size benefit in particular is something ICU4X cares strongly about and is why I would support having this type somewhere (icu_provider seems fine), but Rust programmers by and large care about stack size extremely rarely. The branchlessness is a premature optimization; we made VZV branchless primarily for stack size, not for the perf, which was fine.

Basically: I see this as something that makes some sense for ICU4X. I do not see this as something that is useful for most zerovec consumers, and even if it were I'm not convinced zerovec is the home for it, which makes me strongly oppose having this be in the zerovec crate.

I also think that we should just use Cow unless Cow is actually proving to be a problem. I don't consider needing to use deserialize_with a bunch or an extra byte of stack size to be a major problem.

I've said this before but I'll say it again: I don't like that we keep stuffing the zerovec crate with a grab bag of abstractions that make sense for ICU4X. I want it to be more intentionally designed: we're moving towards it in #5523 which I'm very happy about but I would like for our first reaction to new serialization abstractions to not be to add it to zerovec. I think such things should at least incubate more before we add them.

It's not EncodeAsVarULE, sorry, it's just Box<V>: Deserialize that we need in the bound. Still, one nice clean bound. My point stands that VarULE is already deserializable.

Those are the bounds we need now. That's not a new benefit as far as I can tell.

[sffc]

I think I understand your position, and I think we differ one some fundamentals and experiences. More on that later.

To break down that middle paragraph:

Basically: I see this as something that makes some sense for ICU4X.

OK. Glad we agree on the principle there, even if I see it as making more sense than you do.

I do not see this as something that is useful for most zerovec consumers

I very much disagree with this statement. It is absolutely useful for "most zerovec consumers". That audience is using zerovec because of serde, and they want to put VarULEs in serde structs in exactly the same way ICU4X does, and they can't do so right now because of the Serde bugs involving Cow, which can be hard to detect, resulting in clients getting more allocations than they should. We, the ICU4X team, didn't even notice the Serde bug right away when we started using cows in data structs.

More on this below.

and even if it were I'm not convinced zerovec is the home for it

I haven't heard a counter-suggestion of a home for this type other than icu4x_shared which is not relevant in the hypothetical that it is a type relevant to zerovec consumers.

One other thing you said earlier which I didn't respond to:

The cow-iness of the primary types here comes from an assumption about supporting both human readable and binary deserialization, which is true for ICU4X but isn't actually that necessary for a lot of people choosing to use zero-copy deserialization. Cow is commonly useful in zero-copy deserialization, but it's an orthogonal concern.

ZeroCow doesn't need to use human-readable serialization. It can always serialize to bytes if it wants. I'm happy to discuss the predicate used for forking between Box and &[u8] and/or ways for clients to signal that.

[sffc]

Would you agree that the following would be in scope for the zerovec crate: a standalone tutorial module showing people how to put zerovec types into a data struct for zero-copy deserialization with Serde. The tutorial would include a section explaining how to integrate the types with Cow, highlighting the downfalls of Cow in Serde, and offering workarounds such as deserialize_with, including having to add explicit type parameters to work around the rustc bug you found.

If you agree that such a tutorial is useful, then you agree that this problem space is in scope for zerovec, even if you don't agree with the exact proposed solution.

[sffc]

About ToOwned:

We don't need ToOwned, because VarULE gives us everything we need. We can get a byte slice, allocate it, and cast it back. That's something ToOwned can't do. Therefore, one fewer bound and impl to deal with.

[sffc]

I'm trying to break down where we disagree.

Fundamentals

Fundamental: The bar for adding things to zerovec

Maybe we don't agree on the cost of adding abstractions to the zerovec crate. I feel that the bar should not be super high for adding things to the crate. Not super low, but also not super high. If there's a feature that is useful for "a typical zerovec user", then the feature should be in scope.

In my experience, there are two broad types of library crates: "useful" ones and "minimal" ones. Examples:

• Serde: minimal
• Jiff: useful
• Log: minimal
• Clap: useful

zerovec is one I see as a useful crate. It has both the core traits, ULE and VarULE, as well as abstractions that make them easier for clients to use.

If we want zerovec to become a minimal crate, then we should split it. I wouldn't be opposed to that on principle. But, right now it is a useful crate, and the bar for adding things should reflect that.

Fundamental: ICU4X as a typical zerovec client

Maybe we don't agree on the degree to which ICU4X is an average zerovec user. I think that the way we use zerovec in Serde structs for zero-copy deserialization is very much an "average" or "typical" use case for zerovec. The databake stuff, yokeable stuff, maybe not. But the fundamental concept of getting VarULE types and stuffing them into a data struct with lifetimes on it, absolutely.

I definitely don't consider everything to be in scope for zerovec. Some modern examples:

• ZeroTrie: no, put in its own crate.
• PackedPatternULE: no, put in an ICU4X crate, although I would like to see the enum abstraction upstreamed at some point.

When I say that I think something is in scope for zerovec, it's because I think it is useful for the typical zerovec user, not just ICU4X, and I've weighed the benefits in my mind.

Side note: If it were only up to me, I would like to have a lower bar for zerovec additions, fed more strongly by ICU4X's special needs which I don't consider all that special (optimizing for binary size, memory use, etc), but I respect that we want to have a more clear separation of needs between ICU4X and zerovec. I don't consider ZeroCow as violating that principle.

Fundamental: Borrowing serde impls are relevant to the typical zerovec client

Based on the previous fundamental, "data structs with cows" is a use case for a typical zerovec client. Since zerovec is all about zero-copy, making borrowing impls work is relevant to the typical zerovec client.

Fundamental: Reduced branching is relevant to the typical zerovec client

Clients use zerovec because they are looking to juice their performance. The extra branching in std::borrow::Cow is something we have previously established to show up in microbenchmarks, which propagates up the stack to read-heavy operations such as those on zerovec's top-level documentation page.

Note that I didn't include "stack size" in this list as relevant to the typical zerovec client because I think the argument there is not as strong, even though it would benefit some subset of clients besides just ICU4X.

By Experience

By Experience: deserialize_with is not discoverable and is a pain to use

I did not discover the flaws of Cow until almost a year after I started using it. I offered to either fix the problem in the serde crate or (at least) add documentation on the Cow footgun to the serde crate, but both offers were turned down. deserialize_with exists as an alternative, but it is not an elegant solution. Firstly, it is very much syn dependent in serde-derive: there is no solution in core serde. Secondly, deserialize_with (which is treated in code as a Fn, not a trait) exercises corners of the Rust compiler that result in ICEs and compiler bugs. We have seen not one but two examples in the last week of Robert and me trying to get it to work. HRTBs are another Rust feature that hit corners of the compiler, and I think you agree that it's generally nicer to avoid them.

By Experience: Implementing serde on things with Cow<VarULE> requires code that is confusing, and ZeroCow would improve the developer experience

I always dread implementing serde on ICU4X data structs involving naked Cow<VarULE>s. The code requires a deep understanding of serde, serde-derive, and low-level zerovec all at once.

I make a claim that ZeroCow would make serde impls much easier. As far as I can tell, only one impl would need to be written manually: impl Deserialize for Box<V>, and I guess also impl Serialize for V if you want to serialize, too. Both of those impls should be easy to write, since it's just branching to other impls based on is_human_readable(). However, with stock Cow you need these additinal impls:

• impl Deserialize for &V
• impl ToOwned for V
• Plus the deserialize_with function.

So my expectation is that the total amount of code for implementing Serde would be cut down by approximately half, and it would be less error-prone.

[Manishearth]

Thanks for writing this out, it's helpful.

TLDR: let's focus on that last "by experience" point about the complexity of implementing serde, I think that's the primary key problem here and I'm not familiar with it. I'm not convinced that ZeroCow is the only solution, but it does seem compelling, and we should drill down into that.

---

In my experience, there are two broad types of library crates: "useful" ones and "minimal" ones. Examples:

I'm not sure I fully agree with this distinction, or at least the terms used, but I think my issue here is coming from from a slightly different distinction: "new" and "mature" crates. A "mature" crate is one that may still contain a lot of stuff, but things are added with care, and it has a coherent structure. We've been trying to get ICU4X to this stage over time, and overall we've been succeeding. We are able to do this without being minimal, we're just careful.

I'd like zerovec and yoke to be something that are considered more "mature". I'm quite happy with the trajectory yoke has taken, but I think zerovec needs a lot more work and I'm wary of making the problem worse.

I think this sense of maturity is rather important: zerovec is a large, highly unsafe dependency of ICU4X. I'd like people to have a high opinion of the crate, and I'd like people to not have a hard time unsafe reviewing it. These two work in concert when it comes to Rust-focused clients¹ accepting this as a dependency; it's fine having more and more unsafe (especially hard-to-review unsafe²), but then it may need to be more and more "worth it". "worth it" can derive from the quality, the maturity, and/or the proliferation of the crate. E.g. encoding-rs was painful to review, however because it is rather popular everyone thought it worth it to put in the extra effort into reviewing it and even cleaning up the unsafe ³.

I've seen this dynamic of "not worth it" play out a couple times for unsafe review at Google where we've told importers of some relatively unknown ball of unsafe abstractions that we cannot review their crate, which gives them the options to either visibility restrict (which means the code will not be allowed in security sensitive environments like prod), or find alternate dependencies. I'd rather not have ICU4X be in this position: most larger codebases are starting to care a lot more about unsafe code now and this is going to be in a bigger and bigger problem. While in general consolidating one-off bits of code into generic code is considered good practice, the tradeoff is trickier with unsafe code since generic unsafe code is a much higher bar.

To be clear, unsafe is not the only time I care about maturity: I care about maturity for all of our utils crates; and for Diplomat, but unsafe makes maturity more of a pressing matter in my eyes.

One of the reasons I care a lot about doing #5523 is that it hopes to clean up some of the haphazardness that we have built up over time and provides a more holistically thought out interface. I'm hoping to convince someone to do a proper safety audit of zerovec soon, and this helps make that an easier sell.

So the main aspect of maturity here is just how well thought out the overall œuvre of abstractions are in this crate. This is why I tend to place a high value towards incubating these abstractions more, either as private zerovec abstractions or as ICU4X shared abstractions. We've already come a long way and realized what the holistic model looks like, and it's different than what things looked like when we added them, like in #5523.

Another aspect of maturity of a crate is that the crate has a clear target audience, and this is also why I tend to be wary of strongly coupling zerovec to ICU4X's needs. I've expressed similar opinions when it comes to Diplomat before. In particular, Google-run open source projects have an especially bad reputation for having this problem, and it leads to people . ICU4X is not Google-run, but zerovec is effectively maintained only by Googlers, and I can see this reputation easily harming us when it comes to more adoption. I feel like Diplomat has benefited quite a bit from this, there have been a bunch of places where we could have been far more streamlined for ICU4X⁴ but we went generic and have benefitted from more users, free backends, and more compelling intern projects.

To me, zerovec's target audience is congruent to that of rkyv: People who wish to do zero-copy deserialization, but want to use serde to retain flexibility on the final output format, and/or to have an easier time integrating with the ecosystem.

This brings us to the next thing:

Fundamental: ICU4X as a typical zerovec client

I think ICU4X is close to a typical zerovec client in many ways. I think the need for Cow-like behavior is somewhat typical, in the sense that there is a large class of zero-copy users that needs it, and another large class of zero-copy users⁵ that doesn't. I think the desire for optimized Cow-like behavior is much less typical.

(And as you note: the need for optimizing stack size is also definitely atypical)

fed more strongly by ICU4X's special needs which I don't consider all that special (optimizing for binary size, memory use, etc)

FWIW I think optimizing for binary size is absolutely not special and a standard zerovec user need, as is heap memory use. Less so on stack memory use.

I do sometimes feel that some optimizations aren't "worth it" when it comes to the complexity that they bring us, either for ICU4X or for zerovec. This is what led to me pushing for #5523, where we can get a bunch of optimizations whilst reducing complexity instead of growing it. Hopefully. I'm still working on it and as I previously noted some of the wins I was hoping to get aren't as easily possible, but it's still a net win in my prediction.

Fundamental: Borrowing serde impls are relevant to the typical zerovec client

Agreed, however as I note above I think borrowing Cow-like serde-impls are only somewhat relevant. Which is still something to care about, but just registering that I care somewhat less than borrowing in general.

Fundamental: Reduced branching is relevant to the typical zerovec client

I am not convinced of this. I could be convinced, but I'm not at the moment. I recall the branching showing up in microbenchmarks, but I don't recall it being a huge deal (I could be wrong! I don't know the numbers), and I'm also not convinced that the microbenchmarks are showing the numbers actually relevant to the clients. They've been designed to give a general idea of how the crate works perf-wise ("okay, zerovec is slower than vec, but not too much slower, and varzerovec is noticeably slower than vec, but not onerously so"), but I'm not sure they're actually what matters for clients.

I'm not even convinced this matters for ICU4X's usage patterns that much; almost all of our zerovec-using data structs are used in formatter types that have far far more branching all over the place. I'm open to doing the optimization just for ICU4X but I don't find it super relevant. Looking at the microbenchmarks on zerovec, ICU4X definitely cares about deserialization perf, however for the read microbenchmarks, most of the time ICU4X is doing a single read or a single binary search⁶ amidst a pile of formatter code; not a ton of reads in a row.

With ZeroCow the optimization is even more clear to not be optimizing "a ton of reads in a row": with zerovec I can kind of imagine a usage pattern that hits the same vec multiple times in a way that retriggers the branch⁷, but with ZeroCow it's just one thing; I imagine it would mostly get read once.

(I'll also note that ZeroCow replaces a branch with a bitmask which is not as fast as getting rid of the branch entirely. Still should move the needle)

So overall with ZeroCow's branchlessness I see an optimization I'm not convinced is useful for ICU4X, and I'm even less convinced is useful for the general zerovec audience. It's an optimization I'm happy to perform prematurely in ICU4X to play around with it, but I feel like it reduces zerovec's overall maturity.

By Experience: deserialize_with is not discoverable and is a pain to use

I agree, I just mostly feel that "fixing Cow in serde" feels like scope creep for zerovec.

Firstly, it is very much syn dependent in serde-derive: there is no solution in core serde.

I don't think this makes sense: it's a problem with serde-derive in the first place. Manual serde impls don't have this problem. It's a bit of a non sequitur to ask for there to be a core serde solution to a problem that is not there in core serde.

Secondly, deserialize_with (which is treated in code as a Fn, not a trait) exercises corners of the Rust compiler that result in ICEs and compiler bugs

This is compelling, though this still matches my read of this being a "serde + Cow" problem regardless of zerovec, that we should patch in a separate util or an ICU4X function stuffed in some ICU4X crate somewhere.

I don't think the Fn-vs-trait thing is the primary issue here. I actually think that the Rust compiler corners are just inherent to Deserialize's design in general, I'm not sure this is particularly prone to it. But we can poke at that more.

By Experience: Implementing serde on things with Cow requires code that is confusing, and ZeroCow would improve the developer experience

I always dread implementing serde on ICU4X data structs involving naked Cows. The code requires a deep understanding of serde, serde-derive, and low-level zerovec all at once.

Okay, this is interesting. I don't think I've experienced this and would like to hear more. Requiring a deep understanding of all three of those is somewhat compelling to me for this to go into zerovec.

I also think that understanding this problem may lead to us discovering alternate solutions, for example make_varule⁸ probably should implement ToOwned as well, which in retrospect is a very obvious and clear bit of missing functionality! I'm not sure that's the only aspect of this triangle that needs fixing, but IMO Cow<T: VarULE> should be just as pleasant as Cow<str> ⁹, regardless of what else we decide here.

impl ToOwned for V

I previously couldn't see a ZeroCow design that avoids this. But potentially ZeroCow<OwnedType, BorrowedType> would work. as long as there was an EncodeAsVarULE impl? I'm not sure. I didn't realize this was a part of the purported benefit, I was imagining the design to be ZeroCow<BorrowedType> which still requires a ToOwned-equivalent, and no such equivalent trait currently exists in zerovec (and I don't think it should).

Footnotes

1. I perceive the focus on unsafe review to be something mostly done in places that have a strong enough Rust focus to care; places that are very C++-heavy will often consider unreviewed unsafe Rust to be better than C++. ↩

2. I think yoke is quite decent in how it does unsafe, but zerovec is a bit messier. I'd love to have time to clean this up, I do think this would be rather high impact on client adoption, including at Google, even though when it comes to Google we have ways of temporarily deferring review, and I may also be able to get a proper audit prioritized. ↩

3. I'm still on the hook for doing some of this, but I'll get around to it eventually. ↩

4. Recently I also was asked "why don't we add protobuf support to Diplomat" which is exactly the type of Google-open-source dynamic that leads to the bad reputation. ↩

5. Namely, those that wish to be always zero-copy. This is a nontrivially sized group, I perceive it to be pretty large and potentially even the majority. ↩

6. Which avoids the branch since it's a method on the slice type ↩

7. Note that this is pretty hard. Common subexpression elimination optimizations will collapse the branches in most immutable scenarios. The microbenchmarks deliberately avoid this to give people an idea of the cost of a single read. ↩

8. And also every VarULE combination type in zerovec (VarTupleN, VarTuple), and also whatever non-proc macro VarULE thing we come up with in https://github.com/unicode-org/icu4x/issues/5127 ↩

9. Which isn't 100% pleasant because of the serde issue, but it's not that unpleasant and overall often straightforward to work around. ↩