Abandon Primitive List -> Struct List upgrades?

[Kenton Varda]

Cap'n Proto currently allows e.g. List(Int32) to be upgraded to List(MyStruct) where MyStruct's @0 field is of type Int32. I'm starting to wonder whether this ability should be abandoned.

I originally specified this feature because I have seen cases where people defined a protocol using a primitive list and then had problems when they later realized they needed to attach some extra info to each item. Usually they end up with parallel arrays, which are sad.

But this problem is fairly rare, and meanwhile this requirement has made things more complicated than I expected. Here's some of the problems:

- Andy's canonicalization work is almost super-elegant in that it can operate on a message without knowing the schema. All it does is chop off zeros from the end of structs. But it can't easily tell if a primitive list is actually a list of small structs that potentially need similar truncation.

- capnp::List<T> is considerably less efficient than it could be when dealing with primitive lists, as it has to accommodate the possibility that the elements are not tightly-packed. Accessing an element of a primitive list involves multiplying the index by a runtime-variable "step".

- For some use cases, it would be very valuable to be able to get a direct pointer to an underlying array of primitives, e.g. to pass off to a GPU without copying. Currently this is not possible due to the aforementioned possibility of arbitrary spacing. See: https://github.com/kentonv/capnproto/pull/87

- Structs which have a boolean field @0 currently have to handle the possibility that they may be represented as a single bit which may not be byte-aligned. This is pretty painful to deal with. In C++ it is more of a complexity penalty than an actual performance penalty, but in other languages I'm betting it's worse.

----

With all that said, there are a few problems with simply dropping this compatibility rule today:

- Existing code will actually, as an optimization, encode structs as primitive lists, when those structs are small enough to fit. E.g. a struct containing two Int16s will be encoded as a list of 32-bit elements. With the proposed change, we'd stop writing structs that way and instead always encode them as composite lists. But, we probably need to continue accepting structs encoded as primitives because there is probably existing data out there that we need to go on supporting. Perhaps we can at least assume that no one relies on single-bit structs, though?

- Of course, dropping said optimization would be sad in itself, although in practice I don't think it would be a huge impact. It does mean that you'd no longer want to encode pixel data as a list of structs containing four 8-bit r/g/b/a channels, but I doubt anyone is doing that anyway specifically because if you're encoding pixel data you probably want direct access to the bytes in order to pass them to a GPU as mentioned above. In the new world, List<UInt8> would be the appropriate encoding for such data, and you'd just have to manually group the list into 4-element groups for each pixel.

Thoughts?

-Kenton

[Michi Henning]

Hi Kenton,

- For some use cases, it would be very valuable to be able to get a direct pointer to an underlying array of primitives, e.g. to pass off to a GPU without copying. Currently this is not possible due to the aforementioned possibility of arbitrary spacing. See: https://github.com/kentonv/capnproto/pull/87

Of all the points you mentioned, this one is the killer argument to me. Getting zero copy from the marshaling buffer is big win in some scenarios. To me, this carries a lot of weight.

- Existing code will actually, as an optimization, encode structs as primitive lists, when those structs are small enough to fit. E.g. a struct containing two Int16s will be encoded as a list of 32-bit elements. With the proposed change, we'd stop writing structs that way and instead always encode them as composite lists. But, we probably need to continue accepting structs encoded as primitives because there is probably existing data out there that we need to go on supporting. Perhaps we can at least assume that no one relies on single-bit structs, though?

I don't know how much legacy baggage there is. But, considering that the code should still be considered pre-release, I don't think I'd worry too much about this corner case.

- Of course, dropping said optimization would be sad in itself, although in practice I don't think it would be a huge impact. It does mean that you'd no longer want to encode pixel data as a list of structs containing four 8-bit r/g/b/a channels, but I doubt anyone is doing that anyway specifically because if you're encoding pixel data you probably want direct access to the bytes in order to pass them to a GPU as mentioned above. In the new world, List<UInt8> would be the appropriate encoding for such data, and you'd just have to manually group the list into 4-element groups for each pixel.

I agree. With the OpenGL work I did, the natural thing to do was to pack RGBA into a 32-bit word because that's what the GPU wants to see anyway.

Michi.

[Kenton Varda]

Thanks for the feedback!

On Fri, May 9, 2014 at 12:00 AM, Michi Henning <mi...@triodia.com> wrote:

Hi Kenton,

- For some use cases, it would be very valuable to be able to get a direct pointer to an underlying array of primitives, e.g. to pass off to a GPU without copying. Currently this is not possible due to the aforementioned possibility of arbitrary spacing. See: https://github.com/kentonv/capnproto/pull/87

Of all the points you mentioned, this one is the killer argument to me. Getting zero copy from the marshaling buffer is big win in some scenarios. To me, this carries a lot of weight.

It should be noted that a reasonable alternative exists today: Use `Data` instead, and manually cast the pointer to the desired type. This has the disadvantage of losing type-safety, but the arguable advantage of making it really obvious that the platform isn't handling endianness issues.

But, yes, it's pretty ugly and unintuitive to have to use such a work-around.

-Kenton

[Andreas Stenius]

I like it the way it is now, and would be a bit sad too, if the packed version
went away.

About being able to pass off a direct pointer to the GPU, that ought to be
possible as long as the list has not been upgraded. And whether this is the
case or not is detectable at runtime, right?
So, an application could check if the list is suitable for passing off with a
direct pointer as-is, or if a copy is required (and could act accordingly).
Does this fall under the category "application shoots schema author in the
foot"?
I think it would be a fair trade-off that those who need to use lists in such
ways, keep their schema compatible with such uses. No need to use `Data` and
type-casts.

[Kenton Varda]

On Fri, May 9, 2014 at 1:01 AM, Andreas Stenius <andreas...@astekk.se> wrote:

I like it the way it is now, and would be a bit sad too, if the packed version
went away.

Well, good to know that one of the people who has gone through the whole process of implementing my spec doesn't think it's entirely crazy... :)

Have you seen any use cases where it came in handy, or is this more of a gut feeling?

 

About being able to pass off a direct pointer to the GPU, that ought to be

possible as long as the list has not been upgraded. And whether this is the
case or not is detectable at runtime, right?
So, an application could check if the list is suitable for passing off with a
direct pointer as-is, or if a copy is required (and could act accordingly).
Does this fall under the category "application shoots schema author in the
foot"?

Yes, because most applications won't actually do this check, or they'll do it but won't properly test it and it won't actually work. I want to avoid exposing apps to corner cases they are unlikely to handle.

 

I think it would be a fair trade-off that those who need to use lists in such
ways, keep their schema compatible with such uses. No need to use `Data` and
type-casts.

Then there should be an annotation that says "Schema owner promises this list will never be upgraded".

-Kenton

[Andreas Stenius]

On Friday 09 May 2014 01.10.29 Kenton Varda wrote:
> On Fri, May 9, 2014 at 1:01 AM, Andreas Stenius
>
> <andreas...@astekk.se>wrote:
> > I like it the way it is now, and would be a bit sad too, if the packed
> > version
> > went away.
>
> Well, good to know that one of the people who has gone through the whole
> process of implementing my spec doesn't think it's entirely crazy... :)
>
> Have you seen any use cases where it came in handy, or is this more of a
> gut feeling?

No, not so far, just my gut feeling.

> > About being able to pass off a direct pointer to the GPU, that ought to be
> > possible as long as the list has not been upgraded. And whether this is
> > the
> > case or not is detectable at runtime, right?
> > So, an application could check if the list is suitable for passing off
> > with a
> > direct pointer as-is, or if a copy is required (and could act
> > accordingly).
> > Does this fall under the category "application shoots schema author in the
> > foot"?
>
> Yes, because most applications won't actually do this check, or they'll do
> it but won't properly test it and it won't actually work. I want to avoid
> exposing apps to corner cases they are unlikely to handle.

Ah, but then again, capnproto could actually implement those checks
before handing out a pointer to the application, so the application
will get an exception (or maybe null?) in case the list is unusable as
a direct source for GPU operations (or what not). This way the
application doesn't need to test anything apart from that it actually
got a valid pointer (or be prepared to handle an exception). Either
way, the list testing logic is moved away from the application ;)

>
> > I think it would be a fair trade-off that those who need to use lists in
> > such
> > ways, keep their schema compatible with such uses. No need to use `Data`
> > and
> > type-casts.
>
> Then there should be an annotation that says "Schema owner promises this
> list will never be upgraded".

What effect would/could/should that have on the generated code?

//Andreas

[Igor Lubashev]

I am currently working with a system, where upgrades of primitive lists in messages via parallel arrays happened multiple times. Sad. The ability to promote primitives to structures is an asset.

As for a desire to get primitive lists by a pointer, the reasoning about the API is rather straightforward. A list can either require this access or not. This requirment is driven by the application semantics from the very beginning. It cannot just happen without the application writer realizing it or forgetting about it in version 2 and replacing a primitive with a struct.

As long as there is a function to get a pointer to a list of a particular type, everyone will be happy.

[Andrew Lutomirski]

On Thu, May 15, 2014 at 8:50 PM, Igor Lubashev <igor...@gmail.com> wrote:
> I am currently working with a system, where upgrades of primitive lists in messages via parallel arrays happened multiple times. Sad. The ability to promote primitives to structures is an asset.
>

Is this the kind of list where someone would have been willing to add
an upgradable annotation?

> As for a desire to get primitive lists by a pointer, the reasoning about the API is rather straightforward. A list can either require this access or not. This requirment is driven by the application semantics from the very beginning. It cannot just happen without the application writer realizing it or forgetting about it in version 2 and replacing a primitive with a struct.
>
> As long as there is a function to get a pointer to a list of a particular type, everyone will be happy.
>

--Andy

[Igor Lubashev]

On Friday, May 16, 2014 12:38:38 AM UTC-4, Andrew Lutomirski wrote:

On Thu, May 15, 2014 at 8:50 PM, Igor Lubashev <igor...@gmail.com> wrote:
> I am currently working with a system, where upgrades of primitive lists in messages via parallel arrays happened multiple times. Sad. The ability to promote primitives to structures is an asset.
>

Is this the kind of list where someone would have been willing to add
an upgradable annotation?

Sure, although I suspect that every single primitive list would get annotated.  We have proven that we are not very good at anticipating the future and may need to expand the "record" for any list from a primitive to a struct at some point in time.

[Igor Lubashev]

Just to give an example of what has happened multiple times.

There was a list of 16-bit "resource IDs".

1.  Now we want them 32-bit,

2.  Or now we want to add a "status" or some attribute (or two) for each of those resource IDs.

3.  Or now we want to add a list of "sub-ids" for each resource ID.

[Paul Pelzl]

On Fri, May 9, 2014 at 12:26 AM, Kenton Varda <temp...@gmail.com> wrote:

Cap'n Proto currently allows e.g. List(Int32) to be upgraded to List(MyStruct) where MyStruct's @0 field is of type Int32. I'm starting to wonder whether this ability should be abandoned.

It doesn't look to me like a firm conclusion was reached regarding the primitive list --> struct list upgrade path. Any further thoughts, Kenton?

I'm raising the issue again for selfish reasons: the OCaml implementation is currently broken with regard to List<Struct of Bool @0> when encoded as List<Bool>. And I'm convinced that any solution will be quite ugly due to the lack of byte alignment. If this feature is destined to go away, I would be very pleased to avoid writing a bunch of messy code.

I'm very much in favor of getting rid of primitive list --> struct list upgrades entirely, and forcing struct lists to be encoded as C=7 under all circumstances. But the only case that's *deeply* onerous is upgrading a bool list, and I'm having a hard time seeing much value in that particular use case.

Paul

[Igor Lubashev]

Without getting into implementation details, if list(primitive) cannot be upgraded into list(struct{primitive, primitive}) later, then we would never design messages with list(primitive) and world always have list(struct{primitive}) instead.

Hopefully the code generator produces an efficient encoding for these. And if it does so, one should always be left wondering why the compiler cannot do the list(primitive) => list(struct{primitive}) transformation automatically (with an annotation or by default).

- Igor

—
Sent from Mailbox

--
You received this message because you are subscribed to a topic in the Google Groups "Cap'n Proto" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/capnproto/lRlWBOglQv4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to capnproto+...@googlegroups.com.
Visit this group at http://groups.google.com/group/capnproto.

[Kenton Varda]

Paul, I think it's safe for you to proceed assuming that you don't need to support list-of-struct-of-bool encoded as a bit list. But note that regardless of what we decide, it will probably remain necessary to support reading lists of structs encoded using 8, 16, or 32 bits. I think we can safely discard the bool case because probably no one relies on this currently, but it's very likely that lists of 16-bit and 32-bit structs exist in the wild, and possibly even 8-bit, and those will need to continue to be supported on the read end.

On Sun, Jun 1, 2014 at 6:50 PM, Igor Lubashev <igor...@gmail.com> wrote:

Without getting into implementation details, if list(primitive) cannot be upgraded into list(struct{primitive, primitive}) later, then we would never design messages with list(primitive) and world always have list(struct{primitive}) instead.

I don't think that's quite true.

In practice, I've found that lists of numeric primitives are actually pretty rare. When they do exist, they generally fall into two categories:

- A short list of items that don't particularly need tight packing, but which happened to be representable using a primitive type, therefore the author didn't bother encapsulating them in a struct.

- A long list of numeric data, like pixel or vertex values. In these cases, tight packing is very important. But also in these cases, it is often important to be able to get a raw pointer to the data, or at least be able to iterate over it quickly. Supporting upgrades to structs means neither of these things are possible since the element size is runtime-variable. Meanwhile, though, you would probably never want to upgrade a list of pixel values to a list of structs anyway.

Perhaps what this argues for is that we should have two separate types for these two use cases. List(primitive) should actually be encoded as List(struct{primitive}) (with each element taking at least a full word), and we should have a separate "Data(primitive)" which is used for large lists of numeric data that shall never be upgraded to structs. (We already have "Data" representing specifically the UInt8 -- aka byte -- case of this.)

-Kenton

[Paul Pelzl]

On Tue, Jun 3, 2014 at 4:51 PM, Kenton Varda <ken...@sandstorm.io> wrote:

Paul, I think it's safe for you to proceed assuming that you don't need to support list-of-struct-of-bool encoded as a bit list. But note that regardless of what we decide, it will probably remain necessary to support reading lists of structs encoded using 8, 16, or 32 bits. I think we can safely discard the bool case because probably no one relies on this currently, but it's very likely that lists of 16-bit and 32-bit structs exist in the wild, and possibly even 8-bit, and those will need to continue to be supported on the read end.

I think this is a reasonable position to take, and I'll proceed on that assumption.  Thanks!

Paul

[Ahmed Charles]

On Tuesday, June 3, 2014 2:51:37 PM UTC-7, Kenton Varda wrote:

Perhaps what this argues for is that we should have two separate types for these two use cases. List(primitive) should actually be encoded as List(struct{primitive}) (with each element taking at least a full word), and we should have a separate "Data(primitive)" which is used for large lists of numeric data that shall never be upgraded to structs. (We already have "Data" representing specifically the UInt8 -- aka byte -- case of this.)

Has this received any more consideration? I'm considering a scenario where it would be beneficial to have a list of 32 or 64 bit values directly represented as a flat array and I like the idea of separating "Data" from "List", with one being upgradable and the other one being used for performance.

[Kenton Varda]

Hi Ahmed,

No, there haven't been any code changes since I've been focused on Sandstorm. That said, it has come time for a bunch of Cap'n Proto improvements for Sandstorm's sake, so I've started working on 0.5.0. I think the canonicalization stuff needs to be in there, and it may make sense to go ahead and add Data(T) at the same time.

-Kenton

--
You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.

[Ahmed Charles]

For what my 'vote' is worth, I'd like:

1. Data(T) and List(T) with the semantics you suggested before. I'm curious about the backwards compatibility story here, even though it doesn't impact me since I'm not using Cap'n Proto for anything beyond prototyping yet.
2. Inline Data(T)/List(T) in structures. Data(T) seems easy since it will never change in size, but List(T) seems problematic, since it is likely to change it size and it's not obvious what to do in that situation. So, perhaps only Data(T) is sufficient.

[David Renshaw]

On Tue, Jun 3, 2014 at 5:51 PM, Kenton Varda <ken...@sandstorm.io> wrote:

Perhaps what this argues for is that we should have two separate types for these two use cases. List(primitive) should actually be encoded as List(struct{primitive}) (with each element taking at least a full word), and we should have a separate "Data(primitive)" which is used for large lists of numeric data that shall never be upgraded to structs. (We already have "Data" representing specifically the UInt8 -- aka byte -- case of this.)

I much prefer the idea of restricting List(primitive) to be non-upgradable over the idea of adding new Data(primitive) types. It removes complexity and it seems to satisfy most of the design goals discussed in this thread. I think that manually boxing the elements of a list via List(stuct{primitive}) is a quite natural way to say "I want to be able to evolve the type of the elements of this list".

[David Renshaw]

To be more concrete, the proposal I favor is the following:

1) We disallow upgrades from List(primitive) to List(struct).
2) We disallow new List(struct)'s from being encoded with any element size other than INLINE_COMPOSITE (or perhaps POINTER).

These changes imply that all new messages can be canonicalized using Andy's elegant algorithm. Moreover, elements of a List(primitive) in a new message are guaranteed to be laid out contiguously, so we can update the runtime code (i.e. capnp::List<uint32_t> and friends in C++) to use fixed offsets and to provide access to the raw buffer.

There is a potential compatibility problem. If Alice is using the new runtime but an old schema, and Bob sends her messages encoded with a new schema where a List(primitive) has been upgraded to a List(struct), then Alice's runtime will throw an exception when it tries to decode that list. So Alice is forced to update to the newest schema when she updates her runtime. I don't think that is an unreasonable requirement, and I think it's the only way in which this proposal breaks compatibility.

Under this proposal, it may very well turn out that most things that previously would have been specified in schemas as List(primitive) will now be specified as List(struct{primitive}) -- i.e. you will manually box primitive elements in order to allow potential future upgrades. I think it's a good thing for this boxing to be explicit, as it makes it very clear that each element occupies at least a word of memory. If we think it's too tedious to have to define new structs for these situations, we could allow anonymous structs here, as we do for method parameters and results.

The runtime code for List(struct) will not need to change, and will still be able to read lists encoded as List(primitive).

I disfavor the Data(primitive) proposal because it adds significant complexity without adding any expressive power.

-David

[Andrew Lutomirski]

On Wed, Oct 8, 2014 at 3:49 PM, David Renshaw <dwre...@gmail.com> wrote:
> To be more concrete, the proposal I favor is the following:
>
> 1) We disallow upgrades from List(primitive) to List(struct).
> 2) We disallow new List(struct)'s from being encoded with any element size
> other than INLINE_COMPOSITE (or perhaps POINTER).

I think that, for canonical messages, INLINE_COMPOSITE for all lists
is cleaner. Otherwise a list of single-pointer structs that happen to
be all null will have to end up as INLINE_COMPOSITE anyway, so the
reader has to handle both cases anyway.

--Andy

> --
> You received this message because you are subscribed to the Google Groups
> "Cap'n Proto" group.
> To unsubscribe from this group and stop receiving emails from it, send an

[Phil]

A question for changing 'List(primitive)' like this (non-upgradable and with direct access to the underlying memory) is what to do with big-endian clients?

A big-endian client's reads/writes to a 'List(UInt16)' are byte-swapped by the ListReader/ListWriter, so direct access is unsafe. I think the majority of clients are probably expecting this behaviour, and that a 'List(UInt16)' expresses 'a list of unsigned 16-bit integers'---would they have to migrate to 'List(struct{UInt16})' to preserve this (even if upgradability is not required)?

Adding 'Data(primitive)' provides an opportunity for a different semantic: a 'Data(UInt16)' can express 'a blob of 16-bit wide elements'. Byte order and encoding are the responsibility of the client (or something else). This could also be done through an annotation applied to 'List(primitive)', but that doesn't seem any less complex than extending 'Data'.

- Phil

[David Renshaw]

On Wed, Oct 8, 2014 at 9:58 PM, Phil <p...@partylemon.com> wrote:

A question for changing 'List(primitive)' like this (non-upgradable and with direct access to the underlying memory) is what to do with big-endian clients?

A big-endian client's reads/writes to a 'List(UInt16)' are byte-swapped by the ListReader/ListWriter, so direct access is unsafe. I think the majority of clients are probably expecting this behaviour, and that a 'List(UInt16)' expresses 'a list of unsigned 16-bit integers'---would they have to migrate to 'List(struct{UInt16})' to preserve this (even if upgradability is not required)?

No. Our current accessor methods and iterators for List(primitive) can remain as they are, with their byte-swapping semantics on big endian systems. Only clients that call `asPtr()` should need to worry about endianness.

 

Adding 'Data(primitive)' provides an opportunity for a different semantic: a 'Data(UInt16)' can express 'a blob of 16-bit wide elements'. Byte order and encoding are the responsibility of the client (or something else). This could also be done through an annotation applied to 'List(primitive)', but that doesn't seem any less complex than extending 'Data'.

There's no need for an annotation. If you want the raw blob, you can call `asPtr()`. Otherwise, you call the usual accessors.

 

[Kenton Varda]

In my current work on generics, I actually found myself upgrading a List(UInt64) to List(struct) in schema.capnp. If I didn't have this ability, I would have had to do something much uglier (probably parallel arrays). I now feel convinced that despite appearances this is in fact a pretty common problem.

So where are we?

We know at least:

1) Adding new fields to a struct should not break canonicalization. Therefore List(struct) must always be encoded as INLINE_COMPOSITE.

2) For backwards-compatibility, List(struct) must continue to accept input with elements of any size -- except BIT because it's just too hard and probably no one relies on it.

3) We want some way to represent an array of primitives that are packed and to which you can get a raw pointer.

4) (I assert) We still want List(primitive) -> List(struct) to remain a compatible upgrade, although it's perhaps OK if it breaks canonicalization.

Point (4) means List(primitive) cannot allow raw pointers. Therefore, we do in fact need to introduce a Data(primitive) which represents an always-tightly-packed array of values to which a raw pointer is accessible.

I think that if we do introduce Data(T), then we want List(T) -> Data(T) to be a compatible upgrade, so that people who don't realize at first that they need raw pointers can switch to it later. Of course, Data(T) -> List(T) is NOT a compatible upgrade, because this would allow you to take another hop to List(struct) at which point all your raw pointers break. Essentially, List(primitive) lets you be non-committal about whether you need raw pointers or need upgradability to structs.

So, while I sympathize with David's objections to the complexity, I think we are stuck with only one solution that covers all requirements:

- List(primitive) continues being encoded as it is today.

- List(struct) is always encoded as INLINE_COMPOSITE.

- List(primitive other than Bool) -> List(struct) upgrades are allowed with the caveat that they break canonicalization.

- Data(primitive) is encoded the same as List(primitive) but offers raw pointers and disallows later upgrades to List(struct).

Thoughts?

-Kenton

--
You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.

[Andrew Lutomirski]

On Mon, Oct 13, 2014 at 10:58 PM, Kenton Varda <ken...@sandstorm.io> wrote:
> In my current work on generics, I actually found myself upgrading a
> List(UInt64) to List(struct) in schema.capnp. If I didn't have this ability,
> I would have had to do something much uglier (probably parallel arrays). I
> now feel convinced that despite appearances this is in fact a pretty common
> problem.

Not that this is a strong general argument, but List(UInt64) ->
List(Struct) is easier to support than the other conversions, because
UInt64 is aligned like a struct.

>
> So where are we?
>
> We know at least:
> 1) Adding new fields to a struct should not break canonicalization.
> Therefore List(struct) must always be encoded as INLINE_COMPOSITE.

Agreed.

> 2) For backwards-compatibility, List(struct) must continue to accept input
> with elements of any size -- except BIT because it's just too hard and
> probably no one relies on it.

Hmm. I'm still planning on finishing my reader that's specifically
designed to read canonical messages, so it could leave this out.

What if there were separate List(Struct) for real and List(Struct)
upgraded? They could be different types or one of them could have an
annotation. This is a bit messy, but it would keep the common case
clean.

At some point we'll want a schema upgrade safety checker, so rules
like this won't really be burdensome.

> 3) We want some way to represent an array of primitives that are packed and
> to which you can get a raw pointer.

I agree.

Also, arguably there should be something like Data(2 bytes), which
wouldn't be the same thing as Data(UInt16). In fact, maybe there
should only be Data(number of bytes of each element). This avoids
having an implicit endianness.

[Andrew Lutomirski]

On Mon, Oct 13, 2014 at 10:58 PM, Kenton Varda <ken...@sandstorm.io> wrote:
> In my current work on generics, I actually found myself upgrading a
> List(UInt64) to List(struct) in schema.capnp. If I didn't have this ability,
> I would have had to do something much uglier (probably parallel arrays). I
> now feel convinced that despite appearances this is in fact a pretty common
> problem.
>
> So where are we?
>
> We know at least:
> 1) Adding new fields to a struct should not break canonicalization.
> Therefore List(struct) must always be encoded as INLINE_COMPOSITE.
> 2) For backwards-compatibility, List(struct) must continue to accept input
> with elements of any size -- except BIT because it's just too hard and
> probably no one relies on it.
> 3) We want some way to represent an array of primitives that are packed and
> to which you can get a raw pointer.

> 4) (I assert) We still want List(primitive) -> List(struct) to remain a
> compatible upgrade, although it's perhaps OK if it breaks canonicalization.
>
> Point (4) means List(primitive) cannot allow raw pointers. Therefore, we do
> in fact need to introduce a Data(primitive) which represents an
> always-tightly-packed array of values to which a raw pointer is accessible.

Having slept on this, I'm not sure I'm (yet?) convinced. There are
already upgrades that are only one-way compatible. For example,
upgrading a non-union field to a union will allow new code to read old
data, but not vice versa (although the failure may be silent).

This *might* mean that it would be okay to have List(primitive) allow
raw pointers; instead, reading a List(primitive) that was written by a
newer version of the schema using INLINE_COMPOSITE encoding would just
fail.

What was the example for the schema schema? Would old code still
interpret the upgraded list correctly, or would failing to read it be
just as good an outcome?

--Andy

[Kenton Varda]

On Fri, Oct 17, 2014 at 3:39 PM, Andrew Lutomirski <an...@luto.us> wrote:

Having slept on this, I'm not sure I'm (yet?) convinced.  There are
already upgrades that are only one-way compatible.  For example,
upgrading a non-union field to a union will allow new code to read old
data, but not vice versa (although the failure may be silent).

This *might* mean that it would be okay to have List(primitive) allow
raw pointers; instead, reading a List(primitive) that was written by a
newer version of the schema using INLINE_COMPOSITE encoding would just
fail.

There are a couple big differences between retroactive unionization and struct-izing a primitive list:

- Retroactive unionization only breaks old receivers if you actually send them a message that uses the new union member, whereas a struct-ized list will cause all future messages to be incompatible with raw pointers even if no new information content is actually added. The former lends itself to many reasonable transition strategies while the latter makes transition difficult.

- Use of raw pointers is an implementation detail and thus it is hard for the protocol author to predict whether anyone might be doing it. Many authors may not even know it is an issue. In comparison, adding a new union field is a semantic change in the protocol. The protocol author is likely to understand that existing code isn't checking the union discriminant and can reason about how it might break.

 

What was the example for the schema schema?  Would old code still
interpret the upgraded list correctly, or would failing to read it be
just as good an outcome?

In the schema schema case, I upgraded Node.interface.extends to be a list of structs instead of a list of 64-bit type IDs, where each of the structs starts with the type ID but also contains additional information. The new information is the generic parameter bindings. Old code can get away with ignoring these even when interpreting new schemas that use generics; it will just see all of the type parameters as being AnyPointers.

(Since I was breaking source compatibility anyway, I also renamed "extends" to "superclasses".)

-Kenton

[Kenton Varda]

Update:

- C++ implementation at head now always encodes struct lists as INLINE_COMPOSITE.

- C++ implementation at head no longer supports List(Bool) -> List(struct) upgrades.

[Keir Mierle]

FWIW, I vote to retain support for upgrading List(primitive) to List(struct) - this is a common case that happened to me in the past. Parallel arrays are awful.

[Joshua Warner]

On 26 October 2014 09:44, Keir Mierle <mie...@gmail.com> wrote:

FWIW, I vote to retain support for upgrading List(primitive) to List(struct) - this is a common case that happened to me in the past. Parallel arrays are awful.

<!Tangent alert!>: Data-oriented design would have you believe that sometimes they're not awful - and can, in fact, be exactly what you need, particularly from a performance / cache-friendliness standpoint.  On the other hand, using them in business logic is probably just increasing the complexity for no good reason.  My point is not that they're great and you should always use them, but rather that they're not inherently evil.

-Joshua

[Kenton Varda]

Two thoughts to inject:

1) The Data(T) idea should henceforth be called Blob(T) instead. While we could easily extend the Cap'n Proto language to allow `Data` to be optionally parameterized, we can't very well do the same thing for the `Data` type that exists in C++ (without breaking people). So I'd rather use a new name so that the naming in C++ can be consistent with the naming in the schema definitions.

2) It occurs to me that if we implement the Blob(T) idea it could apply to structs as well, as a way to get back the old optimization of packing small structs tightly. This could allow you to do:

    struct Pixel {

      red @0 :UInt8;

      green @1 :UInt8;

      blue @2 :UInt8;

      alpha @3 :UInt8;

    }

    pixels @0 :Blob(Pixel, 4);

    # Pixels, each packed as a 4-byte value.

`pixels` would be encoded as a list with 32-bit elements, in the same manner that List(Pixel) would have been in the past, except that if new fields are added to Pixel, the list will still stick to 32-bit elements (and those new fields will be unusuable). Thus you get the optimization without sacrificing canonicalization, and moreover we could in fact let you get a raw pointer to the pixel array, allowing you to pass it off to your GPU or whatever.

But this is probably over-engineering. Just thought I'd throw it out there to see what people think.

-Kenton

[Joshua Warner]

    pixels @0 :Blob(Pixel, 4);

    # Pixels, each packed as a 4-byte value.

What if the '4' here is not a byte count, but rather an index into the field ordinals of Pixel?

Furthermore, the concept of limiting the number of fields in a referenced types has other interesting optimization possibilities.  Suppose, as a straw-man, the type `Pixel@4` operated similarly to `Pixel`, except any fields with ordinal >= 4 will be chopped off.  This way, that struct could be used not just in lists, but in many other locations.

```

# struct Pixel, as above

pixels @0 :List(Pixel@4);

# Denotes a list of pixel structs, only allowing 4 fields.

singlePixel @1 :Pixel@4;

# Denotes a pixel struct, which can be included _inline_ in the parent struct, since we know it's size.

# Could be very useful for e.g. an inline Vector3 type

colors @1 :Map(Text, Pixel@4)

# Supposing Map has a `values @1 :List(V)` for it's values, and that generics supported encoding List(V) as a struct list, rather than just a pointer list - said inner `values` field could also be accessed directly as a pointer, passed to the GPU, etc.

```

@kenton, with generics, would the `List(V)` field hypothesized above be encoded like a List(AnyPointer), or a list of the final "branded" type?  I think the latter could be a very useful optimization.

-Joshua

[Phil]

On Mon, Oct 27, 2014 at 11:14 AM, Kenton Varda <ken...@sandstorm.io> wrote:

1) The Data(T) idea should henceforth be called Blob(T) instead. While we could easily extend the Cap'n Proto language to allow `Data` to be optionally parameterized, we can't very well do the same thing for the `Data` type that exists in C++ (without breaking people). So I'd rather use a new name so that the naming in C++ can be consistent with the naming in the schema definitions.

Is there any difference between a `Data` and a `Blob(UInt8)`? If not, the duplication seems strange---having two types to describe a single underlying thing, and with duplicate APIs.

Source compatibility for `capnp::Data` could be preserved with something like:

  template<typename T> struct BasicData { /* contents of current Data struct */ };
  using Data = BasicData<byte>;

(A better name is left as an exercise.)

Phil

[Tim Popham]

singlePixel @1 :Pixel@4;

# Denotes a pixel struct, which can be included _inline_ in the parent struct, since we know it's size.

# Could be very useful for e.g. an inline Vector3 type

I've got a use case where I've exported a recurring group to a struct to avoid repeating the group fields over and over.  I'm considering reverting the change to avoid the pointer overhead.  This extension would provide a welcomed alternative within my schema-verbosity versus message-bloat decision.