ZeroArray

[sffc]

I'm trying to make the following data struct Cow-like:

pub struct LineBreakPropertyTableV1<'data> {
    table: [[u8; 1024]; 128]
}

Although table is technically Copy, it results in a huge stack size. The spirit of this data is that we should borrow the data directly from the data provider buffer.

I want something like this:

pub struct LineBreakPropertyTableV1<'data> {
    table: ZeroArray<'data, 128, [u8; 1024]>
}

Looking for feedback from:

• [ ] @Manishearth

[sffc]

For now, I'm just going to wrap a flat ZeroVec<'data, u8> and have a helper function to compute the indexes.

[Manishearth]

is there something that ZeroArray gets us that, say, Cow<'data, [[u8; 1024]]> does not? Because if I extend the ZeroVec metaphor to ZeroArray and have it Deref to ZeroSlice we still get a lot of large copies. ULE is designed around copies being cheap.

Alternatively, use Cow<'data, [u8]> and have a helper for the indexing. (You can also use ZeroVec but you'd lose the ability to take slices)

I think there is a legit use case for ZeroArray, but given the Copy-dependency of ULE I don't think this is such a use case.

[Manishearth]

You can also use ZeroVec but you'd lose the ability to take slices

We probably should add methods to ZeroVec that allow it to be turned into a slice for when T == T::ULE

[sffc]

How does Cow<'data, [[u8; 1024]; 128]> work in Serde? I imagine we may need a custom Serde impl, in which case a wrapper type would help. And if we make a wrapper type, we may as well make it support types other than u8, which is where my ZeroArray idea came from.

[sffc]

pub struct ZeroArray<T: AsULE, const N: usize>(
    pub [T::ULE; N]
);

Note that type ULE for ZeroArray is itself. This means that we should be able to nest them, like

// Normal type
[[u8; 1024]; 128]

// Zero-copy type
ZeroArray<ZeroArray<u8, 1024>, 128>

You can even nest them inside of a ZeroVec

// Normal type
Vec<[char; 10]>

// Zero-copy type
ZeroVec<ZeroArray<char, 10>>

[Manishearth]

@sffc This is what I was imagining, and this gives us a fixed-size version of ZeroVec which seems useful, but it does not fix your problem: The signature of .get() on ZeroVec, by necessity, creates copies (and presumably it will be the same on ZeroArray, if we make it deref to ZeroSlice, too.

[sffc]

Good point. I'm going to close this issue until I get a clearer design.

[sffc]

I'm going to re-open this issue. To answer @Manishearth's original question:

is there something that ZeroArray gets us that, say, Cow<'data, [[u8; 1024]]> does not?

Yes, it gets us a smaller stack size. I wanted something like this for @hsivonen but currently we only support tuples in this way, not arrays.

[Manishearth]

Is that worth the large stack copies on every .get()? Or are you changing the proposed design as well?

Can VarZeroCow help?

(Also, I would like to better understand the problem being solved: it's unclear if it's the same as the one in the original issue, and that problem isn't fully fleshed out)

[sffc]

I envision ZeroArray being a MultiFieldsULE, where you can .get(5) to get the item at index 5. There could potentially be a getter that returns a [T; N] but that seems like a stretch.

[sffc]

The problem is that MultiFieldsULE aka TupleNULE have a limited length since we define only a fixed number of types, currently up to length 6, but I want to have a fixed-length array that is longer. I want a ZeroSlice but with a const length instead of a length stored as a field.

[Manishearth]

@sffc That is still a statement of why a potential solution (multifields/tuple) does not work: what is the actual problem being solved here? "this solution does not work" is not a problem.

Ideally I'd like to see both the concrete data model that needs to be represented and also the general set of data models you are envisioning.

ZeroArray is a bad solution to the concrete example in the issue (nested large arrays) because of the large copy on get(). The example in the issue is the extent of concrete use cases supplied so far, and if that is the only use case provided, then we should close this issue again as a bad idea. It seems you have a different use case in mind, or a different way of applying it, but I cannot read your mind.

Edit: from your comment: avoiding producing a proper array, so having ZeroArray work more like a Var type than a ULE type, could work. I still see some potential issues around nesting.

But this was why we added VarZeroCow: I feel like it should work here? One of the reasons I agreed to that type in the first place was that this particular way of using it fit nicely into the holistic model.

Maybe I'm missing something and VarZeroCow is insufficient, but it's not really worth it for me to speculate until I have the actual problem in front of me

[Manishearth]

Edit: from your comment: avoiding producing a proper array, so having ZeroArray work more like a Var type than a ULE type, could work. I still see some potential issues around nesting

One of the things that worries me here is that we have a very clear difference between fixed size types and variable sized types in zerovec. They can be combined in different ways, but their individual behaviors are well delimited: ULE types are handled via a converting copy and stored flat in the data, and VarULE types are handled by a reference and stored indirectly in the data. This design is baked pretty deeply into the system; and a type that is about fixed-size data but works indirectly isn't going to really fit into the rest of things, and it's going to be easy to accidentally trigger a stack copy like I pointed out in https://github.com/unicode-org/icu4x/issues/1370#issuecomment-990222227.

The problem is that MultiFieldsULE aka TupleNULE have a limited length since we define only a fixed number of types, currently up to length 6, but I want to have a fixed-length array that is longer. I want a ZeroSlice but without a const length instead of a length stored as a field.

I don't think I understand the parallel you are drawing there: MultiFieldsULE is a VarULE type, it cannot be stored directly in a data type. It is not "aka TupleNULE", that's a ULE type and they work completely differently. You probably meant TupleNVarULE? Sorry if this feels like a nitpick, but this is a context where the introduction of VarULE types is already confusing, so while it is clear to me that "MultiFieldsULE aka TupleNULE" was probably a mistake it's unclear to me in which direction, it's further confusing me in a situation where I don't understand the design.

You can do a VarZeroCow<TupleNVarULE<..>> and take a tuple and make it indirect, which is useful in reducing stack size. That only works for Var types: the ULE equivalent would be to use a Cow, except we don't have a way to get Box<T> ToOwned impls, so perhaps this is where we define ZeroCow<T: AsULE>. This type would not itself be ULE or AsULE or VarULE: you cannot nest it, there is no point in nesting it (stack size wins only appear at the top, indirection is pure cost everywhere else). Perhaps it can also be called Indirect<T: AsULE>. Could even be Indirect<T: ULE> since you'd only ever use this type if T is big, and if T is big, you probably don't want magical AsULE conversions happening.

But that is kind of how I see the use cases in this space fit into the holistic model. Assuming I'm talking about the right use cases.

[sffc]

The "actual problem" is Henri's PR which you left some comments on. He has an array which he's storing as a ZeroVec with a pinky promise of being the right length. He could store the array directly on the stack as you observed, but it is more space. I want him to be able to store the array in ULE space.

I think a VarULE with a const parameter could fail to validate if the length doesn't match the const parameter? ZeroArray is then equivalent to ZeroSlice in every way except for a bit of extra type checking. (It does still require encoding the length into data.) Maybe FixedLengthZeroSlice is a better name.

We could and probably should also support non-var ULE arrays up to a fixed length similar to the lengths we support for tuples, more in line with the original shape of this proposal. You copy the array when you need it, which is fine as long as the array is a reasonable size (say, 128 bytes or less).

[Manishearth]

Seems like that issue got resolved, and there wasn't much desire from his side to reduce the stack size anyway. But I see the problem, and nesting doesn't feature there as it does in the original issue (part of the problem here is that nesting gets tricky with a solution like ZeroArray).

I still don't think ZeroArray is the right abstraction here at all. It feels like a strange blend between a fixed and variable size types that ends up having a lot of extraneous costs. E.g. &FixedLengthZeroSlice<N> stores its length twice, it would have an additonal internal invariant that N is its metadata length. Because these are VarULE types, they can only be nested inside a VarZeroVec, even though that's entirely unnecessary. I don't think large arrays should pay VarULE costs to participate in the ULE universe.

The core motivation I see, generalized past the original issue, is that "ULE types are stored flat and sometimes you don't want that". The data model is already representable; it's not a problem, it's only when you mix in this need that you get problems. And I think that need is independent of the data model (the data model is one common way to hit it).

I don't actually think that data model and performance tuning should be conflated in our holistic design: we should have a set of types that provide the ability to represent data in whatever structure we need, and then a separate set of types that let us control performance characteristics.

Observation: Flat storage is only a problem at the top level. Flat storage within e.g. a VarZeroVec[^1] is totally fine.

I think the solution there should not be array-specific. What we're looking for is a spiritual equivalent to VarZeroCow for the ULE universe. To some extent, that equivalent is Cow itself, except Cow::Owned does flat storage for fixed-size data and we want indirect storage.

I think we should support an Indirect<'a, T> where T: ULE (NOT AsULE to prevent footguns). It behaves like a Cow except the owned variant is boxed.

Name TBD: it's a ULE universe VarZeroCow, but I don't actually know if ZeroCow is a good name for it.

We could and probably should also support non-var ULE arrays up to a fixed length similar to the lengths we support for tuples, more in line with the original shape of this proposal. You copy the array when you need it, which is fine as long as the array is a reasonable size (say, 128 bytes or less).

If we make it convenient to avoid flat storage; perhaps we should just have the impl be on all arrays?

I'm thinking we have a blanket ULE impl on all arrays, but we cap out AsULE at some point to avoid the footgun.

That will mostly work until you want to do ZeroVec<[ULEType; 10000]> since ZeroVec enforces AsULE[^2]. This is the type of thing where I've considered introducing an AsULE guard type that's basically an opaque wrapper around a ULE type; forcing you to only ever interact with vec.as_ule_slice(). As previously, this solution works for all large ULE types, not just arrays. I'm confident we can design something workable for guarding here, I do not think we need to until this specific need actually shows up, though.

[^1]: There's a slight footgun with flat storage inside a ZeroVec where you need to remember to use ULE indexing methods only. We could potentially introduce a guard type for that, unsure, but I see a couple routes here if we want to reduce the footgun. [^2]: There's a potential design where ZeroVec<T> doesn't have any bounds on its own and we rejigger half the methods to work when T: ULE + EqULE instead of AsULE but that would be messy.

[sffc]

I understand what you mean by Indirect<'a, T> more now, thanks.

Can we make this work with VarTuple, too? For example, this would be super handy for use cases like "I have a vector that is 3 or more elements long": you can store the first 3 elements in the head and the rest in the variable portion.

[sffc]

I guess I am sort-of talking about a third class of things in zerovec: fixed-length but always borrowed. Let's call this new class of things FixedULE for now. Then we have ULE, VarULE, and FixedULE.

Arrays are not the only thing one might want to stuff in a FixedULE. You could have large structured data that you also want to put in it.

Any ULE can be a FixedULE. Probably we would have a thin wrapper so that we can do things like adding a .get(&self) -> T function to the FixedULE.

ZeroVec should probably still work directly on ULE, since it has a lot of APIs that involve copying. We might be able to make ZeroSlice work with FixedULE, though. Meanwhile, we would probably want another vector type for FixedULE.

[Manishearth]

I understand what you mean by Indirect<'a, T> more now, thanks.

Can we make this work with VarTuple, too? For example, this would be super handy for use cases like "I have a vector that is 3 or more elements long": you can store the first 3 elements in the head and the rest in the variable portion.

I'm not sure what you're asking for here. I'm guessing the need is "I want to indirectly store a type that has a fixed-length header and a variable length 'rest of the data' thing"? You already can do that:VarZeroCow<VarTuple<Header, Rest>> gives you a fully indirect "variable length type with a header". If you want split allocations you can do (Indirect<Header>, Rest) (you don't need a (var)ULEverse type at the top level).

Basically the indirect allocation problem is already solved for the VarULEverse via VarZeroCow. The ULEverse is where you need something, and Indirect<T> should solve most of that.

I guess I am sort-of talking about a third class of things in zerovec: fixed-length but always borrowed. Let's call this new class of things FixedULE for now. Then we have ULE, VarULE, and FixedULE.

Yeah, that's my worry, I don't want to expand the class of types here for an optimization: I want the data model types to remain data model types, and optimization tweaks to live at a separate layer. I find dealing with two ULEverses to already be a pretty large headache for working in this world (see: ZeroMap); a third seems like too much to handle.

I dislike ZeroArray as a solution because it creates one entry in a brand new class of types that will inevitably need to grow once we retool the zerovec universe to be good with that class of types.

I think we can get all the benefits here without introducing a new kind of ULEverse. Indirect + the rough design I have for guard wrappers should work sufficiently in a way that doesn't leak all over the place.

[Manishearth]

Leaving issue open for some form of Indirect<T>. The precise design can be figured out while implementing.

If we feel like ZeroArray is necessary after seeing Indirect, we can revisit this discussion.